Hung-Yi's LogoHung-Yi’s Journal

Advent of Code 2022: Day 11

A TypeScript solution for the Advent of Code 2022, Day 11 puzzle: monkeys, classes, parsing gymanstics and one neat modulo trick.

Today’s puzzle asks us to simulate a bunch of monkeys throwing items around, where the items are numbers that transform as they are being passed from monkey to monkey.

The example input looks like this.

Monkey 0:
  Starting items: 79, 98
  Operation: new = old * 19
  Test: divisible by 23
    If true: throw to monkey 2
    If false: throw to monkey 3

Monkey 1:
  Starting items: 54, 65, 75, 74
  Operation: new = old + 6
  Test: divisible by 19
    If true: throw to monkey 2
    If false: throw to monkey 0

Monkey 2:
  Starting items: 79, 60, 97
  Operation: new = old * old
  Test: divisible by 13
    If true: throw to monkey 1
    If false: throw to monkey 3

Monkey 3:
  Starting items: 74
  Operation: new = old + 3
  Test: divisible by 17
    If true: throw to monkey 0
    If false: throw to monkey 1

Let’s use an object-oriented approach this time. We can model a monkey by defining a class called Monkey as follows:

class Monkey {
  readonly id: string;
  readonly items: number[];
  private readonly operation: (old: number) => number;
  readonly divisor: number;
  private readonly passDestinationId: string;
  private readonly failDestinationId: string;
  private _inspections = 0;
  get inspections(): number { return this._inspections; }
  private set inspections(x: number) { this._inspections = x; }

  constructor(input: string) {
    const [
      idInput, itemsInput, operationInput,
      divisorInput, passInput, failInput
    ] = input.split('\n');

    this.id = idInput.replace(/[^\d]/g, '');

    this.items = itemsInput
      .trim()
      .replace('Starting items: ', '')
      .split(', ')
      .map(Number);

    const [left, op, right] = operationInput
      .trim()
      .replace('Operation: new = ', '')
      .split(' ');

    this.operation = (old: number) => {
      const x = left === 'old' ? old : Number(left);
      const y = right === 'old' ? old : Number(right);
      switch (op) {
        case '+': return x + y;
        case '-': return x - y;
        case '*': return x * y;
        case '/': return x / y;
      }
    };

    this.divisor = Number(
      divisorInput
        .trim()
        .replace('Test: divisible by ', '')
    );

    this.passDestinationId = passInput
      .trim()
      .replace('If true: throw to monkey ', '')

    this.failDestinationId = failInput
      .trim()
      .replace('If false: throw to monkey ', '')
  }

  play(relief: boolean, globalDivisor: number) {
    const transfers = this.items.map(item => {
      this.inspections++;

      item = this.operation(item);

      // If we're not that anxious yet (part 1),
      // worry levels can be divided by 3 and floored
      if (relief) {
        item /= 3;
        item = Math.floor(item);
      }

      // "keep your worry levels manageable"
      item = item % globalDivisor;

      return {
        send: item,
        to: item % this.divisor === 0
          ? this.passDestinationId
          : this.failDestinationId
      };
    });
    this.items.length = 0;
    return transfers;
  }

  receive(item: number) {
    this.items.push(item);
  }
}

What this class does:

  1. In the constructor(), it takes the puzzle input for one monkey and uses split(), replace() and array deconstruction to parse all the monkey parameters into the class fields. We pay special attention to the operation field, which is a little complicated (we have to detect how many times old is referred to, and switch on the operation: +, -, *, /).
  2. The play() method takes two arguments (a relief boolean flag which toggles part 1 behavior, and a globalDivisor number which is a part 2 optimization). It processes they monkey’s items, doing any arithmetic required, and outputs an object that represents a transfer of an item to another monkey.1 It also tracks the number of item inspections a monkey has done, which is required for the puzzle answers.
  3. The receive() method takes an item (number) and adds it to the monkey’s list of items.

Finally, we can define a simulate() function which simulates the monkeys for a given number of rounds and has a relief flag to toggle the part 1 behavior on and off. See the code comments for explanations of each section 😃

