# ETOOBUSY đźš€ minimal blogging for the impatient

# AoC 2022/21 - When Wolfram Alpha failed me...

**TL;DR**

On with Advent of Code puzzle 21 from 2022: I came up with a simple equation butâ€¦

After day 19, that took me so long, this dayâ€™s puzzle was pretty straightforward. I guess itâ€™s a matter of knowing how to do things beforehand.

Both parts largely require us to evaluate/manipulate arithmetic expressions comprised of sums/subtractions/multiplications/divisions (integer ones, as it happened in my case at least); the second part twist is that one of the operations has to be considered an equal sign, one of the inputs is an unknown variable and the whole thing is an equation that we have to solve for the unknown.

I guess it *might* sound difficult, but if we think about it, we lucky
folks are teached how to do these operations (and their inverse) in the
first years of our education, so itâ€™s no big deal to translate these
rules.

First we have to read the inputs, though. Each line is an expression, which consists either in a value or an operation; it makes sense to parse the lines as such so here we go:

```
for $filename.IO.lines -> $expression {
my $match = $expression ~~ m{^
$<target>=(\w+) \:\s+ $<op1>=(\w+)
[ \s+ $<op>=(\S) \s+ $<op2>=(\w+) ]?
$};
my $nv = nv($match<target>);
if $match<op> {
$nv.init(nv($match<op1>), $match<op>, nv($match<op2>));
}
else {
$nv.init($match<op1>.Int);
}
}
```

As we will deal with expressions, it makes sense (to me) to represent
each operation in an expression, or a single value, as a `Node`

, and
keep track of all nodes (this is the `nv()`

function used above):

```
class Node {
has $.name;
has $.value = Nil;
has $.left = Nil;
has $.right = Nil;
has $.op = Nil;
multi method init ($value) { $!value = $value }
multi method init ($left, Str() $op, $right) {
$!left = $left;
$!right = $right;
$!op = $op;
}
...
}
...
sub nv (Str() $name) { # keep track of all nodes
state %node-for;
return %node-for{$name} //= Node.new(name => $name);
}
```

As it happens, the inputs *are* simple, in the sense that what we have
out of the inputs is a *tree* instead of a more generic *graph*. In
other terms, each four-letters placeholder only appears once on the left
and at most once on the right across all expressions; this simplifies
things a lot for part 2.

Anyway, part 1 is about evaluating the whole thing, with `root`

at
theâ€¦ *root* or our evaluation tree. Many people went the `eval`

route,
which is fair in these challenges; I opted for a more canonical and
boring solution, involving doing the maths step by step. I guess there
was a quick shortcut do express this in Raku butâ€¦ I donâ€™t know it.

```
class Node {
...
method simplified {
return $!value if defined $!value;
my $left = $!left.simplified;
my $right = $!right.simplified;
return "($left $.op $right)" unless $left ~~ Int && $right ~~ Int;
return $!op eq '+' ?? $left + $right
!! $!op eq '-' ?? $left - $right
!! $!op eq '*' ?? $left * $right
!! $!op eq '/' ?? $left div $right
!! die("unknown op $.op");
}
...
}
```

If the node is a simple value, just return it. Otherwise, do the simplification of the expression on both sides, and apply the operation. As anticipated, I went for integer arithmetics and it was fine for my inputs.

The twist in part 2 is that the meaning of two items change:

- the operation in the
`root`

node is an equal sign actually, turning the whole thing into an equation instead of a simple expression; - the value in the
`humn`

node should be disregarded and we have to find out the right one to make the whole equation hold.

I initially thought of *printing* the equation and throwing it to
Wolfram Alpha. Butâ€¦ I hit (like many others) the wall of the
maximum input lenght, so I was back to square zero. Ouch!

The fact that the equation is represented by a *tree* comes to the
rescue here. My approach is to *simplify* the equation until I have the
unknown alone on one side, and a value on the other; with a tree, I have
that the unknown is *only* on one side at each step (even though â€śnot
aloneâ€ť), while the other side is always a simple number. Something like
this:

Now, `f_i(x)`

is by itself an arithmetic expression that involves basic
operations upon our unknown `humn`

/$x$ variable, so we can *invert* it
and obtain a new equation that has the same shape. As an example, letâ€™s
consider we have this at step $i$ of our simplification:

This means:

\[A + f_{i+1} = k \Rightarrow f_{i+1} = K - A\]A couple examples more, also keeping in mind that subtraction and
division are *not commutative*:

In our tree, then, we will have *almost* always three terms that we are
interested into:

- the side with a simple value, i.e. $K$
- the side with an operation, which has two operands $A$ and $f_{i+1}(x)$

We have to take care of the order of the operands in the operation, but itâ€™s really no big deal as we have to take into account only a few possibilities. Hereâ€™s the final product:

```
class Node {
...
method set-as-unknown { $!value = 'x' }
method !expr-value {
my $rv = $!right.simplified;
return ($!left, $rv) if $rv ~~ Int;
return ($!right, $!left.simplified);
}
method solve-as-equal {
my ($expr, $value) = self!expr-value;
while $expr.simplified ne 'x' {
my $op = $expr.op;
if $op ~~ m{ <[ + * ]> } { # commutative
my ($se, $sv) = $expr!expr-value;
$expr = $se;
$value = $op eq '+' ?? $value - $sv !! $value div $sv;
}
elsif $op ~~ m{ <[ / - ]> } { # non-commutative
my ($l, $r) = $expr.left, $expr.right;
if $l.simplified ~~ Int { # K <op> f(x) = V --> f(x) = K <op> V
$expr = $r;
$value = $op eq '-' ?? $l.simplified - $value
!! $l.simplified div $value;
}
else { # f(x) <op> K = V --> f(x) = V <inv-op> K
$expr = $l;
$value = $op eq '-' ?? $value + $r.simplified
!! $value * $r.simplified;
}
}
else { die "unknown op $op" }
}
return $value;
}
...
}
```

The `set-as-unknown()`

method allows us to set node `humn`

a our unknown
variable; then `solve-as-equal()`

does the whole job of taking different
alternatives into consideration and applying the transformation that
eventually lead us to `x = K_n`

, that is our solution.

To account for the modification in the `root`

node, this method is
called onto that specific node; additionally, at each step we make sure
that `$expr`

contains the expression with the unknown, and `$value`

is
our $K$ from the discussion above.

With this saidâ€¦ have fun and stay safe!

*Comments? Octodon, Twitter, GitHub, Reddit, or drop me a line!*