20
🎄 - 2023 DAY 8 SOLUTIONS -🎄
(programming.dev)
An unofficial home for the advent of code community on programming.dev!
Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.
Solution Threads
M | T | W | T | F | S | S |
---|---|---|---|---|---|---|
1 | 2 | 3 | ||||
4 | 5 | 6 | 7 | 8 | 9 | 10 |
11 | 12 | 13 | 14 | 15 | 16 | 17 |
18 | 19 | 20 | 21 | 22 | 23 | 24 |
25 |
Icon base by Lorc under CC BY 3.0 with modifications to add a gradient
console.log('Hello World')
[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)