Advent of Code 2024 (Days 13, 14, 15, 16)

Here is my private leaderboard code if you want to come join the fun: 1598637-22d94a1d.

Feel free to introduce yourself if you ever decide to enter.

The de-facto challenge I ended up going for this year is to minimize the time between Part A and Part B.

Day 13 : Systems of Linear Equations of Two Variables

Here is the link to the problem.

The time between my Part A and Part B solve was like 43 seconds. A record!

Part A

Part A was definitely baiting us to simulate the presses using for loops. But we do maths and we know that this is a system of linear equations in two variables:

$$\begin{cases} x_1m + x_2n = x \\ y_1m + y_2n = y \\ \end{cases}$$

where $(x, y)$ is the target and the $(x_i, y_i)$ are the displacement that the buttons give us. It remains to solve for $m$ and $n$.

Rewriting this as fancy matrices, we get the following:

$$\begin{bmatrix} x_1 & x_2 \\ y_1 & y_2 \end{bmatrix}\begin{bmatrix} m \\ n \end{bmatrix}= \begin{bmatrix} x \\ y \end{bmatrix}$$

Assuming our square matrix is invertible, we have the following.

$$\begin{bmatrix} m \\ n \end{bmatrix}= \begin{bmatrix} x_1 & x_2 \\ y_1 & y_2 \end{bmatrix}^{-1} \begin{bmatrix} x \\ y \end{bmatrix}$$

And since I was coding this first thing in the morning, I misremembered the formula for the inverse of a $2 \times 2$ matrix. Anyway, here is the correct one:

$$\begin{bmatrix} m \\ n \end{bmatrix}= \frac{1}{y_2x_1 + x_2y_1} \begin{bmatrix} y_2 & -x_2 \\ -y_1 & x_1 \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix}$$

Rewriting it to exit linear algebra land, we have

$$\begin{cases} m = y_2x - x_2y \\ n = -y_1x + x_1y \\ \end{cases}$$

And writing it in Python:

import re

def solution_13a(data=None, filename=None):
    if not data:
        lines = parse_13(filename)
    else:
        lines = data
        
    def get_test_case(a, b, p):
        coords = []
        
        matches = re.match(r"Button A: X\+([0-9]+), Y\+([0-9]+)", a)
        x = int(matches[1])
        y = int(matches[2])
        coords.append((x, y))
        
        matches = re.match(r"Button B: X\+([0-9]+), Y\+([0-9]+)", b)
        x = int(matches[1])
        y = int(matches[2])
        coords.append((x, y))

        matches = re.match(r"Prize: X=([0-9]+), Y=([0-9]+)", p)
        x = int(matches[1])
        y = int(matches[2])
        coords.append((x, y))
        
        return tuple(coords)
        
        
    def get_test_cases(lines):
        return [get_test_case(a, b, p) for a, b, p in zip(lines[0::4], lines[1::4], lines[2::4])]
    
    def get_solution(test_case):
        a, b, p = test_case
        x1, y1 = a
        x2, y2 = b
        x, y = p
        # [x1 x2] [m] = [x]
        # [y1 y2] [n]   [y]
        det = x1*y2 - x2*y1
        if det == 0:
            return (None, None)
        m = (y2*x -x2*y)/det
        if m != int(m):
            return (None, None)
        n = (-y1*x + x1*y)/det
        if n != int(n):
            return (None, None)
        return (int(m), int(n))
    
    def solve_test_case(test_case):
        a, b = get_solution(test_case)
        if a is None or b is None:
            return 0
        else:
            return 3*a + b
    
    ret = 0
    for test_case in get_test_cases(lines):
        ret += solve_test_case(test_case)
    return ret

As you can see, a big chunk of the code is regex-ing the input.

Part B

Part B is pretty much just modifying the get_test_case function to add 10000000000000 on the target.

Our solution was constant time so this should work.

Day 14: Mod World Robots

Here is the link to the problem.

The time between my Part A and Part B solve was like 19 minutes. With an asterisk!

Part A

This was an exercise in modular arithmetic.

Finding the positions of the robots at time $t$ could be computed as follows

