Mixing
Why my code doesn't work correctly by sometimes returning true instead of false?
Why my code doesn't work correctly by sometimes returning true instead of false?
This is my code:
function almostIncreasingSequence(sequence) {
var counter = 0;
for (var i = 1; i < sequence.length - 1; i++) {
if (sequence[i] <= sequence[i - 1]) {
counter += 1;
} else if (sequence[i + 1] <= sequence[i - 1]) {
counter += 1;
}
}
if (counter <= 1) {
return true;
}
return false;
}
console.log(almostIncreasingSequence([1, 3, 2, 1]));
console.log(almostIncreasingSequence([1, 2, 5, 5, 5]));
console.log(almostIncreasingSequence([1, 2, 3, 4, 3, 6]));
This code's job is to:
Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.
Example
For sequence = [1, 3, 2, 1], the output should be
sequence = [1, 3, 2, 1]
almostIncreasingSequence(sequence) = false;
There is no one element in this array that can be removed in order to get a strictly increasing sequence.
For sequence = [1, 3, 2], the output should be
sequence = [1, 3, 2]
almostIncreasingSequence(sequence) = true.
You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].
3
[1, 2]
2
[1, 3]
But it doesn't work correctly even after a bunch of edits. Currently, these are the arrays that the code doesn't work correctly on:
[1, 3, 2, 1] It returns true instead of false.
[1, 3, 2, 1]
[1, 2, 5, 5, 5] It returns true instead of false.
[1, 2, 5, 5, 5]
[1, 2, 3, 4, 3, 6] It returns false instead of true.
[1, 2, 3, 4, 3, 6]
I'm editing this code long time ago, every time I add something/edit something, a problem gets fixed but another problem gets messed up and it keeps like that.
EDIT: Please tell me why it doesn't work, don't give me the right code please.
<>
Very related: question about the same problem - that doesn't explain the bug in the code though, just should be an intersting read.
– ASDFGerte
Jun 29 at 8:27
His code was different though. He used splice to remove the item and see if it is false or true but it doesn't work since splice changes the content of the array originally and so that can mess stuff up. My code uses counter and if statements to see if there are more than 1 decreasing number or not in an array. And returns true or false based on that.
– Boy pro
Jun 29 at 8:33
Your code "doesn't work" because you don't have the right algorithm. Not working is the natural state of a program, until you write code to make it work. You haven't done so.
– melpomene
Jun 29 at 8:34
melpomene, you mean the whole logic or that it just needs some tweaks? Because I'm pretty sure that this is the right logic. It just needs some tweaks.
– Boy pro
Jun 29 at 8:35
4 Answers
4
function increasingSequence(sequence,i){
sequence = Array.prototype.slice.call(sequence);
sequence.splice(i,1)
var len = sequence.length;
for(var i=0;i<len-1;i++){
if(sequence[i]>=sequence[i+1])return false;
}
return true;
}
function almostIncreasingSequence(sequence) {
var len = sequence.length;
for(var i=0;i<len-1;i++){
if(sequence[i]>=sequence[i+1]){
return increasingSequence(sequence,i)||increasingSequence(sequence,i+1)
}
}
return true;
}
console.log(almostIncreasingSequence([1,2,3]));
console.log(almostIncreasingSequence([1,3,2]));
console.log(almostIncreasingSequence([1,2,3,3,2]));
It's O(n) , the worst situation is O(2n) ,best situation is O(n)
– Peng
Jun 29 at 9:01
@ASDFGerte That doesn't sound right. I see at most one call to
increasingSequence.– melpomene
Jun 29 at 9:09
increasingSequence
Sadly, this fails for e.g.
[1, 2, 3, 1].– ASDFGerte
Jun 29 at 9:21
[1, 2, 3, 1]
I'm update the answer.now it's right. maybe ....
– Peng
Jun 29 at 9:33
Please add an explanation, not just code. The OP specifically asked for an explanation, and code-only answers tend to not be useful to other readers and therefore attract downvotes.
– Jesse de Bruijne
Jun 29 at 9:52
Thank you all for your answers and help. It was really useful to know that my whole algorithm is completely wrong.
Anyway, what happened to this code's guy?
function almostIncreasingSequence(sequence) {
return sequence.map((_, index) => [...sequence.slice(0, index), ...sequence.slice(index + 1)])
.some(arr => arr.every((value, index) => index === 0 || value > arr[index - 1]));
}
I wanted to make him the right answer. Did his comment get deleted?
The issue with above solution is it being O(n²). Peng's code is O(n) and should, after latest edits, also work. Yes, the person who posted above code deleted his answer (currently, undelete is an option aswell...). PS: this is not an answer, perhaps an edit would be preferrable.
– ASDFGerte
Jun 29 at 9:55
Actually the solution above doesn't have an issue. It passed all the tests without a timeout. But yes, Peng's code works. So I think I will choose him as the right answer. Again, thank you all for your help! Though I didn't understand a lot from these codes, I think by the time goes, I will be able to.
– Boy pro
Jun 29 at 9:59
Peng's solution solved the unit tests i used approximately 200 times faster (!). Note that order issues appear on larger inputs - above solution will have trouble on large inputs which Peng's code would still solve within milliseconds.
– ASDFGerte
Jun 29 at 10:01
But I still don't understand how his code works ):
– Boy pro
Jun 29 at 10:03
Yes, that is a problem. This code challenge seems to make people frequently produce faulty code (as seen here and also on the question i linked, i also made a mistake when first solving it. Presumably because it looks very easy but has several pitfalls, people hurry too much). The resulting storm of people posting their attempts made the original question go into the background.
– ASDFGerte
Jun 29 at 10:08
The most performant way is to go through the sequence only once. This code remembers the previous number and checks if the current one is higher. If it is lower or equal, then it marks the higher number as the mistake, so the next number can be higher again.
function isIncreasingWithMistakes(sequence) {
prev = Number.MIN_VALUE;
var mistakeCounter = 0;
for (var number of sequence) {
if (prev < number) {
// The good case
prev = number
}
else {
// Found a mistake
mistakeCounter += 1
prev = Math.min(prev, number) // Eliminate the higher number
}
// Stop immediately when there are too many mistakes
if (1 < mistakeCounter) {
return false
}
}
return true
}
// These should be true
console.log(isIncreasingWithMistakes([1, 2, 3, 4, 3, 6]))
console.log(isIncreasingWithMistakes([10, 1, 2, 3, 4, 5]))
// These should be false
console.log(isIncreasingWithMistakes([1, 3, 2, 1]))
console.log(isIncreasingWithMistakes([1, 2, 5, 5, 5]))
console.log(isIncreasingWithMistakes([1,2,3,4,3,6,1]))
This seems to work
function _doAlmostIncreasingSequence(_seq, recheck) {
var warning = 0;
var _control = _seq[0] - 1;
for (var i = 0; i < _seq.length; i++) {
var _test = _seq[i];
if (_test <= _control) {
if (recheck) {
var test1 = _seq.slice(0);
var test2 = _seq.slice(0);
test1.splice(i, 1);
test2.splice(i - 1, 1);
return _doAlmostIncreasingSequence(test1) || _doAlmostIncreasingSequence(test2);
}
return false;
}
_control = _test;
}
return true;
}
function almostIncreasingSequence(_seq) {
return _doAlmostIncreasingSequence(_seq, 1);
}
console.log("TRUE :", almostIncreasingSequence([1, 2, 3, 5, 4, 5, 6]));
console.log("TRUE :", almostIncreasingSequence([10, 1, 2, 3, 4, 5, 6]));
console.log("TRUE :", almostIncreasingSequence([4, 5, 6, 6, 7, 8]));
console.log("FALSE :", almostIncreasingSequence([4, 5, 6, 1, 2, 3]));
console.log("TRUE :", almostIncreasingSequence([1, 3, 4, 6, 7, 8, 1, 10, 11, 12]));
console.log("FALSE :", almostIncreasingSequence([1, 3, 2, 1]));
console.log("FALSE :", almostIncreasingSequence([1, 2, 5, 5, 5]));
console.log("TRUE :", almostIncreasingSequence([1, 2, 3, 4, 3, 6]));
It doesn't work.
– Boy pro
Jun 29 at 9:02
This does not answer the question.
– melpomene
Jun 29 at 9:03
@Boypro can you give an example where it does not work?
– itaynoy
Jun 29 at 9:22
[4,5,6,1,2,3]– ASDFGerte
Jun 29 at 9:23
[4,5,6,1,2,3]
@ASDFGerte - you're right, edited
– itaynoy
Jun 29 at 9:26
By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.
Please click the
<>and create a Minimal, Complete, and Verifiable example– mplungjan
Jun 29 at 8:24