AoC 2021 Day 6: We All Glow Down Here

Source: Latternfish

Part 1: Simulate a population of lanternfish. Each fish is immortal, starts having children after 9 days, and has another child after 7 more days. Calculate the number of fish after 80 days.

I can almost guarantee that part 2 will be scaling up significantly, so the obvious answer of keeping a list of ages and simulating each will… probably get very slow. Instead, we don’t care at all about individual fish, let’s just keep their ages:

class School:
'''Represents a school of fish.'''

def __init__(self, fish):
'''Loads the given list of fish into a map of ages.'''

self.data = {
age: 0
for age in range(9)
}

for each in fish:
self.data[each] += 1

@staticmethod
def from_file(file: TextIO):
'''Load a school from a file-like object'''

fish = [
int(age)
for line in file
for age in line.split(',')
]

return School(fish)

def step(self):
'''

All fish increase in age by 1 tick
Fish that are of a spawning age reset to 7 days to spawn and create a new 9 day to spawn fish.

Remember 0 based indexing.
'''

# Remember how many fish are going to spawn
breeding = self.data[0]

# Increase age of each fish by 1
for age in range(1, 9):
self.data[age - 1] = self.data[age]

# Each fish that spawns moves to age 6 (don't overwrite previously age 7) and spawns a new one of age 8
self.data[6] += breeding
self.data[8] = breeding

def __str__(self):
'''Return a comma-delimited list of fish ages.'''

return ','.join(
str(age)
for age, qty in self.data.items()
for _ in range(qty)
)

def size(self):
'''Return the number of fish in the school.'''

return sum(qty for age, qty in self.data.items())


That really handles it. Most of it is bookkeeping: loading in the fish from a file, printing them nicely, and counting the len / number of fish. The interesting bit is step, where we have to be a little careful with ages:

• All fish age 1-8 increase in age 1 step (which means they are one step closer to breeding age)
• All fish age 0 revert to age 6 (which means 6 steps to breeding age) plus spawn a new one

If we count up, that means each number overwrites the one we’ve already done, which is fine.

And… that’s all we really need:

@app.command()
def main(ticks: int, file: typer.FileText):
school = School.from_file(file)

for i in range(ticks):
school.step()

print(school.size())


Run it for 80:

$python3 we-all-glow-down-here.py 80 input.txt 395627  Fin. Part 2: Run the simulation for 256 days. 😄 Called it. $ python3 we-all-glow-down-here.py 256 input.txt
1767323539209


And it’s barely any slower:

$python3 we-all-glow-down-here.py 80 input.txt 395627 # time 38854250ns / 0.04s$ python3 we-all-glow-down-here.py 256 input.txt
1767323539209
# time 38013958ns / 0.04s


Since the time to simulate is mostly taken up with loading/saving, the actual iterations are fast. Heck:

\$ time python3 we-all-glow-down-here.py 1000000 input.txt

11251...59768
1.12e37838

________________________________________________________
Executed in    3.22 secs    fish           external
usr time    3.13 secs   55.00 micros    3.13 secs
sys time    0.03 secs  652.00 micros    0.03 secs


1 MILLION generations in 3 seconds. I did add this to print the scientific notation:

size_string = str(school.size())
print(f'{size_string[0]}.{size_string[1:3]}e{len(size_string)}')


I tried to use f{school.size():e} first, but…

>>> print(f{school.size():e})
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
OverflowError: int too large to convert to float

>>> 1e37838
inf


Yeah. It’s too big for floating point numbers. Fun times!

Fun (subtle) problems with types

So this was an interesting error:

Traceback (most recent call last):
File "/Users/jp/Projects/advent-of-code/2021/06/we-all-glow-down-here.py", line 85, in <module>
app()
File "/opt/homebrew/lib/python3.9/site-packages/typer/main.py", line 214, in __call__
return get_command(self)(*args, **kwargs)
File "/opt/homebrew/lib/python3.9/site-packages/click/core.py", line 829, in __call__
return self.main(*args, **kwargs)
File "/opt/homebrew/lib/python3.9/site-packages/click/core.py", line 782, in main
rv = self.invoke(ctx)
File "/opt/homebrew/lib/python3.9/site-packages/click/core.py", line 1066, in invoke
return ctx.invoke(self.callback, **ctx.params)
File "/opt/homebrew/lib/python3.9/site-packages/click/core.py", line 610, in invoke
return callback(*args, **kwargs)
File "/opt/homebrew/lib/python3.9/site-packages/typer/main.py", line 500, in wrapper
return callback(**use_params)  # type: ignore
File "/Users/jp/Projects/advent-of-code/2021/06/we-all-glow-down-here.py", line 81, in main
print(len(school))
OverflowError: cannot fit 'int' into an index-sized integer


Any guesses?

It’s a bit subtle, but the problem is that len has to return an ‘index-sized integer’, not just any int. So once the size gets too large, I couldn’t use __len__ for the size of the school any more and why I changed to a .size() function instead.