Advent of Code

A very short one for the last day, with a single part to the challenge, and an easy one compared to what we’ve seen in the past week.

With the top row filled with #, the bottom row with ., and each column with an height determined by how many # down we have, not counting the first row (so in this case: 0, 5, 3, 4, 3).

With the top row filled with ., the bottom row with #, and each column with an height determined by how many # up we have, not counting the last row (in this case: 5, 0, 2, 1, 3).

The goal is to find how many lock/key combinations are possible, meaning that there is no overlap in any of the column between the #. In other words: the sum of the heights for each column must be at most equal to 5.

This is very straightforward, no particular trick involved. First, we parse the input file. Each schema for a key or lock is separated by a blank line, so we split by \n\n. We then separate the locks and keys by looking at the first character: if it’s a #, it’s a lock, if it’s a ., it’s a key.

To compute the heights of each column, we first transform the schema in a list of str with split(\n) so that we get a list of rows. Since we want to look at it per-column, we need to transpose it. We can do that quickly with list(zip(*schama)), where *schema unpacks the list, so that zip will then iterate over all the rows at once element by element… which if we convert that to a list will lead to a list of columns. We then count the number of # per-column, removing 1 to account for the first (or last) one.

def get_heights(schema: str):
    per_col = list(zip(*schema))
    return [c.count('#')-1 for c in per_col]

def parse_input():
    with open("day25", 'r') as fp:
        data = fp.read().strip().split('\n\n')
    
    locks = [get_heights(d.split("\n")) for d in data if d[0] == "#"]
    keys = [get_heights(d.split("\n")) for d in data if d[0] == "."]

    return locks, keys

We then need a method to determine if there is no overlap between a lock and a key. We can zip through the heights of both elements, and check that the sum is not above the target height. We use the all built-in function to check if the condition is respected in all elements.

def no_overlap(a: list[int], b: list[int], height: int = 5):
    return all(v1+v2 <= height for v1, v2 in zip(a, b))

All that’s left to do is to iterate through every combination of lock and key, and sum the number of pairs that have no overlap. We could do a double-for-loop, but since itertools has been so useful in these puzzles, let’s make it work one more time, using product to give us an iterator through all possible combinations:

locks, keys = parse_input()
t = sum(no_overlap(lock, key) for lock, key in itertools.product(locks, keys))

print(f"Part 1 answer: {t}")

That was fun. Thank you Eric Wastl for making these puzzles. This was my first year doing these, but it probably won’t be the last – and I’ll probably check out the previous years as well.