$$p(t) = ( p_i+v_i \cdot t, p_j+v_j \cdot t ) \in \frac{\mathbb{Z}}{m_i\mathbb{Z}} \times \frac{\mathbb{Z}}{m_j\mathbb{Z}}$$

That fancy math above is just a reminder to reduce the first component modulo $m_i$ and the second component modulo $m_j$.

Figuring out the quadrants was a couple of if statements, but with care devoted to making sure to avoid the center.

def get_quadrant(position):
    i, j = position
    mi, mj = m
    if i < mi//2 and j < mj // 2:
        return 1
    if i < mi//2 and j > mj // 2:
        return 2
    if i > mi//2 and j > mj // 2:
        return 3
    if i > mi//2 and j < mj // 2:
        return 4
    return 0

Writing it all out, we have:

import re

def solution_14a(data=None, filename=None, m=(7, 11), t=100):
    if not data:
        lines = parse_14(filename)
    else:
        lines = data
        
    def get_test_case(line):
        
        matches = re.match(r"p=([\-0-9]+),([\-0-9]+) v=([\-0-9]+),([\-0-9]+)", line)
        pj = int(matches[1])
        pi = int(matches[2])
        vj = int(matches[3])
        vi = int(matches[4])
        
        return ((pi, pj), (vi, vj))
        
        
    def get_test_cases(lines):
        return [get_test_case(line) for line in lines]        
    
    def get_position(test_case):
        mi, mj = m
        (pi, pj), (vi, vj) = test_case
        return ( (pi+vi*t)%mi, (pj+vj*t)%mj )
    
    # ... get_quadrant function ... #
    
    quadrants = [[] for i in range(5)]
    
    for line in lines:
        test_case = get_test_case(line)
        position = get_position(test_case)
        q = get_quadrant(position)
        quadrants[q].append(position)
    
    ret = 1
    for q in quadrants[1:]:
        ret *= len(q)
    return ret

Part B

We put an asterisk on my $19$-minute time because I basically stared at this statement for a good couple of minutes:

If they’re the same type of robots, they should have a hard-coded Easter egg: very rarely, most of the robots should arrange themselves into a picture of a Christmas tree.

What is the fewest number of seconds that must elapse for the robots to display the Easter egg?

Picture of a Christmas tree? What does that even mean?!

My first attempt was to print all timestamps in which there was a robot in the middle of the first row, presumably to have the top of the Christmas tree. That wasn’t it.

Deciding I would rather spend the rest of my day being bored, free from this shenanigans, I decided to look around. People were like “find the timestamp in which no two robots were in the same place”. I perfectly understand that this had nothing to do with the grid looking like a Christmas tree, but I went for it anyway and got my star.

Didn’t feel very satisfying. Hence the asterisk in the beginning of the section. Although some people liked this type of problem. To each their own I suppose!

Other solutions for Part B included heuristics like robots bunching up. All of them were heuristics in the end.

Day 15: Box-Pushing Bots

Here is the link to the problem.

The time between my Part A and Part B solve was like 1 hour and 22 minutes. No asterisks this time!

Part A

My solution for Part A had a little trick that only works for a row of boxes.

When a robot is pushing a row of boxes, instead of pushing each box one-by-one, I teleport the first box into the next empty space (if there is any).

Here is how it looks like in code.

def push_box(pos, d):
    k = 0
    i, j = pos
    di, dj = d
    while True:
        k += 1
        new_pos = (i+di*k, j+dj*k)
        if new_pos in walls:
            return
        if new_pos in boxes:
            continue
        boxes.remove(pos)  # Teleport this box...
        boxes.add(new_pos) # ...to the end of the row of boxes.
        break

Part B

Part B is where all hell breaks loose.

First, we have to double each character. I did this using some regex magic on the input.

def solution_15b(data=None, filename=None):
    if not data:
        grid, moves = parse_15(filename)
    else:
        grid, moves = data
    
    walls = set()
    boxes_left = set()
    boxes_right = set()
    robot = (-1, -1)
    
    for i, line in enumerate(grid):
        grid[i] = grid[i].replace("#", "##").replace("O", "[]").replace(".", "..").replace("@", "@.")

    for i, line in enumerate(grid):
        for j, char in enumerate(line):
            if char == '#':
                walls.add((i, j))
            if char in '[':
                boxes_left.add((i, j))
            if char in ']':
                boxes_right.add((i, j))
            if char == '@':
                robot = (i, j)

