local fmt = require "fmt"
require "queue"

-- Flip the stack of pancakes at the given position.
local function flip(pancakes, pos, n)
    local s = tostring(pancakes)
    if n == 10 and #s == 9 do s = "0" .. s end
    return tonumber(s:sub(1, pos):reverse() .. s:sub(pos + 1))
end

-- Finds the maximum value in 'map' and returns the first key
-- it finds (iteration order is undefined) with that value
-- and the value itself.
local function find_max(map)
    local max = -1
    local max_key = nil
    for k, v in map do
        if v > max then
            max = v
            max_key = k
        end
    end
    return {max_key, max}
end

-- Return the nth pancake number.
local function pancake(n)
    local init_stack = n < 10 ? tonumber(range(1, n):concat("")) :
                                tonumber(range(1, 9):concat("")) .. "0"
    local stack_flips = {[init_stack] = 0}
    local queue = new queue()
    queue:push(init_stack)
    while !queue:empty() do
        local stack = queue:pop()
        local flips = stack_flips[stack] + 1
        for i = 2, n do
            local flipped = flip(stack, i, n)
            if !stack_flips[flipped] then
                stack_flips[flipped] = flips
                queue:push(flipped)
            end
        end
    end
    return find_max(stack_flips)
end

for n = 1, 10 do
    local [pancakes, p] = pancake(n)
    local t = {}
    for c in tostring(pancakes):gmatch("%d") do t:insert(c) end
    if n == 10 and #t == 9 then t:insert(1, "0") end
    pancakes = "{" .. t:concat(", ") .. "}"
    pancakes = pancakes:replace("0", "10")
    fmt.print("pancake(%2d) = %-2d  example: %s", n, p, pancakes)
end