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 .concat([DIV1, DIV2]) // add dividers .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 .concat([DIV1, DIV2]) // add dividers .sort(compare); // sort const part2 = (packets.indexOf(DIV1) + 1) * (packets.indexOf(DIV2) + 1); console.log("Part 1:", part1); console.log("Part 2:", part2);
Part 1: 5557 Part 2: 22425