Advent of Code - Day 4-5

This is Part 2 of my ongoing commentary of Advent of Code 2024. See Day 1-3 for the previous episode.

Day 1-3 were all about getting used to the format and to the general pipeline of solving these puzzles. Day 1 and 2 were very straigthforward, day 3 came with some RegEx difficulties, but nothing too exotic. Let’s move on to day 4.

Day 4: pattern matching

The puzzle, part 1

Find all occurences of XMAS, in any direction (horizontal, vertical, diagonal, forward and backwards). The solution for the first part should be the number of occurences (in a much larger grid of 140x140 letters).

The solution

Because I was still in RegEx mode from the previous day, I started by a simple method to count the number of occurences of XMAS in a line:

def count_in_line(s: str) -> int:
    return len(re.findall("XMAS", s))

My idea was then to try to frame the rest of the problem as: find all the lines that we need to count “XMAS” in. For the horizontal and vertical lines, that’s easy: we can just go row by row and column by column, and test for each line and its reverse. To go row by row, we just have to split the original block of text by \n. And then we can use the zip(*rows) trick to transpose and go column by column:

horizontals = data.split('\n')
total = 0
for l in horizontals:
    total += count_in_line(l) + count_in_line(l[::-1])

total_horizontal = sum(count_in_line(l) + count_in_line(l[::-1]) for l in data.split('\n'))

But this is a case where I think readability is really improved by explicitly writing the steps. For the verticals:

verticals = zip(*horizontals)
for v in verticals:
    s = ''.join(v) # reform string from list of characters
    total += count_in_line(s) + count_in_line(s[::-1])

And now, I want to add the diagonals. First, I pretend that I have a function to do that, just to finish the “summation” code:

for d in get_diagonals(horizontals):
    total += count_in_line(d) + count_in_line(d[::-1])

But then we have to actually find those diagonals. It’s not particularly difficult per se, but I really struggled to find a satisfying solution (as in: a solution that doesn’t lead to disgusting spaghetti code). To cover all the diagonals, we need to go in four directions (plus the reverse).

From the top row, if we move “bottom-right” and “bottom-left”, we cover the following diagonals in the example:

(This visualization already took more time to do than solving the puzzle I think)

To get the “missing” diagonals, we can then start again from the last row, this time going “top-right” and “top-left”, ignoring the first and last column, which we already covered. Alternatively (and that’s what I did in the code, but I noticed after doing the visualization, which I don’t want to remake!), we can do “top-right”, “bottom-right” from the first column, then “top-left”, “bottom-left” from the last column, ignoring the first and last row. That’s confusing, and in this case I fear my code will not help much, but here it is:

def collect_diagonal(grid: list[list[str]] | list[str], 
                     start_row: int,
                     start_col: int,
                     h_direction: int,
                     v_direction: int) -> str:
    d = []
    dridx = start_row
    dcidx = start_col
    d.append(grid[dridx][dcidx])
    while 0 <= (dcidx := dcidx + h_direction) < len(grid[0]) and \
          0 <= (dridx := dridx + v_direction) < len(grid):
        d.append(grid[dridx][dcidx])
    return ''.join(d)

def get_diagonals(horizontals: list[str]):
    diagonals = []

    # starting from first col
    for row_idx in range(len(horizontals)):
        # down right
        diagonals.append(collect_diagonal(horizontals, row_idx, 0, 1, 1))
        # top right
        diagonals.append(collect_diagonal(horizontals, row_idx, 0, 1, -1))

    # starting from last col, without first and last row
    for row_idx in range(1, len(horizontals)-1):
        # down left
        diagonals.append(collect_diagonal(horizontals, row_idx, len(horizontals[row_idx])-1, -1, 1))
        # top left
        diagonals.append(collect_diagonal(horizontals, row_idx, len(horizontals[row_idx])-1, -1, -1))

    return [d for d in diagonals if len(d) > 4]

I’m sure there are more elegant solutions out there, but it works, and I got to use the walrus operator :=, which is always a nice bonus.

Second part

This time, I couldn’t really re-use much for the second part. No more counting things in line, unfortunately, so I had to basically start from scratch. The goal this time was to find the pattern:

In the same grid, with the MAS also in all directions. This is, in my opinion, a much simpler problem to solve. We have in total four possible patterns to find:

We can now easily go line-by-line, then column by column, through the grid. Every time we find a triple of letters that matches the first row of one of the patterns, we check if the 3x3 region matches the entire pattern, and that’s it. Using the . RegEx wildcard (that we now know doesn’t work for newlines) in our pattern, and re.match, we can get the correct count.

count_matches = 0

# go line by line, column by column, check if match
for i in range(len(horizontals)-2):
    for j in range(len(horizontals[i])-2):
        region = [h[j:j+3] for h in horizontals[i:i+3]]
        for line_patterns in acceptable_patterns:
            is_match = True
            for l,p in zip(region, line_patterns):
                if re.match(p, l) is None:
                    is_match = False
            if is_match:
                break
        if is_match:
            count_matches += 1

Day 5: Order!

The puzzle

Day 5 is all about following the rules and putting things in order. The input is a bit differently laid out than usual. Instead of a single grid, we have two parts separated by a blank line:

The first part defines the rules, which are of the form A|B, meaning “A must come before B. The second part gives us the orders, which are supposed to (but of course don’t) follow the rules.

Part 1 and Part 2 go together well this time around: part 1 is about finding which lines follow the rules, part 2 is about correcting those that don’t. To check that we solve the puzzle, we have to compute the sum of the middle numbers, first of all the correct lines, then of all the re-ordered incorrect lines.

The solution

