Jump to content

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

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('pqueue', function(myrequire)
--[[  Priority Queue implemented in lua, based on a binary heap.
Copyright (C) 2017 Lucas de Morais Siqueira <lucas.morais.siqueira@gmail.com>
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
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
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
  end
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)

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('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('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_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
  end
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
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
   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
      end
    end
  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
        end
      end
    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
    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)()