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('day19', function(myrequire)
--[[ DAY 19 ]]--
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* {:workflows: Workflows :} nl+ {:parts: Parts :} nl*
Workflows <-| Workflow (nl Workflow)*
Workflow <-| Name `{` (Rule `,`)* FinalRule `}`
Name <-- {:name: %w+ :} SKIP
Rule <== Prop Op Val `:` Dest
FinalRule:Rule <== Dest
Prop <-- {:prop: %w+ :}
Op <-- {:op: `<` -> 'lt' / `>` -> 'gt' :}
Val <-- {:val: Number :}
Dest <-- {:dest: %w+ :}
Number <- (%d+ -> tonumber) SKIP
Parts <-| Part (nl Part)*
Part <== `{` Rating ( `,` Rating )* `}`
Rating <-| Prop `=` Val
nl <-- %nl
SKIP <- [ ]*
NAME_SUFFIX <- [_%w]+
]])
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 workflowMap = {}
for _,v in ipairs(ast.workflows) do
workflowMap[v.name] = v
end
ast.workflows = workflowMap
local partList = {}
for i,part in ipairs(ast.parts) do
local partProps = {}
for _,v in ipairs(part) do
partProps[v.prop] = v.val
end
partProps.id = i
partList[i] = partProps
end
ast.parts = partList
return ast
end
--[[ PART 1 ]]--
local function processPart(workflows, name, part)
if name == 'R' then return false end -- rejected
if name == 'A' then return true end -- accepted!
local w = workflows[name]
for _,rule in ipairs(w) do
-- final rule: automatically dispatch
if rule.op == nil then
return processPart(workflows, rule.dest, part)
end
-- otherwise, process 'lt' rule
if rule.op == 'lt' and part[rule.prop] < rule.val then
return processPart(workflows, rule.dest, part)
end
if rule.op == 'gt' and part[rule.prop] > rule.val then
return processPart(workflows, rule.dest, part)
end
end
error("should not reach here")
end
local function part1(source)
local puzzle = parse(source)
local sum = 0
for _,part in ipairs(puzzle.parts) do
local accept = processPart(puzzle.workflows, 'in', part)
if accept then
sum = sum + part.x + part.m + part.a + part.s
end
end
return sum
end
--[[ PART 2 ]]--
local Range = {}
Range.__index = Range
function Range:new(p)
return setmetatable(p or { min=1, max=4000 }, self)
end
-- returns lt, ge split
function Range:split(val)
if val <= self.min then
return nil, self -- entire self is above the split
elseif val > self.max then
return self, nil -- entire self is below the split
else
local lt = Range:new{ min=self.min, max=val-1 }
local ge = Range:new{ min=val, max=self.max }
return lt, ge
end
end
function Range:__len()
-- number of values in the range
return 1 + self.max - self.min
end
function Range:__tostring()
return string.format("[%d,%d]", self.min, self.max)
end
local XMAS = {}
XMAS.__index = XMAS
function XMAS:new(p)
return setmetatable(p or {
x=Range:new(), m=Range:new(), a=Range:new(), s=Range:new(),
}, self)
end
function XMAS:__len()
-- number of values in the XMAS
return compat.len(self.x) * compat.len(self.m) * compat.len(self.a) * compat.len(self.s)
end
function XMAS:biglen()
return BigNum:new(1) * compat.len(self.x) * compat.len(self.m) * compat.len(self.a) * compat.len(self.s)
end
function XMAS:__tostring()
return string.format("{x=%s,m=%s,a=%s,s=%s}", self.x, self.m, self.a, self.s)
end
function XMAS:replace(prop, newRange)
local xmas = XMAS:new{ x=self.x, m=self.m, a=self.a, s=self.s }
xmas[prop] = newRange
return xmas
end
-- returns lt, ge split
function XMAS:split(prop, val)
local r = self[prop]
local lt, ge = self[prop]:split(val)
if lt ~= nil then lt = self:replace(prop, lt) end
if ge ~= nil then ge = self:replace(prop, ge) end
return lt, ge
end
local function processXMAS(workflows, name, xmas, accepted, rejected)
if name == 'R' then -- rejected
if rejected ~= nil then
table.insert(rejected, xmas)
end
return
end
if name == 'A' then -- accepted!
table.insert(accepted, xmas)
return
end
local w = workflows[name]
for _,rule in ipairs(w) do
-- final rule: automatically dispatch
if rule.op == nil then
return processXMAS(workflows, rule.dest, xmas, accepted, rejected)
-- otherwise, process 'lt' rule
elseif rule.op == 'lt' then
local lt,ge = xmas:split(rule.prop, rule.val)
-- recurse to handle the part which matches this rule
processXMAS(workflows, rule.dest, lt, accepted, rejected)
-- continue to handle the part which doesn't match
xmas = ge
elseif rule.op == 'gt' then
local le,gt = xmas:split(rule.prop, rule.val + 1)
-- recurse to handle the part which matches this rule
processXMAS(workflows, rule.dest, gt, accepted, rejected)
-- continue to handle the part which doesn't match
xmas = le
end
end
error("should not reach here")
end
local function part2(source)
local puzzle = parse(source)
local accepted = {}
processXMAS(puzzle.workflows, 'in', XMAS:new(), accepted)
local sum = BigNum:new(0)
for _,v in ipairs(accepted) do
--print(tostring(v), compat.len(v))
sum = sum + v:biglen()
end
return sum
end
--[[ CLI ] ]--
local source = io.input("day19.input"):read("*a")
print('Sum:', part1(source))
print('Combinations:', 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('day19')
end)()
