return (function()
local builders = {}
local function register(name, f)
builders[name] = f
end
register('llpeg', function() return require [[Module:User:Cscott/llpeg]] end)
register('advent.compat', function() return require [[Module:User:Cscott/compat]] end)
register('day10', function(myrequire)
--[[ DAY 10 ]]--
local l = myrequire('llpeg')
local compat = myrequire('advent.compat')
--[[ PARSING ]]--
local Tile = {}
Tile.__index = Tile
function Tile:new(args)
return setmetatable(args, self)
end
function Tile:p()
return l.P(self.c) * l.Cc(self)
end
function Tile:__tostring()
return self.c
end
local NS = Tile:new{c="|",n=true,s=true}
local EW = Tile:new{c="-",e=true,w=true}
local NE = Tile:new{c="L",n=true,e=true}
local NW = Tile:new{c="J",n=true,w=true}
local SW = Tile:new{c="7",s=true,w=true}
local SE = Tile:new{c="F",s=true,e=true}
local GND = Tile:new{c="."}
local START = Tile:new{c="S",start=true}
local nl = l.P"\n"
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"Tile"^1 ),
Tile = NS:p() + EW:p() + NE:p() + NW:p() + SW:p() + SE:p() + GND:p() + START:p(),
}
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:find_start()
for r,row in ipairs(self.data) do
for c,val in ipairs(row) do
if val.start then
return r,c
end
end
end
error("start not found")
end
function Graph:fix_start()
local row,col = self:find_start()
local start = self:at(row,col)
if self:at(row-1, col, {}).s then
start.n = true
end
if self:at(row+1, col, {}).n then
start.s = true
end
if self:at(row, col-1, {}).e then
start.w = true
end
if self:at(row, col+1, {}).w then
start.e = true
end
return row,col
end
function flood_fill(graph)
local r,c = graph:fix_start()
local fill = Graph:new()
fill:set(r,c,0)
local todo = {}
table.insert(todo, {r,c})
table.insert(todo, {r,c})
local i=0
local maxfill = 0
while i < #todo do
i = i + 1
local r,c = compat.unpack(todo[i])
local tile = graph:at(r,c)
local fillval = fill:at(r,c)
local nr,nc
--print("fillval",fillval,"at",r,c)
--print(inspect(tile))
if tile.n and fill:at(r-1, c) == nil then
nr,nc = r-1,c
elseif tile.s and fill:at(r+1, c) == nil then
nr,nc = r+1,c
elseif tile.e and fill:at(r,c+1) == nil then
nr,nc = r,c+1
elseif tile.w and fill:at(r,c-1) == nil then
nr,nc = r,c-1
else
return maxfill,fill -- no more to fill!
end
fill:set(nr,nc,fillval+1)
table.insert(todo,{nr,nc})
maxfill = math.max(maxfill, fillval+1)
end
end
function part1(source)
local graph = parse(source)
--graph:print()
local ans,_ = flood_fill(graph)
return ans
end
--[[ Part 2 ]]--
function compute_inner(g, fill, nrows, ncols)
local inner = false
local sum = 0
for r=1,nrows do
inner = false
for c=1,ncols do
local is_loop = (fill:at(r,c) ~= nil)
if is_loop then
-- we shoot infintesimally south of the midpoint, such that
-- these count as crossing: |7F (south is true)
-- and these do not: -LJ (south is false)
if g:at(r,c).s then
inner = not inner
end
elseif inner then
-- print(r,c)
sum = sum + 1
end
end
end
return sum
end
function part2(source)
local graph = parse(source)
--graph:print()
local _,fill = flood_fill(graph)
local ans = compute_inner(graph, fill, graph:rowN(), graph:colN())
return ans
end
--[[ CLI:
local source = io.input("day10.input"):read("a")
print(part1(source))
print(part2(source))
]]--
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)
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('day10')
end)()
