return (function()
local builders = {}
local function register(name, f)
builders[name] = f
end
register('llpeg.lpegrex', function() return require [[Module:User:Cscott/lpegrex]] end)
register('advent.compat', function() return require [[Module:User:Cscott/compat]] end)
register('bignum', function(myrequire)
local compat = myrequire('advent.compat')
-- poor man's bignum library
local RADIX = 1000 -- power of 10 to make printout easier
local BigNum = {}
BigNum.__index = BigNum
function BigNum:new(n)
return setmetatable( {n or 0}, self):normalize()
end
function BigNum:__tostring()
local result = {}
local first = true
for i=#self,1,-1 do
local n = self[i]
if n ~= 0 or not first then
local s = tostring(n)
if first then
first = false
else
while #s < 3 do s = '0' .. s end
end
table.insert(result, s)
end
end
if #result == 0 then return "0" end
return table.concat(result)
end
function BigNum:normalize()
local i = 1
while self[i] ~= nil do
if self[i] >= 1000 then
local carry = math.floor(self[i] / 1000)
self[i] = self[i] % 1000
self[i+1] = (self[i+1] or 0) + carry
end
i = i + 1
end
return self
end
function BigNum:copy()
local r = BigNum:new()
for i=1,#self do
r[i] = self[i]
end
return r
end
function BigNum.__add(a, b)
if type(a) == 'number' then
a,b = b,a
end
local r = a:copy()
if type(b) == 'number' then
r[1] = (r[1] or 0) + b
else
for i=1,#b do
r[i] = (r[i] or 0) + b[i]
end
end
return r:normalize()
end
function BigNum.__mul(a, b)
if type(a) == 'number' then
a,b = b,a
end
local r = BigNum:new()
if type(b) == 'number' then
for i=1,#a do
r[i] = a[i] * b
end
return r:normalize()
end
for i=1,#a do
for j=1,#b do
local prod = a[i] * b[j]
r[i+j-1] = (r[i+j-1] or 0) + prod
end
r:normalize()
end
return r
end
return BigNum
end)
register('util', function(myrequire)
local function read_wiki_input(func)
return function (frame, ...)
if type(frame)=='string' then
frame = { args = { frame, ... } }
end
local title = mw.title.new(frame.args[1])
local source = title:getContent()
if source == nil then
error("Can't find title " .. tostring(title))
end
source = source:gsub("^%s*<syntaxhighlight[^>]*>", "", 1)
source = source:gsub("</syntaxhighlight[^>]*>%s*$", "", 1)
return func(source)
end
end
return {
read_wiki_input = read_wiki_input,
}
end)
register('day20', function(myrequire)
--[[ DAY 20 ]]--
local lpegrex = myrequire('llpeg.lpegrex')
local compat = myrequire('advent.compat')
local BigNum = myrequire('bignum')
local read_wiki_input = myrequire('util').read_wiki_input
--[[ PARSING ]]--
local patt = lpegrex.compile([[
Puzzle <-| nl* Module (nl Module)* nl*
Module <-| Type? Name `->` {:dest: Dest :}
Dest <-| {%w+} SKIP (`,` {%w+} SKIP)*
Type <-- {:type: `%` -> '%%' / `&` -> '&' :}
Name <-- {:name: %w+ :} SKIP
nl <-- %nl
SKIP <- [ ]*
NAME_SUFFIX <- [_%w]+
]])
local Module = {}
Module.__index = Module
local FlipFlop = setmetatable({}, Module)
FlipFlop.__index = FlipFlop
local Conj = setmetatable({}, Module)
Conj.__index = Conj
local Broadcaster = setmetatable({}, Module)
Broadcaster.__index = Broadcaster
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))
-- turn the lists into maps
local modules = {}
for _,v in ipairs(ast) do
modules[v.name] = v
if v.type == '&' then
setmetatable(v, Conj)
v.inputs = {}
v.inputList = {}
elseif v.type == '%' then
setmetatable(v, FlipFlop)
v.state = false -- initially off
elseif v.name == 'broadcaster' then
setmetatable(v, Broadcaster)
end
end
-- link up inputs of conjunction modules
for _,v in ipairs(ast) do
for _,dest in ipairs(v.dest) do
local m = modules[dest]
if m ~= nil and m.type == '&' then
m.inputs[v.name] = false -- remember a low pulse for each input
table.insert(m.inputList, v.name)
end
end
end
return modules
end
--[[ PART 1 ]]--
local LList = {}
LList.__index = LList
function LList:new()
return setmetatable({}, self)
end
function LList:pullFromHead()
local node = self.first
self.first = self.first.next
if self.first == nil then self.last = nil end
return node.val
end
function LList:addToTail(val)
if self.last == nil then
self.last = { val = val }
self.first = self.last
else
self.last.next = { val=val }
self.last = self.last.next
end
end
function LList:isEmpty()
return self.first == nil
end
function Module:deliverAll(which, sendPulse)
for _,dest in ipairs(self.dest) do
sendPulse(self.name, dest, which)
end
end
function Module:attribs()
return string.format('label="%s%s" ', self.type or "", self.name)
end
function Broadcaster:deliver(source, which, sendPulse)
self:deliverAll(which, sendPulse)
end
function Broadcaster:attribs() return Module.attribs(self) .. "shape=trapezium" end
function FlipFlop:deliver(source, which, sendPulse)
if which == false then
self.state = not self.state
self:deliverAll(self.state, sendPulse)
end
end
function FlipFlop:attribs() return Module.attribs(self) .. "shape=box" end
function FlipFlop:collectState(accum)
if self.state then table.insert(accum, "1") else table.insert(accum, "0") end
end
function Conj:deliver(source, which, sendPulse)
self.inputs[source] = which
local sawLow = false
for _,v in pairs(self.inputs) do
if v == false then sawLow = true ; break end
end
self:deliverAll(sawLow, sendPulse)
end
function Conj:attribs() return Module.attribs(self) .. "shape=ellipse" end
function Conj:collectState(accum)
for _,v in ipairs(self.inputList) do
if self.inputs[v] then table.insert(accum, "1") else table.insert(accum, "0") end
end
end
function pressButton(modules, watch, watchLevel)
local low, high, rx, queue = 0,0,{},LList:new()
-- pressing the button sends a low pulse to the broadcaster, who sends
-- a low pulse to each destination
local function sendPulse(source, dest, which)
if which then high = high + 1 else low = low + 1 end
--if dest == watch and which == watchLevel then rx = rx + 1 end
queue:addToTail({source=source, dest=dest, which=which})
end
sendPulse(nil, 'broadcaster', false) -- button press to broadcaster
local step = 1
while not queue:isEmpty() do
local event = queue:pullFromHead()
local m = modules[event.dest]
if m ~= nil then
m:deliver(event.source, event.which, sendPulse)
end
if watch ~= nil and modules.tj.inputs[watch] == watchLevel then
table.insert(rx, step)
end
step = step + 1
end
return low, high, rx
end
function part1(source)
local modules = parse(source)
local lowSum, highSum = 0, 0
for i=1,1000 do
local low,high = pressButton(modules)
lowSum = lowSum + low
highSum = highSum + high
end
return lowSum * highSum
end
--[[ PART 2 ]]--
function dump_xdot(modules)
print("digraph {")
print(" {")
for _,v in pairs(modules) do
local attribs = v:attribs()
print(string.format('%s [%s]', v.name, attribs))
end
print("rx [shape=doubleoctagon]")
print(" }")
for _,v in pairs(modules) do
for _,d in ipairs(v.dest) do
print(string.format("%s -> %s ;", v.name, d))
end
end
print("}")
end
-- disjoint pieces of the graph found by looking at xdot output
local module_sets = {
-- after 3932 presses matches state after 1 press
-- after 3931 presses the output goes high
{ "kk", "fc", "xb", "lc", "bh", "pv", "vv", "sm", "hh", "bf", "qm",
"fb", "dr", "nx" },
-- period 3918 presses matches state after 1 press
-- after 3917 presses the output goes high
{ "sk", "pm", "xg", "mb", "mt", "st", "zc", "tb", "lg", "gd", "sr",
"zv", "gv", "lq" },
-- after 3944 presses matches state after 1 press
-- after 3943 presses output goes high
{ "vt", "nf", "dl", "sv", "ht", "ch", "xf", "zf", "cz", "zm", "hm",
"hl", "pn", "kx" },
-- after 4058 presses matches state after 1 press
-- after 4057 presses the state goes high
{ "xc", "jd", "gh", "vd", "dc", "gb", "qq", "ts", "sg", "mh", "pb",
"rv", "nh", "rs" },
}
function collectState(modules, module_set)
local accum = {}
for _,v in ipairs(module_set) do
modules[v]:collectState(accum)
end
return table.concat(accum)
end
function find_cycle(modules, module_set)
local i = 1
local seen = {}
local high = {}
local output = module_set[1]
seen[collectState(modules, module_set)] = { afterButton=0, {} }
--print('Before', collectState(modules, module_set))
while true do
local _,_,rx = pressButton(modules, output, true)
local s = collectState(modules, module_set)
--print('After',i,s)
if seen[s] ~= nil then
--print(string.format("Found cycle after %d presses, matches after %d", i, seen[s].afterButton))
--[[
Conveniently enough, the desired output goes high one cycle before
the cycle loops over
]]--
for _,v in pairs(seen) do
if #(v[1]) > 0 then
assert(v.afterButton == (i-1))
end
end
return seen[s].afterButton, i - seen[s].afterButton
end
seen[s] = { afterButton=i, rx }
i = i + 1
end
end
function part2(source)
local totalCycleLength = BigNum:new(1)
for i=1,4 do
-- parse from scratch as a hack to reset the module state
local modules = parse(source)
local start,cycle = find_cycle(modules, module_sets[i])
-- each cycle loops to the point after the first button press,
-- oddly enough.
assert(start == 1)
totalCycleLength = totalCycleLength * cycle
end
-- we should add one step, to get to the initial cycle start point
-- (remember, start == 1), but then subtract one step, because the
-- event we're interested in, when our output goes high, happens one
-- step before the cycle loops over.
return totalCycleLength + (1 - 1)
end
--[[ CLI ] ]--
local source = io.input("day20.input"):read("*a")
--dump_xdot(parse(source))
print('Sum:', part1(source))
print('Fewest button presses:', part2(source))
--[ [ END CLI ]]--
return {
part1 = read_wiki_input(part1),
part2 = read_wiki_input(part2),
}
end)
local modules = {}
modules['bit32'] = require('bit32')
modules['string'] = require('string')
modules['strict'] = {}
modules['table'] = require('table')
local function myrequire(name)
if modules[name] == nil then
modules[name] = true
modules[name] = (builders[name])(myrequire)
end
return modules[name]
end
return myrequire('day20')
end)()
