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
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-point f64 and checked that the solution for x 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
# With unmodified `main` function & `import string` not shown
In [4]: with open("inputs/day13.txt", "r") as f:
...: input_data = f.read().strip().replace(',', '').split('\n\n')
...:
In [5]: part_one, part_two = main(input_data)
In [6]: part_one
Out[6]: 39748
In [7]: part_two
Out[7]: 74926346266863
# Then I modified the function to check if x is fractional
In [8]: def main(input_data):
...: part1_total_cost = 0
...: part2_total_cost = 0
...: for machine in input_data:
...: Ax,Ay,Bx,By,Px,Py = [ int(l[2:]) for l in machine.split() if l[-1] in string.digits ]
...: y,r = divmod((Ay * Px - Ax * Py), (Ay * Bx - Ax * By))
...: if r == 0:
...: x = (Px - Bx * y) / Ax
...: if x % 1 == 0:
...: part1_total_cost += 3*x + y
...: y,r = divmod((Ay * (Px+10000000000000) - Ax * (Py+10000000000000)), (Ay * Bx - Ax * By))
...: if r == 0:
...: x = ((Px+10000000000000) - Bx * y) / Ax
...: if x % 1 == 0:
...: part2_total_cost += 3*x + y
...:
...: return part1_total_cost,part2_total_cost
...:
In [9]: part_one, part_two = main(input_data)
In [10]: part_one
Out[10]: 39748.0
In [11]: part_two
Out[11]: 74478585072604.0 # Correct answer for pt 2 of my input
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!
