Module:User:Cscott/Advent Of Code 2023/Day 11 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)

--PARSING --local Parsec = Parsec.__index = Parsecfunction Parsec:new(args) return setmetatable(args, self)endfunction Parsec:__tostring if self.galaxy then if self.id

nil then return "#" end if self.id < 10 then return tostring(self.id) end if self.id < 36 then return string.char(65 + self.id - 10) end return "#" -- ran out of labels end return "."end

local nl = l.P"\n"

function make_parsec(s) if s

"#" then return Parsec:new end return Parsec:newend

local patt = l.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(self)end

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

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

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

function Graph:number local galaxies = local num = 1 for r,row in ipairs(self.data) do for c,sp in ipairs(row) do if sp.galaxy then sp.id = num num = num + 1 table.insert(galaxies, sp) end end end return galaxiesend

function Graph:expand(amt) if amt

nil then amt = 2 end -- first rows for r=1,self:rowN do local saw_galaxy = false for c=1,self:colN do if self:at(r, c).galaxy then saw_galaxy = true break end end if not saw_galaxy then -- if we didn't see a galaxy, expand space for c = 1,self:colN do self.data[r][c].ylen = amt end end end -- now columns for c=1,self:colN do local saw_galaxy = false for r=1,self:rowN do if self:at(r, c).galaxy then saw_galaxy = true break end end if not saw_galaxy then -- if we didn't see a galaxy, expand space for r=1,self:rowN do self.data[r][c].xlen = amt end end endend

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

function Graph:number_nodes -- number all nodes local V = for r=1,self:rowN do for c=1,self:colN do local sp = self:at(r,c) table.insert(V, sp) sp.v = #V end end return Vend

-- Dijkstra algorithmfunction Graph:shortest_path_from_node(V, galaxies, galaxy_num) local dist = local prev = local Q = PriorityQueue local seen = dist[galaxies[galaxy_num].v] = 0 Q:put(galaxies[galaxy_num], 0) while not Q:empty do local u = Q:pop seen[u.v] = true local neighbor = function(neigh, weight) if neigh

nil then return end if seen[neigh.v] then return end local alt = dist[u.v] + weight if dist[neigh.v]

nil or alt < dist[neigh.v] then dist[neigh.v] = alt prev[neigh.v] = u Q:put(neigh, dist[neigh.v]) end end neighbor(u.n, u.ylen) neighbor(u.s, u.ylen) neighbor(u.e, u.xlen) neighbor(u.w, u.xlen) end local sum = 0 for g=1,#galaxies do local gdist = dist[galaxies[g].v] -- print(string.format("Between galaxy %d and galaxy %d: %d", galaxy_num, g,gdist)) sum = sum + gdist end return sumend

-- Floyd-Warshall algorithmfunction Graph:all_pairs_shortest_path(V, galaxies) -- let dist be a |V| x |V| array of minimum distances initialzed to -- infinity (which we'll represent as 'nil') local dist = for i=1,#V do table.insert(dist,) end -- initialize with edge weights for r=1,self:rowN do for c=1,self:colN do local sp = self:at(r,c) -- dist[v][v] = 0 dist[sp.v][sp.v] = 0 if sp.n ~= nil then dist[sp.v][sp.n.v] = sp.ylen end if sp.s ~= nil then dist[sp.v][sp.s.v] = sp.ylen end if sp.e ~= nil then dist[sp.v][sp.e.v] = sp.xlen end if sp.w ~= nil then dist[sp.v][sp.w.v] = sp.xlen end end end -- ok, the big O(N^3) step for k=1,#V do for i = 1,#V do for j = 1,#V do -- if distances are nil they are infinity if dist[i][k] ~= nil and dist[k][j] ~= nil then if dist[i][j]

nil or dist[i][j] > (dist[i][k] + dist[k][j]) then dist[i][j] = dist[i][k] + dist[k][j] end end end end end -- ok, all pairs shortest paths! local sum = 0 for i=1,#galaxies do for j=i+1,#galaxies do local iv = galaxies[i].v local jv = galaxies[j].v local dist = dist[iv][jv] sum = sum + dist -- print(string.format("Between galaxy %d and galaxy %d: %d", i, j, dist)) end end return sumend

function part12(source, amt) local graph = parse(source) --graph:print graph:expand(amt) local galaxies = graph:number graph:link -- graph:print -- print(graph:rowN,'x',graph:colN) local V = graph:number_nodes --return graph:all_pairs_shortest_path(V, galaxies) local sum = 0 for g=1,#galaxies do sum = sum + graph:shortest_path_from_node(V, galaxies, g) end -- we double counted each pair, so: return math.floor(sum/2)end

function part1(source) return part12(source, 2) endfunction part2(source, amt) return part12(source, amt) end

----

return

end)

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