Advent of Code (in MiniScript), Day 21

JoeStrout - Dec 21 '22 - - Dev Community

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
Enter fullscreen mode Exit fullscreen mode

...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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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!

Image
How can I learn JavaScript effectively and practically?
Image
5 Arguments Head Injury Attorneys Near Me Is Actually a Great Thing
Image
15 Secretly Funny People Working In Leg And Arm Injury Attorneys
Image
Stwórz Idealną Oazę Spokoju: Najlepsze Meble do Sypialni na Każdy Styl
Image
This Week's Top Stories About Leg And Arm Injury Attorney Leg And Arm Injury Attorney
Image
This History Behind Filter Coffee Makers Is One That Will Haunt You Forever!
Image
Hiring in the Open - How Companies Can Discover Top Talent via Opire

opensource, webdev, beginners, programming
Image
Crypto Token Development: A Comprehensive Guide
Image
web-site judi slots online paling dipercaya mudah menang
Image
How to Host a Laravel Project in a Subdirectory on Shared Hosting without Exposing `/public` in the URL

beginners, tutorial, programming, python
Image
The illusion of simplicity: how OOP can overcomplicate simple problems

agile, programming, softwareengineering
Image
Yok Singkirkan saat ini pula dan raup keuntungan besarnya dari judi online
Image
Guide To Bi Fold Door Repair: The Intermediate Guide Towards Bi Fold Door Repair
Image
WebSocket: The Backbone of Real-Time Communication in Modern Web Applications

webdev, javascript, node, backend
Image
Scrapper Concorrente

go, scrappe, goroutines
Image
10 Facebook Pages That Are The Best Of All Time Concerning Repair Bifold Door Top Pivot
Image
15 Startling Facts About Asbestos Exposure Claims That You Never Knew
Image
tips menunjuk situs slots online dari penawaran bonusnya
Image
We are seeking a skilled React Native Developer

webdev, react, mobile
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .