Module:User:Cscott/Advent Of Code 2023/Day 21

return (function()

local builders = {}

local function register(name, f)

builders[name] = f

end

--[[ Priority Queue implemented in lua, based on a binary heap.

License: zlib

This software is provided 'as-is', without any express or implied

warranty. In no event will the authors be held liable for any damages

arising from the use of this software.

Permission is granted to anyone to use this software for any purpose,

including commercial applications, and to alter it and redistribute it

freely, subject to the following restrictions:

1. The origin of this software must not be misrepresented; you must not

claim that you wrote the original software. If you use this software

in a product, an acknowledgement in the product documentation would be

appreciated but is not required.

2. Altered source versions must be plainly marked as such, and must not be

misrepresented as being the original software.

3. This notice may not be removed or altered from any source distribution.

]]--

-- modified by xxopxe@gmail.com

local floor = math.floor

local PriorityQueue = {}

PriorityQueue.__index = PriorityQueue

setmetatable(

PriorityQueue,

{

__call = function ()

local new = {}

setmetatable(new, PriorityQueue)

new:initialize()

return new

end

}

)

function PriorityQueue:initialize()

--[[ Initialization.

Example:

PriorityQueue = require "priority_queue"

pq = PriorityQueue()

]]--

self.heap_val = {}

self.heap_pri = {}

self.current_size = 0

end

function PriorityQueue:empty()

return self.current_size == 0

end

function PriorityQueue:size()

return self.current_size

end

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

end

function PriorityQueue:put(v, p)

--[[ Put an item on the queue.

Args:

v: the item to be stored

p(number): the priority of the item

]]--

self.current_size = self.current_size + 1

self.heap_val[self.current_size] = v

self.heap_pri[self.current_size] = p

self:swim()

end

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

end

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

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, retprio

end

function PriorityQueue:peek()

-- return the top priority item

return self.heap_val[1], self.heap_pri[1]

end

return PriorityQueue

end)

-- "fix" lua's eq metamethod to be consistent with __add etc, that is:

-- try the metamethod if any operand is not a number

local 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 == nil then

mt = getmetatable(b)

if mt ~= nil then op = mt.__eq end

end

if op ~= nil then

return op(a, b)

end

return a == b

end

return eq

end)

-- "fix" lua's lt metamethod to be consistent with __add etc, that is:

-- try the metamethod if any operand is not a number

local 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 == nil then

mt = getmetatable(b)

if mt ~= nil then op = mt.__lt end

end

if op ~= nil then

return op(a, b)

end

return a < b

end

return lt

end)

local compat = myrequire('advent.compat')

local eq = myrequire('eq')

local lt = myrequire('lt')

-- poor man's bignum library

local RADIX = 1000 -- power of 10 to make printout easier

local function maxdigits(a, b)

if #a > #b then return #a end

return #b

end

local function ltz(a)

if type(a) == 'number' then

return a < 0

end

return a.negative or false

end

local BigNum = {}

BigNum.__index = BigNum

function BigNum:new(n)

if n == nil then n = 0 end

assert(type(n)=='number')

if n < 0 then

return setmetatable( {-n, negative=true}, self):normalize()

else

return setmetatable( {n}, self):normalize()

end

function 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

if #result == 0 then return "0" end

return table.concat(result)

end

function BigNum:toNumber()

local m = 1

local sum = 0

for i=1,#self do

sum = sum + (self[i] * m)

m = m * RADIX

end

return sum

end

function BigNum:normalize()

local i = 1

local sawNonZero = false

while self[i] ~= nil do

assert(self[i] >= 0)

if self[i] > 0 then

sawNonZero = true

end

if self[i] >= 1000 then

local carry = math.floor(self[i] / 1000)

self[i] = self[i] % 1000

self[i+1] = (self[i+1] or 0) + carry

end

i = i + 1

end

if not sawNonZero then

self.negative = nil -- -0 is 0

end

return self

end

function BigNum:copy()

local r = BigNum:new()

for i=1,#self do

r[i] = self[i]

end

r.negative = self.negative

return r

end

function BigNum.__unm(a)

if eq(a, 0) then return a end -- -0 is 0

local r = a:copy()

r.negative = not r.negative

return r

end

function BigNum.__add(a, b)

if ltz(b) then

if ltz(a) then

return -((-a) + (-b))

end

return a - (-b)

end

if ltz(a) then

return b - (-a)

end

assert(not ltz(a))

assert(not ltz(b))

if type(a) == 'number' then

a,b = b,a

end

assert(not a.negative)

local r = a:copy()

if type(b) == 'number' then

assert(b >= 0)

r[1] = (r[1] or 0) + b

else

assert(not b.negative)

for i=1,#b do

r[i] = (r[i] or 0) + b[i]

end

return r:normalize()

end

function BigNum.__lt(a, b)

if ltz(a) then

if ltz(b) then

return (-a) > (-b)

end

return true

elseif ltz(b) then

return false

end

if type(a) == 'number' then a = BigNum:new(a) end

