Distress Signal
Tags: adventofcode, algorithms, javascript, programming
Published: 2022-12-14 16:47:54

## [Advent of Code 2022 Day 13](https://adventofcode.com/2022/day/13)

## Part 1
1. My favorite: a recursion puzzle...with `JSON`!
2. Parsing each packet as `JSON`
3. The shell of my algorithm
4. Solving for the first pair in the example
5. Solving for the second pair in the example
6. Solving for the remaining examples
7. Altogether on the example
8. Fingers crossed using my puzzle input

### My favorite: a recursion puzzle...with `JSON`!
One glimpse at `Pair 8`'s walkthrough makes me eager and scared to write a recursive algorithm that might solve Part 1.

I've had successes and failures with recursion throughout AoC.

I hope I can earn at least one gold star today.

I haven't even looked at my puzzle input, but I assume it is full of deeply-nested arrays.

Just looked. Yup!

Surprisingly, it seems each pair is comprised of a list. I figured there would be a packet that is just a number.

Turns out I missed this sentence:
> Each packet is always a list and appears on its own line.

Anyway, here I go!

### Parsing each packet as `JSON`
Thankfully, JavaScript has a built-in method to turn the string representation of a nested array into an actual array that maintains it's tree-like structure:
```js
JSON.parse( '...' )
```

In goes:
```js
'[1,[2,[3,[4,[5,6,7]]]],8,9]'
```

Out comes:
```js
[ 1,
  [ 2,
    [ 3,
      [ 4,
        [ 5,6,7 ]
      ]
    ]
  ],
  8,9
]
```

### The shell of my algorithm
In Pseudocode:
```
Split the input string into an array of strings representing each pair

For each pair, accumulate a sum
  Set a flag for whether this pair is in the correct order
    To become a boolean eventually, but empty for now
  Split each pair string into separate strings
    Parse each one as JSON

  Eventually return the sum incremented by either the index of the current pair or 0, depending on whether the order is correct or not

Return the sum
```

In JavaScript:
```js
return input.split('\n\n').reduce(
  (sum, pair, index) => {
    let correct = null
    let [left, right] = pair.split('\n').map(JSON.parse)
    return sum += correct ? index : 0
  }, 0
)
```

### Solving for the first pair in the example
Slow progress is the goal:
Can I write an algorithm that correctly identifies just the first pair as being in the correct order?

Progress annotated:
- I tried using a variable to track where in the array the `cursor` is at.
- I used a `while` loop that runs as long as `correct` is `null`
- I got it to work
- Then I tried wrapping all my logic in a function
- I struggled to successfully call that function with my cursor having moved forward
- I ditched the `while` loop and switched to recursion
- I would use smaller and smaller arrays, lobbing off the first values from each upon successive calls
- My recursive function returns `true` or `false` when the integers are different values
- And it calls itself again with smaller arrays when the integers are the same value

```js
function isCorrect(left, right) {
  if (
    typeof left[0] == 'number' &&
    typeof right[0] == 'number'
  ) {
    console.log("both values are integers")
    if (left[0] < right[0]) {
      return true
    } else if (left[0] > right[0]) {
      return false
    } else {
      left.shift()
      right.shift()
      return isCorrect(left, right)
    }
  }
}
```

### Solving for the second pair in the example
Slow progress is still the goal:
Can I augment my algorithm to correctly identify that the first two pair are in the correct order?

Progress annotated:
- My algorithm was sadly not prepared to handle a nested list
- I was returning `true` or `false` when I needed to account for three values: right order, wrong order or continue
- I also was not yet accounting for lists of different lengths
- Oh, and for when the next items are different types: one a list and one an integer
- Accounting for all of this required some serious refactoring
- And a bunch more conditions
- And another function

My new `compare` function in JavaScript:
```js
function compare(left, right) {
  let outcome = 0
  while (
    outcome == 0 && 
    left.length > 0 && 
    right.length > 0
  ) {
    outcome = isCorrect(left, right)
    if (outcome == 0) {
      left.shift()
      right.shift()
    }
  }
  return outcome
}
```

