Jump to content

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

From Wikipedia, the free encyclopedia
return (function()
local builders = {}
local function register(name, f)
  builders[name] = f
end
register('llpeg', function() return require [[Module:User:Cscott/llpeg]] end)

register('util', function(myrequire)
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*<syntaxhighlight[^>]*>\n?", "", 1)
      source = source:gsub("</syntaxhighlight[^>]*>%s*$", "", 1)
      return func(source, frame.args[2], frame.args[3])
    end
end

return {
  read_wiki_input = read_wiki_input,
}

end)

register('advent.compat', function() return require [[Module:User:Cscott/compat]] 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 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
  end
  return a == b
end

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 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
  end
  return a < b
end

return lt

end)

register('bignum', function(myrequire)
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
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
  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
  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
  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)

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 call
end

return gcd

end)

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

local Rational = {}
Rational.__index = Rational
function 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({n=n, d=d, reduced=r}, self)
end
function 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 self
end

local function ensureRational(r)
  if type(r) == 'number' then return Rational:new(r, 1, true) end
  assert(getmetatable(r) == Rational)
  return r
  --[[
  if getmetatable(r) == Rational then return r end
  return Rational:newUnreduced(r, 1)
  ]]--
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)
end
function Rational:__unm()
  if eq(self.n, 0) then return self end
  return Rational:new(-self.n, self.d, self.reduced)
end
function 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)
end
function 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)
end
function Rational.__mul(a, b)
  a,b = ensureRational(a), ensureRational(b)
  return Rational:new(a.n*b.n, a.d*b.d)
end
function 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)
end
function Rational.__lt(a, b)
  a,b = ensureRational(a), ensureRational(b)
  return (a.n * b.d) < (b.n * a.d)
end
function Rational.__le(a, b)
  return not (a > b)
end
function 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 update
function Matrix:apply(f)
  for i=1,#self do
    for j=1,#self[i] do
      self[i][j] = f(self[i][j])
    end
  end
  return self
end

-- destructive update to self
function 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,S
end

-- destructive update to self
function 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 x
end

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

--[[
local A = Matrix:new{
  { 1, 1, 1 },
  { 4, 3, -1 },
  { 3, 5, 3 }
}
local Rational = require 'rational'
A:apply(function(n) return Rational:new(n) end)
--local P,S = A:LUPDecompose(3)
--A:print()
--print(P,S)
local C = { 1, 6, 4 }
local X = A:LUPSolve(C, 3)
print(X[1], X[2], X[3])
]]--

return Matrix

end)

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

local Ring = {}
Ring.__index = Ring
function Ring:new(n, m)
  assert(n >=0 and m > 0)
  assert(n < m)
  return setmetatable({n=n, m=m}, self)
end
function Ring:__tostring()
  return string.format("%s mod %s", tostring(self.n), tostring(self.m))
end
function Ring:__unm()
  if self.n == 0 then return self end
  return Ring:new(self.m-self.n, self.m)
end
function 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)
end
function Ring.__sub(a, b)
  return a + (-b)
end
function 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)
  end
end
function 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_b
end

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_input
local 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 end
end

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 result
end

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

--[[ PARSING ]]--

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

local Hail = {}
Hail.__index = Hail
function make_hail(tbl)
  return setmetatable(tbl, Hail)
end
function 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{
   "Hail",
   Hail = l.Ct( l.V"Hailstone" * (nl * l.V"Hailstone")^0 * nl^0) * -1,
   Hailstone = l.Ct( l.Cg(l.V"Coord", "position") * l.P"@" * SKIP * l.Cg(l.V"Coord", "velocity") ) / make_hail,
  Coord = l.Ct( l.Cg(l.V"Number", "x") * SKIP * l.P"," * SKIP *
                l.Cg(l.V"Number", "y") * SKIP * l.P"," * SKIP *
                l.Cg(l.V"Number", "z") * SKIP ),
  Number =  ((l.P"-" ^ -1) * (l.R"09"^1)) / tobignum,
}

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 ast
end


--[[ PART 1 ]]--

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

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

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 true
end

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 count
end

--[[ PART 2 ]]--
local Range = {}
Range.__index = Range
function Range:new()
  return setmetatable({}, self)
end
function Range:le(val)
  if self.max == nil or self.max > val then self.max = val end
end
function Range:ge(val)
  if self.min == nil or self.min < val then self.min = val end
