Advent of Code 2023 🎄

History

Advent of Code is an annual programming challenge event created by Eric Walst and based on the advent calendar. It consists of a series of programming challenges of varying complexity. These tasks may be completed in any programming language. Participants can also compete on the global leaderboard which is solely based on speed (i.e. how fast you reach the solution). The first iteration of the Advent of Code started on December 1st 2015. Over the past few years, it has been gaining popularity.

2023 Edition

This year, I decided to give Advent of Code a try. Unfortunately, I got sick and lost track of it for a few days. I wasn't participating competitively anyway, so nothing stops me from finishing the whole set of problems at some point in the near future. I thoroughly enjoyed solving the challenges and look forward to next year's edition. In this first post, you will find two of my favourite problems from this year as well the thought process and implementation: Day 4 and Day 9.

🔍 Note: complexity seems to be significantly higher in part 2.

Day 4

Part 1

In Day 4 Part 1 we are faced with a regular set intersection problem. In essence, the input data is comprised of an identifier - Card #, owned numbers (i.e. first set of numbers, before the | delimiter), winning numbers (i.e. second set of numbers, after the | delimiter). Starting with 1 point for the first match (i.e. owned number is present in winning numbers), we then double the amount of points for every subsequent match. The solution is the sum of all the points.

Example of the input:

Card 1: 41 48 83 86 17 | 83 86  6 31 17  9 48 53
Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19
Card 3:  1 21 53 59 44 | 69 82 63 72 16 21 14  1
Card 4: 41 92 73 84 69 | 59 84 76 51 58  5 54 83
Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36
Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11

Solution

To parse the relevant data, I decided to make use of regex matching. The main idea is to parse the owned and winning numbers into sets of digits (per scratchcard). In Python, we can then find the intersection between the 2 sets with a trivial set intersection operator - &.

1. Regex matching: We first match the regex pattern to the scratchcard. I decided to capture 3 groups: the card identifier (e.g. Card 1), the owned numbers, and the winning numbers as seen below:

In Python, we can define raw string notation for regular expressions by prefixing a string variable with r, as in:

pattern = r"Card\s+(\d+):(?:\s+)((?:\d+\s*)+)\s\|(?:\s+)((?:\d+\s*)+)"
result = re.match(pattern, scratchcard)

💡 Tip: We only need to capture relevant groups by encapsulating the groups we want to capture in parentheses. Non-capturing groups are prefixed with "?:".

2. Extract digits: The next step involves converting the string "41 48 83 86 17" into a list of integers [41, 48, 83, 86, 17]. This can be easily accomplished using a combination of list comprehension and Python's map built-in function.

Firstly, [*map(int, x.split())] creates a list where we split a given group x into a list of strings that are casted into a list of integers. The resulting map object is then destructured and wrapped in square brackets to create a list. This is then repeated for each captured group in the regex match using a list comprehension.

_, own, win = [[*map(int, x.split())] for x in result.groups()]

💡 Tip: The groups() method returns a tuple containing all the subgroups of the match.

3. Find intersection: Now we only need to find the number of digits present in both sets (i.e. owned and winning) and subtract 1 to it (explained below).

intersection = len(set(own) & set(win)) - 1

4. Compute score: To compute the number of points amassed for a given scratchcard, remember that we start with 1 point for the first match, and then double that score for every subsequent match. This can be calculated using 2^(n-1), where n is the number of intersections.

score = int(2**intersection)

Considering all of the above, we can effortlessly piece together the code and end up with a working solution:

import re


def get_points(scratchcard: str) -> int:
    """Return the total number of points of a scratchcard.
    
    :param str scratchcard: scratchcard
    :return int: total number of points
    """
    result = re.match(pattern, scratchcard)
    _, own, win = [[*map(int, x.split())] for x in result.groups()]
    intersection = len(set(own) & set(win)) - 1
    return int(2**intersection)


if __name__ == "__main__":
    with open("2023/day_04/input.txt", "r") as file:
        data = file.read().splitlines()

    pattern = r"Card\s+(\d+):(?:\s+)((?:\d+\s*)+)\s\|(?:\s+)((?:\d+\s*)+)"
    points = sum(map(lambda x: get_points(x), data))
    print(f"Total number of points: {points}")

Part 2

In Part 2, the challenge gets a little bit more complicated. Instead of counting points, we are now tasked with counting the total number of scratchards we end up with. That is, we now win n copies of the scratchcards that follow a given scratchcard. For example, say we have Card 10 with 3 matching numbers, we would then win one copy of cards 11, 12, and 13. Say now that Card 11 has 2 matching numbers, we would then end up with additional copies of cards 12 and 13.

Example for Day 4 - Part 2.

Summing up the copies of the cards we gained, we would end up with:

{10: 1, 11: 1, 12: 2, 13: 3}

