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_timerswhich 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
- reduce the timer time by 1
- if timer == 0:
- NOTE: As an implementation detail, NEVER add/remove elements from the list you are iterating over. This is why we have a new
new_timerslist that we extend the
current_timersby, 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.split(','))) TIMER_START = 6 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 new_timers.append(TIMER_START+2) else: current_timers[i] = timer - 1 current_timers.extend(new_timers) return len(current_timers) print(solve(get_input()))
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.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 TIMER_START = 6 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 new_counter[TIMER_START] += counter else: # we move the counts from THIS time to the PREVIOUS time new_counter[time-1] += counter[time] counter = new_counter return sum(counter.values()) print(solve(get_input()))
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Furthest Building You Can Reach | LeetCode | Solution Explained
January 20, 2022
Burst Balloons | LeetCode | Solution Explained
January 1, 2022