I was unable to solve part 2 of day 11 of advent of code this year because I couldn't figure out how to handle extremely large numbers in javascript. Here is the code I used:
import { join } from 'path';
import { open } from 'fs/promises';
let monkies: Monkey[] = [];
type MonkeyArgs = {
items: bigint[];
operation: (old: bigint) => bigint;
testNum: number;
testTrueMonkey: number;
testFalseMonkey: number;
};
class Monkey {
items: bigint[];
operation: (old: bigint) => bigint;
throw: (item: bigint) => void;
constructor({
items,
operation,
testNum,
testTrueMonkey,
testFalseMonkey,
}: MonkeyArgs) {
this.items = items;
this.operation = operation;
this.throw = (item: bigint) => {
if (item % BigInt(testNum) === BigInt(0)) {
monkies[testTrueMonkey].items.push(item);
} else {
monkies[testFalseMonkey].items.push(item);
}
};
}
}
const itemsRegex = /Starting items: ((?:\d+(?:, )?)+)/;
const operationRegex = /Operation: new = old (\*|\+) (\d+|old)/;
const testRegex = /Test: divisible by (\d+)/;
const testTrueRegex = /If true: throw to monkey (\d+)/;
const testFalseRegex = /If false: throw to monkey (\d+)/;
const initializeMonkies = async () => {
monkies = [];
const file = await open(join('11', 'input.txt'));
let args: Partial<MonkeyArgs> = {};
for await (const line of file.readLines()) {
if (itemsRegex.test(line)) {
const itemsMatch = line.match(itemsRegex)!;
const items = itemsMatch[1]
.split(', ')
.map((item) => BigInt(parseInt(item, 10)));
args.items = items;
}
if (operationRegex.test(line)) {
const operationMatch = line.match(operationRegex)!;
const num = parseInt(operationMatch[2], 10);
args.operation = (old) =>
operationMatch[1] === '+'
? old + (isNaN(num) ? old : BigInt(num))
: old * (isNaN(num) ? old : BigInt(num));
}
if (testRegex.test(line)) {
const testMatch = line.match(testRegex)!;
args.testNum = parseInt(testMatch[1], 10);
}
if (testTrueRegex.test(line)) {
const testTrueMatch = line.match(testTrueRegex)!;
args.testTrueMonkey = parseInt(testTrueMatch[1], 10);
}
if (testFalseRegex.test(line)) {
const testFalseMatch = line.match(testFalseRegex)!;
args.testFalseMonkey = parseInt(testFalseMatch[1], 10);
const monkey = new Monkey(args as MonkeyArgs);
monkies.push(monkey);
args = {};
}
}
};
const calculateMonkeyBusiness = async ({
rounds,
shouldDivideWorryLevel,
}: {
rounds: number;
shouldDivideWorryLevel: boolean;
}) => {
await initializeMonkies();
const inspections = [...Array(monkies.length).keys()].map(() => 0);
for (let round = 0; round < rounds; ++round) {
console.log(`Doing round ${round + 1}`);
monkies.forEach((monkey, i) => {
monkey.items.forEach((item, j) => {
++inspections[i];
let itemToThrow = item;
itemToThrow = monkey.operation(itemToThrow);
if (shouldDivideWorryLevel) {
itemToThrow = itemToThrow / BigInt(3);
}
monkey.throw(itemToThrow);
});
monkey.items = [];
});
}
return [...inspections]
.sort((a, b) => a - b)
.slice(-2)
.reduce((acc, cur) => cur * acc, 1);
};
const solution = async ({
rounds,
shouldDivideWorryLevel,
}: {
rounds: number;
shouldDivideWorryLevel: boolean;
}) => {
console.log('Calculating monkey business');
console.log(
`Monkey business level after ${rounds} rounds is ${await calculateMonkeyBusiness(
{
rounds,
shouldDivideWorryLevel,
}
)}`
);
};
export const solution1 = async () =>
await solution({ rounds: 20, shouldDivideWorryLevel: true });
export const solution2 = async () =>
await solution({ rounds: 10000, shouldDivideWorryLevel: false });
Notice that I'm using BigInt
. When running solution2
, which has a loop that iterates 10000 times, the program starts to get incredibly slow around the 300th iteration. When it reaches the 364th iteration, it crashes with the following error message:
/home/abias/projects/advent-of-code/2022/11/solution.ts:65
: old * (isNaN(num) ? old : BigInt(num));
^
RangeError: Maximum BigInt size exceeded
at Monkey.args.operation (/home/abias/projects/advent-of-code/2022/11/solution.ts:65:16)
at /home/abias/projects/advent-of-code/2022/11/solution.ts:110:30
at Array.forEach (<anonymous>)
at /home/abias/projects/advent-of-code/2022/11/solution.ts:107:20
at Array.forEach (<anonymous>)
at /home/abias/projects/advent-of-code/2022/11/solution.ts:106:13
at Generator.next (<anonymous>)
at fulfilled (/home/abias/projects/advent-of-code/2022/11/solution.ts:5:58)
at processTicksAndRejections (node:internal/process/task_queues:95:5)
It seems the numbers got too big for BigInt
. How do I handle numbers that big?