Juha-Matti Santala
Community Builder. Dreamer. Adventurer.

Advent of Code - 2022

This is a solution to Day 21 of Advent of Code 2022.

Day 21 - Monkey Math

The monkeys are back! You're worried they're going to try to steal your stuff again, but it seems like they're just holding their ground and making various monkey noises at you.

Eventually, one of the elephants realizes you don't speak monkey and comes over to interpret. As it turns out, they overheard you talking about trying to find the grove; they can show you a shortcut if you answer their riddle.

Each monkey is given a job: either to yell a specific number or to yell the result of a math operation. All of the number-yelling monkeys know their number from the start; however, the math operation monkeys need to wait for two other monkeys to yell a number, and those two other monkeys might also be waiting on other monkeys.

Your job is to work out the number the monkey named root will yell before the monkeys figure it out themselves.

For example:

root: pppw + sjmn
dbpl: 5
cczh: sllz + lgvd
zczc: 2
ptdq: humn - dvpt
dvpt: 3
lfqf: 4
humn: 5
ljgn: 2
sjmn: drzm * dbpl
sllz: 4
pppw: cczh / lfqf
lgvd: ljgn * ptdq
drzm: hmdt - zczc
hmdt: 32

Each line contains the name of a monkey, a colon, and then the job of that monkey:

  • A lone number means the monkey's job is simply to yell that number.
  • A job like aaaa + bbbb means the monkey waits for monkeys aaaa and bbbb to yell each of their numbers; the monkey then yells the sum of those two numbers.
  • aaaa - bbbb means the monkey yells aaaa's number minus bbbb's number.
  • Job aaaa * bbbb will yell aaaa's number multiplied by bbbb's number.
  • Job aaaa / bbbb will yell aaaa's number divided by bbbb's number.

So, in the above example, monkey drzm has to wait for monkeys hmdt and zczc to yell their numbers. Fortunately, both hmdt and zczc have jobs that involve simply yelling a single number, so they do this immediately: 32 and 2. Monkey drzm can then yell its number by finding 32 minus 2: 30.

Then, monkey sjmn has one of its numbers (30, from monkey drzm), and already has its other number, 5, from dbpl. This allows it to yell its own number by finding 30 multiplied by 5: 150.

This process continues until root yells a number: 152.

However, your actual situation involves considerably more monkeys.

I'll admit: I was surprised to find myself thinking "nice, a simple binary tree" and feeling like I knew what I need to do. And I did, this was a rather straight-forward puzzle for me. That is surprising given how bad I am with trees and recursion. Advent of Code has been teaching me!

Modeling

I start with modeling our node.

The node either has a value of its own (if it's a leaf of the tree) or it has a left, right and operation (if it's a non-leaf node).

class Node:

    def __init__(self, name):
        self.name = name
        self.value = None
        self.left = None
        self.right = None
        self.operation = None

    def __repr__(self):
        if self.value:
            return f'<{self.name}: {self.value}>'
        elif self.left and self.right:
            return f'<{self.name}: {self.left.name} {self.operation} {self.right.name}>'
        else:
            return f'<{self.name}: [empty]>'

Read input

I'm still not quite sure how to effectively build a tree when the inputs are not in order. My approach is to read the original values into a dictionary and then loop over that, creating nodes that can be created until all the nodes have been added to a tree.

First, with transformer and utils.read_input, I transform the original input into a list of node data.

Then, with create_tree, I use a temporary dictionary to create and attach nodes to each other and return the root node.

from utils import read_input
import re

def transformer(line):
    name, operation = line.split(': ')
    try:
        operation = int(operation)
    except ValueError:
        operation = re.split(r' (\+|-|\/|\*) ', operation)

    return name, operation

data = read_input(21, transformer)
temp = {}
for node in data:
    temp[node[0]] = node[1]

def create_tree(temp):
    tree = {}
    unfound = []
    while True:
        try:
            name, op = temp.popitem()
        except KeyError:
            if unfound:
                for name, op in unfound:
                    temp[name] = op
                unfound = []
                continue
            else:
                break
        if isinstance(op, int):
            node = Node(name)
            node.value = op
            tree[node.name] = node
            continue
        else:
            left, oper, right = op
            if left in tree and right in tree:
                node = Node(name)
                node.left = tree[left]
                node.right = tree[right]
                node.operation = oper
                tree[node.name] = node
            else:
                unfound.append((name, op))
    return tree['root']

