63 lines
1.8 KiB
Text
63 lines
1.8 KiB
Text
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
|