Monkey Math
Tags: adventofcode, algorithms, javascript, programming
Published: 2022-12-25 19:56:25

## [Advent of Code 2022 Day 21](https://adventofcode.com/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
```

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

### My algorithm in JavaScript
```js
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']
```

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rj6ncnffckyhpppzfvsz.gif)

- 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.