return (functionlocal builders = local function register(name, f) builders[name] = fendregister('llpeg.lpegrex', function return require end)
register('advent.compat', function return require end)
register('bignum', function(myrequire)local compat = myrequire('advent.compat')
-- poor man's bignum librarylocal RADIX = 1000 -- power of 10 to make printout easier
local BigNum = BigNum.__index = BigNumfunction BigNum:new(n) return setmetatable(self):normalizeendfunction 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
'number' then a,b = b,a end local r = a:copy if type(b)
'number' then a,b = b,a end local r = BigNum:new if type(b)
return BigNum
end)
register('util', function(myrequire)local function read_wiki_input(func) return function (frame, ...) if type(frame)
nil then error("Can't find title " .. tostring(title)) end source = source:gsub("^%s*
return
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(nl* Module (nl Module)* nl*Module <-| Type? Name `->` Dest <-| SKIP (`,` SKIP)*
Type <-- Name <-- SKIP
nl <-- %nlSKIP <- []*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, FlipFlop) v.state = false -- initially off elseif v.name
'&' then m.inputs[v.name] = false -- remember a low pulse for each input table.insert(m.inputList, v.name) end end end return modulesend
--PART 1 --
local LList = LList.__index = LListfunction LList:new return setmetatable(self)endfunction LList:pullFromHead local node = self.first self.first = self.first.next if self.first
nil then self.last = self.first = self.last else self.last.next = self.last = self.last.next endendfunction LList:isEmpty return self.first
function Module:deliverAll(which, sendPulse) for _,dest in ipairs(self.dest) do sendPulse(self.name, dest, which) endendfunction Module:attribs return string.format('label="%s%s" ', self.type or "", self.name)end
function Broadcaster:deliver(source, which, sendPulse) self:deliverAll(which, sendPulse)endfunction Broadcaster:attribs return Module.attribs(self) .. "shape=trapezium" end
function FlipFlop:deliver(source, which, sendPulse) if which
function Conj:deliver(source, which, sendPulse) self.inputs[source] = which local sawLow = false for _,v in pairs(self.inputs) do if v
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
watchLevel then rx = rx + 1 end queue:addToTail 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]
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 * highSumend
--PART 2 --
function dump_xdot(modules) print("digraph ")end
-- disjoint pieces of the graph found by looking at xdot outputlocal module_sets =
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)] = --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
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), 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
end)
local modules = modules['bit32'] = require('bit32')modules['string'] = require('string')modules['strict'] = modules['table'] = require('table')local function myrequire(name) if modules[name]