Advent of Code 2022 - Day 21

[Mark Wutka]

Hi Everyone,

Last tuesday, Boris showed a cool implementation of Day 21 from AoC 2022 using Minizinc. Basically, that problem had a file with symbols assigned to constants and equations, like this:

jqnt: pbvp * rlcg
zpmp: mzgv - mbfh
jshn: mrmn * hjbv
mgml: 7
zcsd: 9
wlqf: 5
znrf: thnv * qzwq
gnqr: 2

For part A, you looked for the symbol named root and solved it. It, was just a matter of building an expression tree and evaluating it. For part B, though, somewhere in the expression tree there was a constant symbol named humn, which was the value a human had to enter. Then, you would interpret the root expression as being equality instead of, for example "root: lrnp + ptnb". That is, what value would humn have to be to make lrnp = ptnb.

When I did this one in Ada/SPARK back in 2022, I basically just tried values for humn and adjusted based on whether the equality got closer to correct or farther away. I decided to revisit that one today, and I realized that humn only occurs on one side of the equality - that is, if it occurs in lrnp, it isn't in ptnb, or vice-versa. And since that's the only unknown value, the other side of the inequality can be reduced to a constant. That meant that starting with a constant and an expression tree, I could basically work backwards down the tree until I just had the humn symbol and a constant.

For instance, suppose the top of the expression tree was:

Add abcd 5. and the constant was 27 (abcd is actually just a sub-expression tree that contains humn). Since abcd + 5 = 27, I know that abcd = 27 - 5, so I can then solve abcd with the constant 22. So then, suppose abcd is actually Sub 5 defg, so that 5 - defg = 22. I know then that defg = 5 - 22, and I then solve defg with the constant -17. Anyway, once I implemented this, it was able to solve part b in 0.02 seconds, where the trial&error version took 10 seconds.

Also, even though I spent some time diving into Scheme macros in preparation for AoC 2024, I think I have decided to use OCaml, which is what I did the above coding in. Here is the OCaml function that did the part B calculation:

let rec solve_for_humn node c =
  match node with
  | Add (l, r) ->
     if is_const l then
       solve_for_humn r (c - (const_val l))
     else
       solve_for_humn l (c - (const_val r))
  | Sub (l, r) ->
     if is_const l then
       solve_for_humn r ((const_val l) - c)
     else
       solve_for_humn l (c + (const_val r))
  | Mul (l, r) ->
     if is_const l then
       solve_for_humn r (c / (const_val l))
     else
       solve_for_humn l (c / (const_val r))
  | Div (l, r) ->
     if is_const l then
       solve_for_humn r ((const_val l) / c)
     else
       solve_for_humn l (c * (const_val r))
  | Symbol _ -> raise (Err "Encountered symbol searching for humn")
  | Human -> c
  | Const _ -> raise (Err "Encountered const searching for humn")

  

Mark