local fmt = require "fmt"

-- Converts a string of the form "{1, 2}" into an array: {1, 2}
local function as_array(s)
    local split = s:sub(2, -2):split(", ")
    return split:map(|ss| -> tonumber(ss))
end

-- Merges two maps into one. If the same key is present in both maps
-- its value will be the one in the second map.
local function merge_maps(m1, m2)
    local m3 = {}
    for k, v in m1 do m3[k] = v end
    for k, v in m2 do m3[k] = v end
    return m3
end

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

local function pancake(len)
    local num_stacks = 1
    local goal_stack = fmt.swrite(range(1, len))
    local stacks = {[goal_stack] = 0}
    local new_stacks = {[goal_stack] = 0}
    for i = 1, 1000 do
        local next_stacks = {}
        for new_stacks:keys() as key do
            local arr = as_array(key)
            local pos = 2
            while pos <= len do
                local new_stack = arr:slice(1, pos):reverse()
                table.move(arr, pos + 1, #arr, pos + 1, new_stack)
                new_stack = fmt.swrite(new_stack)
                if !stacks[new_stack] then next_stacks[new_stack] = i end
                ++pos
            end
        end
        new_stacks = next_stacks
        stacks = merge_maps(stacks, new_stacks)
        local perms = stacks:size()
        if perms == num_stacks then
            return {find_max(stacks), i - 1}
        end
        num_stacks = perms
    end
end

for i = 1, 9 do
    local [example, steps] = pancake(i)
    fmt.print("pancake(%d) = %-2d  example: %s", i, steps, example)
end