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

local TRACK_PATH = false

--PARSING --local Block = Block.__index = Blockfunction Block:new(args) return setmetatable(args, self)endfunction Block:__tostring return tostring(self.loss)end

local nl = l.P"\n"

local function make_block(s) return Block:newend

local patt = l.P

local Graph = Graph.__index = Graph

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)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:rowN return #(self.data)end

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

local dirmap =

function Graph:print local sum = 0 for r,row in ipairs(self.data) do for c,val in ipairs(row) do if val

nil then val = " " elseif val.mark then sum = sum + val.loss val = "#" end io.write(tostring(val)) end io.write("\n") end print(sum)end

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:search(entry, exit, min, max) local Q = PriorityQueue entry = self:at(entry.r, entry.c) exit = self:at(exit.r, exit.c) local state = local freelist = local dirs = local reverse = -- since we can't continue in same direction *or* reverse direction, -- then we can share "visited" set keys for n/s and e/w local keymap = Q:put(state, state.loss) local qmax = 0 while not Q:empty do state = Q:pop if Q:size > qmax then qmax = Q:size end if state.block

exit then local p = state.path while p ~= nil do p[1].mark = true p = p[2] end --self:print return state.loss end local visit_key = keymap[state.dir or "nil"] if not state.block[visit_key] then --print(string.format("Visiting col %d row %d from %s (step %d) with loss %d", state.block.c, state.block.r, state.dir, state.amt, state.loss)) state.block[visit_key] = true

for _,d in ipairs(dirs) do if d ~= state.dir and d ~= reverse[state.dir] then local neigh = state.block local nloss = state.loss local npath = state.path for i=1,max do neigh = neigh[d] if neigh

nil then break end nloss = nloss + neigh.loss if TRACK_PATH then npath = end if i >= min then local nstate if #freelist > 0 then nstate = table.remove(freelist) else nstate = end nstate.block = neigh nstate.dir = d nstate.loss = nloss nstate.path = npath Q:put(nstate, nstate.loss) end end end end end table.insert(freelist, state) end return nilend

local function part1(source) local graph = parse(source) graph:link return graph:search(1, 3)end

local function part2(source) local graph = parse(source) graph:link return graph:search(4, 10)end

--CLI ]--local source = io.input("day17.input"):read("*a")print('Loss:', part1(source))print('Ultra Loss:', 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]