return (functionlocal builders = local function register(name, f) builders[name] = fendregister('llpeg', function return require 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('advent.compat', function return require end)
register('eq', function(myrequire)-- "fix" lua's eq metamethod to be consistent with __add etc, that is:-- try the metamethod if any operand is not a numberlocal function eq(a, b) local tya, tyb = type(a), type(b) if tya ~= 'number' or tyb ~= 'number' then local op = nil local mt = getmetatable(a) if mt ~= nil then op = mt.__eq end if op
bend
return eq
end)
register('lt', function(myrequire)-- "fix" lua's lt metamethod to be consistent with __add etc, that is:-- try the metamethod if any operand is not a numberlocal function lt(a, b) local tya, tyb = type(a), type(b) if tya ~= 'number' or tyb ~= 'number' then local op = nil local mt = getmetatable(a) if mt ~= nil then op = mt.__lt end if op
return lt
end)
register('bignum', function(myrequire)local compat = myrequire('advent.compat')local eq = myrequire('eq')local lt = myrequire('lt')
-- poor man's bignum librarylocal RADIX = 1000 -- power of 10 to make printout easier
local function maxdigits(a, b) if #a > #b then return #a end return #bend
local function ltz(a) if type(a)
local BigNum = BigNum.__index = BigNumfunction BigNum:new(n) if n
'number') if n < 0 then return setmetatable(self):normalize else return setmetatable(self):normalize endendfunction BigNum:__tostring local result = if self.negative then table.insert(result, "-") end local first = true for i=#self,1,-1 do local n = self[i] if n ~= 0 or not first then local s = tostring(n) if first then first = false else while #s < 3 do s = '0' .. s end end table.insert(result, s) end end if #result
'number' then a,b = b,a end assert(not a.negative) local r = a:copy if type(b)
'number' then a = BigNum:new(a) end if type(b)
'number' then a = BigNum:new(a) end if type(b)
'number' then a = BigNum:new(a) end if type(b)
0) return r:normalize -- shouldn't actually be necessary?end
function BigNum.__mul(a, b) if type(a)
'number' then if b < 0 then r.negative = true ; b = -b ; end assert(b>=0) for i=1,#a do r[i] = a[i] * b end if a.negative then r.negative = not r.negative end return r:normalize end for i=1,#a do for j=1,#b do assert(a[i] >= 0) assert(b[j] >= 0) local prod = a[i] * b[j] r[i+j-1] = (r[i+j-1] or 0) + prod end end r.negative = a.negative if b.negative then r.negative = not r.negative end return r:normalizeend
function toBinary(a) assert(not a.negative) local bits = local RADIX_DIV_2 = compat.idiv(RADIX, 2) while a[1] ~= nil do table.insert(bits, a[1] % 2) for i=1,#a do a[i] = compat.idiv(a[i], 2) + ((a[i+1] or 0) % 2) * RADIX_DIV_2 end if a[#a]
local function divmod(a, b) if eq(b, 0) then error("division by zero") end if ltz(b) then if ltz(a) then return divmod(-a, -b) end local q,r = divmod(a, -b) if lt(0, r) then q = q + 1 end return -q, -r elseif ltz(a) then local q,r = divmod(-a, b) if lt(0, r) then q = q + 1 end return -q, r end -- ok, a and b are both positive now assert(not ltz(a)) assert(not ltz(b)) if type(a)
'number' then b = BigNum:new(b) end local N,D = a,b local Q,R = BigNum:new(0), BigNum:new(0) local Nbits = toBinary(N:copy) for i=#Nbits,1,-1 do --print("R=",R,"Q=",Q) for i=1,#R do R[i] = R[i] * 2 end if Nbits[i] > 0 then R[1] = R[1] + 1 end R:normalize for i=1,#Q do Q[i] = Q[i] * 2 end if R >= D then R = R - D Q[1] = Q[1] + 1 end Q:normalize end return Q,Rend
function BigNum.__idiv(a, b) local q,r = divmod(a, b) return qend
function BigNum.__mod(a, b) local q,r = divmod(a, b) return rend
----
return BigNum
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('day21', function(myrequire)--DAY 21 --local l = myrequire('llpeg')local PriorityQueue = myrequire('pqueue')local BigNum = myrequire('bignum')local read_wiki_input = myrequire('util').read_wiki_inputlocal compat = myrequire('advent.compat')
local TRACK_PATH = false
--PARSING --local Block = Block.__index = Blocklocal Rock = setmetatable(Block)Rock.__index = Rocklocal Plot = setmetatable(Block)Plot.__index = Plotlocal Start = setmetatable(Plot)Start.__index = Start
function Rock:__tostring return "#" endfunction Plot:__tostring if self.reached then return "O" end if self.start then return "S" end return "."endStart.__tostring = Plot.__tostring -- metamethods don't inherit (oddly)
local nl = l.P"\n"
local function make_block(type) if type
'.' then return setmetatable(Plot) end if type
local patt = l.P
local Graph = Graph.__index = Graph
local function parse(source, addWarp) 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 Graph:new(ast):link(addWarp)end
--Part 1 --function Graph:new(data) return setmetatable(self)end
function Graph:at(row,col,default) return ((self.data or)[row] or)[col] or defaultend
function Graph:foreach(func) -- r,c,val actually for r,row in pairs(self.data or) do for c,val in pairs(row) do func(r,c,val) end endend
local function compare_rc(a, b) if a.r < b.r then return true end if a.r > b.r then return false end if a.c < b.c then return true end if a.c > b.c then return false end -- elements are equal return falseend
function Graph:hash(func) local accum = local coords = self:foreach(function(r,c,val) table.insert(coords,) end) table.sort(coords, compare_rc) for _,v in ipairs(coords) do table.insert(accum, string.format("%d,%d,%s;", v.r,v.c, v.val)) end return table.concat(accum)end
function Graph:set(row,col,val) if self.data
nil then self.data[row] = end self.data[row][col] = valend
function Graph:setDefault(row,col,valfunc) local val = self:at(row, col) if val ~= nil then return val end if type(valfunc)
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
function Graph:link(addWarp) 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) elseif addWarp then sp.n = end if c > 1 then sp.w = self:at(r,c-1) elseif addWarp then sp.w = end if r < self:rowN then sp.s = self:at(r+1,c) elseif addWarp then sp.s = end if c < self:colN then sp.e = self:at(r,c+1) elseif addWarp then sp.e = end if sp.start
local directions =
function Graph:search1(start, steps) local Q = PriorityQueue local sp = self:at(start.r, start.c) local reachCount = 0 local parity = steps % 2 sp.reached = true Q:put(0) while not Q:empty do local state = Q:pop if state.steps % 2
local function part1(source, amt) local graph = parse(source) --graph:print --print local n = graph:search1(graph.start, amt or 64) --graph:print return nend
--PART 2 --
local function sortedKeys(tbl) local sorted = for k,_ in pairs(tbl) do table.insert(sorted, k) end table.sort(sorted) return sortedend
function Graph:search2(start, steps) local sp = self:at(start.r, start.c) local parity = steps % 2
local metagraph = Graph:new local function metagraphAt(mr, mc) return metagraph:setDefault(mr, mc, function return end) end local function setReached(meta, sp) meta.g:set(sp.r, sp.c, true) end local function reached(meta, sp) return meta.g:at(sp.r, sp.c) ~= nil end local function hash(frontier) local accum = local coords = for _,v in ipairs(frontier) do -- ignore meta, ignore steps table.insert(coords,) end table.sort(coords, compare_rc) for _,v in ipairs(coords) do table.insert(accum, string.format("%d,%d;", v.r, v.c)) end return table.concat(accum) end
local memo = local id = 1 local firstLoop = nil local function doOne(currentFrontier, metaNext, seen) local key = hash(currentFrontier) if memo[key] ~= nil then --print("seen", currentFrontier[1].meta.r, currentFrontier[1].meta.c) if firstLoop
parity then reachCount = reachCount + 1 end if state.steps < steps then local nextSteps = state.steps + 1 for _,d in ipairs(directions) do local nextmeta = state.meta local next = state.sp[d] if next ~= nil and next.warp ~= nil then local mr, mc = nextmeta.r + next.r, nextmeta.c + next.c nextmeta = metagraphAt(mr, mc) next = next.warp end if next ~= nil and not next.rock and not reached(nextmeta, next) then setReached(nextmeta, next) -- collect the 'nextFrontier' by metablock local nextFrontier = metaNext:setDefault(nextmeta.r, nextmeta.c,) table.insert(nextFrontier,) end end end end if memo[key].reachCount
local reachCount = 0 local currentFrontier = Graph:new currentFrontier:set(0,0,) setReached(metagraphAt(0,0), sp) --local last = local bigSum = repeat local count=0 local metaNext = Graph:new local seen = local steps = nil currentFrontier:foreach(function(mr,mc,frontier) reachCount = reachCount + doOne(frontier, metaNext, seen) count = count + 1 steps = frontier[1].steps end) currentFrontier = metaNext -- print status if false then local buf = for _,v in ipairs(sortedKeys(seen)) do table.insert(buf, string.format("%d=%d ", v, seen[v])) end --print("Steps", steps, reachCount, table.concat(buf)) end if false then if (steps % (2*131))
nil then bigSum[era] = end for i,v in pairs(seen) do bigSum[era][i] = (bigSum[era][i] or 0) + v end if (steps % 131)
0 return reachCountend
----local function part2(source, amt) local graph = parse(source, true) -- with warps local N1 = graph:search2(graph.start, 1*2*131+65) local N2 = graph:search2(graph.start, 2*2*131+65) local N3 = graph:search2(graph.start, 3*2*131+65) local N2mN1 = N2 - N1 -- 212122 local N3mN2 = N3 - N2 -- 333202 local a = compat.idiv(N3mN2 - N2mN1, 2) local b = N2mN1 - 3*a local c = N1 - a - b --print(N1, N2, N3, a, b, c) local N = compat.idiv(BigNum:new(amt) - 65, 2*131) return N*N*a + N*b + cend
--CLI ]--local source = io.input("day21.input"):read("*a")print('Plots:', part1(source, 6))
-- print('Infinite Plots:', part2(source, 6)) -- 44-- print('Infinite Plots:', part2(source, 10)) -- 110-- print('Infinite Plots:', part2(source, 50)) -- 2268-- print('Infinite Plots:', part2(source, 100)) -- 8993-- print('Infinite Plots:', part2(source, 500)) -- 221398-- print('Infinite Plots:', part2(source, 1000)) -- 884098-- print('Infinite Plots:', part2(source, 5000)) -- 22056540-- print('Infinite Plots:', part2(source, 64)) -- 3751-- print('Infinite Plots:', part2(source, 64+131)) --33904-- print('Infinite Plots:', part2(source, 64+2*131)) -- 94327-- print('Infinite Plots:', part2(source, 64+5*131)) -- 457216-- print('Infinite Plots:', part2(source, 64+10*131)) -- 1667431-- print('Infinite Plots:', part2(source, 64+20*131)) -- 6358111-- print('Infinite Plots:', part2(source, 64+30*131)) -- 14075791
print('Infinite Plots:', part2(source, 26501365)) -- 3751--[[ 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]