if type(b) == 'number' then b = BigNum:new(b) end

for i=maxdigits(a,b),1,-1 do

if (a[i] or 0) < (b[i] or 0) then return true end

if (a[i] or 0) > (b[i] or 0) then return false end

end

return false -- they are equal

end

function BigNum.__le(a, b)

return not (a > b)

end

function BigNum.__eq(a, b)

if ltz(a) ~= ltz(b) then return false end

if type(a) == 'number' then a = BigNum:new(a) end

if type(b) == 'number' then b = BigNum:new(b) end

for i=1,maxdigits(a,b) do

if (a[i] or 0) ~= (b[i] or 0) then return false end

end

return true

end

function BigNum.__sub(a, b)

if ltz(b) then

return a + (-b)

end

if ltz(a) then

return -((-a) + b)

end

if type(a) == 'number' then a = BigNum:new(a) end

if type(b) == 'number' then b = BigNum:new(b) end

if b > a then

return -(b - a)

end

local r = a:copy()

local borrow = 0

for i=1,maxdigits(a,b) do

r[i] = (r[i] or 0) - (b[i] or 0) - borrow

borrow = 0

while r[i] < 0 do

r[i] = r[i] + RADIX

borrow = borrow + 1

end

assert(r[i] >= 0)

end

assert(borrow == 0)

return r:normalize() -- shouldn't actually be necessary?

end

function BigNum.__mul(a, b)

if type(a) == 'number' then

a,b = b,a

end

local r = BigNum:new()

if type(b) == '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

r.negative = a.negative

if b.negative then r.negative = not r.negative end

return r:normalize()

end

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] == 0 then a[#a] = nil end

end

return bits

end

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 a = BigNum:new(a) end

if type(b) == '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,R

end

function BigNum.__idiv(a, b)

local q,r = divmod(a, b)

return q

end

function BigNum.__mod(a, b)

local q,r = divmod(a, b)

return r

end

--[[

print(BigNum:new(4) >= BigNum:new(2))

print(BigNum:new(4) > BigNum:new(2))

print(BigNum:new(2) >= BigNum:new(2))

print(BigNum:new(2) > BigNum:new(2))

print(BigNum:new(4653) // BigNum:new(210))

]]--

return BigNum

end)

local function read_wiki_input(func)

return function (frame, ...)

if type(frame)=='string' then

frame = { args = { frame, ... } }

end

local title = mw.title.new(frame.args[1])

local source = title:getContent()

if source == nil then

error("Can't find title " .. tostring(title))

end

source = source:gsub("^%s*]*>\n?", "", 1)

source = source:gsub("]*>%s*$", "", 1)

return func(source, frame.args[2], frame.args[3])

end

return {

read_wiki_input = read_wiki_input,

}

end)

-- DAY 21 --

local l = myrequire('llpeg')

local PriorityQueue = myrequire('pqueue')

local BigNum = myrequire('bignum')

local read_wiki_input = myrequire('util').read_wiki_input

local compat = myrequire('advent.compat')

local TRACK_PATH = false

-- PARSING --

local Block = {}

Block.__index = Block

local Rock = setmetatable({rock=true,type="#"}, Block)

Rock.__index = Rock

local Plot = setmetatable({plot=true,type="."}, Block)

Plot.__index = Plot

local Start = setmetatable({start=true,type="S"}, Plot)

Start.__index = Start

function Rock:__tostring() return "#" end

function Plot:__tostring()

if self.reached then return "O" end

if self.start then return "S" end

return "."

end

Start.__tostring = Plot.__tostring -- metamethods don't inherit (oddly)

local nl = l.P"\n"

local function make_block(type)

if type=='#' then return setmetatable({}, Rock) end

if type=='.' then return setmetatable({}, Plot) end

if type=='S' then return setmetatable({}, Start) end

error("unknown block type: "..type)

end

local patt = l.P{

"Graph",

Graph = l.Ct( l.V"Row" * (nl^1 * l.V"Row")^0 * nl^0) * -1,

Row = l.Ct( l.V"Block"^1 ),

Block = l.S".#S" / make_block,

}

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({ data=data }, self)

end

function Graph:at(row,col,default)

return ((self.data or {})[row] or {})[col] or default

end

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

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 false

end

function Graph:hash(func)

local accum = {}

local coords = {}

