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

  • Acters@lemmy.world
    3·
    23 hours ago

    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,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}")
    • Sparrow_1029@programming.dev
      2·
      2 days ago

      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 😅)

    • hades@lemm.ee
      1·
      2 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.

      • Acters@lemmy.world
        3·
        2 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.

        • Sparrow_1029@programming.dev
          2·
          2 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.

          • Acters@lemmy.world
            3·
            2 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.

            • Sparrow_1029@programming.dev
              1·
              1 day 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!

              • Acters@lemmy.world
                2·
                23 hours 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.

      • VegOwOtenks@lemmy.world
        21·
        2 days ago

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

        • Acters@lemmy.world
          2·
          2 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.