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:
- In the
constructor()
, it takes the puzzle input for one monkey and usessplit()
,replace()
and array deconstruction to parse all the monkey parameters into the class fields. We pay special attention to theoperation
field, which is a little complicated (we have to detect how many timesold
is referred to, and switch on the operation: +, -, *, /). - The
play()
method takes two arguments (arelief
boolean flag which toggles part 1 behavior, and aglobalDivisor
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 iteminspections
a monkey has done, which is required for the puzzle answers. - 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:
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.