🦀 - 2024 DAY 13 SOLUTIONS -🦀

posted 14 days ago

CameronDev@programming.devM

advent_of_code@programming.dev

33 commentshide report

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

Sort:

Hot Top Controversial New Old

You are viewing a single thread.

View all comments View context

[ - ]

hades@lemm.ee

2 points

14 days ago

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.

permalink

report

parent

[ - ]

VegOwOtenks@lemmy.world

1 point

14 days ago

They do, if the remainder returned by divmod(…) wasn’t zero then it wouldn’t be divisble

permalink

report

parent

[ - ]

Acters@lemmy.world

2 points

13 days ago

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.

permalink

report

parent

[ - ]

Acters@lemmy.world

3 points

13 days ago

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.

permalink

report

parent

[ - ]

Sparrow_1029@programming.dev

2 points

13 days ago

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.

permalink

report

parent

[ - ]

Acters@lemmy.world

3 points

13 days ago

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.

permalink

report

parent

[ - ]

Sparrow_1029@programming.dev

1 point

12 days ago

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!

permalink

report

parent

[ - ]

Acters@lemmy.world

2 points

12 days ago

there is exactly ONE “machine” that causes your result to be incorrect. ONLY for part 2.

Button A: X+67, Y+67
Button B: X+16, Y+73
Prize: X=4877, Y=7214

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.

permalink

report

parent

[ - ]

Sparrow_1029@programming.dev

1 point

12 days ago

Ooh that is tricky of them. Good catch!

permalink

report

parent

Show more comments