Mirage Maintenance

Advent of Code 2023 Day 9

Part 1

An inverted, recursive pyramid scheme!

The diagrams are wonderfully explicit about the recursive nature of these strings of numbers.

Especially their sharing of a base case where all numbers are identical.

This feels like a no-brainer about which strategy to use.

That's good, because I'll need all my brain power for making the recursion work.

Putting the recursive jigsaw together one requirement at a time

First, a function:

function nextDiff() {

}

Next, a parameter:

function nextDiff(listOfValues) {

}

Then, a base case:

function nextDiff(listOfValues) {
  if (listOfValues.length == 1 || listOfValues.every(value => value == listOfValues[0]) {
    return listOfValues[0]
  }
}

Lastly, all non-base cases:

function nextDiff(listOfValues) {
  if (listOfValues.length == 1 || listOfValues.every(value => value == listOfValues[0]) {
    return listOfValues[0]
  } else {
    return nextDiff(listOfValues.reduce((newList, value, index) => {
      if (index < newList.length - 1) {
        newList[index] = Math.abs(value - listOfValues[index + 1])
      }
      return newList
    }, new Array(listOfValues.length - 1))
  }
}

I wrote all that code in this article first. There are probably errors in syntax and logic. Time to copy-paste over to replit.com and really dive in.

Corrected algorithm

After a lot of printing, adjusting, fixing, condensing and line breaking, this is my working nextDiff recursive function:

function nextDiff(listOfValues) {
  if (
    listOfValues.length == 1 || 
    listOfValues.every(value => value == listOfValues[0])
  ) {
    return listOfValues[0]
  } else {
    return listOfValues[listOfValues.length - 1 ] 
      + nextDiff(listOfValues.reduce(
        (newList, value, index) => {
          if (index < newList.length) {
            newList[index] = Math.abs(value - listOfValues[index + 1])
          }
          return newList
        }, new Array(listOfValues.length - 1)))
  }
}

Thankfully, that's where all the work happens.

I wrapped it in a reduce() to process and sum up each line of input:

input.reduce(
  (sum, line) => sum += nextDiff(
    [...line.matchAll(/\d+/g)].map(el => +el[0])
  ), 0)

It generates the correct answer for the example input.

The question is:

• What edge case am I not accounting for in my puzzle input?

Time to run it and find out!

Darn. My answer is too high.

Major error: negative numbers!

My regex completely omits negative numbers.

After fixing that, my answer is a bit lower, so I try submitting it again.

Darn. My answer is still too high.

Revealing some odd results

When I print the list of values as seen in each base case, I find some unsettling results:

[ 2 ]
[ 4 ]
[ 23608 ]
[ 6 ]
[ 24 ]
[ 602 ]
[ 2 ]
[ 50 ]
[ 4 ]
[ 2 ]
[ 52 ]
[ 2 ]
[ 177540 ]

What's going on here?

• My algorithm - in these cases - seems to never reach a state wherein all values are the same within the list
• So it keeps chopping off the last item until only one is left

I should also mention that my algorithm doesn't even reach a case where all values are 0.

That's because to me that seems like a step too far.

I am really just looking for a state where all values are the same, since the next state would be all 0 differences.

Still, I don't know how I'm seeing these 1-element lists.

I'm inspecting the math and everything seems like it is correct.

But something is clearly not working as expected.

Because I'm almost certain each list should eventually reach a state of 1 or more 0s.

Right?

Refactoring a reduce into a for loop

I'm concerned my reduce is misbehaving.

I'll pivot to the more rudimentary for loop.

let newList = []
for (let i = 0; i < list.length - 1; i++) {
  newList.push(list[i] - list[i + 1])
}
return list[list.length - 1] + nextDiff(newList)

And?

Same answer. Huh.

Maybe I need to really really inspect one of my misbehaving input lines.

Digging for the root cause

One of the lines in my input eventually reaches this state:

1 5 5 5 5 5 5 5 5 5 5

It really seems like that 1 should be a 5.

So, what if I stepped back up the chain, adjusting each first value to ensure it resulted in a 5 being there?

Here are both states compared:

16 21 21       16 21 21
 5  0  6       -5  0  6
 5  6 28        5  6 28
 1 22 36        1 22 36
21 14 28       21 14 28
 7 14 41        7 14 41
 7 27 69        7 27 69
20 42 88       20 42 88
22 46 71       22 46 71
24 25 30       24 25 30
 1  5  5        5  5  5

That's it!

The -5 in the second state!

What does this mean about my algorithm?

• It means I must always capture the difference when subtracting the second number from the first number
• It means I should not capture the absolute value
• If the first number is bigger, the resulting value will be psoitive
• If the first number is smaller, the resulting value will be negative and should remain negative

And with that, I re-ran my algorithm.

I saw lists of 0s at the end of each line's recursive chain.

I generated an answer far lower than before.

Sadly, it was incorrect.

Too low.

What's still wrong?

Fixed the start. Now fix the end.

Another line from the input has a chain that ends like this:

-15 -19 -23 -27 -31 -35
   4   4   4   4   4
     0   0   0   0

Right now, my algorithm always adds at the end, increasing the last value.

But in this case, the top line is decreasing.

So, instead of making -35 decrease by 4 to -39, I'm increasing it back up to -31 incorrectly.

How can I fix this behavior?

Here's how:

if (list[list.length - 1] > list[list.length - 2]) {
  return list[list.length - 1] + Math.abs(next)
} else {
  return list[list.length - 1] - Math.abs(next)
}

Confirming. Validating. Coming up short again.

I ran this new algorithm on a few lines of input.

I saw the values I was expecting throughout the recursive chain:

• Values were increasing and decreasing the correct amount in the correct direction along the number scale

I ran it on the full input.

It generated an answer that was lower than my previous Too high submissions and higher than my previous Too low submissions.

I submitted this answer.

Wrong.

Since this was my 4th submission, I got no hints about high or low.

It just wasn't correct.

Re-reading the rules and being more confused

Supposedly there's a hard and fast rule that I overlooked:

A needs to be the result of increasing 3 (the value to its left) by 0 (the value below it); this means A must be 3
B, which needs to be the result of increasing 15 (the value to its left) by 3 (the value below it), or 18

These seem to imply that the next value in any sequence is a larger number as many steps as the new next value in the sequence representing its differences.

Those rules work well and look right for strictly-increasing lines of values.

But that rule looks wrong for strictly decreasing lines of values.

Still, I had to try.

Instead of my condition checking for increasing or decreasing end-of-line values, I now have one line:

return list[list.length - 1] + Math.abs(next)

Take that last value and add to it the positive version of the new last value in the sequence of differences.

Running this new algorithm on my input generated a much lower number. In fact, it was a number I already submitted that was Too low.

Stuck. Confused. Kind of sick of this.

I don't buy into the always-increasing rule.

But my algorithm is clearly getting something wrong about what the next value should be in every case.

So, I'm not sure where to go next.

Especially since I'm all out of hints.

Thanks for the sanity check, reddit

I must have clicked 10 links to different threads about this puzzle looking for validation of edge cases and what I might be getting wrong.

Alas, one kind commenter confirmed:

You can just do the exact thing the problem asks for. ...Generate the differences (later number - earlier number) ...use the fact that every row is the difference of the previous

In my algorithm, I subtract the later number from the earlier number. I need to swap them!

From this:

list[i] - list[i + 1]

To this:

list[i + 1] - list[i]

Additionally, I need to remove all the conditions about determining the new value.

Just return the last value increased by the new value in the difference list, even if it is negative.

My updated algorithm in JavaScript:

function nextDiff(list) {
  if (list.every(value => value == 0)) {
    return 0
  } else {
    let newList = []
    for (let i = 0; i < list.length - 1; i++) {
      newList.push(list[i + 1] - list[i])
    }
    return list[list.length - 1] + nextDiff(newList)
  }
}

Fingers crossed!

• I reran the algorithm
• I generated a number just below my Too high answers
• I submitted it

Correct answer!!!

Finally!!!

Boy, was that starting to get annoyingly frustrating.

Thank you again, reddit.

Part 2

Spoiled by reddit, sadly

Just reverse each line

I'm not sure I would have thought of this on my own.

But I love it, and I'm going to do it in hopes of super-quickly generating a correct answer and moving on from today.

Because I'm over it at this point.

This was Part 1's portion:

const part1 = input.reduce(
  (sum, line) => sum += nextDiff(
    [...line.matchAll(/-?\d+/g)].map(el => +el[0])
  ), 0)

And this is Part 2's portion:

const part1 = input.reduce(
  (sum, line) => sum += nextDiff(
    [...line.matchAll(/-?\d+/g)].map(el => +el[0]).reverse()
  ), 0)

The generated answer is tiny in comparison: about 1k

And it's correct!

Woohoo again!

Ok, bye Day 9!