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

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

local floor = math.floor

local PriorityQueue = PriorityQueue.__index = PriorityQueue

setmetatable(PriorityQueue,)

function PriorityQueue:initialize ---- self.heap_val = self.heap_pri = self.current_size = 0end

function PriorityQueue:empty return self.current_size

0end

function PriorityQueue:size return self.current_sizeend

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 endend

function PriorityQueue:put(v, p) ---- -- self.current_size = self.current_size + 1 self.heap_val[self.current_size] = v self.heap_pri[self.current_size] = p self:swimend

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 endend

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 endend

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, retprioend

function PriorityQueue:peek -- return the top priority item return self.heap_val[1], self.heap_pri[1]end

return PriorityQueue

end)

'string' then 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*\n?", "", 1) source = source:gsub("%s*$", "", 1) return func(source, frame.args[2], frame.args[3]) endend

return

end)

register('day23', function(myrequire)--DAY 23 --local l = myrequire('llpeg')local PriorityQueue = myrequire('pqueue')local read_wiki_input = myrequire('util').read_wiki_input

--PARSING --local Block = Block.__index = Blockfunction Block:new(args) return setmetatable(args, self)endfunction Block:__tostring return string.format("r=%d,c=%d,ty=%s", self.r, self.c, self.type)end

local nl = l.P"\n"

local function make_block(s) return Block:newend

local directions = local dirmap =

local oppositemap =

local patt = l.P

local ManhattanGraph = ManhattanGraph.__index = ManhattanGraph

local function parse(source, isDry) 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 ManhattanGraph:new(ast):link(isDry)end

--Part 1 --function ManhattanGraph:new(data) return setmetatable(self)end

function ManhattanGraph:at(row,col,default) return (self.data[row] or)[col] or defaultend

function ManhattanGraph:rowN return #(self.data)end

function ManhattanGraph:colN return #(self.data[1])end

function ManhattanGraph:print(coords) for r,row in ipairs(self.data) do for c,val in ipairs(row) do if val

nil then val = " " elseif coords then if val.type

'#' then val = '##### ' else val = string.format("%2d,%2d ",r,c) end else val = val.type end io.write(tostring(val)) end io.write("\n") endend

function ManhattanGraph:link(isDry) local function maybe(sp, dir, r, c) if sp.type

'#' then return nil end if r < 1 or c < 1 then return nil end if r > self:rowN or c > self:colN then return nil end local spSlope = dirmap[sp.type] if isDry then spSlope = nil end if spSlope ~= nil and dir ~= spSlope then return nil end local next = self:at(r,c) if next.type

'#' then return nil end local nextSlope = dirmap[next.type] if isDry then nextSlope = nil end if nextSlope ~= nil and nextSlope

oppositemap[dir] then return nil end return next end for r=1,self:rowN do for c=1,self:colN do local sp = self:at(r,c) sp.r, sp.c = r,c sp.n = maybe(sp, 'n', r-1, c) sp.s = maybe(sp, 's', r+1, c) sp.e = maybe(sp, 'e', r, c+1) sp.w = maybe(sp, 'w', r, c-1) --local function print_one(d) print(string.format("%s dir %s connected to %s", sp, d, sp[d])) end for _,d in ipairs(directions) do if sp[d] ~= nil then print_one(d) end end -- end end return selfend

function ManhattanGraph:findEntryExit(row) -- Find the starting node for i=1,self:colN do if self:at(row, i).type

'.' then return self:at(row, i) end end error("couldn't find it")end

local Node = Node.__index = Nodefunction Node:new(old, key) return setmetatable(self)endfunction Node:__tostring local buf = ") return table.concat(buf)end

function ManhattanGraph:compress(isDry) -- Find the starting node and exit node local start =self:findEntryExit(1) local exit = self:findEntryExit(self:rowN) local POSTEXIT = setmetatable -- now walk the maze creating nodes only when there is >1 exit possible local nodeMap = local function makeNewNode(old, key) local newNode = Node:new(old, key) assert(nodeMap[old]

nil) nodeMap[old] = newNode return newNode end local function connect(from, to, cost) --print("Connecting", from, "to", to) table.insert(from.edges,) table.insert(to.incoming,) end

local newStart = makeNewNode(start, start) newStart.start = true local worklist = local i = 1 while i <= #worklist do local todo = worklist[i] ; i = i + 1 local validExits = --nodeMap[todo.old] = todo.new for _,d in ipairs(directions) do if todo.old[d] ~= nil and todo.last ~= oppositemap[d] then table.insert(validExits, d) end end --print("visiting new=", todo.new, "old=",todo.old, "exits",#validExits) if #validExits

0 then -- dead end. But maybe the exit? if todo.old

exit then local newExit = nodeMap[POSTEXIT] if newExit

nil then newExit = makeNewNode(POSTEXIT, exit) newExit.exit = true end connect(todo.new, newExit, todo.cost) end elseif #validExits

1 then -- put this back on the worklist with the same origin node local d = validExits[1] table.insert(worklist,) else -- ok, create a new node because there are multiple ways to go here. -- but key these off a single intersection to prevent shenanigans for _,d in ipairs(validExits) do local nextNode = nodeMap[todo.old[d]] if nextNode

nil then --print("making new node for",d,todo.old[d]) nextNode = makeNewNode(todo.old[d], todo.old) table.insert(worklist,) end connect(todo.new, nextNode, todo.cost + 1) -- link up edges! end end end return newStartend

function Node:topoSort local seen = local S = local L = local i = 1 while i <= #S do local n = S[i] ; i = i + 1 seen[n] = true table.insert(L, n) for _,e in ipairs(n.edges) do local m = e.to seen[m] = true m.topo = (m.topo or 0) + 1 if m.topo

#m.incoming then table.insert(S, m) end end end -- check for cycles for m,_ in pairs(seen) do if (m.topo or 0) < #m.incoming then error("at least one cycle: "..tostring(m)) end m.topo = nil end return L -- a topologically sorted orderend

local function part1(source) local mgraph = parse(source) --mgraph:print local start = mgraph:compress -- longest path: just do shortest path on -G graph, SO LONG AS THIS IS A DAG for _,n in ipairs(start:topoSort) do local max = 0 for _,m in ipairs(n.incoming) do if m.cost + m.from.cost > max then max = m.cost + m.from.cost end end n.cost = max --print(string.format("Longest path to %s is %d", n, max)) if n.exit ~= nil then return n.cost end endend

--PART 2 --

function longest_path(node, cost, seen, level) --print(tostring(node)) if node.exit then return cost end -- yay -- do this the hard way seen[node.key] = true local max = nil for _,e in ipairs(node.edges) do if not seen[e.to.key] then local thisWay = longest_path(e.to, cost + e.cost, seen, level + 1) if thisWay ~= nil and (max

nil or thisWay > max) then max = thisWay end end end if max ~= nil then --print(string.format("%sLongest path through %s is %d", string.rep(" ",level), node, max)) end seen[node.key] = nil -- clean up return maxend

local function part2(source) local mgraph = parse(source, true) --mgraph:print(true) local start = mgraph:compress(true) return longest_path(start, 0,, 0)end

--CLI ]--local source = io.input("day23.input"):read("*a")print('Longest path when wet:', part1(source))print('Longest path when dry:', part2(source))--[[ END CLI ]]--

return

end)

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