JoeStroutWelcome back to my series of Advent of Code solutions in MiniScript! In this challenge, we are tasked with tracking the movement of items (numeric values) as they are tossed around among a set of ornery monkeys.
Each monkey is defined by a section in the input file that looks like this:
Monkey 6:
Starting items: 81, 51, 85
Operation: new = old * old
Test: divisible by 5
If true: throw to monkey 5
If false: throw to monkey 1
The "Starting items" are a list of values, the things that get transformed and passed around. "Operation" is how each monkey transforms a value on its turn; in the example above, the new value is the old value times itself. Other monkeys do things like "old + 7" or "old * 5". The "Test" is always whether the number is divisible by something, and the final two lines indicate the monkey the number is passed to, based on that divisibility.
That "Operation" line is a problem. MiniScript does not have a built-in eval function (though there is a repo for that). If I weren't under time pressure, I'd probably write a very simple expression parser and evaluator that can parse and evaluate A op B, where A and B are either "old" or a number, and op is either '+' or '*'. But this being Advent of Code, I was under time pressure. That seemed like a poor choice.
So, I did what any self-respecting programmer would have done... I cheated.
OK, it's not really cheating. There's nothing in the rules that says you have to write code that reads the input file. So I loaded the input file in my favorite text editor, and manually used search & replace to transform it into valid MiniScript code. The example above became:
m = new Monkey
m.init [81, 51, 85]
m.op = function(old); return old * old; end function
m.divBy = 5
m.ifTrue = 5
m.ifFalse = 1
monkeys.push m
This after I had defined a Monkey class, of course, with the appropriate methods and properties, and a monkeys list to manage them (in retrospect, I probably should have called that barrel instead).
The result was a longer program than usual, but not particularly more difficult than usual. The example input had 4 monkeys, and the real input had 8 (which I transformed separately -- also in retrospect, I should have combined them into one file, transformed them into code all at once, and then split them up again). Here's the final program for Part A:
if 1 then fname = "input.txt" else fname = "example.txt"
Monkey = {}
Monkey.items = null
Monkey.op = null
Monkey.divBy = 1
Monkey.ifTrue = -1
Monkey.ifFalse = -1
Monkey.init = function(items)
self.items = items
end function
Monkey.inspectCount = 0
Monkey.doOneItem = function
if not self.items then return false
item = self.items.pull
self.inspectCount = self.inspectCount + 1
print "monkey " + monkeys.indexOf(self) + " inspects item " + item
item = self.op(item)
print "worry level becomes " + item
item = floor(item/3)
print "monkey gets bored, worry level drops to " + item
if item % self.divBy == 0 then
print "monkey passes to " + self.ifTrue
monkeys[self.ifTrue].items.push item
else
print "monkey passes to " + self.ifFalse
monkeys[self.ifFalse].items.push item
end if
return self.items.len > 0
end function
doOneRound = function
for idx in monkeys.indexes
m = monkeys[idx]
while m.doOneItem; end while
end for
end function
monkeys = []
if fname == "example.txt" then
m = new Monkey
m.init [79,98]
m.op = function(old); return old*19; end function
m.divBy = 23
m.ifTrue = 2
m.ifFalse = 3
monkeys.push m
m = new Monkey
m.init [54, 65, 75, 74]
m.op = function(old); return old + 6; end function
m.divBy = 19
m.ifTrue = 2
m.ifFalse = 0
monkeys.push m
m = new Monkey
m.init [79, 60, 97]
m.op = function(old); return old * old; end function
m.divBy = 13
m.ifTrue = 1
m.ifFalse = 3
monkeys.push m
m = new Monkey
m.init [74]
m.op = function(old); return old + 3; end function
m.divBy = 17
m.ifTrue = 0
m.ifFalse = 1
monkeys.push m
else
m = new Monkey
m.init [83, 97, 95, 67]
m.op = function(old); return old * 19; end function
m.divBy = 17
m.ifTrue = 2
m.ifFalse = 7
monkeys.push m
m = new Monkey
m.init [71, 70, 79, 88, 56, 70]
m.op = function(old); return old + 2; end function
m.divBy = 19
m.ifTrue = 7
m.ifFalse = 0
monkeys.push m
m = new Monkey
m.init [98, 51, 51, 63, 80, 85, 84, 95]
m.op = function(old); return old + 7; end function
m.divBy = 7
m.ifTrue = 4
m.ifFalse = 3
monkeys.push m
m = new Monkey
m.init [77, 90, 82, 80, 79]
m.op = function(old); return old + 1; end function
m.divBy = 11
m.ifTrue = 6
m.ifFalse = 4
monkeys.push m
m = new Monkey
m.init [68]
m.op = function(old); return old * 5; end function
m.divBy = 13
m.ifTrue = 6
m.ifFalse = 5
monkeys.push m
m = new Monkey
m.init [60, 94]
m.op = function(old); return old + 5; end function
m.divBy = 3
m.ifTrue = 1
m.ifFalse = 0
monkeys.push m
m = new Monkey
m.init [81, 51, 85]
m.op = function(old); return old * old; end function
m.divBy = 5
m.ifTrue = 5
m.ifFalse = 1
monkeys.push m
m = new Monkey
m.init [98, 81, 63, 65, 84, 71, 84]
m.op = function(old); return old + 3; end function
m.divBy = 2
m.ifTrue = 2
m.ifFalse = 3
monkeys.push m
end if
for round in range(1,20)
doOneRound
end for
// sort by inspection count
monkeys.sort "inspectCount"
print "Most activity: " + monkeys[-1].inspectCount + ", " + monkeys[-2].inspectCount
print "Monkey business: " + monkeys[-1].inspectCount * monkeys[-2].inspectCount
This produced the right answer.
Part B
In the first part of the challenge, one of the rules was that after each monkey does its operation on the value, we divide it by 3 (rounding down). And we only do 20 rounds of monkey work before computing the answer.
But in part 2, the division by three is removed, and we do 10 thousand rounds. As a result, the numbers blow up. The challenge says "You'll need to find another way to keep your [values] manageable."
I tried running it without finding such a way, and sure enough, the values by the end printed as Infinity (and the monkey business calculation was all wrong on the sample data).
What to do? Well since the tests are always for divisibility, it occurred to me that we could take our values mod something and get the same result. For example, if we're testing for divisibility by 10, we'll get the same answer for 42 as for 142%100, 242%100, 342%100, etc... because 100 (the thing we're modding by) is a multiple of 10 (the thing we're testing for divisibily by).
So, I just looked at the numbers our monkeys were using for divisibility. They were all relatively small prime numbers. I multiplied these together, and got 96577 for the sample monkeys, and 9699690 for the real monkeys. So, where we were dividing by 3 before, we now take the mod of the appropriate number instead. I also took out all the print statements because, at 10000 iterations, that would just take way too long. The new Monkey.doOneItem method looks like this.
Monkey.doOneItem = function
if not self.items then return false
item = self.items.pull
self.inspectCount = self.inspectCount + 1
item = self.op(item)
// item = item % 96577 // for example data
item = item % 9699690 // for real data
if item % self.divBy == 0 then
monkeys[self.ifTrue].items.push item
else
monkeys[self.ifFalse].items.push item
end if
return self.items.len > 0
end function
And, I change the main loop to:
for round in range(1,10000)
doOneRound
if round % 1000 == 0 then
print "Round " + round
for i in monkeys.indexes
print "Monkey " + i + " inspected " + monkeys[i].inspectCount + " times"
end for
end if
end for
This chugged away for a few seconds, printing out its progress every 1000 iterations, ending with:
Round 10000
Monkey 0 inspected 164077 times
Monkey 1 inspected 31322 times
Monkey 2 inspected 124565 times
Monkey 3 inspected 141137 times
Monkey 4 inspected 140371 times
Monkey 5 inspected 140372 times
Monkey 6 inspected 31686 times
Monkey 7 inspected 156713 times
Most activity: 164077, 156713
Monkey business: 25712998901
And this again was the right answer.
Final Thoughts
I felt pretty good about my solution -- time seemed to fly by as I was doing all this, and I never felt like I was spinning my wheels or wasting time. But in the end, Part A took me about 24 minutes, placing 929th. Part A and B together took 29.5 minutes, placing 513th. So not terrible, but certainly not my best.
I went to bed wondering if I made the right choice with converting the input files to code. Should I have parsed it instead? I'm thinking now of making a parser that plucks a value out of a stream of input lines, and advances to the next line, so I could write stuff like:
m = new Monkey
m.init parser.get(" Starting items: {list}")
m.operation = parser.get(" Operation: {str}")
m.divBy = parser.get{" Test: divisible by {n}")
and so forth. With that, it would be almost worth parsing that data. The problem though is still that "operation". I would have had to download and apply that MiniScriptEval package, and I just don't know if I could have done that in less time than it took me to text-edit that stuff into code.
But now that I know Advent of Code is likely to throw such things at us, maybe I'll get that eval package ready, and also make a convenient line-parser as imagined above. Fortune favors the prepared!
