Advent of Code (in MiniScript), Day 21
Tags: miniscript, adventofcode, programming, tutorial
Published: 2022-12-21 15:51:57

Welcome back to my [series](https://dev.to/search?q=JoeStrout%20%23adventofcode&sort_by=published_at&sort_direction=asc) of [Advent of Code](https://adventofcode.com/) solutions in [MiniScript](https://miniscript.org)!  Last night was [Day 21](https://adventofcode.com/2022/day/21), a refreshingly straightforward challenge.

We're given a bunch of variables (called "monkeys" in the challenge) whose value is given as either a simple integer like `42`, or an expression of two other variables like `sllz + lgvd`.  One of these variables is called `root`, and we need to calculate its value.

This is a good use case for recursion: for any variable based on an expression, its value is the value of each of the variables it depends on, combined with the operator (which is always one of `+`, `-`, `*`, or `/`).  I made a `Monkey` class that with the needed properties:

```
Monkey = {}
Monkey.value = null		// numeric value, if known; else null
Monkey.op = ""			// operator (+, -, *, or -)
Monkey.dependsOn = null	// list of 2 monkey names, or null
```

...and then gave it an `evaluate` method that does this recursion as needed.

```
Monkey.evaluate = function
	if self.value != null then return self.value
	arg0 = monkeys[self.dependsOn[0]].evaluate
	arg1 = monkeys[self.dependsOn[1]].evaluate
	self.value = eval.eval(arg0 + self.op + arg1)
	return self.value
end function
```

Note that `dependsOn` is a list of monkey _names_; we look up the corresponding `Monkey` objects in a global map called `monkeys`.  Also, to avoid writing code to handle the four different operators, I used the `eval` module from [this repo](https://github.com/JoeStrout/MiniScriptEval) to evaluate an expression based on the monkey's operator.

The rest of the program is just parsing the data, and then printing the value of the `root` monkey (as `monkeys.root.evaluate`).  Here's the complete code:

```
import "stringUtil"
import "eval"

if 0 then fname = "input.txt" else fname = "example.txt"
lines = file.readLines(fname)
if not lines[-1] then lines.pop

Monkey = {}
Monkey.value = null		// numeric value, if known; else null
Monkey.op = ""			// operator (+, -, *, or -)
Monkey.dependsOn = null	// list of 2 monkey names, or null

Monkey.make = function(line)
	m = line.match("{name}: {name1} {op} {name2}")
	if m == null then
		m = line.match("{name}: {value}")
		if m.value == "0" or val(m.value) then
			noob = new Monkey
			noob.name = m.name
			noob.value = val(m.value)
			return noob
		end if
		print "Error: " + line
		exit
	end if
	noob = new Monkey
	noob.name = m.name
	noob.dependsOn = [m.name1, m.name2]
	noob.op = m.op
	return noob
end function
Monkey.evaluate = function
	if self.value != null then return self.value
	arg0 = monkeys[self.dependsOn[0]].evaluate
	arg1 = monkeys[self.dependsOn[1]].evaluate
	self.value = eval.eval(arg0 + self.op + arg1)
	return self.value
end function

monkeys = {}	// key: name; value: monkey

for line in lines
	m = Monkey.make(line)
	monkeys[m.name] = m
end for

print monkeys.root.evaluate
```

## Part Two

The second part of the challenge adds an interesting wrinkle.  The `root` monkey is now wanting to make the two monkeys it depends on **equal** in value.  And the value of the `humn` (human) variable is now unknown (we ignore the value given for it in the input file).  Our task is to figure out what value of `humn` will make `root`'s two monkeys equal in value.

You might think of just trying a bunch of values for `humn`, since evaluating these monkey trees is pretty quick.  But I don't think that would work well; the values in the real input file are huge, like 87,432,199,155,395 for example.  So trying all possibilities would take too long.

Instead, the thing to do is to use recursion again.  Suppose we know `abcd = 42` (perhaps because `root` depends on `abcd` and some other monkey whose value we can fully evaluate to 42).  And further suppose we have `abcd` defined as `efgh + ijkl`, and we can fully evaluate `ijkl` to 10.  That means `efgh + 10 = 42`, or `efgh = 42 - 10 = 32`.  So now we just need to solve `efgh = 32`.  And if we keep working our way down the chain like this, solving at each step, eventually we'll come to `humn`, and know what its value must be.

To make this possible, we need to know at each step which of the two monkeys in an expression depends on the `humn` variable.  That'll be the one we need to solve for; the other one can be evaluated directly.  So I made this helper method:

```
Monkey.dependsOnHumn = function
	if self.dependsOn == null then return false
	if self.dependsOn.contains("humn") then return true
	return monkeys[self.dependsOn[0]].dependsOnHumn or
	  monkeys[self.dependsOn[1]].dependsOnHumn
end function
```

Then, the `solve` method.  Unfortunately the `eval` module couldn't help me here; I had to handle each of the four operators separately.  In fact I had to do this twice, depending on which of the two monkeys is the one we're solving for.  So the function is a bit longer, but still not very complex.

```
Monkey.solve = function(forValue)
	print "Solving " + self.name + " = " + forValue
	m0 = monkeys[self.dependsOn[0]]; m1 = monkeys[self.dependsOn[1]]
	if m0.dependsOnHumn or m0.name == "humn" then
		arg1 = m1.evaluate
		if self.op == "+" then
			newVal = forValue - arg1
		else if self.op == "-" then
			newVal = forValue + arg1
		else if self.op == "*" then
			newVal = forValue / arg1
		else if self.op == "/" then
			newVal = forValue * arg1
		else
			print "unknown op " + self.op
			exit
		end if
		if m0.name == "humn" then solvedAs newVal
		m0.solve newVal
	else if m1.dependsOnHumn or m1.name == "humn" then
		arg0 = m0.evaluate
		if self.op == "+" then
			newVal = forValue - arg0
		else if self.op == "-" then
			newVal = arg0 - forValue
		else if self.op == "*" then
			newVal = forValue / arg0
		else if self.op == "/" then
			newVal = arg0 / forValue
		else
			print "unknown op " + self.op
			exit
		end if
		if m1.name == "humn" then solvedAs newVal
		m1.solve newVal	
	end if
end function
```

This calls a `solvedAs` function that simply prints the result and then `exit`s the program.

The main program — because I observed that it was always the first of the two monkeys under root that depended on `humn` — was just this:

```
m0 = monkeys[monkeys.root.dependsOn[0]]
m1 = monkeys[monkeys.root.dependsOn[1]]
m0.solve m1.evaluate
```

{% spoiler Here's the complete program for Part Two %}
```
import "stringUtil"
import "eval"

if 1 then fname = "input.txt" else fname = "example.txt"
lines = file.readLines(fname)
if not lines[-1] then lines.pop

Monkey = {}
Monkey.value = null
Monkey.op = ""
Monkey.dependsOn = null  // list of 2 monkeys, or null

Monkey.make = function(line)
	m = line.match("{name}: {name1} {op} {name2}")
	if m == null then
		m = line.match("{name}: {value}")
		if m.value == "0" or val(m.value) then
			noob = new Monkey
			noob.name = m.name
			noob.value = val(m.value)
			return noob
		end if
		print "Error: " + line
		exit
	end if
	noob = new Monkey
	noob.name = m.name
	noob.dependsOn = [m.name1, m.name2]
	noob.op = m.op
	return noob
end function
Monkey.dependsOnHumn = function
	if self.dependsOn == null then return false
	if self.dependsOn.contains("humn") then return true
	return monkeys[self.dependsOn[0]].dependsOnHumn or
	  monkeys[self.dependsOn[1]].dependsOnHumn
end function
Monkey.evaluate = function
	if self.value != null then return self.value
	arg0 = monkeys[self.dependsOn[0]].evaluate
	arg1 = monkeys[self.dependsOn[1]].evaluate
	self.value = eval.eval(arg0 + self.op + arg1)
	return self.value
end function
Monkey.solve = function(forValue)
	print "Solving " + self.name + " = " + forValue
	m0 = monkeys[self.dependsOn[0]]; m1 = monkeys[self.dependsOn[1]]
	if m0.dependsOnHumn or m0.name == "humn" then
		arg1 = m1.evaluate
		if self.op == "+" then
			newVal = forValue - arg1
		else if self.op == "-" then
			newVal = forValue + arg1
		else if self.op == "*" then
			newVal = forValue / arg1
		else if self.op == "/" then
			newVal = forValue * arg1
		else
			print "unknown op " + self.op
			exit
		end if
		if m0.name == "humn" then solvedAs newVal
		m0.solve newVal
	else if m1.dependsOnHumn or m1.name == "humn" then
		arg0 = m0.evaluate
		if self.op == "+" then
			newVal = forValue - arg0
		else if self.op == "-" then
			newVal = arg0 - forValue
		else if self.op == "*" then
			newVal = forValue / arg0
		else if self.op == "/" then
			newVal = arg0 / forValue
		else
			print "unknown op " + self.op
			exit
		end if
		if m1.name == "humn" then solvedAs newVal
		m1.solve newVal	
	end if
end function
			
solvedAs = function(solution)
	print "humn must be: " + solution
	exit
end function

monkeys = {}	// key: name; value: monkey

for line in lines
	m = Monkey.make(line)
	monkeys[m.name] = m
end for

pprint monkeys.root
m0 = monkeys[monkeys.root.dependsOn[0]]
m1 = monkeys[monkeys.root.dependsOn[1]]
m0.solve m1.evaluate
```
{% endspoiler %}

## Results & Conclusions

The first part of this program took about 9.5 minutes, for a rank of 678 in the contest; both parts together took a bit under 30 minutes,  for a rank of 545.  I'm content with these times.  MiniScript was, as always, a pleasure to work in, and nothing about it felt like it was slowing me down.  Part Two took me a few minutes of "hmm... how do I do this?"  But since my rank improved substantially between Part 1 and Part 2, it seems that many other contestants had the same reaction!

We're down to only a handful of additional [challenges for the year](https://adventofcode.com/2022).  I'm looking forward to helping the elves accomplish whatever they're doing.  I honestly haven't been paying that much attention to the story, but at some point I will go back and reread them all, as each chapter is entertaining and well-written!