Skip to content

Instantly share code, notes, and snippets.

@Nevraeka
Created July 1, 2013 05:52
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Nevraeka/5898643 to your computer and use it in GitHub Desktop.
Save Nevraeka/5898643 to your computer and use it in GitHub Desktop.
Linked List detection experiment
#taken from Floyds Algorithm (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare)
def floyd(f, x0)
tortoise = f(x0)
hare = f(f(x0))
while tortoise != hare
tortoise = f(tortoise)
hare = f(f(hare))
end
mu = 0
tortoise = x0
while tortoise != hare
tortoise = f(tortoise)
hare = f(hare)
mu += 1
end
lam = 1
hare = f(tortoise)
while tortoise != hare
hare = f(hare)
lam += 1
end
lam == mu
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment