## floyd cycle detection algorithm

in lua

### Source Code

``````-- Floyd cycle finding algorithm
-- See: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare

-- Detects cycle in a given sequence
-- f : a function which returns the next element (i.e f(x0) = x1, f(x1) = x2, ...)
-- x0 : the initial element
-- returns : the cycle (loop) position, or tail
-- returns : the cycle (loop) length
return function (f, x0)
local tortoise = f(x0)
local hare = f(f(x0))

while tortoise ~= hare do
if not tortoise or not hare then return nil end
tortoise = f(tortoise)
hare = f(f(hare))
end

local mu = 0
tortoise = x0
repeat
tortoise = f(tortoise)
hare = f(hare)
mu = mu + 1
until tortoise == hare

local lambda = 1
hare = f(tortoise)
while tortoise ~= hare do
hare = f(hare)
lambda = lambda + 1
end

return lambda, mu
end
``````
``````-- Tests for floyd.lua
local floyd = require 'floyd'

local total, pass = 0, 0

local function dec(str, len)
return #str < len
and str .. (('.'):rep(len-#str))
or str:sub(1,len)
end

local function run(message, f)
total = total + 1
local ok, err = pcall(f)
if ok then pass = pass + 1 end
local status = ok and 'PASSED' or 'FAILED'
print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

run('Floyd cycle detection test', function()
local t = {}
for i = 1,7 do t[i] = {} end
for i = 1,6 do t[i].next = t[i+1] end
t[7].next = t[2]

local function f(n) return n and n.next end
local len, tail = floyd(f, t[1])
assert(len == 6 and tail == 1)

t[7].next = t[5]
len, tail = floyd(f, t[1])
assert(len == 3 and tail == 4)

t[7].next = nil
assert(floyd(f, t[1]) == nil)
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
:format(total, pass, total-pass, (pass*100/total)))
``````