I’ll be posting here my solutions for AoC 2021. Follow along!
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 increasesFor 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 increasesFor 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!
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 by X units.down X increases the depth by X units.up X decreases the depth by X 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 * depthThe 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 by X units.X units.X units.X.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 * depthThe final solution for day 2 is in my aoc repository!
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.Counters 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!
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] = TrueCheck 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!