Ricardo Busquet

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):

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:

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.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!

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!