Advent of Code Walkthroughs

Dazbo's Advent of Code solutions, written in Python

hydrothermal vents

Advent of Code 2021 - Day 6

Day 6: Lanternfish

Useful Links

Concepts and Packages Demonstrated

NumPydequerange

Counter

Problem Intro

Here I’ve documented three different approaches to this problem:

We’re told that lanternfish populations grow exponentially, and we’re asked to model the growth of the population. Each lanternfish spawns a new lanternfish every 7 days, except for new lanternfish, which require an extra 2 days before spawning a new fish.

Our input data is a list of numbers, which are the number of days left until each fish spawns another fish. The data looks like this:

3,4,3,1,2

Part 1

Given our input data, how many lanternfish will there be after 80 days?

Solution #1

At first glance, this seems like a simple problem. The naive approach is short and easy to write. Alas, as we’ll see, it has a problem!

We create list of fish_timers from the input data, where each timer is the number of days until the next spawn. With each day, we update the existing fish timers, and add the new timers.

input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
with open(input_file, mode="rt") as f:
    data = f.read()
    
fish_timers = list(map(int, data.split(",")))
logger.debug(fish_timers)   # E.g. [3,4,3,1,2]

fish_timers_copy = fish_timers.copy()
days = 80
for _ in range(1, days+1):
    # we can't enumerate since we don't extra iterations when we spawn
    for i in range(len(fish_timers_copy)):
        if fish_timers_copy[i] == 0:
            fish_timers_copy[i] = 6     # reset this fish timer
            fish_timers_copy.append(8)  # spawn a new fish
        else:
            fish_timers_copy[i] -= 1    # decrement this fish timer

logger.info("After %d days, there are %d fish", days, len(fish_timers_copy))   

The code above reads in the input data, splits it at the commas, and then converts each value to an int. Nothing new there.

First, we make a copy of the fish_timers. This is just so that we can use the same original input list when we do part 2.

Then we iterate through 80 days. Note that in this for loop, we store each day in the variable _. This is a convention in Python: if we’re not interested in this variable, and we’re not going to use it, then we use the value _.

Then, for each day, we now iterate through each fish_timer (i.e. each fish), and do the following:

And for Part 1, this approach works fine!

2022-01-09 22:11:00.555:INFO:__main__:  After 80 days, there are 376194 fish

Part 2.

Now we’re simply asked to determine how many fish there will be after 256 days.

This presents us with a predictable problem. Our naive solution doesn’t scale!

Number of days Time to solve
80s0.5s
90s1.1s
100s3.1s
110s6.7s
120s17s

If we extrapolate, this is going to take days to run! We need a different approach.

Solution #2

At this point, it’s obvious we can’t model every fish. We actually only need to track how many there of each timer, e.g. how many fish are spawning now, how many are 1 day away, how many are 2 days away, etc.

Solving the Problem

Here we can read the source data directly into a numpy array, using np.loadtxt. We split the numbers at the commas, and convert each number to an int using dtype=np.int8.

input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)

# read input, which is csv of ints
# Each value is a fish timer, i.e. days until spawning another fish  
data = np.loadtxt(input_file, delimiter=",", dtype=np.int8) # [3 4 3 1 2]

Then we use np.unique() with the return_counts=True attribute to return all the unique fish timers in the input data, and count them all.

# np.unique() returns ordered unique items.  With return_counts=True, it includes counts.
# Timers [1 2 3 4], counts [1 1 2 1]
init_fish_timers, counts = np.unique(data, return_counts=True)

We know there will be timers for all values 0-8 inclusive. Our input data may not include all of these types of timers. So let’s create a one dimensional numpy array of size 9 (i.e. 0-8 inclusive), and initialise all the values to 0. This represents our counters for each fish timer.

Then we can update this ‘zero’ array using the counts we previously obtained from the input data. This works by using the init_fish_timers to find all the corresponding index positions in fish_timers, and then updating value at that position by using the corresponding position in the counts array.

# Initialise fish timers, by setting index positions to the counts in the array  
fish_timers = np.zeros(9, dtype=np.uint64)     # [0 0 0 0 0 0 0 0 0]
fish_timers[init_fish_timers] = counts         # [0 1 1 2 1 0 0 0 0]

Now we create a get_fish_count() function, which returns the number of fish after the required number of days. It works by:

def get_fish_count(fish_timers: np.ndarray, day_num: int) -> int:
    fish = np.copy(fish_timers)    # create a new copy so we don't mutate the original fish
    for _ in range(day_num):
        fish = np.roll(fish, -1)  # Roll: 2 becomes 1, 1 becomes 0, 0 becomes 8 (spawned fish)  
        fish[6] += fish[8]    # Add fish that were 0 are now reset to 6.
    
    return sum(fish)

We can now call this function with both 80 and 256, thus solving both Part 1 and Part 2:

for day in (80, 256):
    logger.info("At day %d, count=%d", day, get_fish_count(fish_timers, day))

The output looks like this:

2022-01-09 22:58:19.820:INFO:__main__:  At day 80, count=376194
2022-01-09 22:58:19.830:INFO:__main__:  At day 256, count=1693022481538
2022-01-09 22:58:19.831:INFO:__main__:  Execution time: 0.0353 seconds

It’s quite quick!

Solution #3

This solution is super fast!

We don’t need numpy. We can achieve the same results using a Counter and a deque.

First, read the data, split it at the commas, convert each value to int, and then store the counts of each type of fish timer:

input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
with open(input_file, mode="rt") as f:
    data = f.read()

data = [int(x) for x in data.split(",")]
fish_timer_counts = Counter(data) # count the timers for each fish

Now we create a deque that contains our nine timer values, 0-8 inclusive. The values are initialised to 0 if there weren’t any in the input data. Else, we use the counts from the input data.

# initialise an array of timer counts, for all timer values 0-8    
timers = deque()
for timer in range(9):
    timers.append(fish_timer_counts[timer] if fish_timer_counts[timer] else 0)

As before, we have a get_fish_count() function. It does the following:

for days in (80, 256):
    logger.info("Fish at day %d: %d", days, get_fish_count(timers, days))

def get_fish_count(timers: deque, days: int):
    fish = timers.copy()    # just so we can repeat this method with a different # of days
    
    for _ in range(days):
        fish.rotate(-1)
        fish[6] += fish[8]  # count of newly spawned fish is same as count of fish that need to be reset
        
    return sum(fish)    

Output:

2022-01-09 22:59:06.606:INFO:__main__:  Fish at day 80: 376194
2022-01-09 22:59:06.607:INFO:__main__:  Fish at day 256: 1693022481538
2022-01-09 22:59:06.608:INFO:__main__:  Execution time: 0.0027 seconds

Yep, under 3ms. Pretty quick!