return (functionlocal builders = local function register(name, f) builders[name] = fendregister('llpeg', function return require end)
register('util', function(myrequire)local function read_wiki_input(func) return function (frame, ...) if type(frame)
nil then error("Can't find title " .. tostring(title)) end source = source:gsub("^%s*
return
end)
register('pqueue', function(myrequire)------ modified by xxopxe@gmail.com
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
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)
register('day25', function(myrequire)--DAY 25 --local l = myrequire('llpeg')local read_wiki_input = myrequire('util').read_wiki_inputlocal PriorityQueue = myrequire('pqueue')
--PARSING --local nl = l.P"\n"local SKIP = l.S" \t"^0
local patt = l.P
local Node = Node.__index = Nodefunction Node:new(p) return setmetatable(p or, self)endfunction Node:addEdge(n) for _,e in ipairs(self.edges) do if e
local function parse(source) local ast, errlabel, pos = patt:match(source) if not ast then error(string.format("Error at pos %s label '%s'", pos, errlabel)) end -- postprocess local graph = -- first create all nodes for _,n in ipairs(ast) do graph[n.name] = Node:new for _,n2 in ipairs(n.connections) do graph[n2] = Node:new end end -- now create all edges for _,n in ipairs(ast) do for _,n2 in ipairs(n.connections) do graph[n.name]:addEdge(graph[n2]) graph[n2]:addEdge(graph[n.name]) end end return graphend
local function sortedKeys(tbl) local sorted = for k,_ in pairs(tbl) do table.insert(sorted, k) end table.sort(sorted) return sortedend
local function shortestPath(from, to, checkEdge) local seen = local Q = PriorityQueue Q:put(0) while not Q:empty do local item = Q:pop if item.node
nil then seen[item.node] = true for _,next in ipairs(item.node.edges) do if seen[next]
nil or checkEdge(item.node, next) then Q:put(item.len+1) end end end end end return nil -- no path foundend
local function part1(source) --mw.log(source) local graph = parse(source) local nodes = sortedKeys(graph) -- pick a node arbitrarily local n = graph[nodes[1]] local clique1, clique2 =, -- try to make paths to every other node in the graph. either: -- 1) there are more than 3 possible paths => this node is in the same -- component as n -- 2) there are only 3 possible paths => this node is in the "other" -- component for i=2,#nodes do local n2 = graph[nodes[i]] local removedEdges = local function makeKey(a, b) return a.name .. '-' .. b.name end local noPathFound = false for i=1,4 do local path = shortestPath(n, n2, function(a, b) return removedEdges[makeKey(a,b)]
nil then noPathFound = true break end -- add this path to the list of removed edges while path.prev ~= nil do removedEdges[makeKey(path.node, path.prev.node)] = true removedEdges[makeKey(path.prev.node, path.node)] = true path = path.prev end end if noPathFound then table.insert(clique2, n2) else table.insert(clique1, n2) end end --print(#clique1, #clique2) return #clique1 * #clique2end
--CLI ]--local do_part1 = falselocal use_example = false
local filenameif use_example then filename = "day25.example"else filename = "day25.input"endlocal source = io.input(filename):read("*a")print(part1(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]