1

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?

Anthony Bias
  • 515
  • 3
  • 20
  • BigInt has no maximum value (as per the spec) but the implementation is likely going to be limited by the available memory/the hosting platform. You don't say if this is node or browser. But either way, no computer has infinite space. – Liam Dec 15 '22 at 11:13
  • Hint: it may help to notice that all of the test numbers are prime. You do not need `BigInt` for this problem. – Unmitigated Dec 18 '22 at 16:37

0 Answers0