Win a copy of Node.js Design Patterns: Design and implement production-grade Node.js applications using proven patterns and techniques this week in the Server-Side JavaScript and NodeJS forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Rob Spoor
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Henry Wong
  • Liutauras Vilda
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Tim Holloway
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Mikalai Zaikin
  • Piet Souris

Is there any way of an infinite loop here?

 
Sheriff
Posts: 8064
569
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Sergiu Dobozi wrote:Code Fights


Sergiu Dobozi wrote:The code I wrote works for all cases except for one


From the discussion above we know already, that OP's code was failing on more test cases than the one he mentioned for the specified Code Fights problem. That gives an idea, that they (Code Fights) haven't got rich test cases too which can make you believe you came up with a decent algorithm.
 
Ranch Hand
Posts: 109
2
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:

Sergiu Dobozi wrote:Code Fights


Sergiu Dobozi wrote:The code I wrote works for all cases except for one


From the discussion above we know already, that OP's code was failing on more test cases than the one he mentioned for the specified Code Fights problem. That gives an idea, that they (Code Fights) haven't got rich test cases too which can make you believe you came up with a decent algorithm.


I think this is on purpose to encourage you to just code more, as a beginner.
Here is my updated code. I worked on the original one I had made.
I included a continue statement to cut down on the time it takes to create all of the sub-arrays, I don't know how well it works though. Also the empty arrays and the arrays with length between 1 and 2 are now taken care of.
 
Sergiu Dobozi
Ranch Hand
Posts: 109
2
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
"I included a continue statement to cut down on the time it takes to create all of the sub-arrays, I don't know how well it works though."
Actually, scratch that. If I wanted to get out of a loop I would have to use a break statement, not a continue statement. But the break statement is not working.
 
Sergiu Dobozi
Ranch Hand
Posts: 109
2
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Sergiu Dobozi wrote:"I included a continue statement to cut down on the time it takes to create all of the sub-arrays, I don't know how well it works though."
Actually, scratch that. If I wanted to get out of a loop I would have to use a break statement, not a continue statement. But the break statement is not working.


Ah, ok. The break statement doesn't work because it only handles the final sequence2 and none of its subsequences. No need to look further into that...
 
Bartender
Posts: 4633
182
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
In my reply I mentioned about comparing the index of an element to the index of that element if the array woud have been sorted. Now, that worked, albeit in (NlogN) time, but the solutions given here were very much shorter and very much more elegant, so I ceased my efforts. I then looked at a more general version:

Given an positive number N and an array of ints of ilength at least N + 2, can we form a non-decreasing subsequence when we delete N elements?
Global Health Warning: there are many better things to spend your time on...  
 
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sergiu, you are using a nested for loop and always traverse the entire length of the array in the inner loop. What's more, the isSorted method will also try to traverse the entire length off the array. Worst-case scenario, your algorithm will be O(n^2), which is very bad when you have very long arrays. You'll never pass those tests with an algorithm like that, no matter how you tweak it.

The solution is a single pass algorithm. You also don't need to go through the entire array most of the time if it will fail the check anyway. You should stop iterating as soon as you find more than one pair that is out of sequence and contains an element that can be dropped.
 
Saloon Keeper
Posts: 8598
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You've cleaned up almost all of the FAILs. Just one left: [1, 2] should return true.
 
Carey Brown
Saloon Keeper
Posts: 8598
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
For the huge array of Length=268435455 your algorithm gives
At line 12.
You'll need to replace your try/catch block with a simple

It appears that when line 5 throws the exception that sequence2 is left in a state where it can't be garbage collected. (Hmmmm sounds like a Java bug feature.)

There were two "let's see if we can break it" tests.

Once you fix your try/catch block then the longSeqArray( 268435455 ) test works in your code in a reasonable amount of time.
The longArray( 5000000 ) test with your code never returned. I can't say if it's gotten into an infinite loop or if it's just not efficiently handling the data. This is where some of the recent comments may help.
 
