Bridge Repair

Advent of Code 2024 Day 7

Part 1

First recursion of the year

At least that's how I intend to earn one gold star today:

• Start with the full list
• Check both addition and multiplication
• For each result, continue with the remainder of the list
• Until I have either exceeded or matched the total

The difficulty will be in the details.

Let's do this!

Crafting my algorithm

First, I need to parse each line into a list of numbers:

let eqs = input.split('\n').map(line => {
  return [...line.matchAll(/\d+/g)].map(el => +el[0])
})

The first element is the desired total.

The rest are the ordered operands of the equation.

I'll need to account for this in my recursive function.

Here's my recursive function:

function eqChecker(operands, amount, test) {
  if (amount > test) {
    return false
  } else if (amount == test && operands.length == 0) {
    return true
  } else if (operands.length) {
    let copy = operands.slice()
    let first = copy.shift()
    return eqChecker(copy, amount + first, test) || eqChecker(copy, amount * first, test)
  }
}

And here is the reduce that uses it:

let part1 = eqs.reduce((count, eq) => {
  if (eqChecker(eq.slice(2), eq[1], eq[0])) {
    count += eq[0]
  }
  return count
}, 0)

As I hoped but never expect, it generates the correct answer for the example input!

Will it finish processing my puzzle input?

And if so, will it generate the correct answer?

I'm honestly not sure...

IT DID!!!

Woah!!!

As excited as I am, I fear that the next part will either add more operators, or require some advanced CS to make recursion no longer a viable solution.

Part 2

Totally unexpected! And way more difficult

How am I even going to do this?

...

A few days later...

A recap of my thought process:

• Is it as simple as adding a third clause to my return condition? Nope
• Is my Part 1 recursive function even configured correctly for success? Nope
• Oh no, is it even feasible to accrue an amount that's a result of prior operations? Nope
• Am I really going to have to approach this with a new strategy? Yup

Considering all new variations

For this equation:

292: 11 6 16 20

These are all possible equations given the three operators:

11 
11+6 
11+6+16 
11+6+16+20 
11+6+16*20 
11+6+1620 
11+6*16 
11+6*16+20 
11+6*16*20 
11+6*1620 
11+616 
11*6 
11*6+16 
11*6+16+20 
11*6+16*20 
11*6+1620 
11*6*16 
11*616 
116 
116+16 
116+16+20 
116+16*20 
116+1620 
116*16 
11616 

Perhaps I can build up a string of each equation and manually evaluate it inside my recursive function.

For instance:
I start with an empty string in the outer-most function call:

""

From there, I create three variations using the next number:

"" + "+N"
"" + "*N"
"" + "N"

Hmm, but this won't work for the first number.

I need to start my first function call with the first number, not an empty string:

"N"

Same thing from there:

"N" + "+N"
"N" + "*N"
"N" + "N"

Ya, that should work.

By the end, I'll have these sample variations, all evaluable:

let eqs = input.split('\n').map(line => {
  return [...line.matchAll(/\d+/g)].map(el => +el[0])
})

Skip to: I coded it...and discovered a bigger issue

I wrote code that successfully generates all variations of equation.

function eqChecker(operands, amount, test) {
  if (amount > test) {
    return false
  } else if (amount == test && operands.length == 0) {
    return true
  } else if (operands.length) {
    let copy = operands.slice()
    let first = copy.shift()
    return eqChecker(copy, amount + first, test) || eqChecker(copy, amount * first, test)
  }
}

• i is used to walk down the list of numbers
• The last clause only proceeds if i is before or at the second-to-last index

The function gets four values:

1. A copy of the list of numbers, minus the expected total
2. The next index
3. The equation string with one of three strings concatenated to it
4. The same test number

I call the function using nearly the same signature as in Part 1:

let part1 = eqs.reduce((count, eq) => {
  if (eqChecker(eq.slice(2), eq[1], eq[0])) {
    count += eq[0]
  }
  return count
}, 0)

The difference is in what I pass as arguments:

1. The list without the expected total amount
2. Start at index 0
3. A string containing the first number
4. The expected total amount

Great news:

• It generates all equation variations

Bad news:

• It evaluates all equations using PEMDAS, not left-to-right

I should have known better...that the built-in JavaScript evaluator would default to the correct order of operations, not left-to-right.

This really throws an even bigger wrench into my algorithm:

• I'm going to have to break each equation apart and evaluate it portion-by-portion

Uggghhh.

Thankfully, I think I know just how to do that.

Doing maths manually

I need to get JavaScript to evaluate an equation like this:

292: 11 6 16 20

In this order:

