Module:User:Cscott/Advent Of Code 2023/Day 18 Explained

return (functionlocal builders = local function register(name, f) builders[name] = fendregister('llpeg', function return require end)

--PARSING --

local nl = l.P"\n"local SKIP = l.S" \t"^0

local patt = 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 astend

--Part 1 --

local Ground = Ground.__index = Ground

function Ground:new local p = 1 local data = data[p] = data[p][p] = return setmetatable(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] = 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 endend

local xoff = local yoff =

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) endend

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] = sum = sum + 1 end end end return sumend

local shape =

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 sumend

--Part 2 --

local Node = Node.__index = Node

function Node:new(p) return setmetatable(p or, self)end

local NGround = NGround.__index = NGroundfunction NGround:new local p = 1 local n = Node:new return setmetatable(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 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 endend

local dir_decode =

local function decode(color) local dist = tonumber(color:sub(1,5), 16) local dir = dir_decode[color:sub(-1)] return dir, distend

local function sortedKeys(tbl) local sorted = for k,_ in pairs(tbl) do table.insert(sorted, k) end table.sort(sorted) return sortedend

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] = -- 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 sumend

--CLI ]--local source = io.input("day18.input"):read("*a")print('Contains:', part1(source))print('Ultra Contains:', part2(source))--[[ END CLI ]]--

return

end)

local modules = modules['table'] = require('table')modules['string'] = require('string')modules['strict'] = local function myrequire(name) if modules[name]