Next, as shown in the sample input, one move can displace a clump of boxes, not necessarily in the same column or row. So now, we have to actually figure out in advance the coordinates of these boxes.

def solution_15b(data=None, filename=None):

    # ... #

    def get_clump(pos, d):
        coords = set()
        to_add = [pos]
        while len(to_add) > 0:
            pos = to_add.pop()
            coords.add(pos)
            i, j = pos
            di, dj = d
            new_pos = i+di, j+dj
            if new_pos in walls:
                continue
            if pos in boxes_left and (i, j+1) not in coords:
                to_add.append((i, j+1))
            if pos in boxes_right and (i, j-1) not in coords:
                to_add.append((i, j-1))
            if new_pos in boxes_left | boxes_right and new_pos not in coords:
                to_add.append(new_pos)
            if new_pos in boxes_left | boxes_right and new_pos not in coords:
                to_add.append(new_pos)
        return coords

Now that we know the coordinates of the boxes that could potentially be moved, how do we move them?

Carefully.

But I didn’t do it that way the first time. A huge chunk of my time was spent with a bug caused by me removing boxes in the coordinate set and then adding them back at the same step.

Adding to_add lists separated these steps and eventually squashed that bug.

def solution_15b(data=None, filename=None):

    # ... #
                
    def move_clump(clump, d):
        clump_list = []
        for c in clump:
            i, j = c
            di, dj = d
            new_pos = i+di, j+dj
            if c in boxes_left:
                clump_list.append(('[', c))
            if c in boxes_right:
                clump_list.append((']', c))
            if new_pos in walls:
                return False
        to_add_left = []
        to_add_right = []
        for c, pos in clump_list:
            i, j = pos
            new_pos = i+di, j+dj
            if c == '[':
                boxes_left.remove(pos)
                to_add_left.append(new_pos)
            if c == ']':
                boxes_right.remove(pos)
                to_add_right.append(new_pos)
        for pos in to_add_left:
            boxes_left.add(pos)
        for pos in to_add_right:
            boxes_right.add(pos)

Note that this function also aborts if the boxes can’t be moved (i.e. if one of the occupied places would have been pushed to a wall).

The rest is just a copy-paste of Part A’s code.

def solution_15b(data=None, filename=None):
    # ... #
            
    def follow_command(pos, d):
        i, j = pos
        di, dj = d
        new_pos = (i+di, j+dj)
        if new_pos in walls:
            return pos
        if new_pos in boxes_left | boxes_right:
            clump = get_clump(new_pos, d)
            move_clump(clump, d)
            if new_pos in walls | boxes_left | boxes_right:
                return pos
        return new_pos
    
    def get_gps(pos):
        i, j = pos
        return i*100 + j
        
    dir_dic = {
        '>': (0, 1),
        '<': (0, -1),
        '^': (-1, 0),
        'v': (1, 0)
    }
            
    for c in moves:
        robot = follow_command(robot, dir_dic[c])
        
    ret = 0
    for box in boxes_left:
        ret += get_gps(box)
    return ret     

Day 16: Zoolander Reindeers

Here is the link to the problem.

The time between my Part A and Part B solve was like 1 hour and 12 minutes.

Also, I just realized that the problems actually have names on literally the first line of the page. We’ll keep our titles anyway. Bonus points for those who get the reference.

Part A

For this problem, I used a priority queue implemented more or less by the heapq Python library.

When you add an element to a priority queue, you assign to it a… priority. It then gets added to its rightful place in the queue. Which is to say, the position in which the elements of the queue remain sorted according to priority.

For this problem, we push discovered position-direction pairs into the priority queue depending on the cost to get there from the given start position.

Going through the queue in priority order, when we encounter an element wherein the position is the end position, we are pretty sure that its associated cost is the lowest cost to get there.

from heapq import heappush, heappop

