return (functionlocal builders = local function register(name, f) builders[name] = fendregister('llpeg', function return require 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('pqueue', function(myrequire)------ modified by xxopxe@gmail.com
local floor = math.floor
local PriorityQueue = PriorityQueue.__index = PriorityQueue
setmetatable(PriorityQueue,)
function PriorityQueue:initialize ---- self.heap_val = self.heap_pri = self.current_size = 0end
function PriorityQueue:empty return self.current_size
function PriorityQueue:size return self.current_sizeend
function PriorityQueue:swim -- Swim up on the tree and fix the order heap property. local heap_val = self.heap_val local heap_pri = self.heap_pri local floor = floor local i = self.current_size
while floor(i / 2) > 0 do local half = floor(i / 2) if heap_pri[i] < heap_pri[half] then heap_val[i], heap_val[half] = heap_val[half], heap_val[i] heap_pri[i], heap_pri[half] = heap_pri[half], heap_pri[i] end i = half endend
function PriorityQueue:put(v, p) ---- -- self.current_size = self.current_size + 1 self.heap_val[self.current_size] = v self.heap_pri[self.current_size] = p self:swimend
function PriorityQueue:sink -- Sink down on the tree and fix the order heap property. local size = self.current_size local heap_val = self.heap_val local heap_pri = self.heap_pri local i = 1
while (i * 2) <= size do local mc = self:min_child(i) if heap_pri[i] > heap_pri[mc] then heap_val[i], heap_val[mc] = heap_val[mc], heap_val[i] heap_pri[i], heap_pri[mc] = heap_pri[mc], heap_pri[i] end i = mc endend
function PriorityQueue:min_child(i) if (i * 2) + 1 > self.current_size then return i * 2 else if self.heap_pri[i * 2] < self.heap_pri[i * 2 + 1] then return i * 2 else return i * 2 + 1 end endend
function PriorityQueue:pop -- Remove and return the top priority item local heap_val = self.heap_val local heap_pri = self.heap_pri local retval, retprio = heap_val[1], heap_pri[1] heap_val[1], heap_pri[1] = heap_val[self.current_size], heap_pri[self.current_size] heap_val[self.current_size], heap_pri[self.current_size] = nil, nil self.current_size = self.current_size - 1 self:sink return retval, retprioend
function PriorityQueue:peek -- return the top priority item return self.heap_val[1], self.heap_pri[1]end
return PriorityQueue
end)
register('day22', function(myrequire)--DAY 22 --local l = myrequire('llpeg')local read_wiki_input = myrequire('util').read_wiki_inputlocal PriorityQueue = myrequire('pqueue')
local function sortedKeys(tbl) local sorted = for k,_ in pairs(tbl) do table.insert(sorted, k) end table.sort(sorted) return sortedend
local function ripairs(val) local i = 1 while val[i] ~= nil do i = i + 1 end local f = function(_, i) i = i - 1 if i
--PARSING --
local nl = l.P"\n"local SKIP = l.S" \t"^0
local patt = l.P
local Brick = Brick.__index = Brickfunction Brick:new(p) return setmetatable(p or, self)endfunction Brick:setAxis assert(self.low.x <= self.high.x) assert(self.low.y <= self.high.y) assert(self.low.z <= self.high.z) if self.low.x ~= self.high.x then self.axis = "x" elseif self.low.y ~= self.high.y then self.axis = "y" elseif self.low.z ~= self.high.z then self.axis = "z" else -- this is a 1x1 brick, axis is arbitrary self.axis = "x" endendfunction Brick:len return 1 + self.high[self.axis] - self.low[self.axis]endfunction Brick:dropOne self.low.z = self.low.z - 1 self.high.z = self.high.z - 1endfunction Brick:raiseOne self.low.z = self.low.z + 1 self.high.z = self.high.z + 1endfunction Brick:cubePos(i) if self.axis
"y" then return self.low.x, self.low.y + i - 1, self.low.z elseif self.axis
local function parse(source) local ast, errlabel, pos = patt:match(source) if not ast then error(string.format("Error at pos %s label '%s'", pos, errlabel)) end --print('Parsed with success!') --return Graph:new(ast) for i=1,#ast do setmetatable(ast[i], Brick) ast[i]:setAxis ast[i].id = i end return astend
local Ground = Ground.__index = Ground
function Ground:new return setmetatable(self)end
function Ground:at(x,y) if self.data[x]
function Ground:set(x,y,val) if self.data
nil then self.data[x] = end if self.minx
nil or x > self.maxx then self.maxx = x end if self.miny
nil or y > self.maxy then self.maxy = y end self.data[x][y] = valend
function Ground:setDefault(x,y,valfunc) local val = self:at(x, y) if val ~= nil then return val end if type(valfunc)
function Ground:addBrick(b) for i=1, b:len do local x,y,z = b:cubePos(i) self:setDefault(x,y,) assert(self:at(x,y)[z]
function Ground:removeBrick(b) for i=1, b:len do local x,y,z = b:cubePos(i) assert(self:at(x,y)[z]
function Ground:canDropOne(b) for i=1, b:len do local x,y,z = b:cubePos(i) z = z - 1 if z < 1 then return false end -- already on the ground local bb = self:at(x,y)[z] if bb ~= nil and bb ~= b then return false end -- someone else there end return trueend
function Ground:computeSupports(b) local res = for i=1, b:len do local x,y,z = b:cubePos(i) z = z - 1 local bb = self:at(x,y,)[z] if bb ~= nil and bb ~= b then res[bb.id] = bb end end b.isSupportedBy = for _,bb in pairs(res) do table.insert(b.isSupportedBy, bb) if bb.supports
function Ground:print local buf = for y=self.miny,self.maxy do for x = self.minx,self.maxx do local stack = self:at(x,y) local maxz = nil for z,_ in pairs(stack or) do if maxz
nil then table.insert(buf, " ") else table.insert(buf, "X") end end table.insert(buf,"\n") end print(table.concat(buf))end
--Part 1 --
local function dropBricksReturnGround(source) local bricks = parse(source) local g = Ground:new for _,b in ipairs(bricks) do g:addBrick(b) end repeat local changed = false for _,b in ipairs(bricks) do if g:canDropOne(b) then g:removeBrick(b) b:dropOne g:addBrick(b) changed = true end end until not changed --print("Lowered!") --g:print for _,b in ipairs(bricks) do g:computeSupports(b) end return g,bricksend
local function part1(source) local g,bricks = dropBricksReturnGround(source) local total = 0 for _,b in ipairs(bricks) do local d = false if #(b.supports or)
--Part 2 --
local function part2(source) local g,bricks = dropBricksReturnGround(source)
local function chainReaction(brick) local dropped = local dropOrder = g:removeBrick(brick) dropped[brick.id] = true table.insert(dropOrder, brick) repeat local changed = false for _,b in ipairs(bricks) do if not dropped[b.id] then if g:canDropOne(b) then dropped[b.id] = true table.insert(dropOrder, b) g:removeBrick(b) b:dropOne g:addBrick(b) changed = true end end end until not changed local chain = 0 for i,b in ripairs(dropOrder) do if b
local sum = 0 for _,b in ipairs(bricks) do local c = chainReaction(b) --print("Brick", b.id, "would cause to fall:", c) sum = sum + c end return sumend
--CLI ]--local source = io.input("day22.input"):read("*a")print('Bricks:', part1(source))print('Sum of falling bricks:', 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]