Advent of Code - Day 1-3

Advent of Code is a very geeky yearly event where the seemingly very geeky Eric Wastl makes an “advent calendar” with daily puzzles from December 1st to December 25th. I learned about this because I recently started following Juha-Matti Santala’s blog, and I thought this looked like a fun thing to do, and maybe to learn – or relearn – some things along the way.

Since I hadn’t done this event before, I first had to get acquainted with the format of the puzzles, which for the first five days at least has followed a very similar structure: you get a file with some data that needs to be parsed, then you have some rules that you need to follow to extract or transform pieces of that data, and then you have to combine some numbers from these transformations to get one integer answer. To make things a little bit easier, there is also always some small-scale example given with the rules – and with the correct answer for that example – so that we can easily test if we’re on the right track. There are always two parts to the puzzle, with the second part only available after solving the first, and bringing a new twist to the puzzle. I don’t know if I will cover all the puzzles, but I think it’s interesting to document the process as well, so here are some notes about the first three days to begin with.

First day and general pipeline

The puzzle

And, in the first part, we then simply need to add those distances to get the final answer. In the example: 2 + 1 + 0 + 1 + 2 + 5 = 11.

In the second part, using the same list, we need this time to compute a similarity score, defined with a new set of rules: for each number x of the “left” list, compute the number of times n that it appears on the right list. The similarity score is then: S = ∑_in_ix_i. In our example:

“3” appears 3 times on the right, so we add 9 to the similarity score. We get in total:

Solution

The puzzle is fairly easy to solve, and the main interest here is in getting used to the format and setting up the overall pipeline:

An easy way to process the data here is to first get it as a table (i.e. list of list) of integers:

def load_data(fname: str) -> list[list[int]]:
    # load data as list of rows, with values cast to int
    data = []
    with open(fname, 'r') as fp:
        data = fp.readlines()
    return [[int(v) for v in d.split()] for d in data]

This will give us the data in the “wrong” order, as a “list of rows”. We need a “list of columns”, which we can get (and sort at the same time, since it’s useful for the first puzzle) in an easy-to-read albeit not super-efficient way:

def parse_data(data: list[list[int]]) -> list[list[int]]:
    # transpose into two columns and sort
    data_left = sorted([d[0] for d in data])
    data_right = sorted([d[1] for d in data])
    return data_left, data_right

Juhis’ solution includes a more general trick that we can use for transposing the data from “list of rows” to “list of columns”, which is less readable but can easily scale to multiple columns:

def transpose_data(data: list[list[int]]) -> list[list[int]]:
    # transpose from list of rows to list of columns
    return list(zip(*data))

