return (function()
local builders = {}
local function register(name, f)
builders[name] = f
end
register('llpeg', function() return require [[Module:User:Cscott/llpeg]] 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[^>]*>\n?", "", 1)
source = source:gsub("</syntaxhighlight[^>]*>%s*$", "", 1)
return func(source, frame.args[2], frame.args[3])
end
end
return {
read_wiki_input = read_wiki_input,
}
end)
register('pqueue', function(myrequire)
--[[ Priority Queue implemented in lua, based on a binary heap.
Copyright (C) 2017 Lucas de Morais Siqueira <lucas.morais.siqueira@gmail.com>
License: zlib
This software is provided 'as-is', without any express or implied
warranty. In no event will the authors be held liable for any damages
arising from the use of this software.
Permission is granted to anyone to use this software for any purpose,
including commercial applications, and to alter it and redistribute it
freely, subject to the following restrictions:
1. The origin of this software must not be misrepresented; you must not
claim that you wrote the original software. If you use this software
in a product, an acknowledgement in the product documentation would be
appreciated but is not required.
2. Altered source versions must be plainly marked as such, and must not be
misrepresented as being the original software.
3. This notice may not be removed or altered from any source distribution.
]]--
-- modified by xxopxe@gmail.com
local floor = math.floor
local PriorityQueue = {}
PriorityQueue.__index = PriorityQueue
setmetatable(
PriorityQueue,
{
__call = function ()
local new = {}
setmetatable(new, PriorityQueue)
new:initialize()
return new
end
}
)
function PriorityQueue:initialize()
--[[ Initialization.
Example:
PriorityQueue = require "priority_queue"
pq = PriorityQueue()
]]--
self.heap_val = {}
self.heap_pri = {}
self.current_size = 0
end
function PriorityQueue:empty()
return self.current_size == 0
end
function PriorityQueue:size()
return self.current_size
end
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
end
end
function PriorityQueue:put(v, p)
--[[ Put an item on the queue.
Args:
v: the item to be stored
p(number): the priority of the item
]]--
--
self.current_size = self.current_size + 1
self.heap_val[self.current_size] = v
self.heap_pri[self.current_size] = p
self:swim()
end
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
end
end
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
end
end
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, retprio
end
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_input
local PriorityQueue = myrequire('pqueue')
local function sortedKeys(tbl)
local sorted = {}
for k,_ in pairs(tbl) do
table.insert(sorted, k)
end
table.sort(sorted)
return sorted
end
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 == 0 then return nil end
return i, val[i]
end
return f, nil, i
end
--[[ PARSING ]]--
local nl = l.P"\n"
local SKIP = l.S" \t"^0
local patt = l.P{
"Bricks",
Bricks = l.Ct( l.V"Brick" * (nl * l.V"Brick")^0 * nl^0) * -1,
Brick = l.Ct( l.Cg(l.V"Coord", "low") * l.P"~" * SKIP * l.Cg(l.V"Coord", "high")),
Coord = l.Ct( l.Cg(l.V"Number", "x") * SKIP * l.P"," *
l.Cg(l.V"Number", "y") * SKIP * l.P"," *
l.Cg(l.V"Number", "z") * SKIP ),
Number = ((l.P"-" ^ -1) * (l.R"09"^1)) / tonumber,
}
local Brick = {}
Brick.__index = Brick
function Brick:new(p)
return setmetatable(p or {}, self)
end
function 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"
end
end
function Brick:len()
return 1 + self.high[self.axis] - self.low[self.axis]
end
function Brick:dropOne()
self.low.z = self.low.z - 1
self.high.z = self.high.z - 1
end
function Brick:raiseOne()
self.low.z = self.low.z + 1
self.high.z = self.high.z + 1
end
function Brick:cubePos(i)
if self.axis == "x" then
return self.low.x + i - 1, self.low.y, self.low.z
elseif self.axis == "y" then
return self.low.x, self.low.y + i - 1, self.low.z
elseif self.axis == "z" then
return self.low.x, self.low.y, self.low.z + i - 1
else
error("bad axis")
end
end
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 ast
end
local Ground = {}
Ground.__index = Ground
function Ground:new()
return setmetatable({data={}}, self)
end
function Ground:at(x,y)
if self.data[x] == nil then return nil end
return self.data[x][y]
end
function Ground:set(x,y,val)
if self.data == nil then
self.data = {}
end
if self.data[x] == nil then
self.data[x] = {}
end
if self.minx == nil or x < self.minx then self.minx = x end
if self.maxx == nil or x > self.maxx then self.maxx = x end
if self.miny == nil or y < self.miny then self.miny = y end
if self.maxy == nil or y > self.maxy then self.maxy = y end
self.data[x][y] = val
end
function Ground:setDefault(x,y,valfunc)
local val = self:at(x, y)
if val ~= nil then return val end
if type(valfunc) == 'function' then
val = valfunc()
else
val = valfunc
end
self:set(x, y, val)
return val
end
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] == nil)
self:at(x,y)[z] = b
end
end
function Ground:removeBrick(b)
for i=1, b:len() do
local x,y,z = b:cubePos(i)
assert(self:at(x,y)[z] == b)
self:at(x,y)[z] = nil
end
end
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 true
end
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 == nil then bb.supports = {} end
table.insert(bb.supports, b)
end
end
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 or z > maxz then maxz = z end
end
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,bricks
end
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 {}) == 0 then
d = true -- doesn't support anything
else
d = true
for _,bb in ipairs(b.supports or {}) do
if #(bb.isSupportedBy) <= 1 then
d = false
break
end
end
end
--[[
print("Brick", b.id, "can be disintegrated:", d)
for _,v in ipairs(b.supports or {}) do
print(" Supports", v.id)
end
for _,v in ipairs(b.isSupportedBy) do
print(" Is supported by", v.id)
end
]]--
if d then total = total + 1 end
end
return total
end
--[[ 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 == brick then
g:addBrick(b) -- replace brick
else
chain = chain + 1
g:removeBrick(b)
b:raiseOne()
g:addBrick(b)
end
end
return chain
end
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 sum
end
--[[ CLI ] ]--
local source = io.input("day22.input"):read("*a")
print('Bricks:', part1(source))
print('Sum of falling bricks:', 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('day22')
end)()
