Advent of Code

I’m officially off schedule now as I didn’t really have much time yesterday for these puzzles, but I’ll try to keep going, without pressuring myself. If I get more behind, that’s fine.

Anyway: day 20 is a maze againg, so we’re continuing from day 18 and day 16. This time, there’s only one path through… but we can cheat.

Part 1 - small cheat

We first need to find how much we can gain by removing a single wall from the maze, creating a shortcut. So for instance, marking $ as the shortcut:

The long way round from A to B is 14 steps, through the shortcut it’s 2, so we gain 12. For the first part of the puzzle, we have to find (in a 141 by 141 grid), all the cheats that save at least 100 steps.

I won’t go through all the parsing and maze-solving steps because it’s exactly the same as in day 18. After that, we have the “best” (and only) path, with a list of Node, which is our class to handle the positions in the grid and their neighbours. And we of course have the grid as a dictionary mapping Position (as a namedtuple) to Node.

The laziest solution that I could think of what simply to create copies of the grid, removing one wall at a time, and recomputing the path so that I could compare the length with the original. But that was way too slow, and completely unecessary. Because we already know most of the path, so we only need to compute how much we shorten it.

I eventually went for a two-pass solution: first, I went through the grid to find “candidate” walls to remove, i.e. walls that were surrounded on the left and right or on the top and bottom by path-nodes.

def find_cheat_candidates(grid: dict[Position, Node]) -> set[Position]:
    maxrow = max(p.row for p in grid.keys())
    maxcol = max(p.column for p in grid.keys())
    candidates = set()
    for r in range(maxrow+1):
        for c in range(maxcol+1):
            n = grid.get(Position(r, c))
            if n is not None:
                continue
            # check if we can make a shortcut
            if grid.get(Position(r-1, c)) is not None and grid.get(Position(r+1, c)) is not None:
                candidates.add(Position(r, c))
            if grid.get(Position(r, c-1)) is not None and grid.get(Position(r, c+1)) is not None:
                candidates.add(Position(r, c))
    return candidates

Then we go through the list of candidates and lookup the position of the neighbours in the path. If we make a shortcut from A to B, then the gain is position(A) - position(B) - 2 (since the new path will always take 2 steps: from A to the wall and from the wall to B).

def find_cheats(grid: dict[Position, Node], path: list[Node]):
    candidates = find_cheat_candidates(grid)
    print(len(candidates), "candidates to check.")

    gains = []
    path_positions = [n.position for n in path]
    for candidate in tqdm.tqdm(candidates):
        # check what are the lowest and highest position neighbours on the path:
        positions = []
        if (ln := Position(candidate.row, candidate.column-1)) in path_positions:
            positions.append(path_positions.index(ln))
        if (rn := Position(candidate.row, candidate.column+1)) in path_positions:
            positions.append(path_positions.index(rn))
        if (tn := Position(candidate.row-1, candidate.column)) in path_positions:
            positions.append(path_positions.index(tn))
        if (bn := Position(candidate.row+1, candidate.column)) in path_positions:
            positions.append(path_positions.index(bn))
        gains.append(max(positions)-min(positions)-2)

    return gains, candidates

grid, start = parse_input(False)
_, path = solve_maze(start, grid) # from Day 16

path.insert(0, start) # add the start which we didn't put in the path before
cheat_lengths, _ = find_cheats(grid, path)

print(f"Part 1 answer: {len([gain for gain in cheat_lengths if gain >= 100])}")

Part 2 - a certain lack of precision

In almost all the puzzles so far (except for the Christmas tree from day 14) I thought that the instructions were very clear and precise (or at least obsfuscated in a way that made sense once you undertand it), but here it’s another one where I didn’t like the formulation, even after completing the puzzle.

So first the twist: now we don’t just remove one wall, but our cheat can take up to 20 steps (including the final step which must end onto the path). We still have to count how many cheats save at least 100 steps.

The confusion comes from what it means to start – or end – cheating. The text is clear that, if there are multiple cheating paths from A to B, we only have to count one. But the question is: do we start cheating when we enter a wall, and end it when we get back to the path, or can we “enter cheat mode” on the path, stay on the path for a few steps, cross walls, get back on the path for a few steps and “end” our cheat mode there?

Fortunately for me, I felt that the latter was easier to implement and that my best bet was to first use that rule, and if I’m wrong add more restrictions later. Because the solution, if we don’t care about staying a bit on the path while “cheating”, is actually very easy. From any point A in the path, we have to find all points B on the path such that B and A are separated by a Manhattan distance of at most 20, and their position in the path are separated by at least 100 plus the Manhattaan distance. We end up with a code that’s actually easier than for part 1:

def manhattan(a: Position, b: Position) -> int:
    return abs(a.row-b.row)+abs(a.column-b.column)

def find_updated_cheats(path: list[Node],
                        min_gain: int = 100,
                        max_cheat: int = 20):
    gains = []
    path_positions = [n.position for n in path]

    for i, pos in tqdm.tqdm(enumerate(path_positions[:-min_gain])):
        for j, target in enumerate(path_positions[i+min_gain:]):
            if (d := manhattan(pos, target)) <= max_cheat:
                gain = j+min_gain-d
                if gain >= min_gain:
                    gains.append(gain)
    return gains

cheats = find_updated_cheats(path, 100, 20)
print(f"Part 2 answer: {len([gain for gain in cheats if gain >= 100])}")

I was fully expecting this to not work – but it did. Part 2 complete then, I guess.