self:foreach(function(r,c,val)

table.insert(coords, {r=r,c=c,val=func(val)})

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 = {}

end

if self.data[row] == nil then

self.data[row] = {}

end

self.data[row][col] = val

end

function Graph:setDefault(row,col,valfunc)

local val = self:at(row, col)

if val ~= nil then return val end

if type(valfunc) == 'function' then

val = valfunc()

else

val = valfunc

end

self:set(row, col, val)

return val

end

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

end

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 = { warp=self:at(self:rowN(), c), r=-1, c=0 }

end

if c > 1 then

sp.w = self:at(r,c-1)

elseif addWarp then

sp.w = { warp=self:at(r, self:colN()), r=0, c=-1 }

end

if r < self:rowN() then

sp.s = self:at(r+1,c)

elseif addWarp then

sp.s = { warp=self:at(1,c), r=1, c=0 }

end

if c < self:colN() then

sp.e = self:at(r,c+1)

elseif addWarp then

sp.e = { warp=self:at(r,1), r=0, c=1 }

end

if sp.start == true then self.start = {r=r, c=c} end

end

return self

end

local directions = { "n", "e", "s", "w" }

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({sp=sp,steps=0}, 0)

while not Q:empty() do

local state = Q:pop()

if state.steps % 2 == parity then reachCount = reachCount + 1 end

if state.steps < steps then

local nextSteps = state.steps + 1

for _,d in ipairs(directions) do

local next = state.sp[d]

if next ~= nil and not next.rock and not next.reached then

next.reached = true

Q:put({sp=next,steps=nextSteps}, nextSteps)

end

return reachCount

end

local function part1(source, amt)

local graph = parse(source)

--graph:print()

--print()

local n = graph:search1(graph.start, amt or 64)

--graph:print()

return n

end

-- PART 2 --

local function sortedKeys(tbl)

local sorted = {}

for k,_ in pairs(tbl) do

table.insert(sorted, k)

end

table.sort(sorted)

return sorted

end

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 { r=mr, c=mc, g=Graph:new() }

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, {r=v.sp.r,c=v.sp.c})

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 == nil then

firstLoop = currentFrontier[1].steps

--print("First loop", firstLoop)

end

else

memo[key] = { id=id }

id = id + 1

end

local reachCount = 0

local nextFrontier = {}

for i=1,#currentFrontier do

local state = currentFrontier[i]

if state.steps % 2 == 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, {meta=nextmeta,sp=next,steps=nextSteps})

end

if memo[key].reachCount == nil then

memo[key].reachCount = reachCount

else

memo[key].bad = true

end

seen[memo[key].id] = (seen[memo[key].id] or 0) + 1

return reachCount

end

local reachCount = 0

local currentFrontier = Graph:new()

currentFrontier:set(0,0,{ {meta=metagraphAt(0,0),sp=sp,steps=0} })

setReached(metagraphAt(0,0), sp)

--local last = {0,0,0,0,0,0}

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)) == 65 then

print("Steps", steps, reachCount)

end

local era = compat.idiv(steps, 131)

if bigSum[era] == 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) == 130 and false then

local buf = {}

for _,v in ipairs(sortedKeys(bigSum[era])) do

table.insert(buf, string.format("%d=%d ", v, bigSum[era][v]))

end

--print(table.concat(buf))

end

until count == 0

return reachCount

end

--[[

We have a cycle of length 131: (first repeated occurrence of a block is at step 197)

Steps 131 392=1 393=1 394=1 395=1

Steps 262 392=1 393=1 394=1 395=1 1436=1 1437=1 1438=1 1439=1

Steps 393 392=1 393=1 394=1 395=1 1436=2 1437=2 1438=2 1439=2

Steps 524 392=1 393=1 394=1 395=1 1436=3 1437=3 1438=3 1439=3

And also at points in the middle of the cycle:

Steps 300 692=2 693=1 694=2 695=1 696=1 697=2 698=1 699=2 1588=1 1589=1 1590=1 1591=1

Steps 431 692=3 693=1 694=3 695=1 696=1 697=3 698=1 699=3 1588=2 1589=2 1590=2 1591=2

Steps 562 692=4 693=1 694=4 695=1 696=1 697=4 698=1 699=4 1588=3 1589=3 1590=3 1591=3

Look at the total reach count at correspondings points in the

cycle. NOTE THAT THE PARITY FLIPS EACH TIME because 131 is odd, so

we should only compare "odd" cycles with "odd" cycles. Be careful

you give the desired ending length when you run the program, or

you'll get sums for the wrong parity!

We want 26501365 steps, which is 101150 * 2*131 + 65!

Luckily, our trick still works!

Steps 327 94909 212122 121080

Steps 589 307031 333202 121080

Steps 851 640233 454282

Steps 1113 1094515

Steps 1375 1669877

Step N*2*131+65 = a*N^2 + b*N + c; solve

N=1 => 94909 = a + b + c 3a + b = 212122 2a=121080 a=60540

N=2 => 307031 = 4a + 2b + c 5a + b = 333202 b=30502

N=3 => 640233 = 9a + 3b + c c=3867

After N*2*131+65 steps, reaches: 60540 * N^2 + 30502 * N + 3867

Solve for N=23, 6091 steps: 32731073

Solve for N=101150 => 619407349431167

]]--

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 + c

end

--[[ 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 {

part1 = read_wiki_input(part1),

part2 = read_wiki_input(part2),

}

end)

local modules = {}

modules['bit32'] = require('bit32')

modules['string'] = require('string')

modules['strict'] = {}

modules['table'] = require('table')

local function myrequire(name)

if modules[name] == nil then

modules[name] = true

modules[name] = (builders[name])(myrequire)

end

return modules[name]

end

return myrequire('day21')

end)()