Welcome back to my series of Advent of Code solutions in MiniScript! Last night was 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 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 exits 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
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
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. 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!
Top comments (1)
Merch Monkey provides the tools and resources to bring your vision to life. With a commitment to quality, convenience, and creativity, Merch Monkey has become a trusted partner for individuals and businesses looking to thrive in the competitive world of online merchandising.
Some comments have been hidden by the post's author - find out more