Day 8: Haunted Wasteland
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)
- Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)
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
[language: Lean4]
I did not make the assumption that the distance from the start to the goal is the same as the cycle length. This made the problem a bit harder, but I’m pretty sure my solution is actually generic. As always, I’ll only post the direct solution. Helper functions (like, in this case, xgcd) are in other files, you can find them together with the full solution on github.
Since my solution contains a ton of comments (that outline my thought process), I’ll again split it in several posts here.
Part1
Actually, all my comments in Part 2 make it too big for a single post. The full solution consists of two functions (that could be combined with a bit more work…).
The first function is a brute-force approach, that has a similar termination condition to the first part. It halts, once all paths are walking in circles. This function does not find a solution yet. Then there is a second function that looks for solutions that appear later, while all paths are already walking in circles. That function writes all goals as equations of the form
x = start + n * period
. The target condition is that all paths have the same value forx
. This was then solved by looking at all permutations between two paths, and solving the Diophantine equations, creating a new, combined, path.In the end, the closest resulting valid goal was also the final result.
Part2, the Brute Force function
And last, but not least, here’s the part that actually finds the result:
Part 2, the part for after the brute force approach fails (don't be alarmed, it's mostly comments, very few actual code lines)