DEV Community

Cover image for Monkey Market
Robert Mion
Robert Mion

Posted on

Monkey Market

#adventofcode #javascript #algorithms #programming

Advent of Code 2024 Day 22

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
Enter fullscreen mode Exit fullscreen mode

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

let buyers = input.split('\n').map(Number)
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode
Mixing and Pruning functions

First, Mixing:

  • Calculate the bitwise XOR or two numbers and use the result

In javascript the XOR operator is a ^:

42 ^ 15 // 37
Enter fullscreen mode Exit fullscreen mode

My function should expect two arguments and return the result:

function mix (secret, value) { return secret ^ value }
Enter fullscreen mode Exit fullscreen mode

Next, Pruning:

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

In javascript the modulo operator is a %:

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

My function should expect one argument and return the result:

function prune (secret) { return secret % 16777216 }
Enter fullscreen mode Exit fullscreen mode
The sequence of three calculations

Calculate the result of multiplying the secret number by 64. Then, mix this result into the secret number. Finally, prune the secret number.

buyer = prune(mix(buyer, buyer * 64))
Enter fullscreen mode Exit fullscreen mode

Calculate the result of dividing the secret number by 32. Round the result down to the nearest integer. Then, mix this result into the secret number. Finally, prune the secret number.

buyer = prune(mix(buyer, Math.floor(buyer / 32)))
Enter fullscreen mode Exit fullscreen mode

Calculate the result of multiplying the secret number by 2048. Then, mix this result into the secret number. Finally, prune the secret number.

buyer = prune(mix(buyer, buyer * 2048))
Enter fullscreen mode Exit fullscreen mode
Do it 2000 times 
for (let i = 0; i < 2000; i++ {
  // all three statements above
}
Enter fullscreen mode Exit fullscreen mode
Altogether

Here's my untested algorithm:

let buyers = input.split('\n').map(Number)
function mix (secret, value) { return secret ^ value }
function prune (secret) { return secret % 16777216 }
let answer = buyers.reduce((sum, buyer) => {
  for (let i = 0; i < 2000; i++) {
    buyer = prune(mix(buyer, buyer * 64))
    buyer = prune(mix(buyer, Math.floor(buyer / 32)))
    buyer = prune(mix(buyer, buyer * 2048))
  }
  sum += buyer
  return sum
}, 0)
Enter fullscreen mode Exit fullscreen mode
First test

I added logging statements to show the first and what I assume is the 2000th secret number.

Pressing run...

...and I'm getting some negative 2000th secret numbers.

I messed something up

Debugging

First, I made a function to store my three calculations:

function regen(buyer) {
    buyer = prune(mix(buyer, buyer * 64))
    buyer = prune(mix(buyer, Math.floor(buyer / 32)))
    buyer = prune(mix(buyer, buyer * 2048))
    return buyer
}
Enter fullscreen mode Exit fullscreen mode

Then, I made a single test case and a shorter loop:

let sample = 123
for (let i = 0; i < 10; i++) {
    console.log(sample)
    sample = regen(sample)
}
Enter fullscreen mode Exit fullscreen mode

I need to be sure I'm seeing the same 10 next secret numbers as per the example:

15887950
16495136
-16249871
704524
-15223532
-4094060
11100544
-4527732
7753432
5908254
Enter fullscreen mode Exit fullscreen mode

Hmm. The four negative values are incorrect, but everything else is correct.

What's going wrong? What's going right?

Why am I even seeing negative numbers?

Walking through the first three generated secret numbers 
123
123 * 64 -> 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

-16249871 WRONG
Enter fullscreen mode Exit fullscreen mode

I see where it's becoming a negative number.

But I'm still not sure how to get the correct next secret number.

Studying integers and bitwise operations

  • bitwise operations in JavaScript work on 32-bit signed integers
  • The largest integer is 2,147,483,647
  • The integer I am attempting to operate on is 3,156,183,040
  • That's a much larger number
  • To operate on it with bitwise operators in JavaScript, I have to use the BigInt data type instead of the Number data type

When I try to execute this code:

let big = BigInt("1541105")
let big2 = BigInt("3156183040")
let result = big ^ big2
Enter fullscreen mode Exit fullscreen mode

I get this integer instead of the negative integer:
3154643953

And when I calculate:

3154643953 % 16777216
Enter fullscreen mode Exit fullscreen mode

I get the correct next secret number:
527345

Wow, what a fun adventure to discover the error in my code!

Now, how can I fix my program to work with BigInts?

Until the errors stop...eventually?

Wrap each integer with BigInt().

That should work, right?

Yes, but there's still the use of Math.floor().

That's a Number data type function. Can't use it on BigInts.

Turns out that's not even necessary. BigInts will only ever be integers.

Cool!

My latest program 

let buyers = input.split('\n').map(BigInt)
function mix (secret, value) { return BigInt(secret ^ value) }
function prune (secret) { return BigInt(secret % BigInt(16777216)) }
function regen(buyer) {
    buyer = prune(mix(buyer, BigInt(buyer * BigInt(64))))
    buyer = prune(mix(buyer, BigInt(buyer / BigInt(32))))
    buyer = prune(mix(buyer, BigInt(buyer * BigInt(2048))))
    return buyer
}
let answer = buyers.reduce((sum, buyer) => {
  for (let i = 0; i < 2000; i++) {
    buyer = regen(buyer)
  }
  sum += buyer
  return sum
}, BigInt(0))
Enter fullscreen mode Exit fullscreen mode

Anything and everything are BigInts.

But guess what...

...it works!

  • I generate the correct next 10 secret numbers for 123
  • I generate the correct 2000th secret number for all four other example secret numbers

I think my algorithm is finally working as intended.

Testing on my puzzle input

I hope it generates the correct answer.

If not, I am out of ideas to debug my program.

Here goes nothing...

...

I got the correct answer!

Woohoo!!!

I'm almost certain Part 2 will up the target secret number to something in the billions or trillions.

That will require the puzzler to determine a pattern that is inherit to the calculations.

If so, I may be throwing the towel in quickly.

Time to find out...

Part 2

Not at all what I expected

Instead, it's a much more interesting twist:

  • Find the four-integer sequence of numbers -9 thru 9
  • That optimizes for the amount of bananas sold by all monkey buyers in my input

If I were to brute-force this, I would write an algorithm that:

For each combination of four integers
  For each monkey buyer's secret number
    Process as many secret numbers, up to 2000
      Stop if the combination occurs
        Add the price to a running total
Enter fullscreen mode Exit fullscreen mode

How many operations would that generate in a worst-case scenario?

Possible 4-digit combinations: 
(-9 thru 9, four times)
19 * 19 * 19 * 19
----
130k

Monkey buyers:
2002 in my puzzle input
130k * 2002
----
261M

2000 secret numbers for each buyer:
261M * 2000
----
522B
Enter fullscreen mode Exit fullscreen mode

Yikes! That's a lot of processing.

There's most certainly a smarter way to arrive at the correct answer.

But I don't know what it could be.

And I'm satisfied with my single gold star.

So, it's off to the next day's challenge for me.

Top comments (0)