Monkey business today!

What is Advent of Code?

In this little series, I want to write about the thought processes I have behind solving the puzzles presented in Advent of Code.

During the Advent of Code small coding puzzles are presented with varying levels of difficulty. They're always Christmas-themed text puzzles where you help elves out of some mess to save the holidays. The puzzles are deliberately ambiguous to not bias puzzlers into a certain solution, they always have an example input in the text to explain some details and an input file for each day that comes in the form of a text file you can download. The solution is a simple number or a string you enter, which is checked by the website automatically. After you finish part 1, part 2 unlocks, which is a variation on part 2. This can be a little twist on part 1 or a large twist that changes the problem formulation into a problem that would take brute force solutions to compute longer than the heat death of the universe would take.

Find my solutions here: github.com/JesperDramsch/advent-of-code

These descriptions won't be a perfect narrative, but rather how I think about these problems and where I see different solutions. I apologise for the possibility of rambling!

The example input

Is this Turing complete? Looks like we're coing to do something terrible here and hopefully avoid eval...

Monkey 0:
  Starting items: 79, 98
  Operation: new = old * 19
  Test: divisible by 23
    If true: throw to monkey 2
    If false: throw to monkey 3

Monkey 1:
  Starting items: 54, 65, 75, 74
  Operation: new = old + 6
  Test: divisible by 19
    If true: throw to monkey 2
    If false: throw to monkey 0

Monkey 2:
  Starting items: 79, 60, 97
  Operation: new = old * old
  Test: divisible by 13
    If true: throw to monkey 1
    If false: throw to monkey 3

Monkey 3:
  Starting items: 74
  Operation: new = old + 3
  Test: divisible by 17
    If true: throw to monkey 0
    If false: throw to monkey 1

The implementation

So this one is another "list of lists" but I actually want to build a Monkey class for this one.

The class needs to keep track of its own items, operation, test, and what happens if the test is true or false.

The items seem to be passed around, so a deque() will do nicely here.

I figured there were more operations than addition and multiplication, but only took a look after I implemented a nice little match-case.

I'm quite proud of what I came up with for the evaluation, using string formatting:

operation = self.operation.replace("old", "{old}").format(old=item)

This replace the "old", however many times it's found with the value of the current item!

After parsing everything, it's just down to playing out the turns:

def turn(self):
    print(self.items)
    while self.items:
        self.inspect_counter += 1
        # Inspect item
        item = self.items.popleft()

        ## Operation
        item = self.worry(item)

        ## Relief
        item //= 3

        # Test item
        if item % self.test_value == 0:
            # If true
            day.data[self.if_true].items.append(item)
        else:
            # If false
            day.data[self.if_false].items.append(item)

Part Deux

The fact that string conversion comes around and bites me is a certain kind of irony...

Python 3.10 has a safety feature to not convert integers with more than 4300 digits to strings anymore.

But regardless, those numbers are getting really big, so just working that out might be interesting.

As the puzzle says beatifulle:

Worry levels are no longer divided by three after each item is inspected; you'll need to find another way to keep your worry levels manageable.

So I was wondering if we can use the fact that each monkey is testing the modulo. Searching for the modulo of multiplication and addition, I ended up on Brillian.

It looks like I can keep the operations separated and apply the modulo piece by piece.

I tried just doing the multiplications first and leaving the additions, but even that exploded, since we have the squaring operation for one monkey unfortunately.

That is also what messes with my head now. I kinda don't want to have this become a nesting operation, and writing this out actually gave me the idea of reducing the calculation on the right for the squaring.

Before I was multiplying the square.

This also ended up as a very large number and failed after a few hundred rounds.

So I needed help. I didn't get to the idea myself, but I should have. I'm pretty sure today wasn't the first day I encountered these modulo shenanigans. I spent way too much time running in the wrong direction. So today I gave up and looked for tips for the first time. Frustrating.

Since it's not my solution, here's the hint that helped me: There is something like a maximum size of the "worry level" that needs to be reached to check if it is divisible by the different monkeys.

Error Log

Here's the error log and of course the fact that part 2 eluded me:

• self.number = int(data[0].split(" ")[1]) NameError: name 'data' is not defined forgot to rename the variable
• self.number = int(text[0].split(" ")[1]) ValueError: invalid literal for int() with base 10: '0:' Overlooked the ":"
• def main(day, part=1): IndentationError: expected an indented block after function definition on line 35 started writing the turn() method, but didn't add pass before working on something different.
• from collection import deque ModuleNotFoundError: No module named 'collection' I can never remember the right name. It's collections
• item //= 3 TypeError: unsupported operand type(s) for //=: 'NoneType' and 'int' looks like I messed something up with the items. Forgot the "new =" in the split of the operation. Also caught that I'm now saving the modified self-operation here.
• operation = self.operation.replace("old", "{old}").format(old=item) ValueError: Exceeds the limit (4300) for integer string conversion; use sys.set_int_max_str_digits() to increase the limit well that's new. Apparently Python cannot convert long ints anymore.
• if sum(remaidners) == 0: NameError: name 'remaidners' is not defined. Did you mean: 'remainders'? Speelink is hart
• item = [sum(item) // 3] TypeError: 'NoneType' object is not iterable tried to return an item.append(...), which is None.
• return [i * int(right) for i in item]TypeError: int() argument must be a string, a bytes-like object or a real number, not 'list' maybe my idea for calculating the modulo arithmetics actually doesn't work out?
• item.append((op, right)) AttributeError: 'int' object has no attribute 'append'
• self.items = deque(deque(self.starting_items)) AttributeError: 'Monkey' object has no attribute 'starting_items' oops. it's just starting_items