원숭이 시장

Source: Dev.to

Part 1

Another math gauntlet

나는 여러 수학 연산을 프로그래밍해야 한다. 일부는 여러 조건문에 포함될 것이다. 이전에도 해본 적이 있다. 다시 할 수 있다는 자신감이 있다. 한 단계—한 문장씩—씩 진행한다.

A slow burn of programming

내 입력은 다음과 같은 정수 리스트이다:

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

Mixing and Pruning functions

Mixing

• 두 숫자의 비트wise XOR을 계산하고 그 결과를 사용한다.

JavaScript에서 XOR 연산자는 ^이다:

42 ^ 15 // 37

내 함수는 두 개의 인자를 받아 결과를 반환해야 한다:

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

Pruning

• 비밀 숫자를 16777216으로 나눈 나머지를 계산하고 그 결과를 사용한다.

JavaScript에서 나머지 연산자는 %이다:

8 % 3 // 2 (3이 8에 두 번 들어가고, 나머지는 2)

내 함수는 하나의 인자를 받아 결과를 반환해야 한다:

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

The sequence of three calculations

1. 비밀 숫자를 64와 곱하고, 그 결과를 비밀 숫자와 XOR한 뒤, prune한다:

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

2. 비밀 숫자를 32로 나누고, 내림한 뒤, 그 결과를 비밀 숫자와 XOR한 뒤, prune한다:

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

3. 비밀 숫자를 2048과 곱하고, 그 결과를 비밀 숫자와 XOR한 뒤, 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

XOR 연산 결과가 32‑비트 부호 있는 정수 범위를 초과하는 값과 이루어지면 음수가 나타난다.

Studying integers and bitwise operations

• JavaScript 비트wise 연산자는 32‑비트 부호 있는 정수에 대해 동작한다.
• 가장 큰 안전 정수는 2,147,483,647이다.
• 값 3,156,183,040은 이 범위를 초과한다.
• 이러한 숫자를 올바르게 다루려면 BigInt를 사용해야 한다.

BigInt 예시:

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

이제:

3154643953n % 16777216n // 527345n

이는 기대한 비밀 숫자와 일치한다.

Until the errors stop… eventually?

모든 숫자 리터럴과 연산을 BigInt로 변환해야 한다. Math.floor() 호출은 필요 없으며, BigInt 나눗셈은 이미 0쪽으로 버린다.

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

모든 숫자가 이제 BigInt이며, 프로그램은 올바른 비밀 숫자를 출력한다.

Testing on my puzzle input

실제 퍼즐 입력에 업데이트된 솔루션을 실행하면 기대한 답이 생성된다. 🎉