Hung-Yi's LogoHung-Yi’s Journal

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