3 ms·
Reading the article, I too felt that another check was needed, to prevent the hare from sometimes leapfrogging eternally. While drafting a snappy comeback to y
by rwolf 17y ago
Reading the article, I too felt that another check was needed, to prevent the hare from sometimes leapfrogging eternally.
While drafting a snappy comeback to your comment that there was no such loop, I tried to find the smallest loop that demonstrated the bug, and came across a very nice pattern:
1: (1,1),(1,1)
2: (1,1),(1,2),(1,1)
3: (1,1),(3,2),(2,3),(1,1)
4: (1,1),(3,2),(1,3),(3,4),(1,1)
5: (1,1),(3,2),(5,3),(2,4),(4,5),(1,1)
6: (1,1),(3,2),(5,3),(1,4),(3,5),(5,6),(1,1)
...
Put another way, once the tortoise enters the loop, it will take <=n-1 steps (where n is the size of the loop) for them to come together (without teleportation).
This problem seems like way too much fun to use in an interview!
- gjm11 17y agoThe point is that (hare position minus tortoise position, modulo loop size if there is a loop) increases by exactly 1 every time. So if there is a loop it will eventually reach 0, fewer than (loop size) steps after entering the loop.