The main thing that I worried about here was how to structure the data in such a way that it would be easy to then check the rules. In the end, I settled on a rulebook as a dict, where the keys would be the values present in the rules. To each value would be associated two lists: a list of all the values that must come before, and a list of all the values that must come after.

So for instance, given our example above, the number 47 appears six times in the rules:

For that, we first load the data as a string, split in two based on the blank line, and parse the rules to construct the dictionary:

def get_rulebook_and_line(suffix: str) -> tuple[dict[int, list[list[int]]], list[list[int]]]:
    data = load_as_str('day5')

    rules, line = data.split('\n\n')

    rules = [[int(p) for p in r.split('|')] for r in rules.split('\n')]
    line = [[int(p) for p in u.split(',')] for u in line.split('\n')]

    return prepare_rulebook(rules), line


def prepare_rulebook(rules: list[list[int]]) -> dict[int, list[list[int]]]:
    """Put the rules in the form:
    
    {P1 : [[P_BEFORE], [P_AFTER]]}
    """
    rules_dict = {}
    for before, after in rules:
        if before not in rules_dict:
            rules_dict[before] = [[], [after]]
        else:
            rules_dict[before][1].append(after)
        if after not in rules_dict:
            rules_dict[after] = [[before], []]
        else:
            rules_dict[after][0].append(before)

    return rules_dict

This makes the rest very easy. To check if a line follows the rule, we go item by item, get the rules for the current items, and check if there is some overlap between the previous items and the “must come after” list, or if there is some overlap between the next items and the “must come before” list. In either case, we mark the line as incorrect.

def check_no_overlap(src: list[int], 
                     ref: list[int]) -> bool:
    for v in src:
        if v in ref:
            return False
    return True

def filter_line(line: list[int], 
                rulebook: dict[int, list[list[int]]]) -> bool:
    for idx in range(len(line)):
        cur = line[idx]
        bef = line[:idx]
        aft = line[idx+1:]
        rbefore = rulebook[cur][0]
        rafter = rulebook[cur][1]
        if not (check_no_overlap(bef, rafter) and check_no_overlap(aft, rbefore)):
            return False
    return True

def filter_lines(lines: list[list[int]], rulebook: dict[int, list[list[int]]]) -> tuple[list[list[int]], list[list[int]]]:
    """Returns the list of correct and incorrect lines"""
    flines = [(filter_line(line, rulebook), line) for line in lines]
    return [line for is_correct, line in lines if is_correct], [line for is_correct, line in lines if not is_correct]

def add_middle(lines: list[list[int]]) -> int:
    return sum([line[len(line)//2] for line in lines])

rules, lines = get_rulebook_and_lines("_sample")
correct, incorrect = filter_lines(lines, rules)
print(add_middle(correct))

For the second part, we go through the incorrect list and we will iteratively swap any two items that are breaking the rules until the list is ordered as we want. To do that, we need to modify our check_no_overlap method to also return the position of the offending party:

def check_no_overlap(src: list[int], ref: list[int]) -> tuple[bool, int|None]:
    for v in src:
        if v in ref:
            return (False, src.index(v))
    return (True, None)

(We will have to slightly change filter_line as well to use check_no_overlap(bef, rafter)[0])

Our re-ordering code will be very similar to the filter, except that we add some recursivity this time. We separate our “before” and “after” check and, as soon as we find a problem, we swap the two values and re-call the function with the swapped values.

def reorder_line(line: list[int], rulebook: dict[int, list[list[int]]]) -> list[int]:
    for idx in range(len(line)):
        cur = line[idx]
        bef = line[:idx]
        aft = line[idx+1:]
        rbefore = rulebook[cur][0]
        rafter = rulebook[cur][1]

        no_overlap_before, idx2 = check_no_overlap(bef, rafter)
        if not no_overlap_before:
            assert idx2 is not None
            # one of the number before must be after -> swap them
            line[idx], line[idx2] = line[idx2], line[idx]
            return reorder_line(line, rulebook)

        no_overlap_after, idx2 = check_no_overlap(aft, rbefore)
        if not no_overlap_after:
            assert idx2 is not None
            idx2 += idx+1 # idx2 is in truncated list
            # one of the number after must be before -> swap them
            line[idx], line[idx2] = line[idx2], line[idx]
            return reorder_line(line, rulebook)
    return line


def reorder_lines(lines: list[list[int]], rulebook: dict[int, list[list[int]]]) -> list[list[int]]:
    return [reorder_line(line, rulebook) for line in lines]

reordered = reorder_updates(incorrect, rules)
print(add_middle(reordered))

We could of course merge the two parts to be more efficient, and at the same time compile the list of correct and re-ordered lines, but that’s too much refactoring for the kind of time I’m willing to give to this!

Day 4-5 conclusions

I think with day 4 I was stuck a little bit in a bad original choice. Reducing the problem to a simple “find pattern in line” was not a problem by itself, but then I didn’t really find an efficient way of parsing the data to do things cleanly. Seeing the second part, maybe I should have looked at it as a 2D pattern matching problem from the start (which given my own background in image analysis should have been something I considered). The XMASs diagonal patterns can be enumerated in a 4x4 grid:

Using a moving window approach and matching those patterns, like I did for part 2, should work, I think?

For day 5 I’m much happier with my result. I think the dictionary approach to encode the rulebook made everything reasonably easy. I did see a cool idea in Juhis’ solution, which is to use a custom sorter. That’s certainly a more efficient way of reordering the lists. It makes me think that this could also be done with a SortableItem custom class, which would have for each item its set of appropriate rules and implement the __lt__(self, other) method using the rulebook. I don’t want to spend too much time on a particular puzzle, however, so I may come back to this later.