Sergiu Dobozi
Ranch Hand
Posts: 109
2
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Carey Brown wrote:You've cleaned up almost all of the FAILs. Just one left: [1, 2] should return true.



Shouldn't it return false since eliminating 1 or 2 just leaves us with a number and not a sequence?
 
Carey Brown
Saloon Keeper
Posts: 8598
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Sergiu Dobozi wrote:

Carey Brown wrote:You've cleaned up almost all of the FAILs. Just one left: [1, 2] should return true.



Shouldn't it return false since eliminating 1 or 2 just leaves us with a number and not a sequence?


Because 1 is less than 2 neither one should be removed so you should end up with the sequence [1, 2], which is correct.
[2, 1] on the other hand should fail because 2 is greater than 1 and so it needs to be removed leaving you with [1] which is incorrect.
 
Sergiu Dobozi
Ranch Hand
Posts: 109
2
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I did a few pull-ups and I finally understood the logic that Junilu used in his algorithm. Here is my updated code.

 
Carey Brown
Saloon Keeper
Posts: 8598
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
With new algorithm:
 
Sergiu Dobozi
Ranch Hand
Posts: 109
2
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Carey Brown wrote:With new algorithm:


This should easily solve that. CodeFights didn't approve the below code though.
 
Carey Brown
Saloon Keeper
Posts: 8598
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Sergiu Dobozi wrote:This should easily solve that. CodeFights didn't approve the below code though.


Do they give you any hint as to why not?
I wouldn't be supprised if there wasn't a test case we didn't handle, or their interpretation of [], [1], [2,1], and [1,1] might be different.
 
Sergiu Dobozi
Ranch Hand
Posts: 109
2
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Carey Brown wrote:

Sergiu Dobozi wrote:This should easily solve that. CodeFights didn't approve the below code though.


Do they give you any hint as to why not?
I wouldn't be supprised if there wasn't a test case we didn't handle, or their interpretation of [], [1], [2,1], and [1,1] might be different.


They only gave one test: [1,1] should return true. So they only care about the sub-arrays if they are ascending, not the arrays themselves and they also don't provide enough test cases because [2,1] would also have to fail.
 
Carey Brown
Saloon Keeper
Posts: 8598
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Sergiu Dobozi wrote:

Carey Brown wrote:

Sergiu Dobozi wrote:This should easily solve that. CodeFights didn't approve the below code though.


Do they give you any hint as to why not?
I wouldn't be supprised if there wasn't a test case we didn't handle, or their interpretation of [], [1], [2,1], and [1,1] might be different.


They only gave one test: [1,1] should return true. So they only care about the sub-arrays if they are ascending, not the arrays themselves and they also don't provide enough test cases because [2,1] would also have to fail.


Ug. [1,1] should be false because it's not an increasing sequence. So, if you hard code this as a special case do you get any further?
 
Sergiu Dobozi
Ranch Hand
Posts: 109
2
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Carey Brown wrote:

Sergiu Dobozi wrote:

Carey Brown wrote:

Sergiu Dobozi wrote:This should easily solve that. CodeFights didn't approve the below code though.


Do they give you any hint as to why not?
I wouldn't be supprised if there wasn't a test case we didn't handle, or their interpretation of [], [1], [2,1], and [1,1] might be different.


They only gave one test: [1,1] should return true. So they only care about the sub-arrays if they are ascending, not the arrays themselves and they also don't provide enough test cases because [2,1] would also have to fail.


Ug. [1,1] should be false because it's not an increasing sequence. So, if you hard code this as a special case do you get any further?


Haha yes. If I do that, it lets me pass.
 
Carey Brown
Saloon Keeper
Posts: 8598
71
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Sergiu Dobozi wrote:

Carey Brown wrote:Ug. [1,1] should be false because it's not an increasing sequence. So, if you hard code this as a special case do you get any further?


Haha yes. If I do that, it lets me pass.


Congrats. As a guess I think that they consider a sequence with only one number in it to be true.
[] false
[1,1] true
[2,1] true
 