end
function Range:__tostring(val)
  local buf = { '[' }
  if self.min == nil then
    table.insert(buf, "inf")
  else
    table.insert(buf, tostring(self.min))
  end
  table.insert(buf, ",")
  if self.max == nil then
    table.insert(buf, "inf")
  else
    table.insert(buf, tostring(self.max))
  end
  table.insert(buf, ']')
  return table.concat(buf)
end

local function check_bounds(hail, vPositive)
  local unk = { x=Range:new(), y=Range:new(), z=Range:new() }
  local coords = { "x", "y", "z" }
  for _,h in ipairs(hail) do
    --print(h.velocity.x, h.velocity.y, h.velocity.z)
    -- h.position + t*h.velocity = unk.position + u*unk.velocity
    -- since we know t and u have to be positive, if we know the sign of
    -- u (which we'll brute force) we can constrain unk.position by h.position
    for _,c in ipairs(coords) do
      if vPositive[c] then -- unk.position >= h.position
        if h.velocity[c] >= 0 then
          -- both velocities are positive, nothing more can be said
        else
          -- hail is moving - while unk is moving +
          -- thus h.position >= unk.position
          unk[c]:le(h.position[c])
        end
      else
        if h.velocity[c] >= 0 then
          -- hail is moving + while unk is moving -
          -- thus h.position <= unk.position
          unk[c]:ge(h.position[c])
        else
          -- both velocities are negative, nothing more can be said
        end
      end
    end
  end
  local buf = {"For "}
  for _,c in ipairs(coords) do
    table.insert(buf, c)
    if vPositive[c] then
      table.insert(buf, "+")
    else
      table.insert(buf, "-")
    end
    if c ~= 'z' then table.insert(buf, ", ") end
  end
  table.insert(buf, " limits are ")
  for _,c in ipairs(coords) do
    table.insert(buf, c)
    table.insert(buf, "=")
    table.insert(buf, tostring(unk[c]))
    if c ~= 'z' then table.insert(buf, ", ") end
  end
  print(table.concat(buf))
  return unk
end

local function apply(tbl, f)
  for i,v in ipairs(tbl) do
    tbl[i] = f(v)
  end
  return tbl
end

local function mkrat(n) return Rational:new(n, tobignum(1)) end
local function mkrat3(v)
  return {x=mkrat(v.x), y=mkrat(v.y), z=mkrat(v.z)}
end
local function bigrat(n,m) return Rational:new(tobignum(n),tobignum(m or 1)) end

function check8(hail)
  -- use x=az+b / y = cz + d form of each line
  -- z = pos.z + t*vel.z => t = z/vel.z - pos.z/vel.z
  -- x = pos.x + t*vel.x => x = pos.x + z(vel.x/vel.z) - (vel.x/vel.z)*pos.z
  --                        x = (vel.x/vel.z)*z + (pos.x - (vel.x/vel.z)*pos.z)
  local function abcd(pos, vel)
    local a = mkrat(vel.x) / mkrat(vel.z)
    local b = mkrat(pos.x) - (mkrat(pos.z) * mkrat(vel.x) / mkrat(vel.z))
    local c = mkrat(vel.y) / mkrat(vel.z)
    local d = mkrat(pos.y) - (mkrat(pos.z) * mkrat(vel.y) / mkrat(vel.z))
    return a,b,c,d
  end
  local a1,b1,c1,d1 = abcd(hail[1].position, hail[1].velocity)
  local a2,b2,c2,d2 = abcd(hail[2].position, hail[2].velocity)
  local a3,b3,c3,d3 = abcd(hail[3].position, hail[3].velocity)
  local a4,b4,c4,d4 = abcd(hail[4].position, hail[4].velocity)
  --[[
    a1*z1 + b1 = unk.a * z1 + unk.b
    c1*z1 + d1 = unk.c * z1 + unk.d

    unk.a*z1 - a1*z1 + unk.b - b1 = 0
    unk.c*z1 - c1*z1 + unk.d - d1 = 0
  ]]--
end

function gradient_descent(hail)
  -- use x=az+b / y=cz+d form
  -- vel.x = a, vel.y = c, vel.z = 1
  -- pos.x = b, pos.y = d. pos.z = 0

  local function crossprod(a, b)
    return {
      x=a.y*b.z - a.z*b.y,
      y=a.z*b.x - a.x*b.z,
      z=a.x*b.y - a.y*b.x,
    }
  end
  local function dist2(hailstone, a, b, c, d)
    local unk_pos = { x=b, y=d, z=mkrat(0) }
    local unk_vel = { x=a, y=c, z=mkrat(1) }
    local hail_pos = mkrat3(hailstone.position)
    local hail_vel = mkrat3(hailstone.velocity)
    local n = crossprod(hail_vel, unk_vel)
    local r1mr2 = {
      x=hail_pos.x - unk_pos.x,
      y=hail_pos.y - unk_pos.y,
      z=hail_pos.z - unk_pos.z,
    }
    local dd = n.x * r1mr2.x + n.y * r1mr2.y + n.z * r1mr2.z
    local n_mag2 = n.x * n.x + n.y * n.y + n.z * n.z
    return (dd * dd) / n_mag2
  end

  -- arbitrarily selected starting position for search
  -- as hail[1] presumably doesn't have z velocity 1 or pos.z = 0
  -- this is *near* but not *actually* the same as hail[1]'s vector
  local start = {
    --[[
    a=hail[1].velocity.x, b=hail[1].position.x,
    c=hail[1].velocity.y, d=hail[1].position.y,
    ]]--
    --a=mkrat(-18), b=mkrat(206273907287337), c=mkrat(-17), d=mkrat(404536114336383),
--    a=bigrat(-1,10), b=bigrat(6893814583987912, 25), c=bigrat(-1,5), d=bigrat(15882393318613117,50)
    --    a=bigrat(-107,1000), b=bigrat(27575205905929417,100), c=bigrat(-37,250), d=bigrat(79411872811990497,250)
    -- a=bigrat(-107,1000), b=bigrat(27616905905929417,100), c=bigrat(-147,1000), d=bigrat(79307872811990497,250),
    -- a=bigrat(-541,5000), b=bigrat(27657105905929417,100), c=bigrat(-361,2500), d=bigrat(79207622811990497,250),
    --a=bigrat(-129,1000), b=bigrat(279241059059294,1), c=bigrat(-61,625), d=bigrat(309020491247961, 1)
--    a=bigrat(-1593,10000), b=bigrat(283241059059294,1), c=bigrat(-333,10000),d=bigrat(286020491247961,1),
    --a=bigrat(-1747,10000),b=bigrat(284841059059294,1),c=bigrat(73,10000),d=bigrat(278720491247961,1),
    --a=bigrat(-1857,10000),b=bigrat(286421059059294,1),c=bigrat(383,10000),d=bigrat(273340491247961,1),
    --a=bigrat(-1857,10000),b=bigrat(286419759059294,1),c=bigrat(383,10000),d=bigrat(273344691247961,1),
    --a=bigrat(-1857,10000),b=bigrat(286419759059294,1),c=bigrat(383,10000),d=bigrat(273344698247961,1),
    --a=bigrat(-1857,10000),b=bigrat(286419758729294,1),c=bigrat(383,10000),d=bigrat(273344698467961,1),
--a=bigrat(-1857,10000),b=bigrat(286419758728794,1),c=bigrat(383,10000),d=bigrat(273344698470961,1),
--a=bigrat(-1857,10000),b=bigrat(286419758728797,1),c=bigrat(383,10000),d=bigrat(273344698470938,1),
--a=bigrat(-9289,50000),b=bigrat(286419758728717,1),c=bigrat(1919,50000),d=bigrat(273344698470858,1),
--a=bigrat(-18763,100000),b=bigrat(286419718728717,1),c=bigrat(4237,100000),d=bigrat(273344658570858,1),
--a=bigrat(-241,1250),b=bigrat(286419463728717,1),c=bigrat(143,2500),d=bigrat(273344403570858,1),
--a=bigrat(-9693,50000),b=bigrat(286416553728717,1),c=bigrat(601,10000),d=bigrat(273341503570858,1),
--a=bigrat(-19439,100000),b=bigrat(286265553728717,1),c=bigrat(77,1250),d=bigrat(273191503570858,1),
--a=bigrat(-19439,100000),b=bigrat(285835553728717,1),c=bigrat(77,1250),d=bigrat(272001503570858,1),
--a=bigrat(-1949,10000),b=bigrat(285945553728717,1),c=bigrat(3149,50000),d=bigrat(268791503570858,1),
--a=bigrat(-39029,200000),b=bigrat(285795553728717,1),c=bigrat(63691,1000000),d=bigrat(268652503570858,1),

--a=bigrat(-39029,200000),b=bigrat(280000000000000,1),c=bigrat(63691,1000000),d=bigrat(260000000000000,1),
--a=bigrat(-122,625),b=bigrat(285200000000000,1),c=bigrat(319,5000),d=bigrat(268500000000000,1),
--a=bigrat(-19519,100000),b=bigrat(285830000000000,1),c=bigrat(6383,100000),d=bigrat(268630000000000,1),
--a=bigrat(-48823,250000),b=bigrat(285795000000000,1),c=bigrat(32067,500000),d=bigrat(268575000000000,1),
--a=bigrat(-97701,500000),b=bigrat(285794400000000,1),c=bigrat(64463,1000000),d=bigrat(268545000000000,1),
--a=bigrat(-3054,15625),b=bigrat(285846500000000,1),c=bigrat(16157,250000),d=bigrat(268488400000000,1),

a=bigrat(3054,15625),b=bigrat(285846500000000,1),c=bigrat(16157,250000),d=bigrat(268488400000000,1),
--[[
  206273907288897 - 18t = x - 97701/500000u
  404536114337943 + 6t  = y + 64463/1000000u
  197510451330134 + 92t = z + u

]]--
  }
  local vars = { "a", "b", "c", "d" }
  local function score(guess)
    local sum = mkrat(0)
    for i=1,4 do
      sum = sum + dist2(hail[i], guess.a, guess.b, guess.c, guess.d)
    end
    return sum
  end
  local function quantize(n, amt)
    local m = (n*amt):toWholeNumber()
    return Rational:new(m, amt)
  end

  local guess = start
  local dim = 1
  local epsilon = bigrat(1, 1000000)
  local beta = bigrat(1,5)
  while true do
    local s = score(guess)
    --print(s:toWholeNumber(), guess.a, guess.b, guess.c, guess.d)
    local buf = {}
    for _,v in ipairs(vars) do
      table.insert(buf, v) ; table.insert(buf, "=bigrat(")
      guess[v]:reduce()
      table.insert(buf, tostring(guess[v].n))
      table.insert(buf, ",")
      table.insert(buf, tostring(guess[v].d))
      table.insert(buf, "),")
    end
    print(s:toWholeNumber(), table.concat(buf))
    if not (s > 0 or s < 0) then break end
    local orig = guess[vars[dim]]
    guess[vars[dim]] = orig + epsilon
    local s2 = score(guess)
    guess[vars[dim]] = orig - epsilon
    local s3 = score(guess)
    guess[vars[dim]] = orig
    --print("Score 2", vars[dim], s2:toWholeNumber())
    --print("Score 3", vars[dim], s3:toWholeNumber())
    -- compute the derivative in this dimension
    local adjustment = 0
    local deriv = 0
    if s2 < s3 then
      if s2 < s then adjustment = mkrat(1) ; deriv = s - s2; end
    else
      if s3 < s then adjustment = mkrat(-1) ; deriv = s - s3; end
    end
    local q
    if dim == 2 or dim == 4 then
      --adjustment = adjustment*guess[vars[dim]]/1000
      --adjustment = adjustment * guess[vars[dim]]/100000
      --adjustment = adjustment * bigrat(1000000, 1)
      --adjustment = adjustment * s / 100*(deriv / epsilon)
      adjustment = adjustment * 100000000
      q = 1
    else
      q = 1000000
      adjustment = adjustment / q
    end
      --[[
    local deriv = (s2 - s)
    local adjustment = (-s * beta / deriv):toWholeNumber()
    --print("Score 1", s:toWholeNumber())
    --print("Score 2", s2:toWholeNumber())
    --print("Derivative", vars[dim], deriv:toWholeNumber())
    if not (adjustment<0 or adjustment>0) then
      if deriv > 0 then adjustment = -1 else adjustment = 1 end
    end
        --print("Adjusting",vars[dim],"by",adjustment)
      ]]--
    guess[vars[dim]] = quantize(guess[vars[dim]] + adjustment, q)
    local s3 = score(guess)
    --print("Score 3", s3:toWholeNumber())
    if s3 > s then -- that didn't work, undo
      guess[vars[dim]] = orig
    end
    dim = dim + 1
    if dim > #vars then dim = 1 end
  end
  print("Found it!", guess.a, guess.b, guess.c, guess.d)
end

function check(hail, vx, vy, vz)
  -- use first 3 hailstones to constrain the three+(2*n) unknowns
  --[[
    [1 0 0 -h1.vx vx 0 0 0 0][unk.x ]   [h1.x]
    [0 1 0 -h1.vy vy 0 0 0 0][unk.y ]   [h1.y]
    [0 0 1 -h1.vz vz 0 0 0 0][unk.z ]   [h1.x]
    [1 0 0 0 0 -h2.vx vx 0 0][t1    ]   [h2.x]
    [0 1 0 0 0 -h2.vy vy 0 0][u1    ]   [h2.y]
    [0 0 1 0 0 -h2.vz vz 0 0][t2    ]   [h2.z]
    [1 0 0 0 0 0 0 -h3.vx vx][u2    ] = [h3.x]
    [0 1 0 0 0 0 0 -h3.vy vy][t3    ] = [h3.y]
    [0 0 1 0 0 0 0 -h3.vz vz][u3    ] = [h3.z]
  ]]--
  local M = Matrix:new{
    {1, 0, 0, -hail[1].velocity.x, vx, 0, 0, 0, 0, },
    {0, 1, 0, -hail[1].velocity.y, vy, 0, 0, 0, 0, },
    {0, 0, 1, -hail[1].velocity.z, vz, 0, 0, 0, 0, },
    {1, 0, 0, 0, 0, -hail[2].velocity.x, vx, 0, 0, },
    {0, 1, 0, 0, 0, -hail[2].velocity.y, vy, 0, 0, },
    {0, 0, 1, 0, 0, -hail[2].velocity.z, vz, 0, 0, },
    {1, 0, 0, 0, 0, 0, 0, -hail[3].velocity.x, vx, },
    {0, 1, 0, 0, 0, 0, 0, -hail[3].velocity.y, vy, },
    {0, 0, 1, 0, 0, 0, 0, -hail[3].velocity.z, vz, },
  }
  --print("originally")
  --M:print()
  M:apply(function(n)
      if type(n)=='number' then return bigrat(n,1) end
      if getmetatable(n)==BigNum then return Rational:new(n, tobignum(1)) end
      return n
  end)
  local b = {
    hail[1].position.x,
    hail[1].position.y,
    hail[1].position.z,
    hail[2].position.x,
    hail[2].position.y,
    hail[2].position.z,
    hail[3].position.x,
    hail[3].position.y,
    hail[3].position.z,
  }
  apply(b, mkrat)
  local x = M:LUPSolve(b, 9)
  print(x)
  if x == nil then return false end
  print("Solved!", inspect(x))
  -- check for non-integer values in solution array
  for i=1,9 do
    if not x[i]:isWholeNumber() then return false end
  end
  -- check for negative time values
  for i=4,9 do
    if x[i] < 0 then return false end
  end
  -- okay, now verify solutions for all other hailstones
  local unk = {
    x=x[1]:toWholeNumber(),
    y=x[2]:toWholeNumber(),
    z=x[3]:toWholeNumber(),
  }
  for i=4, #hail do
    -- 2 unknowns, 2 equations
    -- -h.vx*t + unk.vx*u = h.x - unk.x
    local M2 = Matrix:new{
      { -hail[i].velocity.x, vx },
      { -hail[i].velocity.y, vy },
    }
    M2:apply(mkrat)
    local b = {
      hail[i].position.x - unk.x,
      hail[i].position.y - unk.y,
    }
    apply(b, mkrat)
    local x = M2:LUPSolve(b, 2)
    if x == nil then return false end
    -- check for non-integer or non-positive values
    for i=1,2 do
      if x[i] < 0 or not x[i]:isWholeNumber() then return false end
    end
    -- check that t/u values also work for z axis
    local t,u = x[1]:toWholeNumber(), x[2]:toWholeNumber()
    local hz = hail[i].position.z + t*hail[i].velocity.z
    local uz = unk.z + u*vz
    if hz < uz then return false end
    if hz > uz then return false end
  end
  -- found a solution!
  print(vz,vy,vz, "works!")
  return true
end

local function check_all_bounds(source)
  local hail = parse(source)
  for xsign=0,1 do
    for ysign=0,1 do
      for zsign=0,1 do
        check_bounds(hail, {x=(xsign==1), y=(ysign==1), z=(zsign==1)})
      end
    end
  end
end

local function part2_brute(source)
  local hail = parse(source)
  assert(not check(hail, 0, 0, 0))
  -- brute force search through small vx/vy/vz
  for dist=72,1000 do
    print("dist=",dist)
    local seen = {} -- hack to avoid checking edges twice
    local function mycheck(x,y,z)
      if x==dist or x==-dist or y==dist or y==-dist or z==dist or z==-dist then
        local key = string.format("%d,%d,%d", x, y, z)
        if seen[key] then return false end -- already checked
        seen[key] = true
      end
      return check(hail, x, y, z)
    end
    for i=-dist, dist do
      for j=-dist, dist do
        if mycheck( dist,i,j) then return end
        if mycheck(-dist,i,j) then return end
        if mycheck(i, dist,j) then return end
        if mycheck(i,-dist,j) then return end
        if mycheck(i,j, dist) then return end
        if mycheck(i,j,-dist) then return end
      end
    end
  end
end

local function part2_grad(source)
  local hail = parse(source)
  gradient_descent(hail)
end

local function part2_another_attempt(source)
  local hail = parse(source)
  --check(hail, bigrat(-97701,500000), bigrat(64463,1000000), bigrat(1,1))
  local function abcd(pos, vel)
    local a = mkrat(vel.x) / mkrat(vel.z)
    local b = mkrat(pos.x) - (mkrat(pos.z) * mkrat(vel.x) / mkrat(vel.z))
    local c = mkrat(vel.y) / mkrat(vel.z)
    local d = mkrat(pos.y) - (mkrat(pos.z) * mkrat(vel.y) / mkrat(vel.z))
    return a,b,c,d
  end
  local unk_a = bigrat(-3054,15625)
  local unk_c = bigrat(16157,250000)
  local a1,b1,c1,d1 = abcd(hail[1].position, hail[1].velocity)
  local a2,b2,c2,d2 = abcd(hail[2].position, hail[2].velocity)
  --[[
    a1*z1 + b1 = unk.a * z1 + unk.b
    c1*z1 + d1 = unk.c * z1 + unk.d

    unk.a*z1 - a1*z1 + unk.b - b1 = 0
    unk.c*z1 - c1*z1 + unk.d - d1 = 0

    [unk.a-a1 0 1 0][z1]      [ b1 ]
    [unk.c-c1 0 0 1][z2]      [ d1 ]
    [0 unk.a-a2 1 0][unk.b] = [b2]
    [0 unk.c-c2 0 1][unk.d]   [d2]

                             |        0 0 1 |              |       0 1 0 |
    determinant = (unk.a-a1)*| unk.a-a2 1 0 | - (unk.c-c1)*|unk.a-a2 1 0 |
                             | unk.c-c2 0 1 |              |unk.c-c2 0 1 |

    = (unk.a-a1)*(c2-unk.c) + (c1-unk.c)*(a2-unk.a)
  ]]--
  print("unk_a",unk_a) print("unk_c",unk_c)
  print("a1",a1) print("c1", c1)
  print("a2",a2) print("c2", c2)
  print((unk_a-a1)*(c2-unk_c))
  print((c1-unk_c)*(a2-unk_a))
  local M2 = Matrix:new{
    { (unk_a - a1), bigrat(0), bigrat(1), bigrat(0) },
    { (unk_c - c1), bigrat(0), bigrat(0), bigrat(1) },
    { bigrat(0), (unk_a - a1), bigrat(1), bigrat(0) },
    { bigrat(0), (unk_c - c1), bigrat(0), bigrat(1) },
  }
  local b = { b1, d1, b2, d2 }
  local x = M2:LUPSolve(b, 4)
  print(x)
end

local function part2_residue(source)
  local coords = { "x", "y", "z" }
  local max = 0
  local p = primes(689) -- maximum common factor is 689

  local vResults = {}
  local pResults = {}
  local p2Results = {}
  local hail = parse(source)
  local HACK = 2
  -- for all pairs of hailstones:
  for i=1,#hail do
    for j=i+1,#hail do
      local hail1,hail2 = hail[i], hail[j]
      -- for all pairs of coords:
      for k=1,#coords do
        for l=k+1,#coords do
          local d1,d2 = coords[k], coords[l]
          -- for all prime factors in common between the velocity vectors
          local common1 = gcd(abs(hail1.velocity[d1]), abs(hail1.velocity[d2]))
          local common2 = gcd(abs(hail2.velocity[d1]), abs(hail2.velocity[d2]))
          local common = gcd(common1, common2)
          if common > max then max = common end -- track max common factor
          if not eq(common, 1) then
            for _,pp in ipairs(p) do
              --pp = pp * pp * pp * pp * pp -- HACK
              if pp*pp > common then break end
              if eq(common % pp, 0) then
                -- check for usable residue!
                local pos1d1 = hail1.position[d1] % pp
                local pos2d1 = hail2.position[d1] % pp
                local pos1d2 = hail1.position[d2] % pp
                local pos2d2 = hail2.position[d2] % pp
                if eq(pos1d1, pos2d1) and not eq(pos1d2, pos2d2) then
                  --print("vel", d1,"=0 mod", pp)
                  local key = string.format("v%s=0mod%s", d1, pp)
                  vResults[key] = { coord=d1, mod=pp }
                  --print("pos", d1,"=", pos1d1, "mod", pp)
                  key = string.format("p%s=%smod%s", d1, pos1d1, pp)
                  pResults[key] = { coord=d1, rem=pos1d1, mod=pp }
                  if d1=='x' and eq(pp, 5) then
                    print(string.format("Looking at %s and %s", d1, d2))
                    print(hail1)
                    print(hail2)
                    print("pos", d1,"=", pos1d1, "mod", pp)
                  end
                end
                if eq(pos1d2, pos2d2) and not eq(pos1d1, pos2d1) then
                  --print("vel", d2,"=0 mod", pp)
                  local key = string.format("v%s=0mod%s", d2, pp)
                  vResults[key] = { coord=d2, mod=pp }
                  --print("pos", d2,"=", pos1d2, "mod", pp)
                  key = string.format("p%s=%smod%s", d2, pos1d2, pp)
                  pResults[key] = { coord=d2, rem=pos1d2, mod=pp }
                end
              end
            end
          end
        end
      end
    end
  end
  print("Largest common factor is ", max)
  local v = { x=1, y=1, z=1 }
  for _,k in ipairs(sortedKeys(vResults)) do
    local r = vResults[k]
    print(string.format("Velocity %s = 0 mod %s", r.coord, r.mod))
    v[r.coord] = v[r.coord] * r.mod
  end
  print("So:")
  for _,c in ipairs(coords) do
    print(string.format("Velocity %s = <some constant> * %s", c, v[c]))
  end
  for _,k in ipairs(sortedKeys(pResults)) do
    local r = pResults[k]
    print(string.format("Position %s = %s mod %s", r.coord, r.rem, r.mod))
  end
  return v.x, v.y, v.z
end

--[[
Largest common factor is 	44
Velocity x = 0 mod 3
Velocity y = 0 mod 2
Velocity y = 0 mod 3
Velocity z = 0 mod 4
So:
Velocity x = <some constant> * 3
Velocity y = <some constant> * 6
Velocity z = <some constant> * 2
Position x = 0 mod 3
Position y = 0 mod 3
Position y = 1 mod 2
Position z = 2 mod 4
]]--

local function part2_search2(source)
  local hail = parse(source)
  --check(hail, 3, 6, 4)

  local MOD = 5
  for vx=0,4 do
    for vy=0,4 do
      for vz=0,4 do

  local hail1, hail2, hail3 = hail[1], hail[2], hail[3]

  local M = Matrix:new{
    {1, 0, 0, -hail1.velocity.x, vx, 0, 0, 0, 0, },
    {0, 1, 0, -hail1.velocity.y, vy, 0, 0, 0, 0, },
    {0, 0, 1, -hail1.velocity.z, vz, 0, 0, 0, 0, },
    {1, 0, 0, 0, 0, -hail2.velocity.x, vx, 0, 0, },
    {0, 1, 0, 0, 0, -hail2.velocity.y, vy, 0, 0, },
    {0, 0, 1, 0, 0, -hail2.velocity.z, vz, 0, 0, },
    {1, 0, 0, 0, 0, 0, 0, -hail3.velocity.x, vx, },
    {0, 1, 0, 0, 0, 0, 0, -hail3.velocity.y, vy, },
    {0, 0, 1, 0, 0, 0, 0, -hail3.velocity.z, vz, },
  }
  local function make_ring(n)
    if type(n)=='number' then
      n = n % MOD
      return Ring:new(n, MOD)
    end
    if getmetatable(n)==BigNum then
      n = n % MOD
      n = n:toNumber()
      return Ring:new(n, MOD)
    end
    error("what is this?")
  end
  M:apply(make_ring)
  --M:print()
  local b = {
    hail1.position.x,
    hail1.position.y,
    hail1.position.z,
    hail2.position.x,
    hail2.position.y,
    hail2.position.z,
    hail3.position.x,
    hail3.position.y,
    hail3.position.z,
  }
  apply(b, make_ring)
  local x = M:LUPSolve(b, 9, true)
  print(x)
  if x ~= nil then
    print("Solved!", inspect(x))
  end
      end
    end
  end
end

local function part2_solve3(source)
  local hail = parse(source)
  --[[
    h[i].pos.x + t[i]*h[i].vel.x = unk.pos.x + t[i]*unk.vel.x
    =>
    t[i]*(h[i].vel.x - unk.vel.x) = unk.pos.x - h[i].pos.x
    =>
    t[i] = (unk.pos.x - h[i].pos.x) / (h[i].vel.x - unk.vel.x)
    ...now equate x and y for the same hailstone (aka, same t[i])...
    (unk.pos.x - h[i].pos.x)/(h[i].vel.x - unk.vel.x) =
      (unk.pos.y - h[i].pos.y)/(h[i].vel.y - unk.vel.y)
    =>
    (unk.pos.x - h[i].pos.x) * (h[i].vel.y - unk.vel.y) =
      (unk.pos.y - h[i].pos.y) * (h[i].vel.x - unk.vel.x)
    =>
    u.p.x * h.v.y - u.p.x * u.v.y - h.p.x * h.v.y + h.p.x * u.v.y =
       u.p.y * h.v.x - u.p.y * u.v.x - h.p.y * h.v.x + h.p.y * u.v.x
    =>
    u.p.y * u.v.x - u.p.x * u.v.y =
      -u.p.x * h.v.y + h.p.x * h.v.y - h.p.x * u.v.y + u.p.y * h.v.x - h.p.y * h.v.x + h.p.y * u.v.x
    = -h.v.y * u.p.x + h.v.x * u.p.y + h.p.y * u.v.x - h.p.x * u.v.y  + (h.p.x * h.v.y - h.p.y * h.v.x)

    [ (h2.v.y-h1.v.y) (h1.v.x-h2.v.x) (h1.p.y-h2.p.y) (h2.p.x-h1.p.x) ][u.p.x]
    [ (h3.v.y-h1.v.y) (h1.v.x-h3.v.x) (h1.p.y-h3.p.y) (h3.p.x-h1.p.x) ][u.p.y]
    [ (h4.v.y-h1.v.y) (h1.v.x-h4.v.x) (h1.p.y-h4.p.y) (h4.p.x-h1.p.x) ][u.v.x]
    [ (h5.v.y-h1.v.y) (h1.v.x-h5.v.x) (h1.p.y-h5.p.y) (h5.p.x-h1.p.x) ][u.v.y]

    =[ h2.p.x * h2.v.y - h2.p.y * h2.v.x - h1.p.x * h1.v.y + h1.p.y * h1.v.x]
    =[ h3.p.x * h3.v.y - h3.p.y * h3.v.x - h1.p.x * h1.v.y + h1.p.y * h1.v.x]
    =[ h4.p.x * h4.v.y - h4.p.y * h4.v.x - h1.p.x * h1.v.y + h1.p.y * h1.v.x]
    =[ h5.p.x * h5.v.y - h5.p.y * h5.v.x - h1.p.x * h1.v.y + h1.p.y * h1.v.x]
  ]]--

  local ans = { position={}, velocity={} }
  for _,d in ipairs{ "y", "z" } do
    local h1 = hail[1]
    local rows = {}
    local rhs = {}
    for i=2,5 do
      local h2 = hail[i]
      table.insert(rows, {
                     (h2.velocity[d] - h1.velocity[d]),
                     (h1.velocity.x - h2.velocity.x),
                     (h1.position[d] - h2.position[d]),
                     (h2.position.x - h1.position.x),
      })
      table.insert(rhs,
                   h2.position.x * h2.velocity[d] -
                   h2.position[d] * h2.velocity.x -
                   h1.position.x * h1.velocity[d] +
                   h1.position[d] * h1.velocity.x)
    end
    local M = Matrix:new(rows)
    M:apply(mkrat)
    apply(rhs, mkrat)
    local x = M:LUPSolve(rhs, 4)
    if x ~= nil then
      --print("Solved!")
      --print("pos=", x[1], d, x[2])
      --print("vel=", x[3], d, x[4])
      ans.position.x = x[1]
      ans.position[d] = x[2]
      ans.velocity.x = x[3]
      ans.velocity[d] = x[4]
    end
  end
  print("Position", ans.position.x, ans.position.y, ans.position.z)
  print("Velocity", ans.velocity.x, ans.velocity.y, ans.velocity.z)
  return ans.position.x + ans.position.y + ans.position.z
end

local function part2_manual(input)
   return "Calculation done with paper and pencil"
end

local part2 = part2_manual

--[[ CLI ] ]--
local do_part1 = true
local use_example = true

local filename
if use_example then
  filename = "day24.example"
else
  filename = "day24.input"
end
local source = io.input(filename):read("*a")
if do_part1 then
  -- part 1
  if use_example then
    print('Intersecting hailstones:', part1(source, 7, 27))
  else
    print('Intersecting hailstones:', part1(source, 200000000000000, 400000000000000))
  end
else
  -- part 2
  print("Sum:", part2(source))
end
--[ [ 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('day24')
end)()