17
๐ฆ - 2024 DAY 13 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')
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 ]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.
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.
I did run your code as-is in an ipython REPL to check. These were the results:
REPL session
If you're curious to check against my puzzle input, it's here
Thank you again for the back & forth, and for sharing your solution!
there is exactly ONE "machine" that causes your result to be incorrect. ONLY for part 2.
I see now what your corner case causes. so when my script solves for y first. it will be exact. BUT when you solve for x, it will be not divisible... makes sense now. I didn't expect this. This only occurs because of part 2! so dastardly. well, that was interesting. I guess I am forced to add that extra check... rip those microsecond gains.
Ooh that is tricky of them. Good catch!
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.