猴子市场

Source: Dev.to

第 1 部分

另一个数学考验

我需要编写一系列数学运算。有些运算会出现在多个条件语句中。我以前做过，我有信心还能再做一次。一步——一句话——一步一步来。

编程的慢热

我的输入是一串整数，例如：

1
10
100
2024

我知道我必须从输入字符串中提取每一个：

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

然后，对每个 buyer，我需要处理接下来的 2000 个秘密数字，并计算它们的总和：

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

混合与裁剪函数

混合

• 计算两个数字的 按位异或 (XOR) 并使用结果。

在 JavaScript 中，XOR 运算符是 ^：

42 ^ 15 // 37

我的函数应接受两个参数并返回结果：

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

裁剪

• 计算秘密数字对 16777216 的取模并使用结果。

在 JavaScript 中，取模运算符是 %：

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

我的函数应接受一个参数并返回结果：

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

三步计算序列

1. 将秘密数字乘以 64，将该结果混入秘密数字，然后裁剪：

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

2. 将秘密数字除以 32，向下取整，将该结果混入秘密数字，然后裁剪：

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

3. 将秘密数字乘以 2048，将该结果混入秘密数字，然后裁剪：

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

重复 2000 次

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

在与大于 32 位有符号整数范围的值进行异或后出现了负数结果。

研究整数与位运算

• JavaScript 位运算符在 32 位有符号整数 上工作。
• 最大安全整数是 2,147,483,647。
• 值 3,156,183,040 超出了此范围。
• 为了正确处理这些数字，需要使用 BigInt。

使用 BigInt 的示例：

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

现在：

3154643953n % 16777216n // 527345n

这与预期的秘密数字相匹配。

直到错误停止……最终？

我们需要把所有数值字面量和运算都转换为 BigInt。Math.floor() 调用已经没有必要，因为 BigInt 除法本身会向零截断。

我的最新程序

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);

所有数字现在都是 BigInt，程序能够生成正确的秘密数字。

在我的谜题输入上测试

在实际的谜题输入上运行更新后的解法，得到预期的答案。 🎉