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?
(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.)
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!
