# 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 $O(days)$ solution.

## Math Is Awesome

With just a tiny bit of practical math (matrices) we can get an $O(gd)$ 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, $2_{64}=18446744073709551616$ 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 $10_{100}$ days modulo $2_{64}$, say:

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

## Pshaw, That’s Hardly Math

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