# Advent of Code 2022: Day 13

A TypeScript solution for the Advent of Code 2022, Day 13 puzzle: JSON arrays, recursion, compartor functions and sorting.

Today’s puzzle asks us to parse recursive array data, then implement a custom comparison function to determine strict ordering of these values.

The example input looks like this.

```[1,1,3,1,1]
[1,1,5,1,1]

[[1],[2,3,4]]
[[1],4]

[9]
[[8,7,6]]

[[4,4],4,4]
[[4,4],4,4,4]
```

First we model the recursive array structure as a recursive type called `Packet`. Each `Packet` can either be a plain number or an array of itself.

```type Packet = number | Packet[];
```

Then we’re able to parse the input data into a more sensible structure: a list of pairs of packets.

```const pairs = puzzleInput
.split('\n\n')
.map(lines => lines
.split('\n')
.map(line => JSON.parse(line) as Packet));
```

For convenience, we define a quick utility function to check whether a Packet is a plain number or not. This will come in handy later when writing the `compare()` function.

```const isNumber = (x: Packet) => typeof x === 'number';
```

Now for the challenging part: we define `compare()`, being careful to implement the “short circuit” logic as explained in the puzzle. That is, once we’ve determined whether a pair of packets is the “right” or “wrong” order, we stop the comparison and return early, making sure not to continue checking. We also need some special handling for `Packet[]` arrays of differing lengths.

```// Standard comparison function, implemented for comparing packets.
// i.e. returns -1 for "in the right order"
//      returns 1 for "not in the right order"
//      returns 0 for "continue checking the next part"
// These values allow us to sort() an array of Packets
const CORRECT = -1;
const INCORRECT = 1;
const INDETERMINATE = 0;
const compare = (left: Packet, right: Packet): number => {
if (isNumber(left) && isNumber(right)) {
// left and right are plain numbers
return left < right ? CORRECT
: left > right ? INCORRECT
: INDETERMINATE;
} else if (isNumber(left) && !isNumber(right)) {
// left is plain number
return compare([left], right);
} else if (!isNumber(left) && isNumber(right)) {
// right is plain number
return compare(left, [right]);
} else {
// left and rignt are both lists of Packets
const lefts = left as Packet[];
const rights = right as Packet[];

const result = lefts.reduce<number>(
(result, l, i) => {
if (result !== INDETERMINATE) return result;
const r = rights[i];
// check if right side ran out of items
if (!r) return INCORRECT;
return compare(l, r);
},
INDETERMINATE
);

// check if left side ran out of items
if (result === INDETERMINATE && rights.length > lefts.length)
return CORRECT;
else
return result;
}
}
```

Now part 1 just asks us to add together the (1-based) indices of all the pairs in the “right” order. Note that in this case, our `compare()` function returns the value `-1` for these pairs, so we can `reduce()` and accumulate those matching indices.

```const part1 = pairs.reduce(
(acc, [left, right], ii) =>
compare(left, right) === CORRECT
? acc + ii + 1
: acc,
0
);
```

And part 2 asks us to ignore the pairings and just sort the entire flattened list of packets, with a couple of divider packets thrown in. We then get the positions of the divider packets in the sorted list, and multiply them for the answer.

```const DIV1 = [[2]];
const DIV2 = [[6]];

const packets = pairs
.flatMap(pair => pair)  // flatten
.sort(compare);         // sort

const part2 =
(packets.indexOf(DIV1) + 1) * (packets.indexOf(DIV2) + 1);
```

## Final Solution

```type Packet = number | Packet[];

const pairs = puzzleInput
.split('\n\n')
.map(lines => lines
.split('\n')
.map(line => JSON.parse(line) as Packet));

const isNumber = (x: Packet) => typeof x === 'number';

// Standard comparison function, implemented for comparing packets.
// i.e. returns -1 for "in the right order"
//      returns 1 for "not in the right order"
//      returns 0 for "continue checking the next part"
// These values allow us to sort() an array of Packets
const CORRECT = -1;
const INCORRECT = 1;
const INDETERMINATE = 0;
const compare = (left: Packet, right: Packet): number => {
if (isNumber(left) && isNumber(right)) {
// left and right are plain numbers
return left < right ? CORRECT
: left > right ? INCORRECT
: INDETERMINATE;
} else if (isNumber(left) && !isNumber(right)) {
// left is plain number
return compare([left], right);
} else if (!isNumber(left) && isNumber(right)) {
// right is plain number
return compare(left, [right]);
} else {
// left and rignt are both lists of Packets
const lefts = left as Packet[];
const rights = right as Packet[];

const result = lefts.reduce<number>(
(result, l, i) => {
if (result !== INDETERMINATE) return result;
const r = rights[i];
// check if right side ran out of items
if (!r) return INCORRECT;
return compare(l, r);
},
INDETERMINATE
);

// check if left side ran out of items
if (result === INDETERMINATE && rights.length > lefts.length)
return CORRECT;
else
return result;
}
}

const part1 = pairs.reduce(
(acc, [left, right], ii) =>
compare(left, right) === CORRECT
? acc + ii + 1
: acc,
0
);

const DIV1 = [[2]];
const DIV2 = [[6]];

const packets = pairs
.flatMap(pair => pair)  // flatten
```Part 1: 5557