local fmt = require "fmt"
require "table2"

local function do_trials(trials, np, strategy)
    local pardoned = 0
    for _ = 1, trials do
        local drawers = table.create(100)
        for i = 1, 100 do drawers[i] = i end
        drawers:shuffle()
        local next_trial = false
        for p = 1, np do
            local next_prisoner = false
            if strategy == "optimal" then
                local prev = p
                for __ = 1, 50 do
                    local curr = drawers[prev]
                    if curr == p then
                        next_prisoner = true
                        break
                    end
                    prev = curr
                end
            else
                local opened = table.rep(100, false)
                for ___ = 1, 50 do
                    local n
                    while true do
                        n = math.random(100)
                        if !opened[n] then
                            opened[n] = true
                            break
                        end
                    end
                    if drawers[n] == p then
                        next_prisoner = true
                        break
                    end
                end
            end
            if !next_prisoner then
                next_trial = true
                break
            end
        end
        if !next_trial then pardoned += 1 end
    end
    local rf = pardoned / trials * 100
    fmt.print("  strategy = %-7s  pardoned = %,6s relative frequency = %5.2f%%\n", strategy, pardoned, rf)
end

local trials = 1e5
for {10, 100} as np do
    fmt.print("Results from %,s trials with %d prisoners:\n", trials, np)
    for {"random", "optimal"} as strategy do do_trials(trials, np, strategy) end
end