root = create_tree(temp)

To calculate the value of the tree, I recursively go through the tree.

  1. If the node has a value, we return the value
  2. If not, we return the result of the left subtree and right subtree with our operation
def calculate(node):
    if node.value:
        return node.value

    match node.operation:
        case '+':
            return calculate(node.left) + calculate(node.right)
        case '-':
            return calculate(node.left) - calculate(node.right)
        case '/':
            return calculate(node.left) // calculate(node.right)
        case '*':
            return calculate(node.left) * calculate(node.right)

Part 1

What number will the monkey named root yell?

result = calculate(root)
print(f'Part 1: {result}')
assert result == 31017034894002

Part 2

Due to some kind of monkey-elephant-human mistranslation, you seem to have misunderstood a few key details about the riddle.

First, you got the wrong job for the monkey named root; specifically, you got the wrong math operation. The correct operation for monkey root should be =, which means that it still listens for two numbers (from the same two monkeys as before), but now checks that the two numbers match.

Second, you got the wrong monkey for the job starting with humn:. It isn't a monkey - it's you. Actually, you got the job wrong, too: you need to figure out what number you need to yell so that root's equality check passes. (The number that appears after humn: in your input is now irrelevant.)

In the above example, the number you need to yell to pass root's equality test is 301. (This causes root to get the same number, 150, from both of its monkeys.)

What number do you yell to pass root's equality test?

Part 2 requires a bit more of exploration. I decided to solve it with an approach that checks which subtree (left or right) the humn node is, then calculate the value of the other subtree and with some inverse math, calculate a new target value to pass down, until we find the humn node.

is_child is a depth-first search that goes through all the nodes from left to right until it finds node with name humn.

def is_child(root):
    if root.name == 'humn':
        return True
    if root.value is not None:
        return False
    return is_child(root.left) or is_child(root.right)

This is not the most efficient approach since every time I go down one level, I search the entire subtree again. There's probably a way to build a path to the right node on the first run and then just follow that.

In correct, I check if the left or right subtree has the right node, then calculate the new target value based on the operation and the value of the other subtree.

The inverse math

There are generally 1-2 different cases we can have for each operation.

To go through all the options, I'm using a notation where t is our target value, C is a known value (the result of the other subtree) and x is our unknown value.

case +

  t
 / \
x   C

In the first case, our unkwown is on the left subtree. To calculate what that subtree needs to become, we need to solve the equation t = x+C for x, which becomes x = t-C.

  t
 / \
C   x

In the second case, our unknown is on the right subtree. t = C+x, solved to x is the same x = t-C.

So regardless, when the parent has + operation, we calculate it by subtracting the known C value from it. And because the operation is +, we take the absolute value |t-C| to stay positive.

case -

  t
 / \
x   C

For subtraction, we solve for t = x-C which becomes x = t+C.

  t
 / \
C   x

For the second case, we solve for t = C-x which becomes x = C-t.

case *

  t
 / \
x   C

For the multiplication, first case is t = x*C which becomes x = t/C

  t
 / \
C   x

And the second case is the same: t = C*x -> x = t/C

case /

  t
 / \
x   C

For division, first case is t = x/C -> x = t*C

  t
 / \
C   x

and second case is t = C/x -> x = C/t

def correct(node, target):
    if is_child(node.left):
        value = calculate(node.right)
        match node.operation:
            case '+':
                new_target = abs(target - value)
            case '-':
                new_target = target + value
            case '/':
                new_target = target * value
            case '*':
                new_target = target // value
        new_path = node.left
        if node.left.name == 'humn':
            return new_target
        else:
            return correct(new_path, new_target)
    else:
        value = calculate(node.left)
        match node.operation:
            case '+':
                new_target = abs(value - target)
            case '-':
                new_target = value - target
            case '/':
                new_target = value // target
            case '*':
                new_target = target // value
        new_path = node.right
        if node.right.name == 'humn':
            return new_target
        else:
            return correct(new_path, new_target)

def solve2(root):
    if is_child(root.left):
        return correct(root.left, calculate(root.right))
    else:
        return correct(root.right, calculate(root.left))
part2 = solve2(root)
print(f'Part 2: {part2}')
assert part2 == 3555057453229