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
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
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 ← /+×IsInt.×3_1AB &p /+≡Cost Data &p /+≡(Cost⍜(⊡2|+1e13))Data
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 alsoCost
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
Yeah, I had to fiddle with that limit before it actually worked for me, so it’s clearly quite sensitive to the data :-)
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.