Cycle Detection: Floyd's The Tortoise and the The Hare
Description:
For a general presentation of Cycle detection Problem see this kata: http://www.codewars.com/kata/5416f1834c24604c46000696
The greedy algorithm for cycle detection is trivial but ask for storing at least values and perform a comparison on each pair of values, resulting in an overall quadratic complexity. We want to reduce space and time complexity to use cycle detection efficiently.
Floyd's develloped a pointer algorithm for cycle detection: Tortoise and the Hare. This algorithm uses only two pointers, which move through the sequence at different speeds. Like the tortoise and the hare in Aesop's Fable.
We will now work directly with and .
There is 3 phases for the algorithm:
Main phase of algorithm: starting with tortoise = , hare = , move the tortoise by one and the hare by two . They will eventually be both in the loop and as the distance between them is increasing it will reach a multiple of and they will get the same value.
At this point the tortoise position has walked , the hare , the distance between them is both and . So hare starting at his last position moving in cycle one step at a time and tortoise at moving towards the cycle will intersect at the beginning of the cycle. This is how to find .
Now that they are in the same position, tortoise stay still and hare move in the circle one step at a time, lambda is incremented at each step. So when they meet again we will have .
You will build a function that take and as parameters and return an array [mu,lambda]. All the function will be periodic after some point.
We can find an application of this algorithm for greater purpose, as for exemple Pollard Rho Algorithm for integer factorisation.
This kata is followed by: http://www.codewars.com/kata/cycle-detection-brents-tortoise-and-hare
Similar Kata:
Stats:
Created | Sep 15, 2014 |
Published | Sep 16, 2014 |
Warriors Trained | 1507 |
Total Skips | 717 |
Total Code Submissions | 1413 |
Total Times Completed | 256 |
Python Completions | 181 |
JavaScript Completions | 74 |
Ruby Completions | 20 |
Total Stars | 33 |
% of votes with a positive feedback rating | 92% of 53 |
Total "Very Satisfied" Votes | 46 |
Total "Somewhat Satisfied" Votes | 6 |
Total "Not Satisfied" Votes | 1 |