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)()