Juha-Matti Santala
Community Builder. Dreamer. Adventurer.

Advent of Code - 2021

This is a solution to Day 6 of Advent of Code 2021.

Day 6 - Lanternfish

The sea floor is getting steeper. Maybe the sleigh keys got carried this way?

A massive school of glowing lanternfish swims past. They must spawn quickly to reach such large numbers - maybe exponentially quickly? You should model their growth rate to be sure.

Although you know nothing about this specific species of lanternfish, you make some guesses about their attributes. Surely, each lanternfish creates a new lanternfish once every 7 days.

However, this process isn't necessarily synchronized between every lanternfish - one lanternfish might have 2 days left until it creates another lanternfish, while another might have 4. So, you can model each fish as a single number that represents the number of days until it creates a new lanternfish.

Furthermore, you reason, a new lanternfish would surely need slightly longer before it's capable of producing more lanternfish: two more days for its first cycle.

So, suppose you have a lanternfish with an internal timer value of 3:

  • After one day, its internal timer would become 2.
  • After another day, its internal timer would become 1.
  • After another day, its internal timer would become 0.
  • After another day, its internal timer would reset to 6, and it would create a new lanternfish with an internal timer of 8.
  • After another day, the first lanternfish would have an internal timer of 5, and the second lanternfish would have an internal timer of 7.

A lanternfish that creates a new fish resets its timer to 6, not 7 (because 0 is included as a valid timer value). The new lanternfish starts with an internal timer of 8 and does not start counting down until the next day.

Realizing what you're trying to do, the submarine automatically produces a list of the ages of several hundred nearby lanternfish (your puzzle input). For example, suppose you were given the following list:

3,4,3,1,2

This list means that the first fish has an internal timer of 3, the second fish has an internal timer of 4, and so on until the fifth fish, which has an internal timer of 2. Simulating these fish over several days would proceed as follows:

Initial state: 3,4,3,1,2
After  1 day:  2,3,2,0,1
After  2 days: 1,2,1,6,0,8
After  3 days: 0,1,0,5,6,7,8
After  4 days: 6,0,6,4,5,6,7,8,8
After  5 days: 5,6,5,3,4,5,6,7,7,8
After  6 days: 4,5,4,2,3,4,5,6,6,7
After  7 days: 3,4,3,1,2,3,4,5,5,6
After  8 days: 2,3,2,0,1,2,3,4,4,5
After  9 days: 1,2,1,6,0,1,2,3,3,4,8
After 10 days: 0,1,0,5,6,0,1,2,2,3,7,8
After 11 days: 6,0,6,4,5,6,0,1,1,2,6,7,8,8,8
After 12 days: 5,6,5,3,4,5,6,0,0,1,5,6,7,7,7,8,8
After 13 days: 4,5,4,2,3,4,5,6,6,0,4,5,6,6,6,7,7,8,8
After 14 days: 3,4,3,1,2,3,4,5,5,6,3,4,5,5,5,6,6,7,7,8
After 15 days: 2,3,2,0,1,2,3,4,4,5,2,3,4,4,4,5,5,6,6,7
After 16 days: 1,2,1,6,0,1,2,3,3,4,1,2,3,3,3,4,4,5,5,6,8
After 17 days: 0,1,0,5,6,0,1,2,2,3,0,1,2,2,2,3,3,4,4,5,7,8
After 18 days: 6,0,6,4,5,6,0,1,1,2,6,0,1,1,1,2,2,3,3,4,6,7,8,8,8,8

Each day, a 0 becomes a 6 and adds a new 8 to the end of the list, while each other number decreases by 1 if it was present at the start of the day.

In this example, after 18 days, there are a total of 26 fish. After 80 days, there would be a total of 5934.

Read input

This time our input is once again bit different as instead of every value being on its own line as usual, it's all on one line.

Since our read_input returns a list of inputs, we need to remember to only operate on the first item.

from utils import read_input

def transformer(line):
    return [int(v) for v in line.split(',')]
    
lanternfish = read_input(6, transformer)[0]

Part 1

Find a way to simulate lanternfish. How many lanternfish would there be after 80 days?

In this first part, we need to simulate 80 days of lanternfish mating season.

We loop over the amount of days we want to simulate and each time check if there's need for baby lanternfish (causing a reset on mating timer) or if the mating timer should tick down.

I added debug flag to make it easier to see where mistakes happen when running with a smaller input.

def simulate(fishes, days, debug=False):
    # I'm creating a copy of the original list here 
    # since we're modifying the list in place
    fishes = fishes[:]
    if debug: print(f'Initial state: {fishes}')
    for day in range(days):
        for idx, fish in enumerate(fishes):
            if fish == 0:
                fishes.append(9)
                fishes[idx] = 6
            else:
                fishes[idx] = fish - 1
    if debug: print(f'After day {day + 1}: {fishes}')
    return len(fishes)


result = simulate(lanternfish, 80)
assert result == 380243
print(f'Solution: {result}')

Solution: 380243

Part 2

How many lanternfish would there be after 256 days?

I initially just ran the previous simulate function with 256 days and turns out, the list grows so fast that each day simulates slower and slower to the point that running it for 256 days is not viable.

After running into that, I immediately knew that dictionaries are the way to save me. If I learned one thing in university, it's that whenever you need performance, dictionaries are the way to go. And since we're only interested in days until giving birth and everyone advances at the same rate, we can keep track of how many lanternfish are at any given stage and thus only ever need to loop over 0..8 range rather than an evergrowing list of each individual fish.

We've stripped the fish their individuality and personality and just count them as resources. It's a sad world.

Counter and defaultdict

Python's standard library has really nice special cases of dictionaries that make writing and reading code so much easier. I already used Counter in an earlier puzzle but didn't say anything about it.

Counter is a special dictionary that is created with an input of an iterator (list, dictionary, string, etc) and it creates a dictionary to which it counts how many times each iterable was included.

from collections import Counter
ages = [27, 30, 30, 28, 31, 27]
print(Counter(ages))
## Counter({27: 2, 28: 1, 30: 2, 31: 1})

It also provides a few additional functions: for example it gives you back the items as a list with elements(), provides n most common values with most_common(n) and so on. Check the docs for all of them.

defaultdict is another favorite of mine. It's a dictionary that doesn't error out when key does not exist but rather returns the default value for the type its created with.

In the code below, I create a defaultdict(int) so we don't have to take into account any special cases for when certain days would result in missing populations. It enables operations like new_population[key] += 100 even when key does not exist in new_population as it will default to 0.

Less if cases to check if a key exists or not. Easier to read code. Win-win.

from collections import Counter, defaultdict

def efficient_simulate(fishes, days):
    population = Counter(fishes)
    for day in range(days):
        new_population = defaultdict(int)
        for mating_timer in population:
            if mating_timer == 0:
                new_population[8] = population[0]
                new_population[6] += population[0]
            else:
                new_population[mating_timer - 1] += population[mating_timer]
        population = new_population
    
    pop_count = sum(pop_count for pop_count in population.values())
    return pop_count

result = efficient_simulate(lanternfish, 256)
assert result == 1708791884591
print(f'Solution: {result}')

Solution: 1708791884591

Wrap up

So far this has been the easiest and most straight-forward of the puzzles for me.