Advent of Code 2022 Day 21
I enjoyed completing today's Advent of Code puzzle so I wanted to share my solution. The monkeys from day 11 are back to torment you more, this time by shouting riddles at you.
Part 1
The monkeys will shout either a number at you, or a pair of monkeys and a mathematical operation. If the monkey shouts another monkey's identifier, you need to calculate their number first. Your task is to determine which number the root monkey will yell.
This is fairly straightforward. I created a struct for the monkeys with the ID, a pointer to their number (so it can be nil if they have an operation instead), the operation and the IDs of the operand monkeys. I created a parsing function as well that takes my input and returns a map[string]*monkey , mapping IDs to monkeys.
Then I created a calc function that will take a monkey as a parameter, then return its number if it's not nil. If the number is nil, we find the operand monkeys and recursively call calc on them, then perform the current monkey's operation and return that.
All that's required is to pass the root monkey to calc and there's your answer.
Part 2
Part 2 changes the rules to say that the root monkey isn't performing an addition on his operand monkeys but is checking their equality instead, and that the humn monkey is you, and your task is to determine the right number to balance root's equation.
The most naive path is to find the value of humn and compare it with the other side of the root equation, then increase or decrease as necessary. This is slow even on the test input, so I thought to improve it by implementing a binary search. I started by increasing the value of the increase by 50000, then halving it whenever I went past higher or lower than the other side value. I managed to get this working for the test values, but it was too slow for the real input. (go test's default timeout of 30 seconds is a pretty good benchmark of whether you're going the wrong direction with your puzzle solution).
A better solution is to try and calculate the number you need instead of guessing it. Since only one side of the equation is unknown, we just need to solve for x. I wrote another function to traverse the tree to find which side of the tree is the humn or unknown side. Then, we can calculate the other side using the calc function from part 1. Then we can find the operand monkeys of the unknown side, figure out their values, and repeat.
Here's an example using the test input:
root: pppw + sjmn
- sjmn is the known side and equals 150, meaning pppw must equal 150 too
pppw: cczh / lfqf
- lfqf is 4, so cczh must equal (150 = 4x), or 600
cczh: sllz + lgvd
- sllz is 4, so lgvd must equal (600 = 4 + x), or 596
lgvd: ljgn * ptdq
- ljgn is 2, so ptdq must equal (596 = 2x) or 298
ptdg: humn - dvpt
- dvpt is 3, so humn must equal (298 = x - 3) or 301
The only trouble I ran into here was making sure that the operands were in the correct order. If the left side is the humn side, then we can simply reverse the operations, but on the right side we need to be careful. Here's another test case I wrote to check these edge cases:
// humn should be 3
root: bbbb + aaaa
aaaa: 10
bbbb: dddd + cccc
cccc: 6
dddd: ffff * eeee
eeee: 4
ffff: gggg - hhhh
gggg: 16
hhhh: iiii / humn
iiii: 45
humn: 42
Code for my solution is here.