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 ]
from time import perf_counter_ns import string def profiler(method): def wrapper_method(*args: any, **kwargs: any) -> any: start_time = perf_counter_ns() ret = method(*args, **kwargs) stop_time = perf_counter_ns() - start_time time_len = min(9, ((len(str(stop_time))-1)//3)*3) time_conversion = {9: 'seconds', 6: 'milliseconds', 3: 'microseconds', 0: 'nanoseconds'} print(f"Method {method.__name__} took : {stop_time / (10**time_len)} {time_conversion[time_len]}") return ret return wrapper_method @profiler 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 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 part2_total_cost += 3*x + y return part1_total_cost,part2_total_cost if __name__ == "__main__": with open('input', 'r') as f: input_data = f.read().strip().replace(',', '').split('\n\n') part_one, part_two = main(input_data) print(f"Part 1: {part_one}\nPart 2: {part_two}")
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.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.