Day 11: Monkey in the Middle

Monkeys got your backpack and are throwing your stuff around and you calculate a number based on the value of the items and stuff. Probably just read the description.

full description

Journal

Part I of this was very straight forward. Part II was less so.

This is kind of when performance started to matter. Without the divide by 3, the values got very large quickly.

At first I thought maybe I could use BigInt or something, but the numbers were just too big.

I figured there must be a way to use a modulus to keep the numbers small, but I wasn't sure what that was or even what to search. I did realize that the divisible numbers were primes.

I looked in the aoc subreddit and somebody mentioned discrete mathematics (not something I took in my CS classes) or something. That got me to modulus arithmetic and easy sailing after that.

Also, I didn't see any value in trying to parse the input and create objects and stuff. There's not that many monkeys. So, I just manually created some monkeys...

Relevant Code

export type Monkey = {
  prime: number;
  items: number[];
  getNewWorry: (old: number) => number;
  throwTo: (worry: number) => number;
  inspectCount: number;
};

// This is an example of the monkey objects I created as inputs
const exampleMonkey: Monkey = {
  prime: 23,
  items: [79, 98],
  getNewWorry: (old: number) => old * 19,
  throwTo: (worry: number) => (worry % 23 === 0 ? 2 : 3),
  inspectCount: 0,
};
export const haveARound = (monkeys: Monkey[], lcm?: number) => {
  monkeys.forEach((monkey, i) => {
    while (monkey.items.length) {
      const item = monkey.items.shift()!;
      const newWorry = monkey.getNewWorry(item);
      const newItemVal = lcm ? newWorry % lcm : Math.floor(newWorry / 3);
      monkeys[monkey.throwTo(newItemVal)].items.push(newItemVal);
      monkey.inspectCount++;
    }
  });
};

const getModuloBase = (monkeys: Monkey[]) => {
  return monkeys.reduce((base, monkey) => monkey.prime * base, 1);
};

export const partI = (origMonkeys: Monkey[]) => {
  const monkeys = origMonkeys.map(cloneMonkey);
  for (let i = 0; i < 20; i++) {
    haveARound(monkeys);
  }
  monkeys.sort((a, b) => b.inspectCount - a.inspectCount);

  return monkeys[0].inspectCount * monkeys[1].inspectCount;
};

export const partII = (origMonkeys: Monkey[]) => {
  const monkeys = origMonkeys.map(cloneMonkey);
  const moduloBase = getModuloBase(monkeys);
  for (let i = 0; i < 10000; i++) {
    haveARound(monkeys, moduloBase);
  }
  monkeys.sort((a, b) => b.inspectCount - a.inspectCount);
  return monkeys[0].inspectCount * monkeys[1].inspectCount;
};

const cloneMonkey = (monkey: Monkey): Monkey => {
  return { ...monkey, items: [...monkey.items] };
};

Output

Test Monkeys

Part I: 10605 (1 ms)
Part II: 2713310158 (10 ms)

Real Monkeys

Part I: 98280 (1 ms)
Part II: 17673687232 (48 ms)

Advent of Code 2022

Day 01 - Calorie Counting

Day 07 - No Space On Device

Day 08 - Treetop Tree House

Day 09 - Rope Bridge

Day 10 - Cathode-Ray Tube