DEV Community

Cover image for Monkey Math
Robert Mion
Robert Mion

Posted on

Monkey Math

Advent of Code 2022 Day 21

Part 1

  1. Maybe - just maybe - another gold star
  2. Check them all and collect the one's who have yelled
  3. My algorithm in JavaScript

Maybe - just maybe - another gold star

  • I've encountered this type of puzzle in AoC
  • I recall solving at least Part 1 of that puzzle
  • I recall using a slow algorithm - the only strategy I knew of - and therefore don't recall solving Part 2
  • I intend to re-create that strategy to solve Part 1 here

Check them all and collect the one's who have yelled

How my algorithm will work:

Create an empty dictionary called yelled
While yelled has no key named root
  For each monkey
    If it just yells
      Create a key in dictionary for that monkey's name
        Store as its value the number yelled
    If it has an equation
      If both operands are keys in yelled
        Create a key in dictionary for that monkey's name
          Store as its value the number yelled after evaluating the equation
Enter fullscreen mode Exit fullscreen mode

Now to write it and try it on the example input!

My algorithm in JavaScript

let monkeys = input.split('\n')
let yelled = {}
while (!('root' in yelled)) {
  monkeys.forEach(m => {
    if (new RegExp(/\d+/).test(m)) {
      let [monkey, num] = m.split(' ')
      yelled[monkey.slice(0, -1)] = +num
    } else if (new RegExp(/[+\-\/*]/).test(m)) {
      let [monkey, ref1, op, ref2] = m.split(' ')
      if ((ref1 in yelled) && (ref2 in yelled)) {
        yelled[monkey.slice(0, -1)] = eval(
          `${yelled[ref1]} ${op} ${yelled[ref2]}`
        )
      }
    }
  })
}
return yelled['root']
Enter fullscreen mode Exit fullscreen mode

It worked! And the answer is a huge number!

Part 2

  1. A guessing game. Great.
  2. Really really high.

A guessing game. Great.

  • I'm sure there's a more efficient way to do this
  • But I must resort to starting at 0 and trying every number until I find the right one, assuming it's lower than...say...a few thousand?
  • How high could it be...right?

Really really high.

How do I know?

I used the following starting numbers, adjusting my amount of incrementing from 1 to as high as 1 trillion each iteration:
Starting numbers

  • I logged the numbers associated with both monkeys that must have yelled for root to yell
  • The second monkey never changes
  • The first monkey changed slightly: gradually decreasing with each higher number
  • It was decreasing by much for numbers smaller than a billion
  • I eventually overshot the crossing point: the first number went negative
  • So I walked back my starting number until it was about 1 trillion in difference from the target number
  • And I adjusted my increment value to always go up by 10 to a power one less than the number of digits in the starting number
  • Through careful watching, I identified the next digit in the number before crossing lower than the target number
  • And eventually made it back down to an increment of 1
  • Then, finally, I found the number - in the trillions! - that I must yell to get root's two dependent monkeys to yell the same number

I did it!!

  • I solved both parts!
  • For the first time in seven days!
  • Using an algorithm at first, then a pendulum-like guessing game!

I have no idea how I would have found the answer to Part 2 using strictly an algorithm.

So I'm glad I had the patience to try extremely high numbers and inch my way toward the answer manually.

Star status check

  • I have 30 stars
  • My lowest star count is 34
  • There are four more days
  • I know I am ineligible for the second star on Day 25
  • Which leaves only 7 stars left to earn
  • And these are likely to be the hardest days

So, while I'd love to tie my lowest star count...

...I sense that 2022 will become my new lowest star count.

Though, hopefully I'll still find a way to earn a few more stars.

Top comments (0)