Advent of Code has a leaderboard for people who complete challenges quickly. The more quickly you complete a challenge, the more points you earn. And while I’ve never been fast enough to earn a single point, I did get a rank of 692 on the leaderboard for Part 2 today – my best rank so far this year!¹

I’m solving the Advent of Code challenges in Python. If all you want is my code for this, you can look for it on my GitHub repository. But if you want to hear me explain my solutions, stick around.

Challenge

You and The Historians are inside a computer again – just like you were two days ago, and apparently back in 2017 – and one of its programs walks up to you and challenges you to a race!² (The programs are holding a race condition festival.)

They give you a map of the racetrack, which looks something like this:

###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############

Programs will start on the S tile, and they are allowed to move up, down, left, and right (as long as they don’t run into a wall, or # tile) until they get to the E tile. Each move takes 1 picosecond, and the goal is to reach the end position as quickly as possible. (In this case, it can be done in 84 picoseconds.)

Now, because there is only one path to the end,³ this would be a pretty boring race on its own. So to make it more interesting, the programs are allowed to cheat.

Exactly once during the race, a program may cheat by disabling wall collision for up to 2 picoseconds (which can end up saving plenty of time during the race, if used wisely!). Once the cheat is over, the program must end up back on the track, otherwise it gets disqualified.

Here are some examples of possible cheats (where the 1st and 2nd move of the cheat are marked with 1 and 2). This one would complete the race in 72 picoseconds, saving 12 picoseconds.

###############
#...#...12....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############

This cheat would complete the race in 64 picoseconds, saving 20 picoseconds.

###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...12..#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############

This cheat would save 38 picoseconds.

###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.####1##.###
#...###.2.#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############

And finally, this cheat would save 64 picoseconds (this would bring the program directly to the end position).

###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..21...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############

You want to compile a list of the best possible cheats you could do. For Part 1, you want to count how many cheats would save you at least 100 picoseconds.

Later, you find out that the cheating rule has been changed: you are now allowed to do a single cheat lasting up to 20 picoseconds!

This greatly expands the number of cheats that are possible. For example, this 6-picosecond cheat will save 76 picoseconds.

###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#1#####.#.#.###
#2#####.#.#...#
#3#####.#.###.#
#456.E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############

Note that each cheat has a unique start position (the one just before the first move that walks through walls) and end position, which uniquely identify the cheat. That means that this cheat is exactly the same as the one above, even though the paths are different.

###############
#...#...#.....#
#.#.#.#.#.###.#
#S12..#.#.#...#
###3###.#.#.###
###4###.#.#...#
###5###.#.###.#
###6.E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############

For Part 2, you still want to count how many cheats would save you at least 100 picoseconds. But thanks to the new cheating rule, there are many more cheats that are now possible.

My solution

Another day, another grid-based puzzle. Another maze-based puzzle, in fact; we had another one on Day 16.⁴ But thankfully, today doesn’t involve any complex pathfinding.

First, imports and parsing, same as always.

from collections import defaultdict
from collections.abc import Iterable
from typing import TypeAlias


Vector: TypeAlias = complex
Grid: TypeAlias = defaultdict[Vector, str]
OFFSETS: tuple[Vector, ...] = (1 + 0j, -1 + 0j, 1j, -1j)


def parse_input(lines: Iterable[str]) -> tuple[Grid, Vector, Vector]:
    """
    Parse the input, and return a grid, a starting position, and an
    ending position.
    """
    grid: Grid = defaultdict(lambda: "#")
    start_pos, end_pos = None, None
    for y, line in enumerate(lines):
        for x, char in enumerate(line):
            pos = x + y * 1j
            if char == "S":
                start_pos = pos
            elif char == "E":
                end_pos = pos
            grid[pos] = char
    assert start_pos is not None and end_pos is not None
    return grid, start_pos, end_pos

My solution was to take every position along the path, try every single possible cheat from there, and count the ones that saved 100 picoseconds or more. Or in other words, brute-forcing. (If it works, it works!)

But first, I have to find the path. (This is greatly simplified by the fact that there’s only one of them.) I record each position along the path in a dict, as well as the number of moves we’ve made up to that point.

def count_good_cheats(
        grid: Grid,
        start_pos: Vector,
        end_pos: Vector,
        cheat_length: int,
) -> int:
    """
    Count the number of "cheats" that can be done in the grid that save
    100 picoseconds or more.
    """
    # Start by finding the one path from the start to the end
    pos = start_pos
    # We will record the position along the path at each point
    path: dict[Vector, int] = {start_pos: 0}
    # Until we reach the end
    while pos != end_pos:
        for offset in OFFSETS:
            next_pos = pos + offset
            # Don't move into a wall...
            if grid[next_pos] == "#":
                continue
            # ...or revisit a previously visited tile
            if next_pos in path:
                continue

            # This is the next position along the path
            # NOTE This assumes there are no branches along the path.
            pos = next_pos
            break
        else:
            raise RuntimeError("no path forward exists")

        # Record this position along the path
        path[pos] = len(path)

Then I count the cheats. While I used a pretty simplistic approach for Part 1,⁵ I realized while solving Part 2 that the same approach I used to solve it could be used to solve both parts.

The challenge reminded me of taxicab geometry, which considers the “distance” between two points as the sum of the absolute differences of the coordinates. (Think of it as the number of city blocks a taxi would drive through to get from one point to the other.)

In regular Euclidean geometry, a “circle” is defined as the set of all points at some fixed distance to a center point (and it looks like…well, a circle). In taxicab geometry, this same definition gives something that looks more like a square tilted on its side. We can model all the allowed cheats of a certain length as the points inside of a taxicab circle with a radius of that length.

The way I looped through all the points inside of that taxicab circle was to loop through all X values from -r to r (where r is the radius), and do a nested loop through all Y values from -(r - abs(x)) to r - abs(x). It’s not too elegant, but it works.

    good_cheats = 0
    # For every point along the path
    for pos, move in path.items():
        # For each valid cheat that can be done here
        # NOTE For each valid cheat, the sum of the absolute changes of
        # X and Y is at most the allowed length of the cheat.
        dx_limit = cheat_length
        for dx in range(-dx_limit, dx_limit + 1):
            dy_limit = cheat_length - abs(dx)
            for dy in range(-dy_limit, dy_limit + 1):
                cheat = dx + dy * 1j
                cheat_pos = pos + cheat

I then only record a cheat if it doesn’t end up in a wall, doesn’t end up outside the grid, and saves at least 100 picoseconds over moving to its endpoint normally.

                # Don't do this cheat if it would move us into a wall...
                if grid[cheat_pos] == "#":
                    continue
                cheat_move = path.get(cheat_pos, None)
                if (
                    # ...or if it would move us outside the grid...
                    cheat_move is None
                    # ...or if it wouldn't save enough time
                    or cheat_move - (move + abs(dx) + abs(dy)) < 100
                ):
                    continue

                # This is a good cheat
                good_cheats += 1

    return good_cheats

After defining the count_good_cheats() function, the only difference between Parts 1 and 2 is the cheat_length parameter – 2 for Part 1, and 20 for Part 2.

def aoc2024_day20_part1(lines: Iterable[str]) -> int:
    grid, start_pos, end_pos = parse_input(lines)
    return count_good_cheats(grid, start_pos, end_pos, cheat_length=2)


def aoc2024_day20_part2(lines: Iterable[str]) -> int:
    grid, start_pos, end_pos = parse_input(lines)
    return count_good_cheats(grid, start_pos, end_pos, cheat_length=20)

Overall

Looking through other people’s solutions today, I was hoping to find approaches that were more efficient than mine (because it felt like there should be one). Those were hard to come by.

The challenge prompt explicitly said that there existed only one path from the start to the end, meaning a shortest-path algorithm wouldn’t have been needed today. Despite this, I saw many people who used a shortest-path algorithm anyway, including Dijkstra’s algorithm and breath-first search. (Perhaps this was just out of convenience?)

Looping through every possible cheat on every possible tile was a pretty common solution, although some people did that in different ways. This person looped through every tile within a square centered at the tile, and filtered them by taxicab distance. This person looped through every tile in the entire grid! And this person looped through only the tiles within the required distance, like I did.

One solution I considered is to loop through every pair of points on the path, and check that they’re within the required distance, like this person did. When I tried it, it turned out to be pretty slow, even for Part 1. But I did see some people speed up this approach a bit, like this person, by checking a pair of points only if they’re already 100 steps away or more on the path.

I wasn’t able to find too many approaches that were more efficient than mine. This person had a solution using the external library networkx that ran in about a third of a second, but the algorithms themselves are basically the same.