Claw Contraption

Advent of Code 2024 Day 13

Part 1

Big gulp: every permutation?

Another dreaded shortest path challenge.

Thankfully, it sounds doable with brute force, thanks to the constraint specified:

• No more than 100 button presses

That means if there is a solution, it exists within 1 of 10,000 permutations: 100 * 100 = 10,000

Each machine is represented as 3 lines (plus 1 empty line) in the input, totaling 4 lines.

My input is 1280 lines long.

Thus, the most computations my algorithm would make is:

 100 * 100 ------ 10000 * 1280 / 4 ------ 320 ====== 3200000 

3.2M computations isn't bad at all.

Brute force may be an option for Part 1.

Worth a try!

Attempting to brute-force the solution

Turning strings into integers

First, I need to extract the six important numbers from each machine's input:

input .split('\n') .map(block => { let [AX, AY, BX, BY, PX, PY] = [ ...block.matchAll(/d+/g).map(el => +el[0]) ] }) 

I wrote that here. Then I ran it in a code editor.

Then I debugged and fixed it until I saw the code I expected.

My working algorithm looks like this:

input .split('\n\n') .map(block => [ ...block.matchAll(/\d+/g) ].map(el => +el[0]) ) 

I made some silly mistakes.

But I now see this in my console:

[ [ 94, 34, 22, 67, 8400, 5400 ], [ 26, 66, 67, 21, 12748, 12176 ], [ 17, 86, 84, 37, 7870, 6450 ], [ 69, 23, 27, 71, 18641, 10279 ] ] 

Perfect!

Prepping for 10k permutations

Some tracking variables with starter amounts, and nested loops that count to 100, all inside a reduce that processes each machine:

let part1 = input.reduce( (total, machine) => { let [AX, AY, BX, BY, PX, PY] = machine let min = Infinity let minA = Infinity let minB = Infinity for (let A = 0; A <= 100; A++) { for (let B = 0; B <= 100; B++) { } } return total }) 

Next, some condi-tions, addi-tions and multiplica-tions:

// inside the nested for loops if ((A * AX + B * BX == PX) && (A * AY + B * BY == PY)) { if (3 * A + B < min) { minA = 3 * A minB = B min = minA + minB } } 

Again, I wrote that first here.

Then I copy-pasted it into my code editor and ran it.

And I saw the expected winning token amounts!

I got excited and wrote the rest of the algorithm.

After some clean-up and debugging, here's the final working code:

let part1 = input.reduce( (total, machine) => { let [AX, AY, BX, BY, PX, PY] = machine let min = Infinity for (let A = 0; A <= 100; A++) { for (let B = 0; B <= 100; B++) { if ((A * AX + B * BX == PX) && (A * AY + B * BY == PY)) { if (3 * A + B < min) { min = 3 * A + B } } } } if (min < Infinity) { total += min } return total }, 0) 

Running it on the example input generates the correct answer.

What about on my puzzle input?

...

Well, it finished within a second.

And generated an answer in the 10's of thousands.

Is it correct?

...

It is!

Sweet!

I don't anticipate having the computer science knowledge to refactor my brute-force algorithm into something that can solve Part 2.

I'm still excited to see the twist, though!

Part 2

Yyyyuuupp. Just what I suspected.

1 trillion higher? Yikes!

Just like yesterday's Part 2, I'm stumped.

Bummer.

After a 10-day streak of 2-stars, I'm on a 3-day streak of 1-stars.

To be fair, this is usually the spot each year where I get 0 or 1 stars.

At least I got 1!

Onward to Day 14.