News for hackers. Stuff that matters.
Re:Interviewing for a JavaScript Job by alisey on Sunday February 22, 2015 @02:55PM (#9090751)
I gave this question to a friend and she came up with what I think is a beautiful answer. Remember min and max X and Y coordinates seen so far, and count the number of steps. When this number gets larger than (maxX - minX)*(maxY - minY) we know we're in a cycle.

It's an extension of your idea of counting the total number of visited positions. What I like most about it is that it can work with streamed data.

Re:Interviewing for a JavaScript Job by defen on Sunday February 22, 2015 @09:37PM (#9092266)
That's a really cool solution. One potential problem is that it doesn't find the loop as soon as possible (e.g. if it's going around the perimeter of a square, the cycle is detectable after 4N steps, but the algorithm will take N^2 steps to realize that)
Re:Interviewing for a JavaScript Job by jongraehl on Monday February 23, 2015 @12:49PM (#9095687)
That's nice (and can be easily fixed to handle negative coordinates), but extremely slow (imagine a simple square cycle with side length N. Her solution takes N^2 steps.
Re:Interviewing for a JavaScript Job by zaroth on Sunday February 22, 2015 @03:47PM (#9091005)
Perfection! A beautiful hack around not knowing the size of the board, and even faster detecting cycles to boot.
Re:Interviewing for a JavaScript Job by Udik on Sunday February 22, 2015 @03:15PM (#9090859)
I think it's the best answer so far!