Advent of Code 2022, Day 21: Monkey Math

Part A

On Day 21 we have input like this:

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

So we have variables that contain plain values or some operation using other variables. The task is to output the value of root.

We can write very elegant solution in Ruby using eval:

data = File.readlines("21.txt", chomp: true)

data.map do |line|
  name, expression = line.match(/^(.+?): (.+?)$/).captures
  eval("def #{name}; #{expression}; end")
end

puts root

We just read the input file and define new method for each variable and put the right side into it’s body.

So for the given example we will generate the following code:

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

Then we just call root method and print out the output value.

Part B

Second part is more difficult. Our root variable should perform equality and our humn value is something we need to calculate so this equality test is true.

We can still use the approach from Part A, but now it will be more code. Approach I used is to define humn method to raise an special exception.

Now instead of just calling root method, we can first call it’s left part and check if it raises this special exception. From the example above our root is defined as def root; pppw + sjmn; end. So first we call pppw. If exception is raised it means humn is evaluated somewhere in pppw tree. If not, it must be evaluate on the right side, so sjmn in this case.

Since one side of the operation will not raise the exception, we will know it’s value. And we also know the operation, so using this we can calculate what should be the value of the other side to make it work.

Let’s use example input again. When we evaluate root, pppw will raise exception, but sjmn will just return 150. Because root operation is == and it must be true then pppw must also equal 150.

We can then try to evaluate pppw. It is defined as def pppw; cczh / lfqf; end. Again cczh will raise an exception, but lfqf will just return 4. So we know that cczh / 4 must equal 150, so cczh must equal 600. And we can continue like that until we reach humn variable.

Here is the full code:

require "debug"

# 9584437937672

class SpecialException < StandardError; end

data = File.readlines("21.txt", chomp: true)

@operations = {}

data.map do |line|
  name, expression = line.match(/^(.+?): (.+?)$/).captures

  if expression =~ /\d+/
    if name == "humn"
      eval("def #{name}; raise SpecialException; end")
    else
      eval("def #{name}; #{expression}; end")

      @operations[name] = expression
    end
  else
    left, op, right = expression.match(/(.+?) (\+|\-|\/|\*) (.+)/).captures

    if name == "root"
      op = "=="
    end

    eval("def #{name}; #{left} #{op} #{right}; end")

    @operations[name] = [left, op, right]
  end
end

def parse(node, expected)
  if node == "humn"
    return expected
  end

  known = nil
  value = nil
  left, op, right = @operations[node]

  begin
    value = eval(left)
  rescue SpecialException
    known = :right
    value = eval(right)
  end

  if known.nil?
    known = :left
    value = eval(left)
  end

  if op == "/" && known == :right
    # expected = left / right
    # left = expected * right
    parse(left, expected * value)
  elsif op == "/" && known == :left
    # expected = left / right
    # right = left / expected
    parse(right, value / expected)
  elsif op == "+" && known == :left
    # expected = left + right
    # right = expected - left
    parse(right, expected - value)
  elsif op == "+" && known == :right
    # expected = left + right
    # left = expected - right
    parse(left, expected - value)
  elsif op == "-" && known == :left
    # expected = left - right
    # right = left - expected
    parse(right, value - expected)
  elsif op == "-" && known == :right
    # expected = left - right
    # left = expected + right
    parse(left, expected + value)
  elsif op == "*" && known == :left
    # expected = left * right
    # right = expected / left
    parse(right, expected / value)
  elsif op == "*" && known == :right
    # expected = left * right
    # left = expected / right
    parse(left, expected / value)
  elsif op == "==" && known == :left
    parse(right, value)
  elsif op == "==" && known == :right
    parse(left, value)
  end
end

puts parse("root", true)