local fmt = require "fmt"
require "table2"

local function are_same(a, b)
    for i = 1, #a do
        if a[i] != b[i] then return false end
    end
    return true
end

local function perfect_shuffle(a)
    local n = #a
    local b = table.rep(n, 0)
    local hsize = n // 2
    for i = 1, hsize do b[i * 2 - 1] = a[i] end
    local j = 2
    for i = hsize + 1, n do
        b[j] = a[i]
        j += 2
    end
    return b
end

local function count_shuffles(a)
    local n = #a
    assert(n % 2 == 0 and n > 1, "Array must be even-sized and non-empty.")
    local b = a
    local count = 0
    while true do
        local c = perfect_shuffle(b)
        ++count
        if are_same(a, c) then return count end
        b = c
    end
end

print("Deck size  Num shuffles")
print("---------  ------------")
local sizes = {8, 24, 52, 100, 1020, 1024, 10000}
for sizes as size do
    local a = {0}
    for i = 2, size do a[i] = i - 1 end
    local count = count_shuffles(a)
    fmt.print("%-9d     %d", size, count)
end