11 
11+6 
11+6+16 
11+6+16+20 
11+6+16*20 
11+6+1620 
11+6*16 
11+6*16+20 
11+6*16*20 
11+6*1620 
11+616 
11*6 
11*6+16 
11*6+16+20 
11*6+16*20 
11*6+1620 
11*6*16 
11*616 
116 
116+16 
116+16+20 
116+16*20 
116+1620 
116*16 
11616 

I'd like to split that equation into its parts:

""

The only way I see how is with this triple-chained expression:

"" + "+N"
"" + "*N"
"" + "N"

I pad each operator with white space only to use it as a separator.

A fact about this list of equation parts:

• It will always contain an odd amount of items that is 3 or greater

How can I leverage that fact in some loop that iterates through each operand-operator-operand pair?

Here's my idea:

• Remove the first three items
• Join them as a string and evaluate that as a math expression
• Reattach the result at the beginning of the equation list
• Repeat until the equation list is empty

Here's to hoping it works!

My working math simulator in JavaScript:

"N"

Great news:

• It's showing me the expected computed values

Bad news:

• I'm still not getting the correct answer for one equation in the example input

The example answer can't be wrong...can it??

The answer I keep generating is about 7k short of the expected answer.

That makes me think my algorithm isn't identifying this equation as correct:

let eqs = input.split('\n').map(line => {
  return [...line.matchAll(/\d+/g)].map(el => +el[0])
})

In the explanation of the example input, this is the winning equation:

function eqChecker(operands, amount, test) {
  if (amount > test) {
    return false
  } else if (amount == test && operands.length == 0) {
    return true
  } else if (operands.length) {
    let copy = operands.slice()
    let first = copy.shift()
    return eqChecker(copy, amount + first, test) || eqChecker(copy, amount * first, test)
  }
}

My algorithm evaluates that equation and generates this outcome:

let part1 = eqs.reduce((count, eq) => {
  if (eqChecker(eq.slice(2), eq[1], eq[0])) {
    count += eq[0]
  }
  return count
}, 0)

That's because my algorithm runs like this:

292: 11 6 16 20

I don't see how it could be any other number.

So...I Google'd.

And I found my answer, which was hiding in plain site in the explanation, as always:

All operators are still evaluated left-to-right.

I was pre-concatenating values with each recursive function call.

Instead, my algorithm should be doing this:

11 
11+6 
11+6+16 
11+6+16+20 
11+6+16*20 
11+6+1620 
11+6*16 
11+6*16+20 
11+6*16*20 
11+6*1620 
11+616 
11*6 
11*6+16 
11*6+16+20 
11*6+16*20 
11*6+1620 
11*6*16 
11*616 
116 
116+16 
116+16+20 
116+16*20 
116+1620 
116*16 
11616 

Now that I understand what's supposed to happen, can I adjust my algorithm to match that processing behavior?

Left-to-right...for real this time

Thankfully, adjusting my algorithm was relatively easy.

I added a replaceAll() clause to account for ||.

The new while loop where I process every three items looks like this:

""

And I adjusted my return statement's || clause to include those characters, instead of instantly-concatenating the two numbers.

Testing and re-testing

I ran the algorithm on the example input.

It finally generated the correct answer!!

What a relief!!

I wonder if it will finish running and generate the correct answer on my puzzle input.

Pressing run...

...

...

I got an answer!

It's huge, so that's probably a good sign.

Is it the correct answer?

...

No. Too high.

Bummer.

Am I missing an edge case?

My condition for a winning equation is simply that the processed math equals the test amount.

But, what if one of the variant equations allows for a subset of numbers to generate a correct answer?

To catch and exclude this scenario, I updated my if condition to include one more clause:

"" + "+N"
"" + "*N"
"" + "N"

This way, only if all numbers are processed and the resulting amount equals the test number, will the equation be counted.

The big question:

• Does this change the answer I get?

Pressing run again...

...

Hmm, it sure still looks like the same answer.

Oh, wait, there are two digits near the end that are different!

My new answer is exactly 80 less than before.

Is there an equation with 80 as the expected amount?

Yes!

"N"

Is there a way to make 80 without using all the numbers?

Yes!

"N" + "+N"
"N" + "*N"
"N" + "N"

Was this the sole edge case that I needed to exclude?

Submitting my new answer...

IT'S CORRECT!!!

Woohoo!!!

I did it!!!

That. Was. Exhausting. And exhilarating. And really run. And challenging.

And every reason why I love doing these puzzles.

Onward to the next one!

The above is the detailed content of Bridge Repair. For more information, please follow other related articles on the PHP Chinese website!