Monkey Market

Source: Dev.to

Part 1

Another math gauntlet

I get to program a bunch of math operations. Some will be part of several conditionals. I’ve done it before. I’m confident I can do it again. One step – and sentence – at a time.

A slow burn of programming

My input is a list of integers, like this example:

1
10
100
2024

I know I’ll have to extract each one from my input string:

let buyers = input.split('\n').map(Number);

Then, for each buyer, I’ll have to process the next 2000 secret numbers, and calculate the sum of them all:

let answer = buyers.reduce((sum, buyer) => {
  // determine the next 2000 secret numbers
  // sum += 2000th secret number
  return sum;
}, 0);

Mixing and Pruning functions

Mixing

• Calculate the bitwise XOR of two numbers and use the result.

In JavaScript the XOR operator is ^:

42 ^ 15 // 37

My function should expect two arguments and return the result:

function mix(secret, value) {
  return secret ^ value;
}

Pruning

• Calculate the value of the secret number modulo 16777216 and use the result.

In JavaScript the modulo operator is %:

8 % 3 // 2 (3 goes into 8 two times, leaving a remainder of 2)

My function should expect one argument and return the result:

function prune(secret) {
  return secret % 16777216;
}

The sequence of three calculations

1. Multiply the secret number by 64, mix this result into the secret number, then prune:

   buyer = prune(mix(buyer, buyer * 64));

2. Divide the secret number by 32, round down, mix this result into the secret number, then prune:

   buyer = prune(mix(buyer, Math.floor(buyer / 32)));

3. Multiply the secret number by 2048, mix this result into the secret number, then prune:

   buyer = prune(mix(buyer, buyer * 2048));

Do it 2000 times

for (let i = 0; i  {
  for (let i = 0; i  7872
123 ^ 7872 -> 7867
7867 % 16777216 -> 7867
Math.floor(7867 / 32) -> 245
7867 ^ 245 -> 7758
7758 % 16777216 -> 7758
7758 * 2048 -> 15888384
7758 ^ 15888384 -> 15887950
15887950 % 16777216 -> 15887950

15887950
15887950 * 64 -> 1016828800
15887950 ^ 1016828800 -> 1013579214
1013579214 % 16777216 -> 6946254
Math.floor(6946254 / 32) -> 217070
6946254 ^ 217070 -> 6992416
6992416 % 16777216 -> 6992416
6992416 * 2048 -> 14320467968
6992416 ^ 14320467968 -> 1442558496
1442558496 % 16777216 -> 16495136

16495136
16495136 * 64 -> 1055688704
16495136 ^ 1055688704 -> 1041709600
1041709600 % 16777216 -> 1522208
Math.floor(1522208 / 32) -> 47569
1522208 ^ 47569 -> 1541105
1541105 % 16777216 -> 1541105
1541105 * 2048 -> 3156183040
1541105 ^ 3156183040 -> -1140323343
-1140323343 % 16777216 -> -16249871   ← wrong

The negative result appears after the XOR with a value larger than the 32‑bit signed integer range.

Studying integers and bitwise operations

• JavaScript bitwise operators work on 32‑bit signed integers.
• The largest safe integer is 2,147,483,647.
• The value 3,156,183,040 exceeds this range.
• To handle such numbers correctly, we need to use BigInt.

Example with BigInt:

let big = BigInt("1541105");
let big2 = BigInt("3156183040");
let result = big ^ big2; // 3154643953 (positive)

Now:

3154643953n % 16777216n // 527345n

which matches the expected secret number.

Until the errors stop… eventually?

We need to convert all numeric literals and operations to BigInt. The Math.floor() call is unnecessary because BigInt division already truncates toward zero.

My latest program

let buyers = input.split('\n').map(BigInt);

function mix(secret, value) {
  return secret ^ value; // both are BigInt
}

function prune(secret) {
  return secret % 16777216n;
}

function regen(buyer) {
  buyer = prune(mix(buyer, buyer * 64n));
  buyer = prune(mix(buyer, buyer / 32n));
  buyer = prune(mix(buyer, buyer * 2048n));
  return buyer;
}

let answer = buyers.reduce((sum, buyer) => {
  for (let i = 0; i < 2000; i++) {
    buyer = regen(buyer);
  }
  return sum + buyer;
}, 0n);

All numbers are now BigInts, and the program produces the correct secret numbers.

Testing on my puzzle input

Running the updated solution on the actual puzzle input generates the expected answer. 🎉