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

  • RagingHungryPanda@lemm.ee
    link
    fedilink
    arrow-up
    1
    ·
    1 month ago

    I had to borrow some of y’alls code to finish part 2. My approach and all the attempts I did at trying to get the slopes of lines and such couldn’t get it high enough.

    I thought to move from the prize along it’s furthest away axis until I got to the intersection of the slope of the two buttons.

    I thought that maybe that wasn’t the cheapest way, so I fiddled around with the order of button A and B, but still couldn’t get it high enough.

    It looks like this group was mostly doing the cross product of the prize to the two buttons. I’m too dumb to realize how that would work. I thought you’d want to move along the furthest away axis first, but maybe it doesn’t matter.

    If anyone can see if I did anything obviously wrong, I’d appreciate it. I normally don’t like to take code without fixing whatever it is I was doing since it always bites me in the butt later, but here I am.

    F#

    expand for source
    let getButtonCounts (buttonA: Button) (buttonB: Button) buttonACost buttonBCost (prize:Prize) =
        // my way of trying to solve by moving the greatest axis first doesn't work for part 2.
        // everyone else seems to be using the slope between the two buttons and applying the cost
        // to a part. I don't see how it works but fuck it.
        // I had to add the `abs` calls to a and b to the borrow code, so who knows wtf. I'm done.
        let cpAB = crossProduct buttonA buttonB
        if cpAB = 0 then None
        else
            let detA = crossProduct prize buttonB
            let detB = crossProduct prize buttonA
            let struct(a, rem_a) = Int64.DivRem(detA, cpAB)
            let struct(b, rem_b) = Int64.DivRem(detB, cpAB)
            if (rem_a <> 0 || rem_b <> 0) then None
            else (abs(a) * (int64 buttonACost) + abs(b)) |> Some
        
        
        // here's where my code was. It came up short on part 2
        let (majorAxis:Point2<int64> -> int64), (minorAxis:Point2<int64> -> int64) = if prize.X > prize.Y then _.X, _.Y else _.Y,_.X
        let firstButton,firstCost, secondButton,secondCost =
            if majorAxis buttonA = majorAxis buttonB then (buttonB, buttonBCost, buttonA, buttonACost)
            else if majorAxis buttonA > majorAxis buttonB then (buttonA,buttonACost, buttonB,buttonBCost)
            else (buttonB, buttonBCost, buttonA, buttonACost)
        
        let origin:Point2<int64> = {X = 0; Y = 0}
        let toSlope button  = Segment.Slope.findL {Start = origin; End = button}
        
        let majorLine = (toSlope firstButton) |> fun s -> {Point = prize; Slope = s }
        let minorLine = (toSlope secondButton) |> fun s -> {Point = origin; Slope = s}
        
        let minorOffset = {Point = secondButton; Slope = minorLine.Slope }
        let intersection = Line.intersection majorLine minorOffset
                           |> Option.filter intersectsOnWholeNumber
                           // |> Option.filter (fun i -> i.X <= (float prize.X) && i.Y <= (float prize.Y)) // is in bounds
                           |> Option.map(fun p ->
                               let pp:Point2<int64> = {X = p.X |> round |> int64; Y = p.Y |> round |> int64}
                               pp)
                           // comparing by slopes can intersect outside of the bounds
                           // of the prize, which is not compatible
        
        match intersection with
        | None -> None
        | Some i -> 
            // steps to move to intersection
            let firstMovement =  (majorAxis prize - majorAxis i) / (majorAxis firstButton)
            // steps to move to 0
            let secondMovement = (minorAxis i) / (minorAxis secondButton)
            
            let cost = firstMovement * (int64 firstCost) + secondMovement * (int64 secondCost)
            Some cost
    
  • mykl@lemmy.world
    link
    fedilink
    arrow-up
    0
    ·
    edit-2
    2 months ago

    Uiua

    Pretty much just a transcription of my Dart solution.

    Data   ((⊜⋕⊸∈"0123456789")⊸≠@\n)(¬⦷"\n\n")"Button A: X+94, Y+34\nButton B: X+22, Y+67\nPrize: X=8400, Y=5400\n\nButton A: X+26, Y+66\nButton B: X+67, Y+21\nPrize: X=12748, Y=12176\n\nButton A: X+17, Y+86\nButton B: X+84, Y+37\nPrize: X=7870, Y=6450\n\nButton A: X+69, Y+23\nButton B: X+27, Y+71\nPrize: X=18641, Y=10279"
    IsInt  <0.00001⌵-⁅.
    AB     ÷°⊂≡(/-×⇌°⊟)[0_1 2_1 0_2]
    Cost   /+×IsInt3_1AB
    &p /+≡Cost Data
    &p /+≡(Cost(2|+1e13))Data
    
    • Quant@programming.dev
      link
      fedilink
      English
      arrow-up
      2
      ·
      2 months ago

      Welp, got frustrated again with part one because there kept being something wrong with my totally-not-ugly loop and so came here again. I did have to change IsInt (and thus also Cost to account for different handling) for part two though because I kept getting wrong results for my input.
      I’m guessing it’s because uiua didn’t see the difference between rounded and non-rounded number anymore.

      Here’s the updated, slightly messier version of the two functions that worked out for me in the end :D

      IsInt ← ≍°⊟⍉⍜(⊙(⍉≡↙₂))(/+×)⊙⍉⁅
      Cost  ← /+×3_1×⟜IsInt⊸AB
      

      Could have been done better but I’m lacking the patience for that now

      • mykl@lemmy.world
        link
        fedilink
        arrow-up
        2
        ·
        2 months ago

        Yeah, I had to fiddle with that limit before it actually worked for me, so it’s clearly quite sensitive to the data :-)

  • Acters@lemmy.world
    link
    fedilink
    arrow-up
    0
    ·
    edit-2
    2 months 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}")