Day 13: Claw Contraption
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
It’s interesting that you’re not checking if the solution to x is a whole number. I guess the data doesn’t contain any counterexamples.
we are solving for y first. If there is a y then x is found easily.
(Ax)*x + (Bx)*y = Pxand(Ay)*x + (By)*y = PyBecause of Ax or Ay and Bx or By, lets pretend that they are not
(A*x)*xand(A*y)*yfor both. they are just names. could be rewritten as:(Aleft)*x + (Bleft)*y = Pleftand(Aright)*x + (Bright)*y = Prightbut I will keep them short. solving for y turns into this:
y = (Ay*Px - Ax*Py) / (Ay*Bx - Ax*By)if mod of 1 is equal to 0 then there is a solution. We can be confident that x is also a solution, too. Could there be an edge case? I didn’t proof it, but it works flawlessly for my solution.
Thankfully, divmod does both division and mod of 1 at the same time.
Thank you so much for your explanation! I kind of found some clues looking up perp dot products & other vector math things, but this breaks it down very nicely.
I implemented your solution in rust, and part 2 failed by +447,761,194,259 (this was using signed 64-bit integers,
i64). When I changed it to use signed 64 bit floating-pointf64and checked that the solution forxproduces a whole number it worked.Did you run my python code as is? I would hope it works for everyone. though, I am unsure what the edge cases are, then.
They do, if the remainder returned by divmod(…) wasn’t zero then it wouldn’t be divisble
you are right, we solve for y, but I am confident that solving for x after y would yield the correct result as long as y is fully divisible.