return (function()
local builders = {}
local function register(name, f)
builders[name] = f
end
register('llpeg', function() return require [[Module:User:Cscott/llpeg]] 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('day14', function(myrequire)
--[[ DAY 14 ]]--
local l = myrequire('llpeg')
local PriorityQueue = myrequire('pqueue')
--[[ PARSING ]]--
local Spot = {}
Spot.__index = Spot
function Spot:new(args)
return setmetatable(args, self)
end
function Spot:isEmpty()
return not(self.round or self.cube)
end
function Spot:__tostring()
if self.round then return "O" end
if self.cube then return "#" end
return "."
end
local nl = l.P"\n"
function make_spot(s)
if s == "#" then return Spot:new{cube=true} end
if s == "O" then return Spot:new{round=true} end
return Spot:new{}
end
local patt = l.P{
"Graph",
Graph = l.Ct( l.V"Row" * (nl^1 * l.V"Row")^0 * nl^0) * -1,
Row = l.Ct( l.V"Spot"^1 ),
Spot = l.S"#O." / make_spot,
}
local Graph = {}
Graph.__index = Graph
function parse(source)
--print(inspect(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!')
--print(inspect(ast))
return Graph:new(ast)
end
--[[ Part 1 ]]--
function Graph:new(data)
return setmetatable({ data=data }, self)
end
function Graph:at(row,col,default)
return (self.data[row] or {})[col] or default
end
function Graph:set(row,col,val)
if self.data == nil then
self.data = {}
end
if self.data[row] == nil then
self.data[row] = {}
end
self.data[row][col] = val
end
function Graph:rowN()
return #(self.data)
end
function Graph:colN()
return #(self.data[1])
end
function Graph:print()
for r,row in ipairs(self.data) do
for c,val in ipairs(row) do
if val == nil then val = " " end
io.write(tostring(val))
end
io.write("\n")
end
end
function Graph:link()
for r=1,self:rowN() do
for c=1,self:colN() do
local sp = self:at(r,c)
sp.r, sp.c = r,c
if r > 1 then sp.n = self:at(r-1,c) end
if c > 1 then sp.w = self:at(r,c-1) end
if r < self:rowN() then sp.s = self:at(r+1,c) end
if c < self:colN() then sp.e = self:at(r,c+1) end
--print(string.format("%d,%d %s %s %s %s", sp.r,sp.c,sp.n,sp.e,sp.s,sp.w))
end
end
end
function Graph:numberRocks()
local rocks = {}
local num = 1
for r=1,self:rowN() do
for c=1,self:colN() do
local sp = self:at(r,c)
if sp.round then
sp.id = num
num = num + 1
table.insert(rocks, sp)
end
end
end
return rocks
end
-- the cube rocks partition each row or column, and after each
-- roll all the rocks are going to pile up at each. so we just
-- need to know for a given rock its (wlog) col, compare that to
-- the closest cube in the row, and move it adjacent to the cube.
-- if each cube keeps track of how many rocks have moved beside it,
-- we can space them out appropriately. This makes rocks move
-- through each other! ie doesn't actually respect the rock identity,
-- but the results are correct.
-- HOWEVER, this way also works, and is "fast enough"
function Graph:roll(rocks, dir, keyFunc)
local Q = PriorityQueue()
for _,sp in ipairs(rocks) do
Q:put(sp, keyFunc(sp))
end
-- now start rolling <direction>!
while not Q:empty() do
local sp = Q:pop()
local neigh = sp[dir]
if neigh ~= nil and neigh:isEmpty() then -- can we roll here?
local id = sp.id
sp.round = false
sp.id = nil
neigh.round = true
neigh.id = id
rocks[id] = neigh
Q:put(neigh, keyFunc(neigh))
end
end
end
function Graph:debug_cycle(rocks)
print("Roll north:")
self:roll(rocks, "n", function(sp) return sp.r end)
self:print()
print()
print("Roll west:")
self:roll(rocks, "w", function(sp) return sp.c end)
self:print()
print()
print("Roll south:")
self:roll(rocks, "s", function(sp) return -sp.r end)
self:print()
print()
print("Roll east:")
self:roll(rocks, "e", function(sp) return -sp.c end)
end
function Graph:cycle_one(rocks)
self:roll(rocks, "n", function(sp) return sp.r end)
self:roll(rocks, "w", function(sp) return sp.c end)
self:roll(rocks, "s", function(sp) return -sp.r end)
self:roll(rocks, "e", function(sp) return -sp.c end)
end
function Graph:cycle(rocks, n)
local seen = {}
local i=1
while i <= n do
local h = self:hash()
if seen[h] == nil then
seen[h] = i
self:cycle_one(rocks)
i = i + 1
else
-- short cut!
local s = seen[h]
-- after s steps we're at a cycle point
-- we'll be back here/there in (i-s) more steps
-- so skip ahead as many (i-s) steps as we can
local cycles = math.floor((n - i) / (i - s))
-- print(i,s,cycles)
i = i + cycles*(i-s)
while i<=n do
self:cycle_one(rocks)
i = i + 1
end
return
end
end
end
function Graph:hash()
local t = {}
for r=1,self:rowN() do
for c=1,self:colN() do
local sp = self:at(r,c)
if sp.cube then
-- skip, cubes never move
else
table.insert(t, tostring(sp))
end
end
end
return table.concat(t)
end
function Graph:score()
local sum = 0
for r=1,self:rowN() do
local row_score = 1 + self:rowN() - r
for c=1,self:colN() do
local sp = self:at(r,c)
if sp.round then
sum = sum + row_score
end
end
end
return sum
end
function part1(source)
local graph = parse(source)
graph:link()
--graph:print()
--print()
local rocks = graph:numberRocks()
graph:roll(rocks, "n", function(sp) return sp.r end)
--graph:print()
return graph:score()
end
function part2(source)
local graph = parse(source)
graph:link()
--graph:print()
--print()
local rocks = graph:numberRocks()
graph:cycle(rocks, 1000000000)
--graph:print()
return graph:score()
end
--[[ CLI ] ]--
local source = io.input("day14.input"):read("a")
print('Sum:', part1(source))
print('Sum:', part2(source))
--[ [ END CLI ]]--
return {
part1 = function(frame)
local s = mw.title.new(frame.args[1]):getContent()
return part1(s)
end,
part2 = function(frame)
local s = mw.title.new(frame.args[1]):getContent()
return part2(s, tonumber(frame.args[2]))
end,
}
end)
local modules = {}
modules['table'] = require('table')
modules['string'] = require('string')
modules['strict'] = {}
local function myrequire(name)
if modules[name] == nil then
modules[name] = true
modules[name] = (builders[name])(myrequire)
end
return modules[name]
end
return myrequire('day14')
end)()
