Advent of Code: Day 6

Day 6 is my top favorite in terms of mathematical optimization so far.

Part 1

There are many lanternfish at the sea floor. Each lanternfish has an internal timer that is in a range from 0 to 6. This timer decreases by 1 every day. However, when the timer is 0 and ticks to the next day, it will become 6 instead and a new lanternfish is created! This new lanternfish has a timer of 8.

You're given an input of lanternfish, decoded by their timer. For example, 3,4,3,1,2. Your goal is to find out how many total lanternfish after 80 days.

Thus, my solution is so:

def read(filename):
    file = open(filename)
    fishes = list(map(int, file.read().split(',')))

    return fishes


def solve(fishes):
    for day in range(80):
        for i in range(len(fishes)):
            # Grow
            if fishes[i] == 0:  # breed
                fishes[i] = 6
                fishes.append(8)
                continue

            fishes[i] -= 1

    print(len(fishes))
    return


fishes = read('input.txt')
solve(fishes)

Part 2

Surprisingly, Part 2 doesn't introduce any new mechanics. It simply asks you the same question: how many lanternfish are there after 256 days? So the only detail that changed is the days.

Naively, I changed the days variable into 256 and hit run. A decade later, it still didn't finish. I knew then something was up.

It turned out that the real challenge of this puzzle is memory limit and processing speed. Since the lanternfish grow exponentially, after roughly 100 days, the drag kicked in. My computer couldn't process the growth of these creatures efficiently anymore.

After a session of penning on my notebook, I discovered an elegant solution, a purely mathematical one: Let's call f(x) is the number of lanternfish at timer x. Then after every day, f(x) becomes f(x + 1) with f[8] = f[0] (new fish bred) and f[6] += f[0] due to timer reset from breeding.

This f(x) allows me from maintaining a list of billions of lanternfish to an f(x) list of just 9 members. The solution is now therefore:

def read(filename):
    file = open(filename)
    fishes = list(map(int, file.read().split(',')))

    return fishes


def solve(fishes):
    # Call f(x) is the number of fish at timer x
    f = [0] * 9
    for fish in fishes:
        f[fish] += 1

    for day in range(256):
        f_zero = f[0]
        # Fish decrease value
        for x in range(8):
            f[x] = f[x + 1]

        # Fish 0 breeds new and become 6
        f[6] += f_zero
        f[8] = f_zero

    print(sum(f))
    return


fishes = read('input.txt')
solve(fishes)