Solution

This problem can easily be solved using the magic of ✨recursion✨. The idea is to parse each scratchcard and then:

1. As in Day 4 - Part 1: We make use of regular expressions to capture the relevant groups, extract the digits, and find the intersection between the sets of numbers (i.e. owned and winning numbers).

⚠️ Gotcha: we don't subtract 1 to the length of the intersection in Part 2 since we want the exact length of the range of cards.

2. Count the cards: To count the cards, we use the get_scratchcards() recursive function. In a nutshell, this function will iterate over the cards recusively and count the copies using a counter (i.e. cards variable).

As the code for this part is a bit more verbose, you can find the full solution for this part on GitHub.

Day 9

Part 1

Day 9 was a really fun one to solve. This task is a canonical example of a pattern recognition and sequence extrapolation problem. In a nutshell, we are tasked with finding the differences between consecutive numbers in each sequence (so you always end up with n - 1 numbers for each subsequence) until we reach a sequence solely containing zeroes. Using the differences we computed, we can then extrapolate the next value in a given sequence. The solution is the sum of all the extrapolated values.

As explained in the exercise, imagine with start with the following sequence of numbers:

1   3   6  10  15  21

If we compute the differences between each consecutive pair of numbers, the subsequent sequence equates:

1   3   6  10  15  21
  2   3   4   5   6

This process repeats itself until we reach a resulting sequence that only contains zeroes:

1   3   6  10  15  21
  2   3   4   5   6
    1   1   1   1
      0   0   0

To compute the extrapolated values, we first add a 0 to the last sequence (i.e. the sequence containing only zeroes). Then, for each sequence from the bottom up, we compute the extrapolated value by summing the last number in the sequence with the previous extrapolated value.

1   3   6  10  15  21  '28'
  2   3   4   5   6   '7'
    1   1   1   1   '1'
      0   0   0   '0'

Solution

As in Day 4 - Part 2, this problem seems to be a prime example in which recursion can shine. Given a list of numbers - values, we can compute the differences between each pair of consecutive digits with:

diff = [b - a for a, b in zip(values, values[1:])]

To implement the recursive function, we simply need to define the recursive and base cases. The base case in this problem is reached when all the digits in a sequence are zeroes, the recursive case is reached elsewise.

At first, I made the naïve mistake of just checking if the sum of digits is 0. But this will not give the proper solution since we can still end up with negative numbers that cancel out their positive counterparts (e.g. -2 0 0 2 0) and have the sum of digits equating 0. So instead of checking while sum(diff) for the recursive case, we should check if any of the integers in the sequence is different than zero, i.e. while any(diff). Then, we just need to sum the last integer in the previous sequence to the last integer in the computed sequence of pairwise differences (in the example shown above, this would be: 21+6+1=28).

Having this in mind, it takes little effort to wrap up the concepts and come up with our recursive function:

def get_diff_sum(values: list[int]) -> int:
    """Return the sum of the extrapolated values.

    :return int: sum of extrapolated values
    """
    diff = [b - a for a, b in zip(values, values[1:])]
    while any(diff):
        return values[-1] + get_diff_sum(diff)
    return values[-1]


if __name__ == "__main__":
    with open("2023/day_09/input.txt", "r") as file:
        data = file.read().splitlines()

    data = [[*map(int, line.split())] for line in data]
    print(f"Sum of the extrapolated values: {sum(map(get_diff_sum, data))}")

Part 2

In the second part of Day 9, we are tasked with extrapolating the values backwards. Instead of adding a zero to the end of the final sequence (i.e. the sequence of zeroes), we add it to the beginning. We then fill in the extrapolated values at the beginning of each parent sequence. As seen in the exercise, if we get the following sequence after computing the differences:

10  13  16  21  30  45
   3   3   5   9  15
     0   2   4   6
       2   2   2
         0   0

Extrapolating the values at the beginning gives us:

'5'  10  13  16  21  30  45
  '5'   3   3   5   9  15
   '-2'   0   2   4   6
      '2'   2   2   2
        '0'   0   0

Solution

As it turns out, the solution to this problem is straightforward: instead of calculating the sum of the last digits to compute the next extrapolated value, we calculate the difference of the first digits.

def get_diff_sum(values: list[int]) -> int:
    """Return the sum of the extrapolated values (backwards).

    :return int: sum of extrapolated values
    """
    diff = [b - a for a, b in zip(values, values[1:])]
    while any(diff):
        return values[0] - get_diff_sum(diff)
    return values[0]


if __name__ == "__main__":
    with open("2023/day_09/input.txt", "r") as file:
        data = file.read().splitlines()

    data = [[*map(int, line.split())] for line in data]
    print(f"Sum of the extrapolated values (backwards): {sum(map(get_diff_sum, data))}")