Module:User:Cscott/Advent Of Code 2023/Day 24 Explained

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)

'string' then 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]) endend

return

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

nil then mt = getmetatable(b) if mt ~= nil then op = mt.__eq end end if op ~= nil then return op(a, b) end end return a

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

nil then mt = getmetatable(b) if mt ~= nil then op = mt.__lt end end if op ~= nil then return op(a, b) end end return a < bend

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)

'number' then return a < 0 end return a.negative or falseend

local BigNum = BigNum.__index = BigNumfunction BigNum:new(n) if n

nil then n = 0 end assert(type(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

0 then return "0" end return table.concat(result)endfunction BigNum:toNumber local m = 1 local sum = 0 for i=1,#self do sum = sum + (self[i] * m) m = m * RADIX end return sumendfunction 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 selfendfunction BigNum:copy local r = BigNum:new for i=1,#self do r[i] = self[i] end r.negative = self.negative return rendfunction BigNum.__unm(a) if eq(a, 0) then return a end -- -0 is 0 local r = a:copy r.negative = not r.negative return rendfunction 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 end return r:normalizeendfunction 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 equalendfunction BigNum.__le(a, b) return not (a > b)endfunction 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 trueendfunction 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 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]

0 then a[#a] = nil end end return bitsend

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,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('gcd', function(myrequire)local eq = myrequire('eq')

local function gcd(a, b) if eq(b, 0) then return a end return gcd(b, a % b) -- tail callend

return gcd

end)

register('rational', function(myrequire)-- poor man's rational number librarylocal eq = myrequire('eq')local gcd = myrequire('gcd')local compat = myrequire('advent.compat')

local Rational = Rational.__index = Rationalfunction Rational:new(n, d, reduced) if d

nil then d = 1 end if d < 0 then n,d = -n,-d elseif d > 0 then -- no problem else error("divide by zero") end local r = nil if reduced then r = true end return setmetatable(self)endfunction Rational:reduce if self.reduced then return self end -- find gcd of numerator and denominator if eq(self.n, 0) then self.d = 1 elseif self.d > 1 then local div if self.n > 0 then div = gcd(self.n, self.d) else div = gcd(-self.n, self.d) end if div ~= 1 then self.n = compat.idiv(self.n, div) self.d = compat.idiv(self.d, div) end end self.reduced = true return selfend

local function ensureRational(r) if type(r)

'number' then return Rational:new(r, 1, true) end assert(getmetatable(r)

Rational) return r ----end

function Rational:isWholeNumber self:reduce return eq(self.d, 1)end

function Rational:toWholeNumber return compat.idiv(self.n, self.d)end

function Rational:__tostring self:reduce if self:isWholeNumber then return tostring(self.n) end return tostring(self.n) .. "/" .. tostring(self.d)endfunction Rational:__unm if eq(self.n, 0) then return self end return Rational:new(-self.n, self.d, self.reduced)endfunction Rational.__add(a, b) a,b = ensureRational(a), ensureRational(b) return Rational:new(a.n * b.d + b.n * a.d, a.d * b.d)endfunction Rational.__sub(a, b) a,b = ensureRational(a), ensureRational(b) return Rational:new(a.n * b.d - b.n * a.d, a.d * b.d)endfunction Rational.__mul(a, b) a,b = ensureRational(a), ensureRational(b) return Rational:new(a.n*b.n, a.d*b.d)endfunction Rational.__div(a, b) a,b = ensureRational(a), ensureRational(b) if type(a.n) ~= 'number' then a.n:normalize end if type(a.d) ~= 'number' then a.d:normalize end if type(b.n) ~= 'number' then b.n:normalize end if type(b.d) ~= 'number' then b.d:normalize end return Rational:new(a.n*b.d, a.d*b.n)endfunction Rational.__lt(a, b) a,b = ensureRational(a), ensureRational(b) return (a.n * b.d) < (b.n * a.d)endfunction Rational.__le(a, b) return not (a > b)endfunction Rational.__eq(a, b) a,b = ensureRational(a), ensureRational(b) return eq(a.n * b.d, b.n * a.d)end

return Rational

end)

register('matrix', function(myrequire)local eq = myrequire('eq')

local Matrix = Matrix.__index = Matrix

function Matrix:new(p) return setmetatable(p or, self)end

function Matrix:newNxM(n, m) local m = for i=1,n do local row = for j=1,m do table.insert(row, 0) end table.insert(m, row) end return self:new(m)end

-- destructive updatefunction Matrix:apply(f) for i=1,#self do for j=1,#self[i] do self[i][j] = f(self[i][j]) end end return selfend

-- destructive update to selffunction Matrix:LUPDecompose(N, nopivots) local P = for i=1,N do P[i] = i -- unit permutation matrix end local S = 0 -- counting pivots for i=1,N do if nopivots then if eq(self[i][i], 0) then return nil -- matrix is degenerate end else local maxA = 0 local imax = i for k=i,N do local absA = self[k][i] if absA < 0 then absA = -absA end if absA > maxA then maxA = absA imax = k end end if not (maxA > 0) then --print("i", i, "maxA", maxA) --self:print return nil end -- failure, matrix is degenerate if imax ~= i then -- pivoting P P[i],P[imax] = P[imax],P[i] -- pivoting rows of A self[i],self[imax] = self[imax],self[i] -- counting pivots (for determinant) S = S + 1 end end

for j=i+1,N do --print(self[i][i]) assert(not eq(self[i][i], 0)) self[j][i] = self[j][i] / self[i][i] for k=i+1,N do self[j][k] = self[j][k] - self[j][i] * self[i][k] end end --print("after pivot of",i) --self:print end return P,Send

-- destructive update to selffunction Matrix:LUPSolve(b, N, nopivots) local P,S = self:LUPDecompose(N, nopivots) if P

nil then return nil end print("Decomposed!", P, S) local x = for i=1,N do x[i] = b[P[i]] for k=1,i-1 do x[i] = x[i] - self[i][k] * x[k] end end for i=N,1,-1 do for k=i+1,N do x[i] = x[i] - self[i][k] * x[k] end x[i] = x[i] / self[i][i] end return xend

function Matrix:print local buf = for i=1,#self do for j=1,#self[i] do table.insert(buf, tostring(self[i][j])) table.insert(buf, ' ') end table.insert(buf, "\n") end print(table.concat(buf))end

----

return Matrix

end)

register('ring', function(myrequire)-- modular arithmeticlocal eq = myrequire('eq')local compat = myrequire('advent.compat')

local Ring = Ring.__index = Ringfunction Ring:new(n, m) assert(n >=0 and m > 0) assert(n < m) return setmetatable(self)endfunction Ring:__tostring return string.format("%s mod %s", tostring(self.n), tostring(self.m))endfunction Ring:__unm if self.n

0 then return self end return Ring:new(self.m-self.n, self.m)endfunction Ring.__add(a, b) local r, m if type(a)

'number' then m = b.m r = (a % m) + b.n elseif type(b)

'number' then m = a.m r = a.n + (b % m) else assert(eq(a.m, b.m)) m = a.m r = a.n + b.n end if r >= m then r = r - m end return Ring:new(r, m)endfunction Ring.__sub(a, b) return a + (-b)endfunction Ring.__eq(a, b) if type(a)

'number' then return eq(a % b.m, b.n) elseif type(b)

'number' then return eq(a.n, b % a.m) else assert(eq(a.m, b.m)) return eq(a.n, b.n) endendfunction Ring.__mul(a, b) -- there are better algorithms, but this will do for now local r, m if type(a)

'number' then m = b.m r = ((a % m) * b.n) elseif type(b)

'number' then m = a.m r = (a.n * (b % m)) else assert(eq(a.m, b.m)) m = a.m r = (a.n * b.n) end return Ring:new(r % m, m)end

function Ring.__div(a, b) -- compute modular inverse of b; this is only valid if modulus is prime local t, newt = 0, 1 local r, newr = b.m, b.n while not eq(newr, 0) do local quotient = compat.idiv(r, newr) t, newt = newt, t - quotient * newt r, newr = newr, r - quotient * newr end if r > 1 then error("divisor is not invertible") elseif t < 0 then t = t + b.m end local inverse_b = Ring:new(t, b.m) if eq(a.n, 1) then return inverse_b end return a * inverse_bend

function Ring.__idiv(a, b) return Ring.__div(a, b)end

return Ring

end)

register('day24', function(myrequire)--DAY 24 --local l = myrequire('llpeg')local read_wiki_input = myrequire('util').read_wiki_inputlocal BigNum = myrequire('bignum')local Rational = myrequire('rational')local Matrix = myrequire('matrix')local Ring = myrequire('ring')local eq = myrequire('eq')local lt = myrequire('lt')local gcd = myrequire('gcd')local compat = myrequire('advent.compat')

local inspect = _G['print'] or function end

local function abs(n) if lt(n, 0) then return -n else return n endend

local function primes(n) local result = local notA = local i = 2 while i*i <= n do if notA[i]

nil then table.insert(result, i) local j = i*i while j <= n do notA[j] = true j = j + i end end i = i + 1 end while i<=n do if notA[i]

nil then table.insert(result, i) end i = i + 1 end return resultend

local function sortedKeys(tbl) local sorted = for k,_ in pairs(tbl) do table.insert(sorted, k) end table.sort(sorted) return sortedend

--PARSING --

local function tobignum(n) return BigNum:new(tonumber(n)) end

local Hail = Hail.__index = Hailfunction make_hail(tbl) return setmetatable(tbl, Hail)endfunction Hail:__tostring return string.format("%s,%s,%s @ %s,%s,%s", self.position.x, self.position.y, self.position.z, self.velocity.x, self.velocity.y, self.velocity.z)end

local nl = l.P"\n"local SKIP = l.S" \t"^0

local patt = l.P

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 return astend

--PART 1 --

function determinant(a, b, c, d) return a*d - b*cend

function sign(x) if lt(x, 0) then return -1 end if lt(0, x) then return 1 end return 0end

function hailstone_intersection(a, b, min, max) local x1, x2 = a.position.x, a.position.x + a.velocity.x local y1, y2 = a.position.y, a.position.y + a.velocity.y local x3, x4 = b.position.x, b.position.x + b.velocity.x local y3, y4 = b.position.y, b.position.y + b.velocity.y local d = determinant(x1-x2, x3-x4, y1-y2, y3-y4) if d

0 then return false end -- no intersection! local td = determinant(x1-x3, x3-x4, y1-y3, y3-y4) if sign(td) ~= sign(d) then return false end -- intersection in past local ud = determinant(x1-x3, x1-x2, y1-y3, y1-y2) if sign(ud) ~= sign(d) then return false end -- intersection in past local Px = a.position.x + compat.idiv(a.velocity.x * td, d) --print(Px) if lt(Px, min) or lt(max, Px) then return false end -- intersection not in range if eq(Px, max) then print("warning x") end local Py = a.position.y + compat.idiv(a.velocity.y * td, d) --print(Py) if lt(Py, min) or lt(max, Py) then return false end -- intersection not in race if eq(Py, max) then print("warning y") end return trueend

local function part1(source, min, max) min,max = tonumber(min),tonumber(max) local hail = parse(source) local count = 0 for i=1,#hail do for j = i+1, #hail do if hailstone_intersection(hail[i], hail[j], min, max) then --print("Intersection:", inspect(hail[i]), inspect(hail[j])) count = count + 1 end end end return countend

--PART 2 --local Range = Range.__index = Rangefunction Range:new return setmetatable(self)endfunction Range:le(val) if self.max

nil or self.max > val then self.max = val endendfunction Range:ge(val) if self.min

nil or self.min < val then self.min = val endendfunction Range:__tostring(val) local buf =