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
TIMER_START+2
- else
- 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 thecurrent_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[0].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[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
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[0]
new_counter[TIMER_START] += counter[0]
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()))
Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.
Recommended Posts
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