Advent of Code 2021 | Day 6 | Solutions in Python3

I have shared the annotated code with solution explanation for Advent of Code 2021, Day 6 challenge.

Part 1: Logic

  • we start with a list of timers, current_timers which are values like: [3, 4, 3, 1, 2]
  • as we iterate over the timers
    • if timer == 0:
      • restart the current timer
      • add a new timer to the list, starting from TIMER_START+2
    • else
      • reduce the timer time by 1
  • NOTE: As an implementation detail, NEVER add/remove elements from the list you are iterating over. This is why we have a new new_timers list that we extend the current_timers by, for the next iteration.

Part 1: Code

def get_input():
    data = []
    with open("input.txt") as f:
        data = f.readlines()
    return data

def solve(data):
    # only the first line of the input file has the relevant data
    current_timers = list(map(int, data[0].split(',')))
    for _ in range(80):
        # for all the new fishes that have spawned
        new_timers = []
        for i, timer in enumerate(current_timers):
            if timer == 0:
                # when timer 0, reset the current timer
                current_timers[i] = TIMER_START
                # and spawn new timers, and set their own reference
                # starting timers
                current_timers[i] = timer - 1
    return len(current_timers)


Part 2: Logic

  • Running the code for 256 iterations should logically work. But, as population growth is exponential, the solution will simply take a long long time to complete
  • What can we do? One thing is to realize that we can not distinguish between two fishes of the same timer values.
  • We can simply group together fishes with the same value, in a dictionary like format: counter[time] = number of fishes with the timer set to "time"
  • This way our total length of the data structure is no longer increasing exponentially. Why?
  • We only have 8 distinct values for the times 😀

Part 2: Code

from collections import defaultdict

def get_input():
    data = []
    with open("input.txt") as f:
        data = f.readlines()
    return data

def solve(data):
    current_timers = list(map(int, data[0].split(',')))
    # stores frequency of each time
    # aka counter[time]: #fishes
    # or the number of fishes at the given time, "time"
    counter = defaultdict(int)
    for time in current_timers: counter[time] += 1

    for _ in range(256):
        new_counter = defaultdict(int)
        # for all the new fishes that have spawned
        for time in counter:
            if time == 0:
                # all the current fishes at time 0 restart their counters
                # from TIMER_START &&
                # they spawn new fishes with timer starting from TIMER_START+2
                new_counter[TIMER_START+2] += counter[0]
                new_counter[TIMER_START] += counter[0]
                # we move the counts from THIS time to the PREVIOUS time
                new_counter[time-1] += counter[time]
        counter = new_counter

    return sum(counter.values())


Avatar for Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.