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.