We believe that everyone deserves a good and free education. The purpose of Tech School is to give everyone a chance to learn IT by giving free, high-quality tutorials and coding courses.
This cycle detection in functional graph problem can be solved by the Floyd's Tortoise and Hare algorithm in O(P+L) time and O(1) memory, where P is the start point of the loop, and L is the length of the loop: en.wikipedia.org/wiki/Cycle_detection
TL;DR?
The basic idea is, for all i >= P, we have f(i) = f(i+k*L), because all points after P is in the loop, so:
f(k*L) = f(2*k*L) => there must exist a point x=k*L in the loop that f(x) = f(2*x) => if a hare and a tortoise start their race at 0, and the hare moves 2 times as fast as the tortoise, they will meet at the point x=k*L in the loop.
f(P) = f(P+k*L) => when the hare and the tortoise meet at x=k*L, if we reset the hare's position to 0 and set its speed to be the same as the tortoise, then after P steps, they will meet again at P, or the starting point of the loop => this is the point we want to find.
Thanks a lot! It never occurred to me that such question even has several named algorithms. Hare-and-Tortoise obviously couldn't be applied as is (because we have single function to call and it has some state) - but obviously it will fit in some modified version, especially if we allow restarting generator.
I'll send the link to your comment to my fellow, so thanks from him too, beforehand :)
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
This cycle detection in functional graph problem can be solved by the Floyd's Tortoise and Hare algorithm in O(P+L) time and O(1) memory, where P is the start point of the loop, and L is the length of the loop: en.wikipedia.org/wiki/Cycle_detection
TL;DR?
The basic idea is, for all
i >= P, we havef(i) = f(i+k*L), because all points after P is in the loop, so:f(k*L) = f(2*k*L)=> there must exist a pointx=k*Lin the loop thatf(x) = f(2*x)=> if a hare and a tortoise start their race at 0, and the hare moves 2 times as fast as the tortoise, they will meet at the pointx=k*Lin the loop.f(P) = f(P+k*L)=> when the hare and the tortoise meet atx=k*L, if we reset the hare's position to 0 and set its speed to be the same as the tortoise, then after P steps, they will meet again at P, or the starting point of the loop => this is the point we want to find.Thanks a lot! It never occurred to me that such question even has several named algorithms. Hare-and-Tortoise obviously couldn't be applied as is (because we have single function to call and it has some state) - but obviously it will fit in some modified version, especially if we allow restarting generator.
I'll send the link to your comment to my fellow, so thanks from him too, beforehand :)