Advent of Code 2021
~ ~ ~ ~~ ~~~~~~~~~~~~~~~
..''''
. . :
. . .' ....'
I'll be posting here my solutions for AoC 2021. Follow along!
Table of contents
Day 1: Sonar Sweep
https://adventofcode.com/2021/day/1
For part 1, we're given a list of numbers and are asked how many times the numbers increase relatively to the previous number. The solution is pretty straightforward: loop over the list, compare each item with the previous, count the occurrence where it's greater than the previous:
from pathlib import Path
def part_1():
with open(Path(__file__).parent / "input.txt") as file:
previous = int(file.readline())
increases = 0
for value in map(int, file):
increases += value > previous
previous = value
return increases
For part 2, we're asked to consider the sum of a three-measurement sliding window. I thought I would need a deque
to keep a list of 3 values, or use list comprehension + slices, when I remembered about these recipes in the python docs. I copied over an implementation for a generator of these windows and used for my solution:
import collections
from itertools import islice
from pathlib import Path
def sliding_window(iterable, n):
# sliding_window('ABCDEFG', 4) -> ABCD BCDE CDEF DEFG
it = iter(iterable)
window = collections.deque(islice(it, n), maxlen=n)
if len(window) == n:
yield tuple(window)
for x in it:
window.append(x)
yield tuple(window)
def part_2():
with open(Path(__file__).parent / "input.txt") as file:
it = sliding_window(map(int, file), 3)
previous = next(it)
increases = 0
for window in it:
increases += sum(window) > sum(previous)
previous = window
return increases
For the next days, I'm adding more-itertools
to have these recipes readily available!
Check my repository for the final code for day 1. See y'all tomorrow!
Day 2: Dive!
https://adventofcode.com/2021/day/2
Today, we're piloting a submarine, which has a planned course defined by a series of instructions (our input):
forward X
increases the horizontal position byX
units.down X
increases the depth byX
units.up X
decreases the depth byX
units.
I think this looks neat with Python 3.10's structural pattern matching:
horizontal = depth = 0
for command in file:
match command.split(" "):
case ["forward", distance]:
horizontal += int(distance)
case ["up", distance]:
depth -= int(distance)
case ["down", distance]:
depth += int(distance)
return horizontal * depth
The puzzle claim that the result doesn't make sense, and when checking the submarine manual we notice the intructions track not only horizontal position and depth, but also aim, and the commands are also entirely different:
down X
increases your aim byX
units.- up X decreases your aim by
X
units. - forward X does two things:
- It increases your horizontal position by
X
units. - It increases your depth by your aim multiplied by
X
.
- It increases your horizontal position by
The solution looks a lot like part 1, but tracking the new aim
variable:
horizontal = depth = aim = 0
for command in file:
match command.split(" "):
case ["forward", distance]:
horizontal += int(distance)
depth += int(distance) * aim
case ["up", distance]:
aim -= int(distance)
case ["down", distance]:
aim += int(distance)
return horizontal * depth
The final solution for day 2 is in my aoc repository!
Day 3: Binary Diagnostic
https://adventofcode.com/2021/day/2
On day 3, we're running diagnostics on the submarine. Our puzzle input is a list of binary number that can be decoded into information about the submarine. For part 1, we're checking power consumption by calculating two values: the game rate, determined by finding the most common bit in the corresponding position of all numbers in our input; and the epsilon rate, calculated similarly, but by finding the less common bit.
My solution was a straighforward translation of the requirements into python code. I used collection.Counter
s to count the bits for each position, retrieving the value using Counter.most_common
.
LENGTH = 12 # size of numbers in the report
report = [line.strip() for line in file]
def count(report: Iterable[str], position: int) -> Counter[str]:
return Counter([value[position] for value in report])
counters: list[Counter[str]] = []
for position in range(LENGTH): # O(LENGTH)
counters.append(count(report, position)) # O(n)
gamma = [counter.most_common()[0][0] for counter in counters]
epsilon = [counter.most_common(2)[1][0] for counter in counters]
return list_of_bits_to_int(gamma) * list_of_bits_to_int(epsilon)
Next, we're checking the life support rating, again by calculating two numbers, the oxygen generator rating and the CO2 scrubber rating. To be honest, the description of how to locate these values will be much more clear in the actual puzzle than I'd be able to summarize. Let me just show you the code:
report = list(parse(file))
oxygen_report = co2_report = report # keep a reference of the original reports
for position in range(LENGTH):
counter = count(oxygen_report, position) # count the bits at the posstion
most_common, total = counter.most_common()[0]
if len(oxygen_report) % 2 == 0 and total == len(oxygen_report) / 2:
most_common = "1" # tie breaker
if len(oxygen_report) != 1: # filter out the numbers in the report that matches the most common
oxygen_report = [
value for value in oxygen_report if value[position] == most_common
]
for position in range(LENGTH):
# same deal as the above--but we're filtering out the numbers that match the less common bit
counter = count(co2_report, position)
most_common, total = counter.most_common()[0]
if len(co2_report) % 2 == 0 and total == len(co2_report) / 2:
most_common = "1"
if len(co2_report) != 1:
co2_report = [
value for value in co2_report if value[position] != most_common
]
return list_of_bits_to_int(oxygen_report[0]) * list_of_bits_to_int(co2_report[0])
On day 3 I basically translated the requirements to python--I was surprised there weren't a lot of bitwise trickery to get to the solution. Now we wait for day 4. Eric likes to make us work on the weekends with these puzzles (See https://adventofcode.com/2020/day/5, https://adventofcode.com/2020/day/12...), so I'll be waiting for some fun work tomorrow.
Check the full solution here!
Day 4: Giant Squid
https://adventofcode.com/2021/day/4
As expected, a lot of work for me today, having to figure out a data model for storing a board of bingo. I won't go over the process to get to this class a lot, there are some duplicated data and for-loops that can be optimized, but I got to a solution and I think the class is pretty clear to understand. Follow along in comments to understand each part--here it goes:
from dataclasses import field, dataclass
@dataclass
class Board:
numbers: dict[tuple[int, int], int] = field(default_factory=dict)
checked: dict[tuple[int, int], bool] = field(init=False, default_factory=dict)
all_numbers: dict[int, tuple[int, int]] = field(default_factory=dict, init=False)
_winner: bool = field(default=False, init=False)
def add_square(self, i: int, j: int, number: int) -> None:
"""
Used to build the board, from numbers in the puzzle input.
I'm storing the checked state as a separate dictionary. A colleague solution
converted rows and columns into sets and compared to a set of the drawn numbers,
which is pretty clever
"""
self.numbers[i, j] = number
self.checked[i, j] = False
self.all_numbers[number] = (i, j)
def unchecked(self) -> Iterator[int]:
"""Yields the unchecked numbers on the board for score calculation."""
for i in range(BOARD_SIZE):
for j in range(BOARD_SIZE):
if not self.checked[i, j]:
yield self.numbers[i, j]
def winner(self) -> bool:
"""Checks if a board is the winner if all positions in a row or column are checked."""
if self._winner:
return self._winner
for i in range(BOARD_SIZE):
row_checked = all(self.checked[i, j] for j in range(BOARD_SIZE))
column_checked = all(self.checked[j, i] for j in range(BOARD_SIZE))
if row_checked or column_checked:
self._winner = True
return self._winner
return False
def check(self, number) -> None:
"""'checks' a drawn number against the board, marking it."""
if self.winner():
return
if number not in self.all_numbers:
return
i, j = self.all_numbers[number]
self.checked[i, j] = True
Check the rest of the game in the repo, but it's basically a loop over the drawn numbers and all stored boards, calling board.check()
and board.winner()
to verify the states.
Let's wait for Sunday's puzzle!