return (function()
local builders = {}
local function register(name, f)
builders[name] = f
end
register('llpeg', function() return require [[Module:User:Cscott/llpeg]] end)
register('day18', function(myrequire)
--[[ DAY 13 ]]--
local l = myrequire('llpeg')
--[[ PARSING ]]--
local nl = l.P"\n"
local SKIP = l.S" \t"^0
local patt = l.P{
"DigPlan",
DigPlan = l.Ct( l.V"Step" * (nl * l.V"Step")^0 * nl^0) * -1,
Step = l.Ct( l.Cg(l.V"Dir", "dir") * SKIP *
l.Cg(l.V"Number", "dist") * SKIP *
l.Cg(l.V"Color", "color") * SKIP ),
Dir = l.S"UDLR",
Number = ((l.P"-" ^ -1) * (l.R"09"^1)) / tonumber,
Color = l.P"(" * SKIP * l.P"#" * SKIP * l.C(l.R("09","af")^1) * SKIP * l.P")",
}
local 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)
return ast
end
--[[ Part 1 ]]--
local Ground = {}
Ground.__index = Ground
function Ground:new()
local p = 1
local data = {}
data[p] = {}
data[p][p] = { color="unknown", ['in'] = nil }
return setmetatable({x=p,y=p,data=data,minx=p,maxx=p,miny=p,maxy=p}, self)
end
function Ground:at(x,y)
if self.data[x] == nil then return nil end
return self.data[x][y]
end
function Ground:dig(dir, x, y, color)
if self.data[x] == nil then self.data[x] = {} end
self.data[self.x][self.y].out = dir
self.data[x][y] = { color=color, ['in']=dir }
self.x = x
self.y = y
if x < self.minx then self.minx = x end
if y < self.miny then self.miny = y end
if x > self.maxx then self.maxx = x end
if y > self.maxy then self.maxy = y end
end
local xoff = { U=0, D=0, R=1, L=-1 }
local yoff = { U=-1, D=1, R=0, L=0 }
function Ground:move(dir, color, n)
if n > 1 then
for i=1,n do self:move(dir, color, 1) end
else
self:dig(dir, self.x + xoff[dir], self.y + yoff[dir], color)
end
end
function Ground:fill()
local sum = 0
for y=self.miny,self.maxy do
local inside = false
for x=self.minx,self.maxx do
local sp = self:at(x,y)
if sp ~= nil then
sum = sum + 1
-- as with day 10, we shoot infintesimally "down" such that
-- we count as crossing anything with 'in' or 'out' = down.
if sp['in']=='U' or sp['out']=='D' then
inside = not inside
end
elseif inside then
self.data[x][y] = { color="unknown" }
sum = sum + 1
end
end
end
return sum
end
local shape = {
UU = "|",
UD = "i",
UR = "F",
UL = "7",
DU = "'",
DD = "|",
DR = "L",
DL = "J",
RU = "J",
RD = "7",
RR = "-",
RL = ".",
LU = "L",
LD = "F",
LR = ".",
LL = "-",
}
function Ground:print()
local result = {}
for y=self.miny,self.maxy do
for x=self.minx,self.maxx do
local sp = self:at(x,y)
if sp ~= nil then
if sp['in'] ~= nil and sp.out ~= nil then
local key = sp['in'] .. sp['out']
table.insert(result, shape[key])
else
table.insert(result, "#")
end
else
table.insert(result, " ")
end
end
table.insert(result, "\n")
end
return table.concat(result)
end
local function part1(source)
local instrs = parse(source)
local g = Ground:new()
for _,i in ipairs(instrs) do
g:move(i.dir, i.color, i.dist)
end
--print(g:print())
local sum = g:fill()
--print(g:print())
return sum
end
--[[ Part 2 ]]--
local Node = {}
Node.__index = Node
function Node:new(p)
return setmetatable(p or {}, self)
end
local NGround = {}
NGround.__index = NGround
function NGround:new()
local p = 1
local n = Node:new{x=p,y=p}
return setmetatable({ x=p, y=p, nodes={[p]={[p]=n}}, lastNode=n}, self)
end
function NGround:dig(dir, dist)
local x, y = self.x + xoff[dir]*dist, self.y + yoff[dir]*dist
self.x,self.y = x,y
self.lastNode.out = dir
self.lastNode = Node:new{x=x,y=y,['in']=dir}
if self.nodes[y] == nil then self.nodes[y] = {} end
if self.nodes[y][x] ~= nil then
self.lastNode = self.nodes[y][x]
self.lastNode['in'] = dir -- should be last node in the path
else
self.nodes[y][x] = self.lastNode
end
end
local dir_decode = { ["0"] = "R", ["1"] = "D", ["2"] = "L", ["3"] = "U" }
local function decode(color)
local dist = tonumber(color:sub(1,5), 16)
local dir = dir_decode[color:sub(-1)]
return dir, dist
end
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 part2(source)
local testing = false
local instrs = parse(source)
local g = NGround:new()
for _,i in ipairs(instrs) do
if testing then
-- use the original directions, to test if we get the original result
g:dig(i.dir, i.dist)
else
-- use the new "part 2" decoded directions
local dir,dist = decode(i.color)
g:dig(dir, dist)
end
end
-- now go top to bottom as before, but skipping ahead to the
-- "next interesting y coordinate" each time.
local row = {}
local lastRow,lastWidth = nil, nil
local sum = 0
for _,y in ipairs(sortedKeys(g.nodes)) do
-- sum the width up to this point
if lastRow ~= nil then
-- add to the overall sum the number of blocks that have been dug
-- in all the rows since `lastRow` -- each of these contained
-- `lastWidth` blocks. Don't add the number of blocks in *this*
-- row, we'll handle that below.
sum = sum + lastWidth * (y - lastRow)
end
-- replace any existing x positions in row with the new ones
for _,n in pairs(g.nodes[y]) do
row[n.x] = n
end
-- now go through the row left to right. We're going to shoot
-- "just north of center" (north_inside) and "just south of center"
-- (south_inside) and keep track of the total cubes filled in
-- "on this row" (row_sum) using "either north inside or south inside"
-- as the criterion, and also separately track the cubes that will
-- be filled in on the rows south of here (south_sum). Also track
-- in "nrow" how many vertical lines are leaving this row, so that
-- we can account for them in future rows.
local north_inside = false
local nrow = {}
local last_south_inside = nil
local last_row_inside = nil
local row_sum = 0
local south_sum = 0
for _,x in ipairs(sortedKeys(row)) do
local sp = row[x]
local was_row_inside = (last_south_inside ~= nil) or north_inside
if sp['in']=='D' or sp['out']=='U' then
-- only these nodes cross a ray sent "just north of center"
north_inside = not north_inside
end
if sp['in']=='U' or sp['out']=='D' then
-- only these nodes cross a ray sent "just south of center"
nrow[x] = {['in']="D",['out']="D",x=x,y=y} -- vertical will continue
if last_south_inside == nil then
last_south_inside = x
else
south_sum = south_sum + (1 + x - last_south_inside)
last_south_inside = nil
end
end
local is_row_inside = (last_south_inside ~= nil) or north_inside
if is_row_inside and not was_row_inside then
last_row_inside = x
elseif was_row_inside and not is_row_inside then
row_sum = row_sum + (1 + x - last_row_inside)
end
end
row = nrow
lastRow = y + 1
lastWidth = south_sum
-- add to the overall sum the number of blocks dug *on this row*
sum = sum + row_sum
end
return sum
end
--[[ CLI ] ]--
local source = io.input("day18.input"):read("*a")
print('Contains:', part1(source))
print('Ultra Contains:', 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('day18')
end)()