Sergiu Dobozi
Ranch Hand
Posts: 109
2
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Carey Brown wrote:

Sergiu Dobozi wrote:

Carey Brown wrote:Ug. [1,1] should be false because it's not an increasing sequence. So, if you hard code this as a special case do you get any further?


Haha yes. If I do that, it lets me pass.


Congrats. As a guess I think that they consider a sequence with only one number in it to be true.
[] false
[1,1] true
[2,1] true


Thanks! I think philosophically speaking it's true that a sequence with one number is simultaneously ascending and descending, on some level of paradoxical thinking. I am not so sure what a mathematician would say about that though.
 
Junilu Lacar
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Sergiu Dobozi wrote:Thanks! I think philosophically speaking it's true that a sequence with one number is simultaneously ascending and descending, on some level of paradoxical thinking. I am not so sure what a mathematician would say about that though.


That's awesome. So now, we can say that a boat on the water is both sinking and flying at the same time.  
 
Junilu Lacar
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
And if I look at my empty wallet, I'm simultaneously getting richer and poorer.  That truly boggles my mind but CodeFights isn't getting any rep points from me on this one.
 
Junilu Lacar
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
... one more for good measure.

This is what a straight flush poker hand looks like in the CodeFights backroom: ♣2 ♥2 ♥4 ♥5 ♥6

They should probably stay away from Vegas.  ¯\_(ツ)_/¯
 
Marshal
Posts: 74059
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Junilu Lacar wrote:. . . we can say that a boat on the water is both sinking and flying at the same time.  

Take a photograph of a boat on water and from that photograph prove she isn't sinking. Nor that she isn't being salvaged by being pumped full of air. You can't.
Regard the one‑element sequence as the base case in a recursive algorithm to find whether the sequence is ascending or descending. You would have a universal quantification like this in an ascending sequence:-
nn ∈ 1...mySeq.cardinality ⇒ mySeq(n) > mySeq(n − 1)
Where the indices in the sequence are 0‑based, and the ... operator works on a fromInclusive/toExclusive basis. If you recognise a difference between increasing and strictly increasing, you could use ≥ rather than > for not strictly increasing.
If you have a 1‑element sequence, the enumerated set 1...mySeq.cardinality is empty and the inclusion predicate will return false for all values of n. Since false ⇒ anything is always true, that implication will return true for all values of n and the quantification will be true. But that is vacuous truth. It is like going into a world of double negatives, just as you cannot prove the boat isn't sinking from a photograph. You can do the same for a decreasing sequence; the 1‑element sequence can act as the base case for recursion to find whether a sequence is decreasing.

We actually use the 1‑element sequence as a base case. The basic form of merge sort breaks down an array or a sequence until it reaches the largest sequence which one can certain is already sorted (i.e. is ascending), which in the absence of other verification is a 1‑element sequence. If you use a Comparator or similar sorting in descending order, you are again using the base case of such a recursion.
 
Campbell Ritchie
Marshal
Posts: 74059
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

A few minutes ago, I wrote:. . . a 1‑element sequence, the enumerated set 1...mySeq.cardinality is empty . . .

A bit like writing a for loop for a 1‑element array:-My enumerated set would start at 1, but it will go ...1 and that second 1 is on a toExclusive basis, so the set will include all numbers n • n > 1 ∧ n ≤ 0, so that set will be empty.
 
Junilu Lacar
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:

Junilu Lacar wrote:. . . we can say that a boat on the water is both sinking and flying at the same time.  

Take a photograph of a boat on water and from that photograph prove she isn't sinking. Nor that she isn't being salvaged by being pumped full of air. You can't.


Exactly. By the same logic, if you take [1], you can't tell whether it's increasing or decreasing either, because those attributes are relative to another data point. If you only have one data point, then there's no sequence.

