return (function()
local builders = {}
local function register(name, f)
builders[name] = f
end
register('llpeg', function() return require [[Module:User:Cscott/llpeg]] end)
register('day8', function(myrequire)
--[[ DAY 8 ]]--
local l = myrequire('llpeg')
--local inspect = require 'inspect'
--[[ PARSING ]]--
local SKIP = l.P" " ^ 0
local nl = l.P"\n"
function tok(s) return l.P(s) * SKIP end
function record(graph, name, node)
node.name = name
graph[name] = node
if graph._nodes == nil then graph._nodes = {} end
table.insert(graph._nodes, name)
return graph
end
local patt = l.P{
l.Ct( l.V"Instructions" * nl^1 * l.V"Graph" * -1),
Instructions = l.Cg( l.Ct( l.V"Dir" ^ 1 ), "instrs" ),
Graph = l.Cg( l.Ct("") * ( (l.V("GraphNode") % record)^1 ), "graph" ),
GraphNode = l.V"Location" * tok("=") * l.V"Node" * nl^0,
Node = l.Ct( tok"(" * l.Cg( l.V"Location", "L" ) * tok"," *
l.Cg( l.V"Location", "R" ) * tok")" ),
Dir = l.C( l.S"LR" ) * SKIP,
Location = l.C( l.R("AZ","09") ^ 1 ) * SKIP,
}
function parse(source)
--print(inspect(source))
local ast, errlabel, pos = patt:match(source)
if not ast then
local lineno, colno, line = lpegrex.calcline(source, pos)
local colhelp = string.rep(' ', colno-1)..'^'
error('syntax error: '..lineno..':'..colno..': '..errlabel..
'\n'..line..'\n'..colhelp)
end
--print('Parsed with success!')
--print(inspect(ast))
ast.nodes = ast.graph._nodes
ast.graph._nodes = nil
return ast
end
--[[ PART 1 ]]--
function part1(source)
local input = parse(source)
local steps = 0
local location = "AAA"
local i = 1
while location ~= "ZZZ" do
steps = steps + 1
local dir = input.instrs[i]
location = input.graph[location][dir]
i = i + 1
if i > #input.instrs then i = 1 end
end
return steps
end
--[[ Part 2 ]]--
function find_cycle(input, location)
local start = location
local stops = {}
local steps = 0
local i = 1
local seen = {}
local path = {}
repeat
seen[location .. "-" .. i] = steps
table.insert(path, location)
local node = input.graph[location]
if node.stop then table.insert(stops, steps) end
local dir = input.instrs[i]
--table.insert(path, dir)
location = node[dir]
steps = steps + 1
i = i + 1
if i > #input.instrs then i = 1 end
until seen[location.."-"..i] ~= nil
table.insert(path,location)
-- after 'inital' steps we start the cycle
local initial = seen[location.."-"..i]
-- after 'initial + n*cyclelength' steps we are at the same place
local cyclelength = steps - initial
-- path[s+1] is where we are at after step `s` (silly 1-based language)
assert(path[1+initial] == path[1+initial+cyclelength])
-- subtract the initial portion from the stops
-- after 'n*cyclelength + stop' steps we are at a stop; note that the
-- 'initial' portion is already included in the 'stop' amount
assert(string.sub(path[1+stops[1]], -1) == "Z")
return cyclelength, stops
end
function gcd(a,b) -- good ol' euclid
while a ~= b do
if a > b then
a = a - b
else
b = b - a
end
end
return a
end
function lcm(nums)
local partial = {}
for i=1,#nums do
partial[i] = nums[i]
end
local prod = 1
for i=1,#nums do
-- remove common factors of i from the rest of the list
for j=i+1,#nums do
partial[j] = math.floor(partial[j] / gcd(partial[i], partial[j]))
end
prod = prod * partial[i]
end
return prod
end
function part2(source)
local input = parse(source)
-- post process!
local location = {}
for _,name in ipairs(input.nodes) do
local node = input.graph[name]
local lastchar = string.sub(name, -1)
if lastchar == "A" then
node.start = true
table.insert(location, name) -- collect starting locations
elseif lastchar == "Z" then
node.stop = true
end
end
-- print(inspect(input))
-- find cycles for each starting location
local nums = {}
for i=1,#location do
local cyclelen,stops = find_cycle(input, location[i])
-- luckily there's only one stop per cycle!
assert(#stops == 1) -- not guaranteed!
-- luckily the stop position is exactly the same as the cyclelength
assert(cyclelen == stops[1]) -- not guaranteed!
-- solve simultaneous equations:
-- a*cycle1 + stop1 = b*cycle2 + stop2 = c*cycle3 + stop3 = ...
-- because we're so lucky, this is just
-- a*cycle1 = b*cycle2 = c*cycle3 = ..
-- which is just the least common multiple of cycle1..etc
-- if we were *really* lucky these would all be primes, but alas.
--print(cyclelen,inspect(stops))
table.insert(nums, cyclelen)
end
return lcm(nums)
end
-- CLI version
--[[
local source = io.input("day8.input"):read("a")
print(part1(source))
print(part2(source))
]]--
return {
part1 = function(frame)
local s = mw.title.new(frame.args[1]):getContent()
return part1(s)
end,
part2 = function(frame)
local s = mw.title.new(frame.args[1]):getContent()
return part2(s)
end,
}
end)
local modules = {}
modules['table'] = require('table')
modules['string'] = require('string')
modules['strict'] = {}
local function myrequire(name)
if modules[name] == nil then
modules[name] = true
modules[name] = (builders[name])(myrequire)
end
return modules[name]
end
return myrequire('day8')
end)()
