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
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,r = divmod(Px - Bx * y, Ax)
if r == 0:
part1_total_cost += 3*x + y
y,r = divmod((Ay * (Px+10000000000000) - Ax * (Py+10000000000000)), (Ay * Bx - Ax * By))
if r == 0:
x,r = divmod((Px+10000000000000) - Bx * y, Ax)
if r == 0:
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}")
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-point f64 and checked that the solution for x produces a whole number it worked.
They do, if the remainder returned by divmod(…) wasn’t zero then it wouldn’t be divisble
