Advent of Code 2021
~ ~ ~ ~~ ~~~~~~~~~~~~~~~ ..'''' . . : . . .' ....'
I'll be posting here my solutions for AoC 2021. Follow along!
Table of contents
Day 1: Sonar Sweep
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!
Today, we're piloting a submarine, which has a planned course defined by a series of instructions (our input):
forward Xincreases the horizontal position by
down Xincreases the depth by
up Xdecreases the depth by
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 Xincreases your aim by
- up X decreases your aim by
- forward X does two things:
- It increases your horizontal position by
- It increases your depth by your aim multiplied by
- It increases your horizontal position by
The solution looks a lot like part 1, but tracking the new
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
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
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() for counter in counters] epsilon = [counter.most_common(2) 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() 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() 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) * list_of_bits_to_int(co2_report)
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
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 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.winner() to verify the states.
Let's wait for Sunday's puzzle!