AoC 2021 - Day 6

Today’s challenge is here. We have to find the amount of fish ‘split’ after some days. A problem based on exponential growth.

When I started doing this challenge I first thought about using Object-Oriented Programming, but that didn’t work out. When calculating large amounts of fish I started to run out of memory and the algorithm was too slow.

Loading the data:

def load() -> list[int]:
    with open('../.input/day06') as f:
        return [int(line) for line in f.read().split(",")]

Task 1

Pretty simple, we just need to advance the fish and then count the amount of fish. I created simple methods in the LanternFish class that do just that.

Here’s a class that represents a fish:

class LanternFish:
    def __init__(self, cycle: int, current: int = None):
        self.cycle = cycle
        self.current = current or cycle
        self.children = []

    def advance(self) -> None:
        self.current -= 1
        [child.advance() for child in self.children]
        if self.current == -1:
            self.current = self.cycle
            self.children.append(LanternFish(cycle=6, current=8))

    def count(self) -> int:
        return 1 + sum([child.count() for child in self.children])

Here we iterate through number of days and advance the fish. The way fishes are related to each other is that they all form a tree. When I advance a fish, I also advance all of its children. The amount of fish is the sum of the amount of fish in the tree.

def solve1() -> int:
    fishes = [LanternFish(cycle=6, current=init) for init in load()]
    [[fish.advance() for fish in fishes] for _ in range(80)]
    return sum([fish.count() for fish in fishes])

Task 2

Here I took a different approach, I stored the fishes in a simple dictionary. The key is the day and the value is the number of fishes. I then iterate through the days and advance the fishes.

The way this works is kind of hard to explain really, but the key to it all is the % modulo operator. The modulo operator returns the remainder of a division. In this case, the modulo operator is used to determine whether some fish should give birth.

def solve2() -> int:
    fishes = { i: 0 for i in range(7) }
    newborns = { i: 0 for i in range(9) }

    for init in load():
        fishes[init] += 1

    for epoch in range(256):
        born_from_old = fishes[epoch % 7]
        fishes[epoch % 7] += newborns[epoch % 9]
        newborns[epoch % 9] += born_from_old

    return sum(fishes.values()) + sum(newborns.values())