Day 21: Monkey Math

Racket has promises built-in so I decided to just lazy evaluation. Racket promises are created with delay and evaluated using force but there's very neat form lazy which will go all the way through the chain until everything is evaluated which is ideal for this problem since I don't have to keep checking "are we there yet?" on all those promises.

(define NUMBER   #px"^(\\w+): (\\d+)$")
(define EQUATION #px"^(\\w+): (\\w+) (.) (\\w+)$")

(define (part-01 input)
  (force (hash-ref (parse-monkeys input) "root")))

(define (parse-monkeys input)
  (define monkeys (make-hash))
  (for ([l (in-list input)])
    (match l
      [(pregexp NUMBER (list _ name num))
       (hash-set! monkeys name (string->number num))]
      [(pregexp EQUATION (list _ name l op r))
       (hash-set!
        monkeys name
        (lazy ((case op [("+") +] [("-") -] [("*") *] [("/") /])
               (force (hash-ref monkeys l))
               (force (hash-ref monkeys r)))))]))
  monkeys)

I considered re-arranging the expressions so it formed a valid equation for the value of humn as in classic algebra. I will come back to this because it sounds like a nice problem. Instead I chose a binary search for the right value of humn.
My "clever" part 01 solution won't work nicely because once a promise is forced, it doesn't change which makes it trickier.
Instead I wrote a simple evaluator for the tree and did the binary search for the value of humn required. I chose 2¹²⁸ but in the past I've used a continual doubling range when the limits are unknown. It worked out OK.

(define (part-02 input)
  (define-values (tree human target) (human-ancestor input))
  (find-human-value tree human target))

;; which side has humn?
;; return the tree, humn parent, value of the other side for root to match.
(define (human-ancestor input)
  (match-define (list _ left _ right)
    (for/first ([eqn (in-list input)]
                #:when (string=? "root" (substring eqn 0 4)))
      (string-split eqn)))
  (define original (expression-tree input))
  (define changed  (hash-update original "humn" add1))

  ;; if left evaluations are the same, then right is humn
  (if (= (evaluate-tree original left) (evaluate-tree changed left))
      (values original right (evaluate-tree original left))
      (values original left  (evaluate-tree original right))))

(define (find-human-value tree node target)
  (define (search from to)
    (define mid (quotient (+ from to) 2))
    (define e (evaluate-tree (hash-set tree "humn" mid) node))
    (cond [(> from to) 'fail]
          [(= e target) mid]
          [(< e target) (search from (sub1 mid))]
          [(> e target) (search (add1 mid) to)]))
  (search 0 (expt 2 128)))

(define (expression-tree input)
  (for/fold ([tree (hash)])
            ([line (in-list input)])
    (match line
      [(pregexp NUMBER (list _ name num))
       (hash-set tree name (string->number num))]
      [(pregexp EQUATION (list _ name l op r))
       (define f (case op [("+") +] [("-") -] [("*") *] [("/") /]))
       (hash-set tree name (list f l r))])))

(define (evaluate-tree tree node)
  (match (hash-ref tree node)
    [(? number? n) n]
    [(list op l r)
     (op (evaluate-tree tree l) (evaluate-tree tree r))])))

Using this evaluate-tree solves part 1 a little quicker than the promise version but I got to discover the lazy form.

#!/usr/bin/env python3
import sys
from typing import List
from typing import Tuple
import re
import sympy as sy

def get_data(filename: str) -> List[str]:
    with open(filename,'r') as f:
        lines = f.read().splitlines()
    return lines

equation_pattern = re.compile("([\w]{4}): ([\w]{4}) (.) ([\w]{4})")
constant_pattern = re.compile("([\w]{4}): ([\d]+)")
generic_pattern  = re.compile("([\w]{4}): (.+)")

class Equation(object):
    def __init__(self,line):
        matches = re.search(equation_pattern, line)
        self.name  = matches[1]
        self.left  = matches[2]
        self.right = matches[4]
        self.op    = matches[3]

def part1():

    # Input
    input = get_data(sys.argv[1])
    monkeys = {}
    equations = []
    for line in input:
        if matches := re.search(constant_pattern,line):
            monkeys[matches[1]] = int(matches[2])
        else:
            equations.append(Equation(line))

    # Solve
    while len(equations) > 0:
        for eqn in equations:
            if eqn.left in monkeys and eqn.right in monkeys:
                monkeys[eqn.name] = int(eval(f"{monkeys[eqn.left]} {eqn.op} {monkeys[eqn.right]}"))
        equations = [eqn for eqn in equations if eqn.name not in monkeys]

    print(f"Part 1: {monkeys['root']}") # 152479825094094

def part2():

    # Input
    input = get_data(sys.argv[1])
    monkeys = {}
    for line in input:
        matches = re.search(generic_pattern,line)
        monkeys[matches[1]] = matches[2]

    # Build equation
    eq_l = monkeys['root'].split()[0]
    eq_r = monkeys['root'].split()[2]
    monkeys.pop('root')
    monkeys.pop('humn')
    while len(monkeys) > 0:
        for word in eq_l.split():
            if word in monkeys:
                eq_l = eq_l.replace(word,'( '+monkeys[word]+' )')
                monkeys.pop(word)
        for word in eq_r.split():
            if word in monkeys:
                eq_r = eq_r.replace(word,'( '+monkeys[word]+' )')
                monkeys.pop(word)

    # Solve
    eq_l = sy.parse_expr(eq_l)
    eq_r = sy.parse_expr(eq_r)
    x = sy.symbols('humn')
    part2 = sy.solve(eq_l - eq_r)[0]
    print(f"Part 2: {part2}") # 3360561285172

if __name__ == "__main__":
    part1()
    part2()