Day 20: Race Condition
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
Hey - I’ve a question about this. Why is it correct? (Or is it?)
If you have two maps for positions in the maze that give (distance to end) and (distance from start), then you can select for points p1, p2 such that
d(p1, p2) + distance-to-end(p1) + distance-to-start(p2) <= best - 100
however, your version seems to assume that distance-to-end(p) = best - distance-to-start(p) - surely this isn’t always the case?
There is exactly one path without cheating, so yes, the distance to one end is always the total distance minus the distance to the other end.
Gotcha, thanks. I just re-read the problem statement and looked at the input and my input has the strongest possible version of that constraint: the path is unbranching and has start and end at the extremes. Thank-you!
I missed that line too:
So I also did my pathfinding for every variation in the first part, but realised something must be wrong with my approach when I saw part 2.
(I ask because everyone’s solution seems to make the same assumption - that is, that you’re finding a shortcut onto the same path, as opposed to onto a different path.)
Some others have answered already, but yes, there was a well-hidden line in the problem description about the map having only a single path from start to end…