# 2022 Day 21: Monkey Math

I really enjoyed today’s puzzle! Observations / hints / spoilers:

• The example does not cover all the cases you need to check in Part 2. Interestingly, the input is relatively small if you look at it right, so even though I got Part 2 wrong the first time, it didn’t take me long to work through the example and find my mistake.
• In part 1, recursion works, especially if you store a node’s value after computing it.
• In part 2, take care when rewriting subtraction and division. The correct result depends on which direcdtion you have to branch down.

# 4 days left!!!

The only issue I had with switching from test to real input was, that I tried to calculate all monkey’s values. That lead to overflow even after changing the value type to Long_Long_Integer. When changing it to only calculate needed values for the root monkey, it worked in an instant.

This time, Hashed_Maps was easy to use with the String(1…4) keys. Used a Vector for the queue while calculating.

Run time is small enough to call it near-instant event with both parts.

Interesting! I tried from the start simply to calculate `root`’s values. I guess there must be more than one tree in the puzzle input, because no monkey depends on `root`, and if `root` depended on the monkeys whose values overflow, we’d have a problem!

Nice to have an easier one! I had the same issue of having to switch from Integer to Long_Integer for the second part, but no problems there otherwise.

Part 1 I just store the constants and formulas in a map and the when I compute a value, if it is a formula, I recursively compute the left and right values using the map.

Part 2 I’m sure this is a suboptimal way to approach it, but I have a guess value, starting at 1, and compute left and right with humn=guess and humn=guess+1, then I figure out by comparison whether to increase or decrease guess. I increment/decrement the guess by large amounts when the diff is big, and then by progressively smaller amounts as it gets smaller.

Hmm, I believe I needed a longer integer already on the first part, where my answer was `110181395003396`.

Also, I just realized that there’s an implicit assumption that each monkey informs only one other monkey. That is, only one monkey is listening for `humn`’s number, and only one other monkey is listening for that monkey’s number, etc.

For Part 2, I did something quite different from you:

• the problem is one of determining the goal for each monkey whose value depends on `humn`

• `root`’s goal is to get `left - right = 0`; that is, I rewrite `root`’s operation as subtraction (from addition in my case).
In the example, `root` is originally `pppw + sjmn`; now it’s `pppw - sjmn` with a goal of 0
• let `monkey := root`

• while `monkey /= humn`

1. `monkey` obviously computes a value from two other monkeys; left `M` be the one that depends on `humn`, and `N` the one that does not
In the example, when `monkey = root` then `M` would be `pppw` and `N` would be `sjmn`.
2. use `N`’s value, `monkey`’s operation, and `monkey`’s goal to compute `M`’s goal

• In the example, when `monkey = root`, then `sjmn`’s value is 150, and since `roots` operation is `pppw - sjmn` with a goal of 0, we reason that `pppw`’s goal becomes `0 + sjmn = 150`.

• Notice that if you have to descend the other way, the new formula is different! If `sjmn` depended on `humn` and `pppw`’s value was 150, then `sjmn`’s goal would become `0 - pppw = -150`!!! That was the mistake I made when first attempting Part 2.

3. if `N = humn`, return the goal; otherwise, return to step 1

Implemented by turning the data into an Ada function, plus a little edition for the `root` and `humn` cases.
See the transformed example below.
For part 1, call the function, with `part => part_1`;
for part 2, find a zero of the function, with `part => part_2`.
To find the zero, I have let `x` grow by doubling it until `f(-x)` has the opposite sign of `f(x)`, then I have reduced the range `[-x, x]` by dichotomy.

Total run time for both parts:
0.32 seconds with HAC,
0.0021 seconds with GNAT.

``````  function Compute_Mini (part : Part_Type; human : Integer_64) return Integer_64
is
function Eval (m : Monkey_Mini) return Integer_64 is
begin
case m is
when root_m =>
case part is
when part_1 => return Eval (pppw) + Eval (sjmn);
when part_2 => return Eval (pppw) - Eval (sjmn);
end case;
when dbpl   => return 5;
when cczh   => return Eval (sllz) + Eval (lgvd);
when zczc   => return 2;
when ptdq   => return Eval (humn_m) - Eval (dvpt);
when dvpt   => return 3;
when lfqf   => return 4;
when humn_m =>
case part is
when part_1 => return 5;
when part_2 => return human;
end case;
when ljgn   => return 2;
when sjmn   => return Eval (drzm) * Eval (dbpl);
when sllz   => return 4;
when pppw   => return Eval (cczh) / Eval (lfqf);
when lgvd   => return Eval (ljgn) * Eval (ptdq);
when drzm   => return Eval (hmdt) - Eval (zczc);
when hmdt   => return 32;
end case;
end Eval;
begin
return Eval (root_m);
end Compute_Mini;
``````
3 Likes

Neat idea, embedding the monkeys as assignment statements in your code!