# Day 21: Monkey Math

See Day 21 for a detailed description of the problem.

Continuing to solve the Advent of Code 2022 problems (see Advent of Code - Day 1).

To run the example code in this post save the code into file such as `advent.jactl` and take your input from the Advent of Code site (e.g. `advent.txt`) and run it like this:

``````\$ cat advent.txt | java -jar jactl-2.0.0.jar advent.jactl
``````

## Part 1

In this challenge you are given a list of symbols and a simple mathematical formula for how to work out the value of each symbol. The formula can be a number or a binary expression of two other symbols. The goal is to evaluate all the expressions in order to work out the value of the `root` symbol.

Each line can look like:

``````abcd: 3
``````

or

``````efgh: zyxw * abcd
``````

I decided not to bother about coding an efficient solution, and instead chose to take advantage of the built-in `eval` function in Jactl to transform the expressions in to Jactl and then evaluate them. I pass in a Map of the variables each time and continually evaluate the expressions until I stop getting a value of `null` back. If any of the `eval` calls returns `null` it means that there was some sort of error (such as one of the symbols having a `null` value). Once every expression returns non-null it means we have a value for all symbols, and so we can just return the value of `root`.

``````def monkeys = stream(nextLine).map{ s/:/=/; s/(\d+)/\$1L/ }.filter{ it }
Map vars = monkeys.map{ s/=.*// }.collectEntries{ [it,null] }
while (monkeys.filter{ eval(it, vars) == null }) {}
vars.root
``````

There are quite a few expressions in the actual input, so it does take around 14s to fully evaluate everything since `eval` has to compile and execute each expression every time.

## Part 2

For part 2 the requirements change a bit. The expression for the `root` symbol must now be interpreted as an equality check (irrespective of whatever operator it has). So something like `root: abcd + efgh` should be interpreted as meaning that we have to verify that `abcd` and `efgh` are equal.

The trick is that now we have to find the number value for the `humn` symbol that ensures that the equality check for the `root` symbol will succeed.

First of all, we replace the value for the `humn` symbol with a marker value of `XXXX`. Then we recursively replace the symbols for the `root` expression with their expressions and replace any symbols in those expressions with their expressions and so on, building up an expression tree.

This leaves us with a tree where every node is either a number (or `XXXX`) or a subtree with `[lhs:lhsnode, op:op, rhs:rhsnode]` where the node values can themselves be further subtrees.

Fortunately, `humn` only occurs in one expression so there is only one marker in our tree structure. This allows us to iteratively manipulate our root expression tree until we end up with `XXXX` on one side on its own and a subtree on the otherside that we can evaluate to work out the value for `XXXX` and thus give the required value for the `humn` symbol.

Since our top root expression is an equality, as long as we perform the same operation to both sides of the equality we still have an equality that is true. So if we add the same thing to both subtrees or subtract the same thing, for example, we won’t violate the equality.

For the purpose of doing these manipulations we will keep a `lhs` variable which is the side where the marker lives and an `rhs` variable which is the other side of the equality. The `lhs` variable will be of the form `lhsnode op rhsnode`. (For the sake of illustrating how this works, we will assume that the marker is always in the `lhsnode` subtree of the `lhs` variable.) We then iterate, performing the opposite of the current operation. For example, if the operator is `+` then we would do this:

``````lhs = lhsnode
rhs = [lhs:rhs, op:'-', rhs:rhsnode]
``````

When `lhs` is just the marker on its own we have finished.

At that point we convert the `rhs` tree back into a string and evaluate it using `eval`.

``````def monkeys = stream(nextLine).collectEntries{ /(.*): (.*)\$/r; [\$1, \$2] }
def root = monkeys.'root'
def marker = 'XXXX'
monkeys.humn = marker

def parse(it) {
/^[\d]+\$/r              and return it as long
/^[a-z]+\$/r             and return parse(monkeys[it])
/^\${marker}\$/r          and return it
/(.*) ([\/*+-=]) (.*)/r and return [lhs:parse(\$1), op:\$2, rhs:parse(\$3)]
}
def containsMarker(node) { node == marker || node instanceof Map && (containsMarker(node.lhs) || containsMarker(node.rhs)) }

def tree = parse(root)
def lhs  = containsMarker(tree.lhs) ? tree.lhs : tree.rhs
def rhs  = containsMarker(tree.lhs) ? tree.rhs : tree.lhs
while (lhs.size() == 3) {
def isLhs = containsMarker(lhs.lhs)
lhs.op == '+' and rhs = isLhs ? [lhs:rhs, op:'-', rhs:lhs.rhs] : [lhs:rhs,     op:'-', rhs:lhs.lhs]
lhs.op == '*' and rhs = isLhs ? [lhs:rhs, op:'/', rhs:lhs.rhs] : [lhs:rhs,     op:'/', rhs:lhs.lhs]
lhs.op == '-' and rhs = isLhs ? [lhs:rhs, op:'+', rhs:lhs.rhs] : [lhs:lhs.lhs, op:'-', rhs:rhs]
lhs.op == '/' and rhs = isLhs ? [lhs:rhs, op:'*', rhs:lhs.rhs] : [lhs:lhs.lhs, op:'/', rhs:rhs]
lhs = isLhs ? lhs.lhs : lhs.rhs
}

def toExpr(node) { node !instanceof Map ? "\${node}L" : "(\${toExpr(node.lhs)} \${node.op} \${toExpr(node.rhs)})" }
eval(toExpr(rhs))
``````