Day 20: Race Condition
Todays challenge was yet another 2D puzzle map with a difference. It took me a while to understand what was expected and meant from the "cheat". But with trial and error I found a solution and understanding.
I opted for Python again today, mostly as I'm enjoying learning a new coding language, and each day finding a different approach / new method or function to use. I'm slowly beginning to learn the syntax and better ways / different ways of writing the same thing.
I hope the solution and brief explanation helps. Apologies the write-ups are getting shorter, the challenges are more difficult and getting closer to Xmas I'm struggling to find the time to solve, and writeup in great detail.
Problem
The basic concept of the challenge was - navigating a grid from a start position (S) to an endpoint (E). The program can move up, down, left, or right, with walls (#) blocking movement. However, during the race, the program can "cheat" and temporarily pass through walls for up to 2 picoseconds and 20 picoseconds, allowing the program to save time.
Part 1
Work out how many cheats would have to take place to save >= 100 "picoseconds" with a cheat time of 2 seconds.
Main concepts are:
can_move(grid, position, visited)
Checks if the program can move to the specified position. It checks if the position is within bounds, not yet visited, and if it’s a valid move (track, start, or end).
traverse_grid(grid, start, end)
Implements the main grid traversal. This function simulates the program moving from the start (S) to the end (E) while recording the steps taken. Each move counts as 1 picosecond, and the visited dictionary tracks the time taken to reach each position.
``` count_cheat_positions(grid, visited)
After the program has traversed the grid, this function checks for potential "cheats." It evaluates if a position, when visited, allows the program to "cheat" (pass through a wall for 2 picoseconds) and save time. It checks if the program can move through two consecutive moves that may bypass walls, and get back on the track and how much time this would save.
Finally, it counts how many cheats save at least 100 picoseconds.
## Part 2
Part 2 works in a very similar way, with the biggest difference being the longer cheat time, we now have 20picoseconds to cheat.
get_cheat_endpoints(coords, track)
Part Two introduces a more significant change here. Instead of just checking immediate neighbours, this function now finds nearby positions within a **20-unit range**. It returns a set of positions that are within this range of the current coordinate.
This is crucial because the cheat now allows for a larger cheating duration (up to 20 picoseconds).
manhattan_distance(coord1, coord2)
This function calculates the Manhattan distance between two coordinates. The Manhattan distance is relevant because it is the primary measure of distance in a grid which doesn’t travel in diagonals, especially when evaluating the time saved through cheating.
The Manhattan distance function is required in Part Two because the cheat rule allows the program to cheat over a wider range of positions (up to 20 places), and this range needs to be evaluated using the Manhattan distance. In Part One, the distance of a cheat is far less.
As always feel free to follow and reach out on [Twitter](https://x.com/grantdotdev)
Top comments (0)