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