local fmt = require "fmt"
require "queue"

-- Flip the stack of pancakes at the given position.
local function flip(pancakes, pos)
    local s = tostring(pancakes)
    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 = tonumber(range(1, n):concat(""))
    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)
            if !stack_flips[flipped] then
                stack_flips[flipped] = flips
                queue:push(flipped)
            end
        end
    end
    return find_max(stack_flips)
end

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