const simulate = (rounds: number, relief: boolean) => {
  // Split the puzzle input into input for each monkey
  // based on the blank lines, then construct a Monkey
  // object for each.
  const monkeys = puzzleInput
    .split('\n\n')
    .map(monkeyInput => new Monkey(monkeyInput));

  // Create a Map of Monkeys, keyed by ID.
  // This makes it easy for us to find a destination monkey
  // when transferring items later.
  const monkeyMap = new Map(monkeys.map(m => [m.id, m]));

  // Calculate the global divisor by getting the product
  // of every monkey's divisor. When we mod by this global
  // value, each monkey's divisor test will have the same
  // pass/fail behavior but the actual numbers will be
  // smaller and more manageable.
  const globalDivisor = monkeys
    .map(m => m.divisor)
    .reduce((p, x) => p * x);

  // For each round, each monkey inspects its items,
  // and each transfer needs to be received by the
  // destination monkey.
  for (let round = 0; round < rounds; round++)
    for (const monkey of monkeys)
      for (const { send, to } of monkey.play(relief, globalDivisor))
        monkeyMap.get(to).receive(send);

  // Calculate the puzzle answer by getting the top 2
  // monkeys by inspection count, then multiply.
  return monkeys
    .map(m => m.inspections)
    .sort((a, b) => b - a)
    .slice(0, 2)
    .reduce((p, x) => p * x, 1);
}

Now the only difference between part 1 and part 2 is the relief toggle, which is enabled for part 1, and the number of rounds, which is much higher for part 2.

const part1 = simulate(20, true);
const part2 = simulate(10000, false);

Final Solution

class Monkey {
  readonly id: string;
  readonly items: number[];
  private readonly operation: (old: number) => number;
  readonly divisor: number;
  private readonly passDestinationId: string;
  private readonly failDestinationId: string;
  private _inspections = 0;
  get inspections(): number { return this._inspections; }
  private set inspections(x: number) { this._inspections = x; }

  constructor(input: string) {
    const [
      idInput, itemsInput, operationInput,
      divisorInput, passInput, failInput
    ] = input.split('\n');

    this.id = idInput.replace(/[^\d]/g, '');

    this.items = itemsInput
      .trim()
      .replace('Starting items: ', '')
      .split(', ')
      .map(Number);

    const [left, op, right] = operationInput
      .trim()
      .replace('Operation: new = ', '')
      .split(' ');

    this.operation = (old: number) => {
      const x = left === 'old' ? old : Number(left);
      const y = right === 'old' ? old : Number(right);
      switch (op) {
        case '+': return x + y;
        case '-': return x - y;
        case '*': return x * y;
        case '/': return x / y;
      }
    };

    this.divisor = Number(
      divisorInput
        .trim()
        .replace('Test: divisible by ', '')
    );

    this.passDestinationId = passInput
      .trim()
      .replace('If true: throw to monkey ', '')

    this.failDestinationId = failInput
      .trim()
      .replace('If false: throw to monkey ', '')
  }

  play(relief: boolean, globalDivisor: number) {
    const transfers = this.items.map(item => {
      this.inspections++;

      item = this.operation(item);

      // If we're not that anxious yet (part 1),
      // worry levels can be divided by 3 and floored
      if (relief) {
        item /= 3;
        item = Math.floor(item);
      }

      // "keep your worry levels manageable"
      item = item % globalDivisor;

      return {
        send: item,
        to: item % this.divisor === 0
          ? this.passDestinationId
          : this.failDestinationId
      };
    });
    this.items.length = 0;
    return transfers;
  }

  receive(item: number) {
    this.items.push(item);
  }
}

const simulate = (rounds: number, relief: boolean) => {
  // Split the puzzle input into input for each monkey
  // based on the blank lines, then construct a Monkey
  // object for each.
  const monkeys = puzzleInput
    .split('\n\n')
    .map(monkeyInput => new Monkey(monkeyInput));

  // Create a Map of Monkeys, keyed by ID.
  // This makes it easy for us to find a destination monkey
  // when transferring items later.
  const monkeyMap = new Map(monkeys.map(m => [m.id, m]));

  // Calculate the global divisor by getting the product
  // of every monkey's divisor. When we mod by this global
  // value, each monkey's divisor test will have the same
  // pass/fail behavior but the actual numbers will be
  // smaller and more manageable.
  const globalDivisor = monkeys
    .map(m => m.divisor)
    .reduce((p, x) => p * x);

  // For each round, each monkey inspects its items,
  // and each transfer needs to be received by the
  // destination monkey.
  for (let round = 0; round < rounds; round++)
    for (const monkey of monkeys)
      for (const { send, to } of monkey.play(relief, globalDivisor))
        monkeyMap.get(to).receive(send);

  // Calculate the puzzle answer by getting the top 2
  // monkeys by inspection count, then multiply.
  return monkeys
    .map(m => m.inspections)
    .sort((a, b) => b - a)
    .slice(0, 2)
    .reduce((p, x) => p * x, 1);
}

const part1 = simulate(20, true);
const part2 = simulate(10000, false);

console.log("Part 1:", part1);
console.log("Part 2:", part2);
Part 1: 58056
Part 2: 15048718170

Footnotes:

1

Note that an individual Monkey doesn’t know about the other monkeys’ existence, other than a string ID reference. This is by design, as it adheres to the “single responsibility” principle of object oriented design.