Day 18

• Puzzle for the day
• Full code for my solution

My daily routine during Advent of Code is waking up, picking my iPad from the night desk and reading through the puzzle description. I then go on with my morning routine while thinking about the puzzle.

Today’s puzzle description had me suspicious - it sounded too simple. I was very happy to see it be exactly that. Today’s part 1 is basically a simplified version of Day 16 so I was able to pick up that code, modify it a bit and got the result. It’s using A* search algorithm.

But let’s not put the reindeer before the sleigh and let’s start from the inputs.

Read input

Our input today is a list of coordinates:

5,4
4,2
4,5
3,0
2,1
6,3
2,4
1,5
0,6
3,3
2,6
5,1
1,2
5,5
2,5
6,5
1,4
0,4
6,4
1,1
6,1
1,0
0,5
1,6
2,0

To read this input in, we split on the comma and convert each side to an integer:

def map_fn(line: str) -> Coordinate:
    x, y = line.split(",")
    return Coordinate(int(x), int(y))

If you’re new to my solutions and are wondering what is this map_fn, I explained my setup in Day 00. In a nutshell, I have a read_input function that accepts a map function that is run against each line of the input. In my utility library I also have a namedtuple Coordinate that I use a lot in these puzzles.

These coordinates represent corrupted blocks in memory – or impenetrable walls in a maze.

Part 1

Part 1 is a classic path finding puzzle. We take a look at the first 1024 corrupted blocks and find the shortest path. My mistake here was that I kept looking at the first 1000 instead and kept wondering how my code didn’t work correctly.

I used A* again because it’s the one path finding algorithm I’ve grown to be somewhat confident in.

The only change I made to my code from Day 16 was I removed all the directions related bits. So instead of storing (position, direction), I store position. You can check the full code for today’s solution in GitHub.

After those changes, we find the shortest path after the first 1024 blocks have been corrupted:

def part_1():
    coordinates = read_input(18, map_fn, False)
    start = Coordinate(0, 0)
    target = Coordinate(70, 70)
    _, score = find_shortest_path(start, target, coordinates[:1024])
 
    print(f"Part 1: {score}")

Part 2

Second part brings in something new for us to learn! Now we need to find out which coordinate is the first one where we cannot reach the goal anymore.

We could run the path finding function for every iteration but that would be very slow. If we think about our search space a bit, we can see that after the first blockage, everything will be blocked and vice versa, everything before the blockage will find a path.

This is a perfect circumstance for binary search.

In binary search, we count indices from both ends and as long as they are different, we search the middle value:

def find_first_blocking_corruption(
    start: Coordinate, target: Coordinate, corrupted: List[Coordinate]
) -> int:
    """Returns the index of the first corrupted tile that blocks path
    from start to target."""
    left = 1025
    right = len(corrupted) - 1
    mid = 0

Here, left is the starting index from 1025 since we know that the first 1024 lead to a path from part 1. right is the starting index from the end of the list. These are our boundaries. mid is our middle point that we’ll use to check which half of the list our problem is at.

We then loop until our left is smaller or equal than right. On each iteration, we find the new mid point and check if we can find a path.

If we cannot, we check if the previous spot allows us to find a path. If it does, we know we found the first corrupted memory block and return mid - 1. The -1 is required because of how Python’s slicing works.

Slicing in Python

Square brackets ([ ]) after a list can do quite a lot in Python.

• You can get a value by index with report[index]

• You can get everything until an index (not including the indexed item) with report[:index]

• You can get everything from index onward with report[index:]

• You can get everything between two indices (start included, end not) with report[start:end]

• You can get every nth item with report[::2]

Since the end index is not included in the search (corrupted[:mid])‘s last index is mid -1.

If the previous block is also a corrupted block, we move the new right boundary to that and continue searching.

If we can find a path, we move the left boundary to the right side of the mid boundary which we had deemed safe.

while left <= right:
	mid = (left + right) // 2
	result = find_shortest_path(start, target, corrupted[:mid])
	if result is None:
		if find_shortest_path(start, target, corrupted[: (mid - 1)]) is not None:
			return mid - 1
		right = mid - 1
	else:
		left = mid + 1

This will find us the boundary.

def find_first_blocking_corruption(
    start: Coordinate, target: Coordinate, corrupted: List[Coordinate]
) -> int:
    """Returns the index of the first corrupted tile that blocks path
    from start to target."""
    left = 1025
    right = len(corrupted) - 1
    mid = 0
    while left <= right:
        mid = (left + right) // 2
        result = find_shortest_path(start, target, corrupted[:mid])
        if result is None:
            if find_shortest_path(start, target, corrupted[: (mid - 1)]) is not None:
                return mid - 1
            right = mid - 1
        else:
            left = mid + 1

To then solve the puzzle, we find the first blocker and print that Coordinate out:

def part_2():
    coordinates = read_input(18, map_fn, False)
    start = Coordinate(0, 0)
    target = Coordinate(70, 70)
    index = find_first_blocking_corruption(start, target, coordinates)
    first_blocker = coordinates[index]
    print(f"Part 2: {first_blocker}")

Today was bit of a palate cleanser after the past couple of days. And since today is a day when I have a frontend meetup to host, I’m very happy I got through this before noon and I don’t have to think about it any more.