Module aoc::year2022::day21

Monkey Math

The Monkeys form a binary tree. We first compute the result by recursively following the strucuture all the ways to the leaves. We also find the humn node and all its parents the same way, marking them as “unknown”.

For part two we know that the value on the left and the right of the root must be equal. Following the tree down the path previously marked “unknown” we recursively solve equations until we reached the humn node.

For example say the root’s children are a and b

    yell[a] = 6
    unknown[a] = false
    yell[b] = 5
    unknown[b] = true

So this implies b is a parent of humn and must equal 6 to pass (the current value is irrelevant). We then recursively look at the children of b:

    yell[c] = 4
    unknown[a] = true
    operation = "+"
    yell[d] = 4
    unknown[b] = false

We know that c + d must equal 6 so this implies c = 2. We then recursively look at the children of c

    yell[humn] = 123
    unknown[a] = true

Once we finally reach the humn node the value that we currently have 2 is the answer.

Structs

• Input

Enums

• Monkey 🔒
• Operation 🔒

Functions

• compute 🔒
  Recursively compute the total following the tree structure all the way to the leaves.
• find 🔒
  Recursively find the humn node then mark it and all its parents all the way to the root as “unknown”.
• inverse 🔒
  Recursively finds the value of the expression on the “unknown” side so that it equals the known side.
• parse
• part1
• part2