Advent of Code 2022 Day 13
Part 1
 My favorite: a recursion puzzle...with
JSON
!  Parsing each packet as
JSON
 The shell of my algorithm
 Solving for the first pair in the example
 Solving for the second pair in the example
 Solving for the remaining examples
 Altogether on the example
 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 deeplynested 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 builtin method to turn the string representation of a nested array into an actual array that maintains it's treelike 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 ascorrect
isnull
 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
orfalse
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
orfalse
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
Rechecking 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
 Did I do myself a huge favor?
 Splitting the input into a list of individual packets
 The part I overlooked: inplace list deletion
 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 returning1
,0
or1
 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: inplace 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 builtin array and string methods!  Oh, and tons of debugging, trialanderror, 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.
Top comments (0)