def solution_16a(data=None, filename=None):
    if not data:
        grid = parse_16(filename)
    else:
        grid = data
        
    def get_positions(grid):
        s = None
        e = None
        for i, line in enumerate(grid):
            for j, char in enumerate(line):
                if char == 'S':
                    s = (i, j)
                if char == 'E':
                    e = (i, j)
        return s, e

    def navigate_maze(grid):
        h = []
        
        dir_dic = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        s, e = get_positions(grid)
        
        heappush(h, (0, s, 0))
        
        visited = set()
        
        while len(h) > 0:
            c, p, d = heappop(h)
            
            if (p, d) in visited:
                continue
                
            if p == e:
                return c
                
            visited.add((p, d))
            
            q = p[0]+dir_dic[d][0], p[1]+dir_dic[d][1]
            ii, jj = q
            
            if grid[ii][jj] != '#':
                to_go = (c+1, q, d)
                if to_go not in visited:
                    heappush(h, to_go)
            
            to_go = (c+1000, p, (d+1)%4)
            if to_go not in visited:
                heappush(h, to_go)
                
            to_go = (c+1000, p, (d-1)%4)
            if to_go not in visited:
                heappush(h, to_go)
                
        return -1
    
    return navigate_maze(grid)    

Part B

For Part B, we need to find ALL paths which arrive at the end position with the minimal cost.

So we can’t simply stop when p == c anymore.

best_time = None
        
visited = set()

while len(h) > 0:
    c, p, d = heappop(h)
    
    if (p, d) in visited:
        continue
        
    if p == e:
        best_time = c
        
    if best_time is not None and c > best_time:
        break

We edit the while loop as follows.

Moreover, we need to remember how we got there.

We could add the whole path we took as an additional value that we push to the heap. But we could take inspiration from Hansel and Gretel and leave breadcrumbs.

By leaving breadcrumbs, we add just the step before arriving to a position. So for example, we arrived to $(2, 2)$ via $(2, 1)$, we add $(2, 1)$ as a parent of $(2, 2)$.¹

To keep track of the multiple ways to get to a position, we use a defaultdict, which I somehow keep on misspelling as defaultdic:

from heapq import heappush, heappop
from collections import defaultdict

def solution_16b(data=None, filename=None):
    # ... #
    
    def navigate_maze(grid):
        # ... #

        heappush(h, (0, s, 0))
        best_time = None
        
        visited = set()
        parent_dic = defaultdict(lambda: [])

As promised, we need to put this parent dictionary to good use. Every time we add discover a new position-direction pair, we remember where we were when we discover it and keep this information in parent_dic.

from heapq import heappush, heappop
from collections import defaultdict

def solution_16b(data=None, filename=None):
    # ... #
    
    def navigate_maze(grid):
        # ... #

        parent_dic = defaultdict(lambda: [])
        
        while len(h) > 0:
            # ... #

            if grid[ii][jj] != '#':
                to_go = (c+1, q, d)
                if to_go not in visited:
                    parent_dic[(c+1, q, d)].append((c, p, d))
                    heappush(h, to_go)
            
            to_go = (c+1000, p, (d+1)%4)
            if to_go not in visited:
                parent_dic[(c+1000, p, (d+1)%4)].append((c, p, d))
                heappush(h, to_go)
                
            to_go = (c+1000, p, (d-1)%4)
            if to_go not in visited:
                parent_dic[(c+1000, p, (d-1)%4)].append((c, p, d))
                heappush(h, to_go)

Now that we have set ourselves up, we could write the following cached recursive function and call it from the end position.

%%time
from heapq import heappush, heappop
from collections import defaultdict
from functools import cache

def solution_16b(data=None, filename=None):
    # ... #
    
    def navigate_maze(grid):
        
        # ... #

        while len(h) > 0:
            # ... #

        coords = set()
        
        @cache
        def is_part_of_shortest_path(key):
            c, p, d = key
            if (c, p, d) == (0, s, 0):
                coords.add(p)
                return True
            ret = False
            for parent in parent_dic[(c, p, d)]:
                ret = ret | is_part_of_shortest_path(parent)
            if ret:
                coords.add(p)
            return ret
            
        for i in range(4):
            is_part_of_shortest_path((best_time, e, i))

        return len(coords)
    
    return navigate_maze(grid)

And that’s it for the last four days.

Footnotes

1. I am lying a bit here because I did not talk about the direction. Technically, I also took into account the direction in addition to the position. ↩