5 kyu

Cycle Detection: Floyd's The Tortoise and the The Hare

181 of 256user3482173

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 μ+λ\mu + \lambda 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 x0x_0 and ff.

There is 3 phases for the algorithm:

  1. Main phase of algorithm: starting with tortoise = x1x_1, hare = x2x_2, move the tortoise by one tortoise=f(tortoise)tortoise=f(tortoise) and the hare by two hare=f(f(hare))hare=f(f(hare)). They will eventually be both in the loop and as the distance between them is increasing it will reach a multiple of λ\lambda and they will get the same value.

  2. At this point the tortoise position has walked ν\nu , the hare 2ν2\nu, the distance between them is both ν\nu and kλk\lambda. So hare starting at his last position moving in cycle one step at a time and tortoise at x0x_0 moving towards the cycle will intersect at the beginning of the cycle. This is how to find μ\mu.

  3. 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 λ\lambda.

You will build a function that take ff and x0x_0 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

Mathematics
Algorithms

Stats:

CreatedSep 15, 2014
PublishedSep 16, 2014
Warriors Trained1507
Total Skips717
Total Code Submissions1413
Total Times Completed256
Python Completions181
JavaScript Completions74
Ruby Completions20
Total Stars33
% of votes with a positive feedback rating92% of 53
Total "Very Satisfied" Votes46
Total "Somewhat Satisfied" Votes6
Total "Not Satisfied" Votes1
Ad
Contributors
  • user3482173 Avatar
  • jhoffner Avatar
  • zloyrusskiy Avatar
  • utoppia Avatar
Ad