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
    link
    2
    edit-2
    12 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 = (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}")
    
    
    • @[email protected]
      link
      fedilink
      17 hours 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
        link
        2
        edit-2
        2 hours 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.

        • @[email protected]
          link
          fedilink
          1
          edit-2
          1 hour 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.

      • @VegOwOtenks
        link
        0
        edit-2
        6 hours ago

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

        • @Acters
          link
          12 hours 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.

    • @[email protected]
      link
      fedilink
      18 hours 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 😅)