Ruby, part 2. The code is horrible, but I am kind of proud of myself, seeing how others used binary search, o some online equation solvers.

The idea is starting from root build two chains of operations - one which ends in 'humn' and the other, where it ends in value node. Then at the root we know the final value of one chain, and need to go through the human chain reversing each operation so we end up with the initial value 'humn' should return.

# frozen_string_literal: true

require 'set'

file_path = File.expand_path('input.txt', __dir__)

file = File.open(file_path)
$monkeys = Set.new

file.readlines.map(&:chomp).each do |line|
  name, rest = line.split ':'
  parts = rest.split ' '
  if parts.size == 1
    $monkeys.add({ name: name, value: parts.first.to_i })
  else
    $monkeys.add({ name: name, left: parts.first, op: parts[1].to_sym, right: parts.last, value: nil })
  end
end

human_chain = []
target = 'humn'
loop do
  monkey = $monkeys.find { _1[:left] == target || _1[:right] == target }
  human_chain << monkey
  break if monkey[:name] == 'root'

  target = monkey[:name]
end

$human_chain_names = human_chain.map { _1[:name] }
monkey = $monkeys.find { _1[:name] == 'root' }
other_chain = []
loop do
  target = [monkey[:left], monkey[:right]].reject { $human_chain_names.include? _1 }.first
  break unless monkey[:value].nil?

  other_chain << monkey
  monkey = $monkeys.find { _1[:name] == target }
end

def value(node)
  node = $monkeys.find { _1[:name] == node }
  return node[:value] unless node[:value].nil?

  left = value(node[:left])
  right = value(node[:right])
  left.send(node[:op], right)
end

def perform(target, known_value, op, side)
  return (target - known_value) if op == :+
  return (target / known_value) if op == :*

  if op == :-
    return (target + known_value) if side == :left
    return (known_value - target) if side == :right
  end
  return (target * known_value) if side == :left
  return (known_value / target) if side == :right
end

def reverse(chain, target)
  chain = chain.drop(1)
  monkey = chain.first
  loop do
    left = monkey[:left]
    right = monkey[:right]
    op = monkey[:op]

    if left == 'humn'
      known_value = value(right)
      return perform(target, known_value, op, :left)
    elsif right == 'humn'
      known_value = value(left)
      return perform(target, known_value, op, :right)
    end

    known_node = [left, right].reject { $human_chain_names.include? _1 }.first
    next_node = [left, right].select { $human_chain_names.include? _1 }.first
    known_value = value(known_node)
    side = ($human_chain_names.include? left) ? :left : :right
    target = perform(target, known_value, op, side)
    monkey = $monkeys.find { _1[:name] == next_node }
  end
end

root = $monkeys.find { _1[:name] == 'root' }
target = value([root[:left], root[:right]].reject { $human_chain_names.include? _1 }.first)

print reverse(human_chain.reverse, target)