day-6

Solution in Python for the day 6 puzzle of the 2021 edition of the Advent of Code annual programming challenge.

🎄🌟🌟 Lanternfish 🎄🌟🌟

🔍📖 Annotated Puzzle Statement

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.

The emphasis on the word exponentially is not innocent. We can expect some sort geometric list processing.

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.

The lanternfish's internal timer can be computed by doing a modulo of itself with 7, however further down we have:

The new lanternfish starts with an internal timer of 8 and does not start counting down until the next day.

This means that a modulo 7 will not work due to returning zero instead of seven. A solution would consist on using a classic method for updating the timer value:

SPAWN_TIME = 7

def update_timer(timer: int) -> int:
    if timer == 0:
        timer = SPAWN_TIME
    timer -= 1
    return timer

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

The iteration loop could be something like:

1. Count number of zeroed items
2. Update each item by decreasing its value by one a apply module seven
3. Append the counted number of times the number eight to the end of the list

💾🔍 Content Decoding

The input contents are a comma separated list of integers.

3,4,3,1,2

The goal is to obtain a list:

[3,4,3,1,2]

The corresponding method ending being one the simplest so far:

def load_contents(filename: Path) -> [int]:
    """Load and convert contents from file

    :param filename: input filename
    :return: coordinates
    """
    with open(filename, encoding='utf-8') as buffer:
        line = next(iter(buffer.readlines()))
        tokens = [int(t) for t in line.strip().split(',')]
        return tokens

💡🙋 Implementation

The first part is straightforward to implement, especially with a inner method which makes things quite neat.

def solve_part_one(contents: any) -> int:
    """Solve the first part of the challenge

    :param contents: input puzzle contents
    :return: expected challenge answer
    """
    def update_timer(timer: int) -> int:
        if timer == 0:
            timer = SPAWN_TIME
        return timer - 1

    lanternfishs = contents.copy()
    for _ in range(1, DURATION + 1):
        respawned = sum(1 for timer in lanternfishs if timer == 0)
        lanternfishs = [update_timer(timer) for timer in lanternfishs]
        lanternfishs.extend([8] * respawned)
    answer = len(lanternfishs)
    return answer

Contents	Command	Answer	Time
input.txt	./day_6.py input.txt -p 1	362639	5229.7 ms

😰🙅 Part Two

🥺👉👈 Annotated Statement

How many lanternfish would there be after 256 days?

The above solver implementation recomputes the data each day. Because the number of lanterfishes double every seven days we can deduce that the result will be roughly equal to 362639 * 2 ^ ((256-80) / 7) = 1.3×10^13 which obviously cannot be computed using the same method as above.

🤔🤯 Puzzle Solver

An interesting fact is that the number doubles every seven days. Applying some inverse logic means that we only need to compute the quantity corresponding to a modulo of to 256 by seven and multiplying the value at this age by two to the power of 256 divided by seven.

This leaves us with f(256) = f(256 % 7) * 2 ^ (256 // 7) = f(4) * 2**36. Right? Wrong! Problem is that newly spawned lanterfishes start with a timer set to eight, meaning that this formula doesn't stand. So back to the beginning.

📝 Note: When in doubt, stare at the data

It always pays to take a step back when facing a dead end. In practice this means taking a deeper look into the input contents of puzzle and extract some features. These are likely to open a path for solving with success the puzzle.

Doing a routing check on the highest lanternfish timer returns 5 on our dataset.

>>> max(lanterfishes)
5

This is quite a eye-opener because this means that there are likely to be just a few different values for the initial timers. This is a textbook case for using the Counter class.

from collections import Counter
c = Counter(lanternfishs)
c
Counter({1: 124, 4: 55, 5: 45, 2: 43, 3: 33})

Just like that the number of input data went from 300 down to 5, nearly two orders of magnitude less! Doing so we can compute up to approx 190 days in a several dozen of seconds. This is however not enough for reaching 256, meaning a further improvement is warranted.

For instance, there must be a way to mathematically compute the number of lanterfishes spawned from a single one depending on its initial timer value.

As a first step let us compute the number of lanternfishs directly spawned by a single one. The puzzle statement indicates it will spawn each time its timer hits zero.

def count_directly_spawned_lanternfishs(days: int, initial_timer: int) -> int:
    ...

The first one is spawned as soon as its timer hits zero, meaning that if the number of days is lower than the initial timer it will obviously have spawned none.

if (days < initial_timer):
    return 0

We also know that it spawns every seven days once the timer reaches zero.

total_days = days + (7 - initial_timer)
directly_spawned_lanterfishes = total_days // 7

Arranging variables we obtain the final form:

def count_directly_spawned_lanternfishs(days: int, initial_timer: int) -> int:
    total_days = days + (7 - initial_timer)
    return total_days // 7

We can now compute number of directly spawned lanterfishes from a single one with an intial timer of 1 after 256 days: 37. Next step is where we thrown in some recursion. 🤯

DEFAULT_TIMER = 8

def count_lanternfishs(days: int, start_day: int = 0,
                       initial_timer: int = DEFAULT_TIMER) -> int:
    lanternfishs: int = 1
    first_spawn_day = start_day + initial_timer + 1
    for current_day in range(first_spawn_day, days, SPAWN_TIME):
        lanternfishs += count_lanternfishs(days=days, start_day=current_day)
    return lanternfishs

Running on a single lanternfish we have the following runtimes:

Days	Duration (ms)	Answer
150	1449.9	460699
160	3396.1	1098932
170	7913.8	2690561
180	18087.8	6249351
190	43798.7	15164971

Sadly this new implementation is barely better than the original. Back to the drawing board.

Find a way to simulate lanternfish.

Reflecting on this line, we must change the way this problem was diced, meaning doing away with the recursion since it is a dead end. As it is often the case, the clue is in front of us.

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

The different timer values appear to be in a small range, with the highest timer in the input data set being 5. This means that rather treating each lanterfish as an individual, we could bundle all the lanterfishes with the same timer in an entry. The key to this entry obviously being its time value.

from collections import Counter, defaultdict

lanternfishes = defaultdict(int)
lanternfishes.update(dict(Counter(contents)))

The next thing is to implement to daily update logic:

• All the timer values are decremented by one, meaning all the lanterfishes of a timer value N are shifted to the timer value N-1
• All the lanternfishes with a timer value of -1 are immediately recycled (i.e added to the lanternfishes of timer 6) and spawn the same amount of lanternfishes with a timer of 8.

for day in range(1, 1+duration):
    for timer in range(-1, 8):
        lanternfishes[timer] = lanternfishes[timer+1]
    lanternfishes[6] += lanternfishes[-1]
    lanternfishes[8] = lanternfishes[-1]

This puzzle was great: it showcased the importance of understanding state changes rather then just modeling the behavior of individual elements. Factorizing was a good first step but once again states and their transition is the key.

Contents	Command	Answer	Time
input.txt	./day_6.py input.txt -p 2	1639854996917	4.4 ms