51 lines
1.4 KiB
Text
51 lines
1.4 KiB
Text
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
|