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
Python
Execution time: ~<1 millisecond (800 microseconds on my machine)
Good old school linear algebra from middle school. we can solve this really really fast. With minimal changes from part 1!
FastCode
[ paste ]
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 = Px
and(Ay)*x + (By)*y = Py
Because of Ax or Ay and Bx or By, lets pretend that they are not
(A*x)*x
and(A*y)*y
for both. they are just names. could be rewritten as:(Aleft)*x + (Bleft)*y = Pleft
and(Aright)*x + (Bright)*y = Pright
but 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-pointf64
and checked that the solution forx
produces 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.
This is a really excellent, clean solution! Would you mind breaking down how the piece of linear algebra works (for a shmo like me who doesn’t remember that stuff frum school heh 😅)
https://lemmy.world/comment/13950499
take the two equations, solve for y, and make sure y is fully divisible.