Continuing our Advent of Code adventure from last time. Let’s see what the next batch of puzzles has in store.
Day 6
Simulating the life cycles of lanternfish… My implementation for part 1 was naive: I just keep a list of fish, and update/extend the list at every step:
def simulate(days: int) -> int:
with open('input.txt', 'r') as f_input:
fish = list(map(lambda x: int(x), f_input.readline().split(',')))
for _ in range(days):
new_fish_count = 0
for i, f in enumerate(fish):
if f == 0:
fish[i] = 6
new_fish_count += 1
else:
fish[i] -= 1
if new_fish_count > 0:
fish.extend([8 for _ in range(new_fish_count)])
return len(fish)
This does work, but after completing part 1 we are hit with AoC’s infamous “part 2 is just part 1, but more steps”. We don’t have to do anything different for part 2; we just have to simulate 256 days instead of 80.
The original naive implementation doesn’t scale to this size, as even assuming 1 byte per fish, the final list would require twice as much RAM as I have in this computer. Not to mention constantly enumerating and updating this giant list becomes undoable long before that.
After some deep pondering, I realized that we don’t have to keep the list of all individual fish at all; we just have to keep track of how many fish there are of each age, and update these numbers at each step. The new simulation function then becomes:
def simulate(days: int) -> int:
with open('input.txt', 'r') as f_input:
fish = list(map(lambda x: int(x), f_input.readline().split(',')))
# map of the number of fishes for each age (age can be 0..8)
fish_age_count = defaultdict(lambda: 0)
for f in fish:
fish_age_count[f] += 1
for _ in range(days):
fish_age_count_new = {}
# aging for fishes 1..8 -> simply age by 1 day
for i in range(1, 9):
fish_age_count_new[i - 1] = fish_age_count[i]
# aging for fishes 0 -> create new fishes with age 8, then add to population of age 6
fish_age_count_new[6] += fish_age_count[0]
fish_age_count_new[8] = fish_age_count[0]
for i in range(9):
fish_age_count[i] = fish_age_count_new[i]
return sum([fish_age_count[i] for i in range(9)])
This runs pretty much instantly for both parts.
Day 7
This one wasn’t very interesting to me. It’s more a math/statistics question as opposed to a programming puzzle.
For part 1, I guessed that we needed either the mean or the median. I tried both on the example, and it turned out we needed the median. I applied that to my input, and apparently got the right answer. Great.
import statistics
with open('input.txt', 'r') as f_input:
positions = list(map(lambda x: int(x), f_input.readline().split(',')))
def solution_part_1():
target = int(statistics.median(positions))
print(sum([abs(p - target) for p in positions]))
Part 2 was more guesswork on my part.
First, the new movement cost. I suspected there would be some easy way of computing it, so I literally googled “1+2+3+4” and to my surprise found a Wikipedia article of the same name, which gave me the movement cost formula.
def movement_cost(x: int) -> int:
return (x * (x + 1)) // 2
Bruteforcing a whole bunch of positions wouldn’t be very efficient, so I again made an assumption and guessed that the optimal position would be somewhere close to the mean. So I did a kind of guided brute-force around that guess, and again got the correct answer.
def solution_part_2():
mean_pos = int(statistics.mean(positions))
print(min(
[sum(
[movement_cost(abs(p - t)) for p in positions]
) for t in range(mean_pos - 10, mean_pos + 10)] # guess that the best pos is somewhere close to mean
))
I leaned nothing today.
Day 8
Again, it wasn’t really about programming today. This one is more of a logic puzzle.
I spent a decent amount of time up front to figure out how to decode the numbers, and programmed that deduction logic into a class:
class InputLine:
def __init__(self, l: str):
split = l.split(' ')
self.patterns = split[:10]
self.output = split[-4:]
self.digit_map = {}
# 1 is the only 2-segment number
enc_1 = next(x for x in self.patterns if len(x) == 2)
self.digit_map[''.join(sorted(enc_1))] = 1
# 7 is the only 3-segment number
enc_7 = next(x for x in self.patterns if len(x) == 3)
self.digit_map[''.join(sorted(enc_7))] = 7
# 4 is the only 4-segment number
enc_4 = next(x for x in self.patterns if len(x) == 4)
self.digit_map[''.join(sorted(enc_4))] = 4
# 8 is the only 7-segment number
enc_8 = next(x for x in self.patterns if len(x) == 7)
self.digit_map[''.join(sorted(enc_8))] = 8
# 5-segment numbers: 2, 3, 5
# 6-segment numbers: 0, 6, 9
# 6 is the only 6-segment number that is not a superset of 7
enc_6 = next(x for x in self.patterns if len(x) == 6 and not set(x) > set(enc_7))
self.digit_map[''.join(sorted(enc_6))] = 6
# 5 is the only 5-segment number that is a subset of 6
enc_5 = next(x for x in self.patterns if len(x) == 5 and set(x) < set(enc_6))
self.digit_map[''.join(sorted(enc_5))] = 5
# 0 is the only 6-segment number that is not a superset of 5
enc_0 = next(x for x in self.patterns if len(x) == 6 and not set(x) > set(enc_5))
self.digit_map[''.join(sorted(enc_0))] = 0
# 3 is the only 5-segment number that is a superset of 7
enc_3 = next(x for x in self.patterns if len(x) == 5 and set(x) > set(enc_7))
self.digit_map[''.join(sorted(enc_3))] = 3
# 9 is the only 6-segment number that is a superset of 3
enc_9 = next(x for x in self.patterns if len(x) == 6 and set(x) > set(enc_3))
self.digit_map[''.join(sorted(enc_9))] = 9
# 2 is the only 5-segment number that is not a subset of 9
enc_2 = next(x for x in self.patterns if len(x) == 5 and not set(x) < set(enc_9))
self.digit_map[''.join(sorted(enc_2))] = 2
def value(self) -> int:
v = 0
v += self.digit_map[''.join(sorted(self.output[0]))] * 1000
v += self.digit_map[''.join(sorted(self.output[1]))] * 100
v += self.digit_map[''.join(sorted(self.output[2]))] * 10
v += self.digit_map[''.join(sorted(self.output[3]))]
return v
input_lines = []
with open('input.txt', 'r') as f_input:
for line in f_input:
input_lines.append(InputLine(line.rstrip()))
And that’s basically it.
For part 1, we just count the number of times the unique-length digits occur:
def solution_part_1():
print(sum([len([o for o in l.output if len(o) in [2, 3, 4, 7]]) for l in input_lines]))
Then for part 2, we sum the actual values:
def solution_part_2():
print(sum([l.value() for l in input_lines]))
gg, ez.
Day 9
This one is a bit more interesting. We have a hightmap (basically a grid), and we have to find out some of its properties.
First, parse the input:
# (0,0) is top-left
heightmap = []
with open('input.txt', 'r') as f_input:
for line in f_input:
heightmap.append(list(map(lambda x: int(x), line.rstrip())))
height = len(heightmap)
width = len(heightmap[0])
To make things slightly less confusing, I also add a helper function to get the value for a given x-y position:
def value(x: int, y: int) -> int:
return heightmap[y][x]
For the first part, we need to find all local minima, which are points that are lower than all of their neighbors. We’ll first create a helper function to fetch the values of a point’s neighbors:
def neighbor_values(x: int, y: int) -> List[int]:
n_list = []
# top
if y > 0:
n_list.append(value(x, y - 1))
# bottom
if y < height - 1:
n_list.append(value(x, y + 1))
# left
if x > 0:
n_list.append(value(x - 1, y))
# right
if x < width - 1:
n_list.append(value(x + 1, y))
return n_list
Then, the local-minimum function is pretty simple:
def is_local_minimum(x: int, y: int) -> bool:
point_value = value(x, y)
return all([p > point_value for p in (neighbor_values(x, y))])
For part 1, we then just sum the values of all local minima:
def solution_part_1():
risk = 0
for i_x in range(width):
for i_y in range(height):
if is_local_minimum(i_x, i_y):
risk += 1 + value(i_x, i_y)
print(risk)
That was pretty easy, but part 2 gets a bit more tricky. Now we have to find the three largest basins, which are areas on the grid enclosed by points with value 9.
For this I just loop through all points in the grid, and from each point that I haven’t seen yet, I start a BFS along its neighbors, stopping when I hit the borders or nodes with value 9. I first need a second neighbor function that returns coordinates instead of values:
def neighbor_coords(x: int, y: int) -> List[Tuple[int, int]]:
n_list = []
# top
if y > 0:
n_list.append((x, y - 1))
# bottom
if y < height - 1:
n_list.append((x, y + 1))
# left
if x > 0:
n_list.append((x - 1, y))
# right
if x < width - 1:
n_list.append((x + 1, y))
return n_list
I then go through the whole grid, add all of the basins I find to a list, and then sort by length to get the top 3.
def solution_part_2():
seen = set()
basins = []
for i_x in range(width):
for i_y in range(height):
n_v = value(i_x, i_y)
if n_v == 9 or (i_x, i_y) in seen:
continue
seen.add((i_x, i_y))
basin = [(i_x, i_y)]
to_check = Queue()
for n in neighbor_coords(i_x, i_y):
if n not in seen:
to_check.put(n)
seen.add(n)
while to_check.qsize() > 0:
n = to_check.get()
n_x, n_y = n
n_v = value(n_x, n_y)
if n_v == 9:
continue
basin.append(n)
for n in neighbor_coords(n_x, n_y):
if n not in seen:
to_check.put(n)
seen.add(n)
basins.append(basin)
basins.sort(key=len)
print(len(basins[-1]) * len(basins[-2]) * len(basins[-3]))
The key to this solution, besides the BFS, was using a set instead of a list to keep track of seen nodes, which drastically improved runtime.
Day 10
This one was fun. After all, dealing with mismatched brackets is part of a programmer’s daily routine. As such, it was immediately obvious to me that all we needed was a stack to create a simple scoring function for part 1:
from collections import deque
bracket_pairs = {('(', ')'), ('[', ']'), ('{', '}'), ('<', '>')}
def score_illegal(line: str) -> int:
brackets = deque()
for c in line:
if c in ('(', '[', '{', '<'):
brackets.append(c)
else:
c_open = brackets.pop()
c_pair = (c_open, c)
if c_pair not in bracket_pairs:
match c:
case ')':
return 3
case ']':
return 57
case '}':
return 1197
case '>':
return 25137
return 0
Here we just find the first non-matching pair, and return the appropriate score.
We then just sum all the scores for part 1:
with open('input.txt', 'r') as f_input:
nav_prgm = [x.rstrip() for x in f_input.readlines()]
def solution_part_1():
print(sum([score_illegal(x) for x in nav_prgm]))
Part 2 is very similar, only this time we have to score the missing brackets. We read through the line and push/pop all brackets, and then end by scoring the remaining open brackets:
def score_incomplete(line: str) -> int:
brackets = deque()
for c in line:
if c in ('(', '[', '{', '<'):
brackets.append(c)
else:
brackets.pop() # assumes that this matches, and it's not an illegal line
score = 0
while len(brackets) > 0:
c = brackets.pop()
score *= 5
match c:
case '(':
score += 1
case '[':
score += 2
case '{':
score += 3
case '<':
score += 4
return score
We score all non-illegal lines this way, and then select the middle score:
def solution_part_2():
scores = []
for line in nav_prgm:
if score_illegal(line) == 0:
scores.append(score_incomplete(line))
scores.sort()
print(scores[len(scores) // 2])
And that’s another 5 days done!