Advent of Code (in MiniScript), Day 11
Tags: miniscript, adventofcode, programming
Published: 2022-12-11 14:18:07

Welcome back to my [series](https://dev.to/search?q=JoeStrout%20#adventofcode&sort_by=published_at&sort_direction=asc) of [Advent of Code](https://adventofcode.com/) solutions in [MiniScript](https://miniscript.org)!  In [this challenge](https://adventofcode.com/2022/day/11), 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](https://github.com/JoeStrout/MiniScriptEval) 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](https://github.com/JoeStrout/MiniScriptEval), 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!