josephus problem

in lua

Source Code

``````-- Josephus problem implementation
-- See: http://en.wikipedia.org/wiki/Josephus_problem

-- Returns the survivor
-- n       : the initial number of people
-- k       : the count for each step
-- returns : the survivor's number
local function josephus_recursive(n, k)
if n == 1 then return 1
else
return ((josephus_recursive(n-1,k)+k-1)%n)+1
end
end

-- Returns the survivor
-- n       : the initial number of people
-- k       : the count for each step
-- returns : the survivor's number
local function josephus_loop(n, k)
local r, i = 0, 1
while i <= n do
r = (r + k) % i
i = i + 1
end
return r + 1
end

-- Private wrapper
local function j(n, k, s)
if n == 1 then return 1 end
local new_s = ((s or 1) + k - 2) % n + 1
local survivor = j(n - 1, k, new_s)
return survivor < new_s and survivor or survivor + 1
end

-- Returns the survivor
-- n       : the initial number of people
-- k       : the count for each step
-- returns : the survivor's number
local function josephus_elaborated(n, k)
return j(n, k, 1)
end

-- Returns the survivor (assumes the count is k = 2)
-- n       : the initial number of people
-- returns : the survivor's number
local function josephus_2(n)
return josephus_loop(n, 2)
end

-- Returns the survivor (assumes the count is k = 2)
-- Alternate implementation using logarithm.
-- n       : the initial number of people
-- returns : the survivor's number
local function josephus_log_2(n)
return 2*(n - 2 ^ math.floor(math.log(n, 2)))+1
end

return {
recursive    = josephus_recursive,
loop         = josephus_loop,
elaborated   = josephus_elaborated,
standard     = josephus_2,
standard_log = josephus_log_2,
}
``````
``````-- Tests for josephus.lua
local j = require 'josephus'

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

-- Solutions for k = 2
local solutions = {1 ,1 ,3 ,1 ,3 ,5 ,7 ,1 ,3 ,5 ,7 ,9 ,11 ,13 ,15 ,1}

run('Josephus recursive test', function()
for n = 1,16 do assert(j.recursive(n, 2) == solutions[n]) end
end)

run('Josephus loop-based test', function()
for n = 1,16 do assert(j.loop(n, 2) == solutions[n]) end
end)

run('Josephus elaborated test', function()
for n = 1,16 do assert(j.elaborated(n, 2) == solutions[n]) end
end)

run('Josephus standard test', function()
for n = 1,16 do assert(j.standard(n) == solutions[n]) end
end)

run('Josephus standard logarithm-based test', function()
for n = 1,16 do assert(j.standard_log(n) == solutions[n]) end
end)

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