My updated `isCorrect` function in JavaScript:
```js
function isCorrect(left, right) {
  if (left.length == 0 && right.length > 0) {
    return -1
  } else if (right.length == 0 && left.length > 0) {
    return 1
  }
  if (
    typeof left[0] == 'number' &&
    typeof right[0] == 'number'
  ) {
    if (left[0] < right[0]) {
      return -1
    } else if (left[0] > right[0]) {
      return 1
    } else {
      return 0
    }
  } else if (
    typeof left[0] == 'object' &&
    typeof right[0] == 'object'
  ) {
    return compare(left[0], right[0])
  } else if (
    typeof left[0] !== typeof right[0]
  ) {
    return compare(
      typeof left[0] == 'object' ? left[0] : [left[0]],
      typeof right[0] == 'object' ? right[0] : [right[0]]
    )
  }
}
```

With logging statements inserted, I see that my algorithm works on the second example:
```
[ [ 1 ], [ 2, 3, 4 ] ] [ [ 1 ], 4 ]
both values are lists

[ 1 ] [ 1 ]
both values are integers

[ [ 2, 3, 4 ] ] [ 4 ]
exactly one value is an integer

[ 2, 3, 4 ] [ 4 ]
both values are integers

correct order
```

### Solving for the remaining examples
Re-checking the first example:
```
[ 1, 1, 3, 1, 1 ] [ 1, 1, 5, 1, 1 ]
both values are integers

[ 1, 3, 1, 1 ] [ 1, 5, 1, 1 ]
both values are integers

[ 3, 1, 1 ] [ 5, 1, 1 ]
both values are integers

correct order
```

Trying my luck with the third example:
```
[ 9 ] [ [ 8, 7, 6 ] ]
exactly one value is an integer

[ 9 ] [ 8, 7, 6 ]
both values are integers

wrong order
```

Woohoo!

Trying my luck with the fourth example helped me discover another gap:
- I was failing to compare lists when one is empty and the other is not

My updated `while` loop condition in my `compare` function:
```js
// Old
while (
  outcome == 0 && 
  left.length > 0 && 
  right.length > 0
) {}

// New
while (
  outcome == 0 && 
  (left.length > 0 || right.length > 0)
) {}
```

Trying it again on the fourth example:
```
[ [ 4, 4 ], 4, 4 ] [ [ 4, 4 ], 4, 4, 4 ]
both values are lists

[ 4, 4 ] [ 4, 4 ]
both values are integers

[ 4 ] [ 4 ]
both values are integers

[ 4, 4 ] [ 4, 4, 4 ]
both values are integers

[ 4 ] [ 4, 4 ]
both values are integers

[] [ 4 ]
left side ran out of items
correct order
```

Sweet!

How about the fifth example?
```
[ 7, 7, 7, 7 ] [ 7, 7, 7 ]
both values are integers

[ 7, 7, 7 ] [ 7, 7 ]
both values are integers

[ 7, 7 ] [ 7 ]
both values are integers

[ 7 ] []
right side ran out of items
wrong order
```

Nice!

And the sixth example?
```
[] [ 3 ]
left side ran out of items
correct order
```

Nice again!

And the seventh example?
```
[ [ [] ] ] [ [] ]
both values are lists

[ [] ] []
right side ran out of items
wrong order
```

Nice yet again!

And the final example?
```
[ 1, [ 2, [ 3, [Array] ] ], 8, 9 ] [ 1, [ 2, [ 3, [Array] ] ], 8, 9 ]
both values are integers

[ [ 2, [ 3, [Array] ] ], 8, 9 ] [ [ 2, [ 3, [Array] ] ], 8, 9 ]
both values are lists

[ 2, [ 3, [ 4, [Array] ] ] ] [ 2, [ 3, [ 4, [Array] ] ] ]
both values are integers

[ [ 3, [ 4, [Array] ] ] ] [ [ 3, [ 4, [Array] ] ] ]
both values are lists

[ 3, [ 4, [ 5, 6, 7 ] ] ] [ 3, [ 4, [ 5, 6, 0 ] ] ]
both values are integers

[ [ 4, [ 5, 6, 7 ] ] ] [ [ 4, [ 5, 6, 0 ] ] ]
both values are lists

[ 4, [ 5, 6, 7 ] ] [ 4, [ 5, 6, 0 ] ]
both values are integers

[ [ 5, 6, 7 ] ] [ [ 5, 6, 0 ] ]
both values are lists

[ 5, 6, 7 ] [ 5, 6, 0 ]
both values are integers

[ 6, 7 ] [ 6, 0 ]
both values are integers

[ 7 ] [ 0 ]
both values are integers
wrong order
```

Hooray!

### Altogether on the example
Will it output a sum of 13?

...

Yes, it did! Yay!

### Fingers crossed using my puzzle input
- Will it run without error?
- Will it output an integer?
- Will it be the correct answer?

...

YAAAASSSSSS!

What an incredible sense of accomplishment!

## Part 2
1. Did I do myself a huge favor?
2. Splitting the input into a list of individual packets
3. The part I overlooked: in-place list deletion
4. Find the indices of the divider packets

### Did I do myself a huge favor?
- It seems I now need to perform a global `sort()`
- `sort()` works by comparing values and returning `-1`, `0` or `1`
- That's exactly what my algorithm does!
- Now I need to adjust it to work as a function I can pass into `sort()`
- I'm feeling good about this!

### Splitting the input into a list of individual packets
```js
input
  .split('\n\n')
  .flatMap(pair => pair.split('\n').map(JSON.parse))
```

### The part I overlooked: in-place list deletion
I tried running this algorithm:
```js
input
  .split('\n\n')
  .flatMap(pair => pair.split('\n').map(JSON.parse))
  .sort(compare)
```

What I saw confused me:
```
[
  [ [ 2, 3, 4 ] ],    [ 4 ],
  [ 3, 1, 1 ],        [ [], 4, 4 ],
  [ [ 4 ], 4, 4, 4 ], [],
  [],                 [ [] ],
  [ [ [] ] ],         [ [ [Array] ], 8, 9 ],
  [ [ 2 ] ],          [ [ [Array] ], 8, 9 ],
  [ 3 ],              [ 5, 1, 1 ],
  [ [ 6 ] ],          [ 7 ],
  [ [ 8, 7, 6 ] ],    [ 9 ]
]
```

Those are not the original packets.

Why? Because my algorithm passes arrays by reference to a function that calls `shift()` as it tries to `walk along` the array...thus removing elements from the original array.

How might I account for this?

Whew! Thankfully, `slice()` copies all nested arrays.

Thus, my updated `compare` function looks like:
```js
function compare(left, right) {
  left = left.slice()
  right = right.slice()
  let outcome = 0
  while (outcome == 0 && (left.length > 0 || right.length > 0)) {
    outcome = isCorrect(left, right)
    if (outcome == 0) {
      left.shift()
      right.shift()
    }
  }
  return outcome
}
```

Running my algorithm on the example input with the divider packets in place outputs an array in the properly sorted order!

Next:
- Find the indices of the divider packets
- Cross my fingers even more tightly in hopes that my algorithm generates the correct answer for my puzzle input

### Find the indices of the divider packets
```js
let sorted = input
  .split('\n\n')
  .flatMap(pair => pair.split('\n').map(JSON.parse))
  .sort(compare)
  .map(JSON.stringify)
return (
  (sorted.indexOf('[[2]]') + 1) * 
  (sorted.indexOf('[[6]]') + 1)
)
```

Works great on the example input!

Does it generate the correct answer for mine?

...

YAAAASSSSS AGAIN!!!

Oh my word. Super rewarding.

## I did it!!
- I solved both parts!
- By way of recursion, conditions, `reduce()`, `sort()` and a slew of other built-in array and string methods!
- Oh, and tons of debugging, trial-and-error, logging statements, and patience!

Wow, that was quite the gauntlet!

I'm elated that I solved both parts.

These packet pairs are a puzzle I won't soon forget.