Lanternfish

Oh boy. This task will separate the mathematical thinkers from the… not-so.

The setup is:

You have some list of numbers. For each step, the numbers all decrease by 1. Upon reaching 0, the number is removed and the two numbers 6 and 8 are added to the list. Given such a list, after n steps, how many numbers are there in the list.

Q: is this:

  • a dynamic programming problem?
  • a memoization problem?
  • a problem involving matrices?
  • a problem involving polynomials?
  • a recurrence problem?

A: it’s any of the above you feel comfortable with.

See the day 14 problem Extended Polymerization for a more convoluted or complex version of this problem where we’ll use the same techniques.

Prelude

As usual:

aoc = __import__('aoc-common').aoc()
import numpy as np
import re

text = aoc.input_text(6)

# Intentionally avoiding numpy because we might want bigints now.
nums = [int(x) for x in text.strip().split(',') if x.isdigit()]

Math Is Terrifying

To the unmathematical mind it’s a problem of memoization.

import functools

@functools.cache
def num_fishies(day):
  """From a single fishie starting at 0, how many fishies are there after `day`
  days?

  """
  if day <= 0:
    return 1
  return num_fishies(day-7) + num_fishies(day-9)

def tot_fishies(nums, day):
  return sum(num_fishies(day - x) for x in nums)

print(f'answer to part 1: {tot_fishies(nums, 80)}')
print(f'answer to part w: {tot_fishies(nums, 256)}')

This is a linear-ish solution.

Math Is Awesome

With just a tiny bit of practical math (matrices) we can get an solution.

M = np.asmatrix(np.eye(9, 9, 1, dtype=np.uint64))
M[(6,8), 0] = 1

v = np.bincount(nums, minlength=9).astype(np.uint64)

print(f'(better) answer to part 2: {(M**256 @ v).sum()}')

print(f'or after 100 000 days: {str((M.astype(object)**100_000 @ v.astype(object)).sum())[:100]}...<plenty more digits>')

In practice this is only helpful when dealing with modular numbers or something in a finite field. If we’re dealing with integers directly, they will grow at an exponential rate, meaning their bit length increase linearly, meaning the cost of each arithmetic operation actually goes up and becomes the dominant factor in our complexity analysis. The problem in calculating the number of fishes after, say, days, isn’t the number of “matrix multiplications” themselves, it’s actually the numbers themselves that grow too big to handle. But we can easily calculate the number of fishes after days modulo , say:

>>> (M**(10**100) @ v).sum()
10473238934407972448

Pshaw, That’s Hardly Math

Well, yes, sure. See Wikipedia for further study.