100 doors problem


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Tags

puzzle

Source Code

-- 100 doors problem implementation
-- See : http://rosettacode.org/wiki/100_doors

-- Collects keys of values matching a predicate
local function collect(t, v)
  local s = {}
  for k,_v in ipairs(t) do
    if _v == v then s[#s+1] = k end
  end
  return s
end

-- Simulates the 100 doors problem
-- returns : a table of all open doors
--           a table of all closed doors
local function hundred_doors()
  local doors = {}
  for mp = 1, 100 do
    for i = mp, 100, mp  do
      doors[i] = (doors[i] == nil and false or not doors[i])
    end
  end
  return collect(doors, true), collect(doors, false)
end

return hundred_doors
-- Tests for 100doors.lua
local hundred_doors = require '100doors'

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('Open doors are perfect squares of integers', function()
  local open, closed = hundred_doors()
  for i, v in ipairs(open) do
    assert(math.floor(math.sqrt(v)) == math.sqrt(v))
  end
end)

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