Module:User:Cscott/Advent Of Code 2023/Day 14 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 Spot = Spot.__index = Spotfunction Spot:new(args) return setmetatable(args, self)endfunction Spot:isEmpty return not(self.round or self.cube)endfunction Spot:__tostring if self.round then return "O" end if self.cube then return "#" end return "."end

local nl = l.P"\n"

function make_spot(s) if s

"#" then return Spot:new end if s

"O" then return Spot:new end return Spot: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: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 --print(string.format("%d,%d %s %s %s %s", sp.r,sp.c,sp.n,sp.e,sp.s,sp.w)) end endend

function Graph:numberRocks local rocks = local num = 1 for r=1,self:rowN do for c=1,self:colN do local sp = self:at(r,c) if sp.round then sp.id = num num = num + 1 table.insert(rocks, sp) end end end return rocksend

-- the cube rocks partition each row or column, and after each-- roll all the rocks are going to pile up at each. so we just-- need to know for a given rock its (wlog) col, compare that to-- the closest cube in the row, and move it adjacent to the cube.-- if each cube keeps track of how many rocks have moved beside it,-- we can space them out appropriately. This makes rocks move-- through each other! ie doesn't actually respect the rock identity,-- but the results are correct.

-- HOWEVER, this way also works, and is "fast enough"function Graph:roll(rocks, dir, keyFunc) local Q = PriorityQueue for _,sp in ipairs(rocks) do Q:put(sp, keyFunc(sp)) end -- now start rolling ! while not Q:empty do local sp = Q:pop local neigh = sp[dir] if neigh ~= nil and neigh:isEmpty then -- can we roll here? local id = sp.id sp.round = false sp.id = nil neigh.round = true neigh.id = id rocks[id] = neigh Q:put(neigh, keyFunc(neigh)) end endend

function Graph:debug_cycle(rocks) print("Roll north:") self:roll(rocks, "n", function(sp) return sp.r end) self:print print

print("Roll west:") self:roll(rocks, "w", function(sp) return sp.c end) self:print print

print("Roll south:") self:roll(rocks, "s", function(sp) return -sp.r end) self:print print

print("Roll east:") self:roll(rocks, "e", function(sp) return -sp.c end)end

function Graph:cycle_one(rocks) self:roll(rocks, "n", function(sp) return sp.r end) self:roll(rocks, "w", function(sp) return sp.c end) self:roll(rocks, "s", function(sp) return -sp.r end) self:roll(rocks, "e", function(sp) return -sp.c end)end

function Graph:cycle(rocks, n) local seen = local i=1 while i <= n do local h = self:hash if seen[h]

nil then seen[h] = i self:cycle_one(rocks) i = i + 1 else -- short cut! local s = seen[h] -- after s steps we're at a cycle point -- we'll be back here/there in (i-s) more steps -- so skip ahead as many (i-s) steps as we can local cycles = math.floor((n - i) / (i - s)) -- print(i,s,cycles) i = i + cycles*(i-s) while i<=n do self:cycle_one(rocks) i = i + 1 end return end endend

function Graph:hash local t = for r=1,self:rowN do for c=1,self:colN do local sp = self:at(r,c) if sp.cube then -- skip, cubes never move else table.insert(t, tostring(sp)) end end end return table.concat(t)end

function Graph:score local sum = 0 for r=1,self:rowN do local row_score = 1 + self:rowN - r for c=1,self:colN do local sp = self:at(r,c) if sp.round then sum = sum + row_score end end end return sumend

function part1(source) local graph = parse(source) graph:link --graph:print --print local rocks = graph:numberRocks graph:roll(rocks, "n", function(sp) return sp.r end) --graph:print return graph:scoreend

function part2(source) local graph = parse(source) graph:link --graph:print --print local rocks = graph:numberRocks graph:cycle(rocks, 1000000000) --graph:print return graph:scoreend

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