Module:User:Cscott/Advent Of Code 2023/Day 19 Explained

return (functionlocal builders = local function register(name, f) builders[name] = fendregister('llpeg.lpegrex', function return require end)

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

0 then return "0" end return table.concat(result)endfunction 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 selfendfunction BigNum:copy local r = BigNum:new for i=1,#self do r[i] = self[i] end return rendfunction 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:normalizeendfunction 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 rend

return BigNum

end)

'string' then 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*", "", 1) source = source:gsub("%s*$", "", 1) return func(source) endend

return

end)

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(Workflow (nl Workflow)*Workflow <-| Name ``Name <-- SKIPRule <

Prop Op Val `:` DestFinalRule:Rule <

DestProp <-- Op <-- Val <-- Dest <-- Number <- (%d+ -> tonumber) SKIP

Parts <-| Part (nl Part)*Part <

``Rating <-| Prop `=` Val

nl <-- %nlSKIP <- []*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 astend

--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 sumend

--PART 2 --

local Range = Range.__index = Rangefunction Range:new(p) return setmetatable(p or, self)end-- returns lt, ge splitfunction 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 local ge = Range:new return lt, ge endendfunction Range:__len -- number of values in the range return 1 + self.max - self.minendfunction Range:__tostring return string.format("[%d,%d]", self.min, self.max)end

local XMAS = XMAS.__index = XMASfunction XMAS:new(p) return setmetatable(p or, self)endfunction 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)endfunction XMAS:biglen return BigNum:new(1) * compat.len(self.x) * compat.len(self.m) * compat.len(self.a) * compat.len(self.s)endfunction XMAS:__tostring return string.format("", self.x, self.m, self.a, self.s)endfunction XMAS:replace(prop, newRange) local xmas = XMAS:new xmas[prop] = newRange return xmasend-- returns lt, ge splitfunction 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, geend

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 sumend

--CLI ]--local source = io.input("day19.input"):read("*a")print('Sum:', part1(source))print('Combinations:', 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]