EDIT: See my concession if going by "math sense" below. I still say that common sense dictates that you can't have an increasing sequence with 0 or 1 numbers.  Do you think if I tell my son to take comfort when he looks in his wallet and sees only one $1 bill in there: "Don't worry son, math tells us that there's actually an increasing sequence of dollar bills in there. Pretty soon, you'll be able to make next month's rent for your apartment. If you wait long enough, you can put a down payment on a small house."  
 
Junilu Lacar
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sometime math sense defies common sense.  Common sense tells you that something can't be increasing and decreasing at the same time.  Going back to my example of 100 degrees or 0 degrees.  You can't say whether or not it's getting hotter or colder from either of those temperature readings unless you know what the next temperature reading is.  

However, if you use "math sense" and say that the empty set is part of every sequence, and I suppose the empty set is always less than any other element, then I suppose by math sense, a 1-element sequence can be considered both increasing and decreasing at the same time. I still say you're not going to have any luck winning any money using that kind logic in a poker game.
 
Junilu Lacar
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@OP: You know you could have saved everybody some grief if you had included these constraints given by CodeFights:

Constraints:
2 ≤ sequence.length ≤ 10^5,
-10^5 ≤ sequence[i] ≤ 10^5.


 
Junilu Lacar
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So I guess CodeFights takes the "math sense" view of "strictly increasing" in that a single-element sequence is considered as strictly increasing.

So the initial check would be changed to:

And you'd pass all their tests. ¯\_(ツ)_/¯
 
Liutauras Vilda
Sheriff
Posts: 8064
569
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Alright, so more details were given there, we just haven't been told. Now question is, why those constraints are given but not covered in their test cases and OP's algorithm passed, while actually shouldn't as doesn't address both of those constraints.
I have refactored my version without changing initial logic, but having those details current algorithm isn't correct anymore - probably I'll leave it here, enough.
 
Liutauras Vilda
Sheriff
Posts: 8064
569
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Junilu Lacar wrote:And you'd pass all their tests.

Would you? I'd think that our algorithms doesn't check how big numbers are, and maximum allowed number of elements in the sequence.
That's probably mean those constraints define what kind of data we could be given to work with.
 
Junilu Lacar
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:

Junilu Lacar wrote:And you'd pass all their tests.

Would you? I'd think that our algorithms doesn't check how big numbers are, and maximum allowed number of elements in the sequence.
That's probably mean those constraints define what kind of data we could be given to work with.



Kind of. I signed up for CodeFights because I wanted to see this thing for myself.  Test 10 uses [1, 1] for input and expects the result to be true.  So, as I said, they must be taking Campbell's and I guess the "math sense" point of view on single-element arrays being strictly increasing sequences. Like OP, that was the only test that didn't pass for my original solution. After changing the initial check to return true for any 2-element array, the test passed.

So [2, 1] should return true, [1, 1] should return true by the definition used by CodeFights of a strictly increasing sequence.
 
Junilu Lacar
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
CodeFights is actually kind of fun. I'm on Level 5, Task 4 now in the Arcade. Most of the arcade challenges were pretty straightforward. The only one I kind of got stuck on for about 15 minutes was the "Are Similar?" problem on Level 4. I had to throw away my first algorithm because it was failing just one of ten hidden tests.  My second algorithm that passed all the tests turned out to be simpler anyway.
 
Campbell Ritchie
Marshal
Posts: 74059
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Junilu Lacar wrote:. . . Test 10 uses [1, 1] for input and expects the result to be true.  So, as I said, they must be taking Campbell's and I guess the "math sense" point of view on single-element arrays being strictly increasing sequences. . . .

It would be nice if they had explained that, though.
 
Junilu Lacar
Marshal
Posts: 16597
278
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Unfortunately, they don't. One of the frustrating things about that site, which I can still buy into despite the annoyance, is that they don't give you many hints related to their hidden tests. You just have to figure it out yourself. In that one problem I got stuck on where you had to determine if two arrays can be made equal by swapping at most one pair of elements, I never really figured out why my first algorithm had failed one test. I just threw it out and started over with another approach.
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic