Distress Signal

Advent of Code 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:

JSON.parse( '...' )

In goes:

'[1,[2,[3,[4,[5,6,7]]]],8,9]'

Out comes:

[ 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:

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

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:

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:

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:

// 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

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:

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:

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

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.