Bridge Repair-JS Tutorial-php.cn

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])
})

Copy after login

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)
  }
}

Copy after login

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)

Copy after login

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

Copy after login

These are all possible equations given the three operators:

Copy after login

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:

""

Copy after login

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

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

Copy after login

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"

Copy after login

Same thing from there:

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

Copy after login

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])
})

Copy after login

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)
  }
}

Copy after login

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:

A copy of the list of numbers, minus the expected total
The next index
The equation string with one of three strings concatenated to it
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)

Copy after login

The difference is in what I pass as arguments:

The list without the expected total amount
Start at index 0
A string containing the first number
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

Copy after login

In this order:

Copy after login

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

""

Copy after login

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

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

Copy after login

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"

Copy after login

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])
})

Copy after login

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)
  }
}

Copy after login

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)

Copy after login

That's because my algorithm runs like this:

292: 11 6 16 20

Copy after login

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:

Copy after login

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