*data will “unpack” data into the row1, row2, ..., rown list, and zip will “pack” those lists element by element, getting first a list with [row1[0], row2[0], ..., rown[0], then a list with row1[1] ... rown[1], etc. zip returns a generator, so if we want the list of columns we can cast its results with list(). This is a nice trick to keep under the hood if needed, but for this particular puzzle I’ll keep to the simpler version.

Once we have our sorted data, the first part is very easy to compute, as we just have to take the sum of the absolute differences between pairs of points. The code to compute the “Part 1” answer is therefore:

raw_data = load_data("day1")
data_left, data_right = parse_data(raw_data)
total_dist = sum([abs(l-r) for l, r in zip(data_left, data_right)])

total_dist = 0
for l, r in data_left, data_right:
    total_dist += abs(l-r)

For the second part, we have to implement the similarity score, which we can do by iterating through the left list and counting the occurences of the value in the right list.

sim = 0
for dl in data_left:
    c = sum(dr==dl for dr in data_right)
    # alternatively: c = data_right.count(dl)
    sim += dl*c

Day 2: not much to say

Day 2 was straightforwad and mostly in the same vein. This time the data had to be parsed as a list of rows – which we already do with our load_data method. Then, we had to use some rules to check if each row is “valid”. A “valid” row contain only all-increasing or all-decreasing values, with an absolute difference between adjacents values bounded between 1 and 3 inclusive.

I implemented this rule by sorting the list of values in both order and checking if either sorted list matches the original. If not, the line is invalid. If it matches, we can proceed to check pairs of adjacent elements using itertools.pairwise:

def is_valid(row: list[int]) -> bool:
    if not ((row == sorted(row)) or (row == sorted(row, reverse=True))):
        return False
    
    for a, b in itertools.pairwise(row):
        if (abs(a-b) < 1) or (abs(a-b) > 3):
            return False
    
    return True

Part 2 added the twist that a row could be valid if it has one bad value, i.e. if by removing one value we can get a valid row. To check that, we can first check if the entire row is valid. If it’s not the case, we iterate through the elements, each time creating a “row without element idx” using row_ = row[:idx] + row[idx+1:]. If any of those is valid, then we consider the row “almost valid” and accept it.

def is_almost_valid(row: list[int]) -> bool:
    if is_valid(row):
        return True
    
    for idx in range(len(row)):
        row_ = row[:idx] + row[idx+1:]
        if is_valid(row_):
            return True
    
    return False

Day 3: RegEx time

Day 3 is the first where it wasn’t completely straightforward for me, as I had to refresh my RegEx knowledge a little bit.

The first part was not too bad, and I just needed to get the W3C RegEx reference to make sure I got it right. This time we have a weird string of text like the example:

And we need to extract the “instructions” of the form mul(a, b). Then we have to perform these multiplications, and sum the results. This time, we therefore have to load the whole data as a big string:

def load_data(fname: str) -> str | None:
    with open(fname, 'r') as fp:
        return fp.read(fp)
    return None

Then we need to create our RegEx pattern: pattern = r"mul\((\d+)?,(\d+)?\)", which we can use to capture all instances of mul(a, b) where a and b are integers. We can use Python’s built-in re module to do this:

text = load_data("day3")
pattern = r"mul\((\d+)?,(\d+)?\)"
all_matches = re.findall(pattern, text)

This will give us a list of tuples with the two integers a and b as strings, so we still have to cast them, then multiply and sum. Putting everything in nice possibly-reusable functions, I got:

def get_with_pattern(pattern: str, text: str, fn: Callable[[Sequence], Any]):
    results = []

    all_matches = re.findall(pattern, text)

    for m in all_matches:
        results.append(fn(m))

    return results

def find_multiplications(code: str) -> list[tuple[int, int]]:
    pattern = r"mul\((\d+)?,(\d+)?\)"
    cast = lambda m : (int(m[0]), int(m[1]))

    return get_with_pattern(pattern, code, cast)

text = load_data("day3")
multiplications = find_multiplications(text)
res = sum(m[0]*m[1] for m in multiplications)

Part 2 is where I got stuck for a bit for the first time. For part 2, we have two additional instructions: do() and don't() that we have to find. That part is easy, as we can create RegEx patterns as well. When we encounter a don't(), our code is “disabled” and we have to ignore any mul instruction until we get a do() that “enables” the system again. The system starts in “enabled” state.

The probably-best way to do this would have been to find all matches of either our mul(a, b) pattern, do() and don't(), and go through them in order while keeping track of the enabled/disabled status. The pattern would be something like pattern = r"(mul\((\d+)?,(\d+)?\)|do\(\)|don't\(\))".

I unfortunately made the mistake of trying to be clever. I wanted to reuse my find_multiplications method directly, so I thought I’d rather first remove all the “disabled” part of the code, and then I would immediately be able to get my answer. So I used a pattern pattern = r"don't\(\)((.)*?)do\(\)" to get “everything between a don't() and a do(), using the . as a RegEx wildcard to catch every character. I tried it on the example, and got the right answer, then tried it on the real data and… that didn’t work.

I overlooked two things: one, it’s possible that there is a final don't() in the code with no do() after to reactivate it. In this case, we have to remove from the don't() to the end, but this is not captured by my RegEx. That’s an easy fix: I just have to use a r"don't\(\)" pattern as a second pass, and remove the end of the code if I find a match. Two, I missed that the . wildcard captures every character except newlines. So I was actually missing a whole bunch of don't()...do() bits because they contained line breaks. There were none in the example, but there were many of these in the actual puzzle data. This is, fortunately, also an easy fix, as we can add |\n to the . in our pattern to truly capture all characters. This gives us the code filtering function to remove disabled parts:

def remove_with_pattern(pattern: str, text: str):
    """Remove everything inside a pattern"""
    
    while (match := re.search(pattern, text)) is not None:
        text = text[:match.start()] + text[match.end():]

    return text

def remove_disabled(code: str) -> str:
    pattern = r"don't\(\)((.|\n)*?)do\(\)"

    code = remove_with_pattern(pattern, code)

    # check if there is still a "don't()"
    pattern = r"don't\(\)"
    match = re.search(pattern, code)
    if match is not None:
        code = code[:match.start()]

    return code

text = remove_disabled(load_data("day3"))
multiplications = find_multiplications(text)
res = sum(m[0]*m[1] for m in multiplications)