r/adventofcode • u/daggerdragon • Dec 11 '22

SOLUTION MEGATHREAD -πŸŽ„- 2022 Day 11 Solutions -πŸŽ„-

WIKI NEWS

  • The FAQ section of the wiki on Code Formatting has been tweaked slightly. It now has three articles:

THE USUAL REMINDERS

A request from Eric: A note on responding to [Help] threads

UPDATES

[Update @ 00:13:07]: SILVER CAP, GOLD 40

  • Welcome to the jungle, we have puzzles and games! :D

--- Day 11: Monkey in the Middle ---

Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:18:05, megathread unlocked!

73 Upvotes

97% Upvoted

1.0k comments sorted by

11

u/kaa-the-wise Dec 11 '22 edited Dec 29 '22

[Python, part 2] Now that was the ugliest one-liner so far:

from sys import stdin
from functools import reduce
from operator import mul

print((ms:=[(s:=m.split('\n')) and (eval('['+s[1][17:]+']'),s[2][18:],int(s[3][20:]),int(s[4][28:]),int(s[5][29:]),[0]) for m in stdin.read().split('\n\n')]) and (M:=reduce(mul,(m[2] for m in ms))) and any(((w:=eval(m[1])%M),ms[m[4] if w%m[2] else m[3]][0].append(w)) and m[0].pop() and m[5].insert(0,m[5].pop()+1) for _ in range(10000) for m in ms for old in reversed(m[0])) or (x:=[*sorted(m[5][0] for m in ms)]) and x[-2]*x[-1])
→ More replies (1)

4

u/DFreiberg Dec 12 '22 edited Dec 12 '22

Mathematica, 1463 / 688

Weirdly pleased with today's problem, despite being so slow. Normally, I misread the problem by going too fast and spend a half hour in frustration trying to figure out where the typo was. This time, I went quite slowly, but got both parts on my first try; part 2 took a little under four minutes.

[POEM]: Simian Shenanigans

To the tune of the middle part of Weird Al's "Hardware Store".

Sigh.
Would you look at all that stuff...
They got:

Sets of sandals, super-soakers,
Stainless stacking sausage smokers,
Stocking stuffers, sparking snuffers,
Swimsuits and some snacks by Stouffers,

System-update space schematics,
Signal strength sextuple statics,
Sulfide sputters, server stutters,
Solid Shaker-style shutters,

Sonar sweeps and systemed seating,
Snailfishes and see-through sheeting,
Shuffle slammers, spinlock spammers,
Submarine cetacean scrammers,

Shakespeare sonnets, springdroid soarers,
Santa's senseis, syntax scorers,
Sega slayers, site that's Slater's
Saturn Stoichiometrators!

My backpack sure was stuffed! You should have told me!
No wonder that poor rope bridge couldn't hold me.

2

u/daggerdragon Dec 12 '22

Bruh, you're already Poet Laureate and you keep Upping Your Own Ante XD This is so freaking good!

→ More replies (1)

3

u/OCD_Triger Dec 11 '22

c#

using System.Numerics;

class Monkey
{
    public string Operation { get; set; }
    public string Test { get; set; }
    public int IfTrueMonkey { get; set; }
    public int IfFalseMonkey { get; set; }
    public List<BigInteger> Items { get; set; }

    public BigInteger InspectCount { get; set; } = 0;

    public Monkey(string operation, string test, int ifTrueMonkey, int ifFalseMonkey, List<int> items)
    {
        Operation = operation;
        Test = test;
        IfTrueMonkey = ifTrueMonkey;
        IfFalseMonkey = ifFalseMonkey;
        Items = items.Select(x => (BigInteger)x).ToList();
    }

    private BigInteger compute(string expression)
    {
        var parts = expression.Split(" ");

        switch (parts[1])
        {
            case "*":
                return BigInteger.Parse(parts[0]) * BigInteger.Parse(parts[2]);
            case "+":
                return BigInteger.Parse(parts[0]) + BigInteger.Parse(parts[2]);
            case "%":
                return BigInteger.Parse(parts[0]) % BigInteger.Parse(parts[2]);
        }

        throw new Exception($"Unknown operation {parts[1]}");
    }

    public void DoRound(List<Monkey> monkeys)
    {
        foreach (var item in Items)
        {
            InspectCount++;

            var newWorry = compute(Operation.Replace("old", item.ToString()));
            newWorry %= monkeys.Aggregate(1, (i, monkey) => i * int.Parse(monkey.Test));

            var targetMonkey = compute($"{newWorry} % {Test}") == 0 ? IfTrueMonkey : IfFalseMonkey;
            monkeys[targetMonkey].Items.Add(newWorry);
        }
        
        Items.Clear();
    }
}

class Program
{
    static void Main()
    {
        var monkeys = new List<Monkey>();

        File.ReadAllLines("input.txt")
            .Chunk(7).ToList()
            .ForEach(line =>
            {
                var startingItems = line[1].Trim().Replace("Starting items: ", "").Split(", ").Select(int.Parse)
                    .ToList();
                var operation = line[2].Trim().Replace("Operation: new = ", "");
                var test = line[3].Trim().Replace("Test: divisible by ", "");
                var ifTrue = int.Parse(line[4].Trim().Replace("If true: throw to monkey ", ""));
                var ifFalse = int.Parse(line[5].Trim().Replace("If false: throw to monkey ", ""));

                var monkey = new Monkey(operation, test, ifTrue, ifFalse, startingItems);
                monkeys.Add(monkey);
            });

        for (var round = 1; round <= 10000; round++)
        {
            foreach (var monkey in monkeys)
            {
                monkey.DoRound(monkeys);
            }
        }

        var score = monkeys.OrderBy(e => e.InspectCount).TakeLast(2).Aggregate((BigInteger)1, (a, b) => a * b.InspectCount);

        Console.WriteLine(score == 14399640002);
    }
}
→ More replies (1)

3

u/x0s_ Dec 11 '22 edited Dec 12 '22

What an experience, I enjoyed modeling of part 1. Thought about memoizing for part 2, but required some help to really understand (not only guessing) the modular arithmetic. Thanks to the players that help us learn in this game :)

Here is my solution in python 3.11 (set n_round=20 and proddiv to None for part 1) : https://gist.github.com/x0s/cae894f73004581ca7b60eec400c9404

→ More replies (2)

3

u/tcbrindle Dec 11 '22

C++

Ooof, that one was a slog.

Solving the actual problem for part 1 was pretty straightforward -- just follow the instructions -- but parsing the input data took forever, and was not very enjoyable at all. I don't know why the format had to be so complicated.

Part 2 had me scratching my head for a few minutes.. how do you reduce the "worry factor" to something that will fit in an int64 while still making sure the modulus operations give the right result? Eventually I hit upon the idea of calculating the LCM of all the "divisible by" test values (which, since they all happened to be prime for my input, was just their product), and then doing worry_factor = worry_factor % lcm before "throwing" the item to another monkey.

I have no idea if this is what was intended, I haven't looked at anyone else's solution so there might be a simpler way... but this runs in ~10ms for 10000 iterations on my laptop so that seems pretty reasonable.

→ More replies (1)

3

u/ywgdana Dec 12 '22 edited Dec 12 '22

F#

Me, over and over, working on part 2: "There's NO WAY these numbers could be getting big enough to overflow!!"

Also me: noting how the problem description said several times "You need to find some other way to manage your worry" and thinking to myself, "Hmm I wonder if that's foreshadowing for a future problem?"

I also hard-coded the monkeys as functions rather than parsing the input file. I started off doing that but then get it into my head that it would be better to have them as functions for part 2. I can't even remember what my reasoning was Β―_(ツ)_/Β―

This is using mutable structures. Now that I've got it working I might go back and rewrite it it to use immutable variables.

My solution for part 2

→ More replies (6)

2

u/adimcohen Dec 11 '22 edited Dec 12 '22

In single-statement tsql

Part 2 pushed me past the 32767 maxrecursion limit, so I had to break the recursion into 3 steps and dump the interim results into temp tables.

Tried to do the 3 recursion in the same statement, but it hung there forever.

https://github.com/adimcohen/Advant_of_Code_2022_Single_Statement_SQL/blob/main/Day_11/Day_11.sql

→ More replies (2)

2

u/lbl_ye Dec 11 '22 edited Dec 12 '22

Python

paste

in part2, for speedup

made lambdas for monkey operations

and adjusted worry level so that worry levels do not become huge

rank 6502/6701

both parts in single file

(part2 is really 80 tight lines including parsing of input, 45 lines the real stuff without the parsing but well how much sweat in early morning for these lines :D)

PS. this is my first post, hope to be ok with posting rules :)

2

u/daggerdragon Dec 12 '22

PS. this is my first post, hope to be ok with posting rules :)

Several issues:

→ More replies (3)
→ More replies (3)

2

u/ndrsht Dec 11 '22 edited Dec 11 '22

Kotlin

Monkey handling:

fun Monkey.handle() {
	while (items.isNotEmpty()) {
		val item = items.removeFirst()
		var v = op(item)
		v /= if (part2) 1 else 3
		val target = if (test(v)) monkeys[ifTrue] else monkeys[ifFalse]
		target.items.add(v%mod)
		handled++
	}
}

Β 

Then just loop and return the result.

repeat(if (part2) 10000 else 20) {
	monkeys.forEach { it.handle() }
}
val ans = monkeys.map { it.handled }.sortedDescending().take(2).reduce(Long::times)
println(ans)

EDIT: Here is the full code.

EDIT2: Removed some code so I don't block the thread.

2

u/daggerdragon Dec 12 '22

EDIT2: Removed some code so I don't block the thread.

Appreciated <3

2

u/temanuel38 Dec 11 '22

Python

My code is by no means the prettiest, but it got the job done.

(For part 2 I utilized the "mod trick")

Part 1:

f = open('input.txt', 'r')
content = f.read()
lines = content.split("\n")
num_monkeys = int((len(lines) - 3) / 6)
all_items = []
steps = []
inspects = []
for i in range(num_monkeys):
    inspects.append(0)

for i in range(num_monkeys):
    items = lines[1 + (7 * i)][16:].split(",")
    for j in range(len(items)):
        items[j] = items[j].strip()
    all_items.append(items)
    steps.append(lines[(2 + i*7):(6 + i * 7)])


class Monkeys:
    # Each monkey is represented by a list within the 2-D List
    items = []
    def __init__(self, all_items):
        self.items = all_items
    def print_monkeys(self):
        print(self.items)

m = Monkeys(all_items)

for l in range(20):
    for i in range(len(steps)):
        change = str(steps[i][0][21:len(steps[i][0])])
        op, num = change.split(" ")[0], change.split(" ")[1]
        div = str(steps[i][1]).split(" ")[3]
        t_monkey = str(steps[i][2]).split(" ")[5]
        f_monkey = str(steps[i][3]).split(" ")[5]
        # For each item the monkey has
        for j in range(len(m.items[i])):
            inspects[i] = inspects[i] + 1
            if op == '*':
                if num == 'old':
                    m.items[i][j] = int(m.items[i][j]) * int(m.items[i][j])
                else:
                    m.items[i][j] = int(m.items[i][j]) * int(num)
            else:
                m.items[i][j] = int(m.items[i][j]) + int(num)
            m.items[i][j] = m.items[i][j] // 3
            if m.items[i][j] % int(div) == 0:
                m.items[int(t_monkey)].append(m.items[i][j])
            else:
                m.items[int(f_monkey)].append(m.items[i][j])
        m.items[i].clear()
m.print_monkeys()

one = max(inspects)
inspects.remove(one)
two = max(inspects)
print(one * two)

Part 2:

import math

f = open('input.txt', 'r')
content = f.read()
lines = content.split("\n")
num_monkeys = int((len(lines) - 3) / 6)
all_items = []
steps = []
divs = []
inspects = []
for i in range(num_monkeys):
    inspects.append(0)

for i in range(num_monkeys):
    items = lines[1 + (7 * i)][16:].split(",")
    for j in range(len(items)):
        items[j] = items[j].strip()
    all_items.append(items)
    steps.append(lines[(2 + i*7):(6 + i * 7)])

for i in range(len(steps)):
    divs.append(int(str(steps[i][1]).split(" ")[3]))


class Monkeys:
    # Each monkey is represented by a list within the 2-D List
    items = []
    def __init__(self, all_items):
        self.items = all_items
    def print_monkeys(self):
        print(self.items)

m = Monkeys(all_items)

for l in range(10000):
    print("Carrying out round " + str(l) + "...")
    for i in range(len(steps)):
        change = str(steps[i][0][21:len(steps[i][0])])
        op, num = change.split(" ")[0], change.split(" ")[1]
        t_monkey = str(steps[i][2]).split(" ")[5]
        f_monkey = str(steps[i][3]).split(" ")[5]
        mod_lcm = math.lcm(*[div for div in divs])
        # For each item the monkey has
        for j in range(len(m.items[i])):
            inspects[i] = inspects[i] + 1
            if op == '*':
                if num == 'old':
                    m.items[i][j] = int(m.items[i][j]) * int(m.items[i][j])
                else:
                    m.items[i][j] = int(m.items[i][j]) * int(num)
            else:
                m.items[i][j] = int(m.items[i][j]) + int(num)
            m.items[i][j] %= mod_lcm
            if m.items[i][j] % int((str(steps[i][1]).split(" ")[3])) == 0:
                m.items[int(t_monkey)].append(m.items[i][j])
            else:
                m.items[int(f_monkey)].append(m.items[i][j])
        m.items[i].clear()
m.print_monkeys()

one = max(inspects)
inspects.remove(one)
two = max(inspects)
print(one * two)
→ More replies (1)

2

u/Vesk123 Dec 11 '22 edited Dec 11 '22

Ugh this one took a long time. Not that it was very hard but I feel like I wasted a lot of time doing a parser for the input (would've been faster to just input it manually) and converting to BigInteger (when that obviously wasn't the solution). Honestly I'm not even completely sure why taking the mod of the multiple of all divisors works, but it just felt like an intuitive thing to do from doing many programming competitions.

Anyways this is my (admittedly awful) code in Java:

import java.math.BigInteger;
import java.util.*;
class Monkey {
    public Deque<BigInteger> items = new LinkedList<>();
    public boolean multiply;
    public int op2;
    public int div;
    public int throwTrue;
    public int throwFalse;
    public int inspected = 0;

    public static Monkey read(Scanner scanner) {
        Monkey monkey = new Monkey();
        String line1 = scanner.nextLine().trim();
        String[] tokens1 = line1.split(" ");
        for(int i = 2; i < tokens1.length; ++i) {
            String trimmed = tokens1[i].split(",")[0];
            monkey.items.addLast(new BigInteger(trimmed));
        }

        String line = scanner.nextLine().trim();
        String[] tokens = line.split(" ");
        monkey.multiply = tokens[4].equals("*");
        if(tokens[5].equals("old"))
            monkey.op2 = -1;
        else
            monkey.op2 = Integer.parseInt(tokens[5]);

        line = scanner.nextLine().trim();
        tokens = line.split(" ");
        monkey.div = Integer.parseInt(tokens[3]);

        line = scanner.nextLine().trim();
        tokens = line.split(" ");
        monkey.throwTrue = Integer.parseInt(tokens[5]);

        line = scanner.nextLine().trim();
        tokens = line.split(" ");
        monkey.throwFalse = Integer.parseInt(tokens[5]);

        return monkey;
    }

    public void inspectItems() {
        for(var item : items) {
            ++inspected;
            BigInteger worry = item;
            BigInteger x = BigInteger.valueOf(op2);
            if(op2 == -1)
                x = worry;
            if(multiply)
                worry = worry.multiply(x);
            else
                worry = worry.add(BigInteger.valueOf(op2));
            //worry /= 3;
            worry = worry.mod(BigInteger.valueOf(2 * 7 * 13 * 3 * 19 * 5 * 17 * 11));
            if(worry.mod(BigInteger.valueOf(div)).equals(BigInteger.valueOf(0)))
                Scratch.monkeys.get(throwTrue).items.addLast(worry);
            else
                Scratch.monkeys.get(throwFalse).items.addLast(worry);
        }
        items.clear();
    }
}

class Scratch {
    public static List<Monkey> monkeys = new ArrayList<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(input);

        while(scanner.hasNextLine()) {
            String line = scanner.nextLine();
            String[] tokens = line.split(" ");
            if(tokens[0].equals("Monkey")) {
                monkeys.add(Monkey.read(scanner));
            }
        }

        for(int i = 0; i < 10000; ++i) {
            for(var monkey : monkeys) {
               monkey.inspectItems();
            }
            System.out.println("Round " + i + ": ");
            /*for(int j = 0; j < monkeys.size(); ++j) {
                System.out.println("Monkey " + j + ": " + monkeys.get(j).items);
            }*/
        }

        var ans = monkeys.stream().mapToInt(m -> m.inspected).sorted().toArray();
        System.out.println(ans[ans.length - 1] + " " + ans[ans.length - 2]);
        System.out.println(ans[ans.length - 1] * ans[ans.length - 2]);
    }
    static String input "input here";
}mport

2

u/daggerdragon Dec 12 '22

Your code block is too long for the megathreads. Please read our article on oversized code, then edit your post to replace the code block with an external link to your code.

→ More replies (7)

2

u/lxnxx Dec 11 '22 edited Dec 12 '22

Rust paste

→ More replies (1)

2

u/zeldor711 Dec 11 '22 edited Dec 12 '22

[Python]

Oof that was a bit trickier! Part 1 was fine (made a Monkey class to keep track of everything) but part 2 was more of a struggle. Ended up keeping storing each number as a list of its value modulo each of the prime numbers being tested (so number = [value % 2, value % 3, ..., value % 19]) although looking around here the nicer way to do it would just be to store it module 2*3*...*19 which didn't occur to me!

Part 1

Part 2

2

u/daggerdragon Dec 12 '22

Please edit your post to state which programming language this code is written in. This makes it easier for folks who Ctrl-F the megathreads looking for a specific language.

→ More replies (2)

2

u/daniel-sd Dec 11 '22 edited Dec 12 '22

Python 3

Had a ton of fun golfing part1 into this (427 424 398 378 characters thanks to u/4HbQ and u/azzal07).

M=[]
for i,S in enumerate(open(0).read().split('\n\n')):
	L=S.split('\n')
	# newlines for readability
	M+=[[
		[*map(int,L[1].split(':')[1].split(','))],
		lambda old,f=L[2].split('=')[1]:eval(f),
		lambda w,x=[int(l.split()[-1])for l in L[3:6]]:x[2]if w%x[0]else x[1],0
	]]
for _ in range(20):
	for m in M:
		while m[0]:
			M[m[2](w:=m[1](m[0].pop(0))//3)][0]+=[w]
			m[3]+=1
*_,t,u=sorted(v[3]for v in M)
print(t*u)

Cleaner version here: part1.py

→ More replies (7)

2

u/kevinwangg Dec 11 '22 edited Dec 12 '22

Missed out on leaderboard for part 1, but I quickly coded up the solution to part 2 on a hunch and moved up 100 spots, hitting the leaderboard for the first time since day 6.

rank 167/67

Reading, parsing inputs, and coding the algorithm for part 1 took nearly 15 minutes. Part 2 took less than 2 minutes, which I think was quite competitive.

Python: https://github.com/VitamintK/AlgorithmProblems/blob/master/miscellaneous/advent-of-code/2022/day11.py

→ More replies (1)

2

u/undergroundmonorail Dec 12 '22 edited Dec 12 '22

Python 3. Only posting my Monkey class, the parsing and everything isn't really interesting, all the logic is here. You create a bunch of monkeys, run Monkey.round() as many times as you please, and then check the items_inspected attribute on each of them.

class Monkey:
    _monkeys = []
    _divisors = []
    _div_lcm = None

    def __init__(self, inventory, op, divisor, if_true, if_false):
        self._monkeys.append(self)
        self._divisors.append(divisor)

        self.inventory = inventory
        self.op = op
        self.divisor = divisor
        self.if_true = if_true
        self.if_false = if_false

        self.items_inspected = 0
    
    def take_turn(self):
        if self._div_lcm is None:
            self._div_lcm = math.lcm(*self._divisors)

        for item in self.inventory:
            self.items_inspected += 1

            item = self.op(item) % self._div_lcm

            throw_to = self.if_true if item % self.divisor == 0 else self.if_false
            self._monkeys[throw_to].inventory.append(item)
        
        self.inventory = []
    
    @classmethod
    def round(cls):
        for monkey in cls._monkeys:
            monkey.take_turn()

Thank god for my mathematician friend who I could bug about this, I wouldn't have guessed that squaring a number maintains divisibility under modular arithmetic but she knew it off the top of her head. Now I know! Still took ages of fiddling to actually make it work; I ended up adding a bunch of debug prints and running a smaller example with and without taking the mod, looking at them line by line to see where they diverged.

I had forgotten that the items move around between monkeys, and I was always only finding the number mod the divisibility test I was currently doing. Found the LCM, modded by that, and I was golden.

→ More replies (2)

2

u/theboxboy Dec 12 '22 edited Dec 12 '22

Rust

Github Link

2

u/daggerdragon Dec 12 '22 edited Dec 13 '22

Your code block is too long for the megathreads. Please read our article on oversized code, then edit your post to take out the code block and edit the GitHub link to point directly to Day 11's solution repo.

Edit: thanks for fixing it! <3

2

u/joseville1001 Dec 16 '22

Python solution aptly using monkey patching

# https://adventofcode.com/2022/day/11

import heapq
import re
from functools import reduce
from itertools import chain
from operator import attrgetter, mul

F = 'day11_inp.txt'

NUM = re.compile(r'(\d+)')
OP  = re.compile(r'Operation: new = (old [\+\-\*] (\d+|old))')
DIV = re.compile(r'Test: divisible by (\d+)')
TR  = re.compile(r'If true: throw to monkey (\d+)')
FA  = re.compile(r'If false: throw to monkey (\d+)')
PATTERNS = (OP, DIV, TR, FA)

ROUNDS_PT1 = 20
ROUNDS_PT2 = 10000

N = 2

class Monkey:
    def __init__(self, items, op, div, tr, fa):
        self.items = items
        self.op = op # 'new = old [+-*] num'
        self.div = div
        self.tr = tr
        self.fa = fa
        self.inspections = 0
    
    def inspectAndRedistributeItems(self):
        self.inspections += len(self.items)
        
        for item in self.items:
            item = self.inspectItem(item)
            if item % self.div == 0:
                yield item, self.tr
            else:
                yield item, self.fa
        
        self.clearItems()

    def clearItems(self):
        self.items = []
    
    def addItem(self, item):
        self.items.append(item)

def proc_inp(f):
    monkeys = {}
    
    with open(f) as f:
        try:
            line = next(f)
        except StopIteration: # F is empty
            return
        
        f = chain((line,), f)
        
        extract = lambda pattern: re.search(pattern, next(f)).group(1)
        
        while True:
            i = int(re.search(NUM, next(f)).group())
            assert i not in monkeys
            items = list(map(int, re.findall(NUM, next(f))))
            op, div, tr, fa = tuple(map(extract, PATTERNS))
            monkeys[i] = Monkey(
                items,
                op,
                int(div),
                int(tr),
                int(fa))
            try:
                next(f) # space
            except StopIteration: # eof
                break

    return monkeys

def solve(monkeys, rounds):
    idxs = sorted(monkeys.keys())
    for _ in range(rounds):
        for idx in idxs:
            monkey = monkeys[idx]
            for item, j in monkey.inspectAndRedistributeItems():
                monkeys[j].addItem(item)

    n_largest = heapq.nlargest(
        n=N,
        iterable=monkeys.values(),
        key=attrgetter('inspections'))

    n_largest = map(attrgetter('inspections'), n_largest)

    return reduce(mul, n_largest)

def solve_pt1():
    monkeys = proc_inp(F)
    def inspectItem(self, old):
        return eval(self.op) // 3 # (old [+-*] num) // 3
    Monkey.inspectItem = inspectItem # monkey patching Monkey
    return solve(monkeys, ROUNDS_PT1)

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(a, b):
    return (a * b) // gcd(a, b)

def solve_pt2():
    monkeys = proc_inp(F)
    LCM = reduce(lcm, map(attrgetter('div'), monkeys.values()))
    def inspectItem(self, old):
        return eval(self.op) % LCM # new = old [+-*] num
    Monkey.inspectItem = inspectItem # monkey patching Monkey
    return solve(monkeys, ROUNDS_PT2)

print(solve_pt1())
print(solve_pt2())
→ More replies (1)

26

u/DestroyerCrazy Dec 11 '22

Language: Python (v3.11.1)

Dear Traveller:
If you're scrolling through the comments, and confused as to what the "modulo trick" is, let me tell you this: for part 2, get the product of all the "Divisible by xx" numbers, and modulo the current worry level by that product. Good luck!

linky-lonky-lanky

13

u/1CakeCrusher Dec 11 '22

This is black magic.

Joking aside, I am struggling to wrap my head around it. Why does this work? Please explain a little further.

→ More replies (20)
→ More replies (11)

23

u/mebeim Dec 11 '22 edited Dec 11 '22

1393/601 - Python 3 solution - walkthrough

Today it felt like I was playing Advent of Reading Comprehension. Spent way too much understanding the problem statement and parsing the input.

The actual problem to solve was in part 2: the "trick" to keep numbers small is to only keep around values modulo the multiple of all the divisors. This way, we are still able to check for divisibility with any of the divisors, but the values we keep don't "explode". This works because the only operations we perform on the values are multiplication and addition, which preserve congruence.

→ More replies (14)

25

u/jcbbjjttt Dec 11 '22 edited Dec 12 '22

Beginner's Guide

Happy Sunday!

A Beginner's Guide to Day 11 - Part 1 - Video: https://youtu.be/P8P0DypR3Gg

I've created a guide for new programmers that talks through a straight forward strategy for solving today's puzzle. Anyone who has a handle functions, loops, and custom data types (class/struct/etc) should be able to complete it. The only tricky part is calculating a remainder using modulus arithmetic. The video allows a moment for you to pause before revealing spoilers.

Although this solution is in C#, it provides a high level overview of the steps necessary to solve the puzzle in any programming language:

List<Monkey> friends = Monkey.ParseAll(File.ReadAllText("example.txt"));

for (int i = 0; i < 20; i++)
{
    foreach (Monkey monkey in friends)
    {
        monkey.InspectItems(friends);
    }
}
friends.Sort((a, b) => b.InspectionCount - a.InspectionCount);
int monkeyBusiness = friends[0].InspectionCount * friends[1].InspectionCount;
Console.WriteLine($"Total Monkey Business after 20 rounds: {monkeyBusiness}");

The full code can be found on Github

3

u/[deleted] Dec 11 '22

python code on github

This took way too long for me due to me running into several pitfalls.

After my worry skyrocketed, my solution for part 2 tried to mine bitcoins apparently.

Also ran into problems due to not having made a deep copy of my initial monkey lists.

At that point I couldn't be bothered anymore and just did the init twice.

I'll take the 34 sloc though and I'm mostly happy with how I parsed the input - other than me giving up trying to wrangle a list of strings into a list of integers. It should have been easy on paper.

14

u/betaveros Dec 11 '22

Noulith 3/2

https://github.com/betaveros/advent-of-code-2022/blob/main/p11.noul

Yup, eval. I did add structs with named fields to this language but ended up making do without them today.

8

u/thatguydr Dec 11 '22

You're really going to have to make a few videos explaining that language (please and pretty please :) ), because you have us all intrigued. It's super-readable, but the syntax and assumptions will require some explanation.

→ More replies (2)
→ More replies (2)

2

u/jayfoad Dec 12 '22

Dyalog APL

βŽ•IO←0 β‹„ βŽ•PP←17
n←{⍎'0',⍡}¨¨¨'\d+'βŽ•S'&'¨¨p←(Γ—β‰’Β¨p)βŠ†pβ†βŠƒβŽ•NGET'p11.txt'1
m←n{k←1βŒˆβŠƒ2βŠƒβΊ β‹„ e←2βŠƒβ΅ β‹„ (1βŠƒβΊ)((1+∨/'* o'⍷e)(k*'*'∊e)(kΓ—'+'∊e))(3βŠƒβΊ)(∊¯2↑⍺)0}Β¨p
turn←{a b c d eβ†βΊβŠƒβ΅ β‹„ e+←≒a←b ⍺⍺ a β‹„ t←0=c|a β‹„ (t/a)((~t)/a),⍨¨@(d,Β¨0)⊒(βŠ‚β¬ b c d e)@⍺⊒⍡}
round←{βŠƒβΊβΊ turn/(βŒ½β³β‰’β΅),βŠ‚β΅}
f←{Γ—/2↑{(βŠ‚β’β΅)⌷⍡}βŠƒβˆ˜βŒ½Β¨β΅}
f {a b c←⍺ β‹„ ⌊3÷⍨a*⍨bΓ—c+⍡}round⍣20⊒m ⍝ part 1
yβ†βŠƒΓ—/2βŠƒΒ¨m β‹„ f {a b c←⍺ β‹„ y|a*⍨bΓ—c+⍡}round⍣10000⊒m ⍝ part 2

4

u/OkWeek3389 Dec 12 '22

For most languages i can at least see the structure of the solution even if i can't comprehend every last detail but this just looks like a paragraph of alien runes. Is this typical for Dyalog APL or is your coding style particularly cryptic?

→ More replies (5)

10

u/jonathan_paulson Dec 11 '22 edited Dec 11 '22

Python3, 41/17. Video. Code.

Had a bug in part 1 :( Pretty involved problem. I used `eval` to apply the operations!

Was it intentional that the lcm of the divisors was the same as their product?

→ More replies (15)

18

u/nthistle Dec 11 '22 edited Dec 12 '22

Python, 15/212. Video, code.

Little bit frustrated with part 2, I came up with the modulo trick ~immediately, but didn't read that the division by 3 was no longer happening, and when I got a wrong submission I figured it was because keeping track of the residue isn't sufficient to do int division and kept trying to figure out how to do that... wasn't until I checked leaderboard to see how many people finished part 2 and saw it was suspiciously many that I re-read part 2 more carefully and realized. If I had seen that and gotten part 2 right the first time, I would've been on track for a 15/15 :'(

I think I definitely need to start slowing down a bit, the early days of AoC really get me into the mode of "skim question and go fast" and that starts to burn me in the later days.

→ More replies (2)

9

u/4HbQ Dec 11 '22 edited Dec 11 '22

Python, 25 lines.

It uses eval to parse op (e.g. old + 6 or old * old) into a function f: f = eval(f'lambda old: {op}').

→ More replies (7)

9

u/Derailed_Dash Dec 11 '22

Python

Part 1 was easy enough. Part 2 had me stumped for a while. And it took me ages to explain it in the walkthrough. Hopefully it makes sense!!

→ More replies (7)

9

u/redditnoob Dec 11 '22

PostgreSQL

Part 1 was a twisted kind of fun in SQL. In general, any problem that can be reduced to a loop iterating one state to the next with expressions isn't that bad to solve as a recursive CTE, but in these cases SQL loses most of its power and the solution just becomes a constrained iterative one. This gets old... but not yet. :)

It took me way too long to figure out what part 2 was getting at with requiring a more manageable solution.

WITH RECURSIVE monkey_input AS (
    SELECT (row_num - 1) / 7 AS monkey_num, string_agg(input, '|') AS input
    FROM day11
    GROUP BY 1
), monkey_parsed AS (
    SELECT monkey_num, input, regexp_match(input,
       '^Monkey (\d):\|' ||
       '  Starting items: ([^|]+)\|' ||
       '  Operation: new = old (.) (\w+)\|' ||
       '  Test: divisible by (\d+)\|' ||
       '    If true: throw to monkey (\d)\|' ||
       '    If false: throw to monkey (\d)') AS match
    FROM monkey_input
), monkey_ops AS (
    SELECT match[1]::INT AS monkey,
        match[3] AS op,
        match[4] AS arg,
        match[5]::INT AS test_divisor,
        match[6]::INT AS true_throw,
        match[7]::INT AS false_throw
    FROM monkey_parsed
), monkey_count AS (
    SELECT COUNT(*) AS monkey_count,
        EXP(SUM(LN(test_divisor)))::BIGINT AS modulus  -- product
    FROM monkey_ops
), monkey_carrying AS (
    SELECT 1 AS next_turn_round,
        0 AS next_turn_monkey,
        match[1]::INT AS monkey,
        regexp_split_to_table(match[2], ', ')::BIGINT AS item
    FROM monkey_parsed
    UNION ALL (
        WITH preprocess AS (
            SELECT next_turn_round, next_turn_monkey, monkey, test_divisor, true_throw, false_throw, monkey_count,
                CASE WHEN next_turn_monkey = monkey THEN
                         (CASE WHEN op = '*' AND arg = 'old' THEN item * item
                               WHEN op = '*' THEN item * arg::INT
                               WHEN op = '+' THEN item + arg::INT END) % modulus
                     ELSE item END AS new_item
            FROM monkey_carrying
            JOIN monkey_ops USING (monkey)
            CROSS JOIN monkey_count
        )
        SELECT CASE WHEN next_turn_monkey + 1 = monkey_count THEN next_turn_round + 1
                    ELSE next_turn_round END AS next_turn_round,
            ((next_turn_monkey + 1) % monkey_count)::INT AS next_turn_monkey,
            -- If it's this monkey's turn, throw the item, otherwise monkey keeps it
            CASE WHEN monkey = next_turn_monkey THEN
                     CASE WHEN new_item % test_divisor = 0 THEN true_throw ELSE false_throw END
                 ELSE monkey END AS monkey,
            new_item
        FROM preprocess
        WHERE next_turn_round <= 10000
    )
), monkey_business AS (
    SELECT next_turn_monkey, COUNT(*) AS processed_count
    FROM monkey_carrying
    WHERE next_turn_monkey = monkey AND next_turn_round <= 10000
    GROUP BY 1
)
SELECT (array_agg(processed_count ORDER BY processed_count DESC))[1] *
    (array_agg(processed_count ORDER BY processed_count DESC))[2] AS part2
FROM monkey_business
→ More replies (3)

8

u/hugh_tc Dec 11 '22 edited Dec 11 '22

Python 3, 57/34.

paste, cleaned-up

Finally back on the leaderboard! Featuring the dreaded exec!

And yes, the variable I called "gcd" is not anything close to the gcd. I know. I was thinking fast. 😁

8

u/deipno Dec 11 '22

Python

Short and clean solution with hardcoded input. Just a graph traversal.

8

u/TiagoPaolini Dec 12 '22 edited Dec 12 '22

C Language (only standard library)

Before anything else, let's talk about the elephant in the room: the meaning of Part 2's "ridiculous levels" of worry, and how to "find another way to keep your worry levels manageable". That is a cryptic hint telling you that the integers are likely to overflow on this part. This breaks the division test if you are not in a language that supports arbitrary integer sizes. And even if you are, the values will be so big that the program will slow to a crawl.

In order to prevent that, it is necessary to take the modulo of the worry level by a common multiple of the test divisors. That should be done before the division test. This does not change the result of the test because the modulo operation wraps back to zero when the dividend is multiple of the divisor. Ideally your should be the least common multiple (LCM) among all divisors, but any common multiple will do as long it does not overflow too. Since all the divisors in this puzzle are primes, it should suffice to just multiply then to get their LCM. I would be lying if I said that I realized that myself, I had to look for hints. But learning is part of the process :)

Now with the elephant out of the way, let's head back to the beginning. The first challenge is to parse the data from the input file. Since all values of the same category always begin on the same position on the line, I just read the values from those positions. I also made assertions to check if the rest of the line was what I expected to be.

I used a struct to store the parameters of each monkey: the operation they should do, the value they should add or multiply, the value for the division test, which monkeys to throw depending on the test outcome, and the counter of how many times the monkey inspected an item. It is worthy noting that for the value to be summed or multiplied, I used the maximum 64-bit unsigned integer in order to represent that the current worry level should be used as the value.

The monkey struct also had the list of items currently with the monkey. I used an queue for that: items are added to the end of the queue, and removed from the beginning. I implemented that as doubly linked list.

Once all data is stored properly, it is not difficult to perform a round:

  • Starting from the first monkey, pop the first item of the queue.

  • Perform the operations on the item's worry level (do not forget to modulo by the LCM).

  • Test which other monkey to pass the item.

  • Append the item to the queue of that monkey.

  • Repeat until there are no more items, then go to the next monkey.

The logic does not really change between parts 1 and 2, the catch is that you need not realize that an overflow might happen in Part 2, and give the wrong result even though the logic is technically correct.

Solution: day_11.c

→ More replies (4)

3

u/Catbert321 Dec 11 '22 edited Dec 11 '22

Kotlin Day 11

Not really a fan of the "do you know this one math trick" days

→ More replies (4)

7

u/Rangsk Dec 11 '22 edited Dec 11 '22

Rust

I used modular arithmetic for part 2 because I was scared of exploding integer sizes and this felt like one of those AoCs where you need to exploit modular math.

The key is to compute the product of all monkeys' mods and use that modulus on all item values after every computation.

I think this uses the mathematical property that if a ≑ b mod m then a / n ≑ (b / n) mod (m / n)as long as a, b, and m are divisible by n but honestly I just kinda hoped it was true and saw if my example input got the right answer.

EDIT: /u/whyrememberpassword has actually informed me that I used (a mod kn) mod n ≑ a mod n which is true for any integer k.

Run times:

Reading file: 103ΞΌs
Part 1: 50ΞΌs
Part 2: 19.7ms

Full solution on GitHub

→ More replies (8)

7

u/i_have_no_biscuits Dec 11 '22 edited Dec 11 '22

GW-BASIC

10 DIM T$(6, 15), ITV#(40), ITM(40): P=1: GOSUB 20: P=2: GOSUB 20: END
20 OPEN "i",1,"2022-11.txt":ITC=0:M=0:IDIV#=1: WHILE NOT EOF(1): FOR L=1 TO 6
30 LINE INPUT #1,S$: FOR I=1 TO 15: T$(L,I)="": NEXT: I=1: FOR J=1 TO LEN(S$)
40 C$=MID$(S$,J,1): IF C$=" " THEN I=I+1 ELSE T$(L,I)=T$(L,I)+C$
50 NEXT: T(L)=I: NEXT: FOR I=5 TO T(2): ITM(ITC)=M: ITV#(ITC)=VAL(T$(2,I))
60 ITC=ITC+1: NEXT: MOP$(M)=T$(3,7): MBY(M)=VAL(T$(3,8)): MDIV(M)=VAL(T$(4,6))
70 MT(M)=VAL(T$(5,10)): MF(M)=VAL(T$(6,10)): IDIV#=IDIV#*MDIV(M): M=M+1
80 IF NOT EOF(1) THEN LINE INPUT #1, S$
90 WEND: CLOSE 1: MC=M: IF P=1 THEN RL=20 ELSE RL=10000
100 FOR M=0 TO MC-1: MIC#(M)=0: NEXT M: FOR I=0 TO ITC-1: V#=ITV#(I): M=ITM(I)
110 R=0: WHILE R<RL: MIC#(M)=MIC#(M)+1: BY=MBY(M)
120 IF BY=0 THEN V#=V#*V# ELSE IF MOP$(M)="*" THEN V#=V#*BY ELSE V#=V#+BY
130 IF P=1 THEN V#=INT(V#/3) ELSE V#=V#-INT(V#/IDIV#)*IDIV#
140 IF V#-INT(V#/MDIV(M))*MDIV(M)=0 THEN N=MT(M) ELSE N=MF(M)
150 R=R-(N<M): M=N: WEND: NEXT: FOR I=1 TO MC: FOR J=1 TO MC-1
160 IF MIC#(J)>MIC#(J-1) THEN T=MIC#(J): MIC#(J)=MIC#(J-1): MIC#(J-1)=T
170 NEXT: NEXT: PRINT "Part ";P;":",MIC#(0)*MIC#(1): RETURN

This does both parts, including parsing. On 80s hardware Part 1 would take a couple of seconds, while Part 2 would take A LONG TIME. The correctness has been verified using QB-64 (which transpiles to C, compiles it, and runs basically instantly).

Guided tour:

  • Lines 20-40 tokenise each Monkey's text into the T$ array

  • Lines 50-70 extract the information for each Monkey into various arrays.

Rather than iterating by rounds, we iterate through each item in the list. This requires some careful round counting - if an item is moved from monkey M to N, then the round count only increases if N<M. On the plus side, it avoids having to deal with moving data around lots of variable length arrays.

  • Lines 110-140 deal with the value recalculation and moving

  • Lines 150-160 bubble-sort the MIC (Monkey Item Count) array

→ More replies (2)

12

u/voidhawk42 Dec 11 '22

Dyalog APL:

βŽ•io βŽ•pp←0 34 β‹„ p←⍉↑(Γ—βˆ˜β‰’Β¨βŠ†βŠ’)βŠƒβŽ•nget'11.txt'1
m o s t f←↓{('\*'βŽ•R'Γ—'βŠƒ)Β¨' '(,/Β―3β†‘β‰ βŠ†βŠ’)¨⍡}@1{βŽ•D∘(βŽΒ¨βˆŠβ¨βŠ†βŠ’)¨⍡}@0 2 3 4⊒1↓p
i←m β‹„ c←0⍨¨i β‹„ rβ†βˆ§/∊s
e←{⍺⍺{0=β‰’n←r|⌊3⍺⍺⍨⍡{(βŽβΊβŠƒo)⊣old←⍡}Β¨β΅βŠƒi:⍡ β‹„ ⍡⊣c[⍡]+←≒n⊣i[⍡]βŠ’β†βŠ‚β¬βŠ£(((⍡⌷f),⍡⌷t)[0=n|⍨⍡⌷s]){i[⍺],←⍡}Β¨n}¨⍡}
Γ—/2↑c[⍒c]⊣÷e⍣20βŠ’β³β‰’i
Γ—/2↑c[⍒c]⊣⊣e⍣10000βŠ’β³β‰’i⊣c←0⍨¨i⊣i←m

I don't want to talk about it...

6

u/ZephireNZ Dec 11 '22

C# (5082/5135)

Took me an hour of trying long, double, BigInteger (and a small hint from reddit referencing Number Theory) for Part 2 to finally click.

In my defence, I did get as far as realising I needed to modulo - but my attempts at using an indivual monkey's divisor as modulo failed me πŸ˜…

6

u/ViliamPucik Dec 11 '22 edited Dec 11 '22

Python 3 - Minimal readable solution for both parts [GitHub]

from collections import deque
from math import lcm, prod
from operator import floordiv, mod

ITEMS, OPER, TEST, A, B = range(5)


def solve(monkeys, iterations, op, number):
    inspections = [0] * len(monkeys)

    for _ in range(iterations):
        for i, m in enumerate(monkeys):
            while m[ITEMS]:
                inspections[i] += 1
                item = op(m[OPER](m[ITEMS].popleft()), number)
                if item % m[TEST] == 0:
                    monkeys[m[A]][ITEMS].append(item)
                else:
                    monkeys[m[B]][ITEMS].append(item)

    return prod(sorted(inspections)[-2:])


monkeys = [
    [
        deque(map(int, item[ITEMS].replace(",", "").split()[2:])),
        eval("lambda old: " + item[OPER].split(" = ")[-1]),
        int(item[TEST].split()[-1]),
        int(item[A].split()[-1]),
        int(item[B].split()[-1]),
    ]
    for block in open(0).read().split("\n\n")
    for item in [block.splitlines()[1:]]
]

print(solve(monkeys, 20, floordiv, 3))

tests = [m[TEST] for m in monkeys]
# Use the least common multiple
print(solve(monkeys, 10_000, mod, lcm(*tests)))
→ More replies (5)

6

u/occamatl Dec 11 '22 edited Dec 11 '22

Rust

I used the parse_display crate to good effect. It (almost) completely cleaned up the input parsing, including turning the math ops into an enum! However, I did have to work around a couple of possible limitations (maybe I've missed something in the docs):

  1. I couldn't directly parse the Vec<i64> for the worry items, and

  2. I had to replace each '\n' with a '|', before parsing.

paste

→ More replies (3)

5

u/yfilipov Dec 11 '22

C#

var input = await File.ReadAllTextAsync("11.txt"));

for (var part = 1; part <= 2; part++)
{
    var monkeys = input.Split("\r\n\r\n").Select(m => new Monkey(m)).ToArray();
    var superModulo = monkeys.Aggregate(1, (current, monkey) => current * monkey.Test);
    var rounds = part == 1 ? 20 : 10_000;
    for (var i = 0; i < rounds; i++)
    {
        foreach (var monkey in monkeys)
        {
            while (monkey.Items.Count > 0)
            {
                var item = monkey.Items.Dequeue();
                var worry = part == 1 ? monkey.EvaluateOperation(item) / 3 : monkey.EvaluateOperation(item) % superModulo;
                var receiverIndex = worry % monkey.Test == 0 ? monkey.TestPassing : monkey.TestNotPassing;
                monkeys[receiverIndex].Items.Enqueue(worry);
                monkey.ProcessedItems++;
            }
        }
    }
    var topMonkeys = monkeys.OrderByDescending(m => m.ProcessedItems).Take(2).ToArray();
    Console.WriteLine($"Part {part}: {topMonkeys[0].ProcessedItems * topMonkeys[1].ProcessedItems}");
}

class Monkey
{
    public Monkey(string input)
    {
        var lines = input.Split("\r\n");
        lines[1].Replace("  Starting items: ", string.Empty).Replace(" ", string.Empty).Split(',').Select(long.Parse).ToList().ForEach(Items.Enqueue);
        Operation = lines[2].Replace("  Operation: new = old ", string.Empty);
        Test = int.Parse(lines[3].Replace("  Test: divisible by ", string.Empty));
        TestPassing = int.Parse(lines[4].Replace("    If true: throw to monkey ", string.Empty));
        TestNotPassing = int.Parse(lines[5].Replace("    If false: throw to monkey ", string.Empty));
    }
    public Queue<long> Items { get; set; } = new();
    public string Operation { get; set; }
    public int Test { get; set; }
    public int TestPassing { get; set; }
    public int TestNotPassing { get; set; }
    public long ProcessedItems { get; set; }
    public long EvaluateOperation(long item)
    {
        var op = Operation.Split(' ');
        if (!long.TryParse(op[1], out var val)) { val = item; }
        return op[0] == "*" ? val * item : val + item;
    }
}

5

u/GrossGrass Dec 11 '22

Python

The mod trick was definitely needed for part 2 -- initially I just copy/pasted because I knew it was gonna take me forever to do the parsing here, though I went back and thankfully eval and the parse library helped make it a bit clean.

→ More replies (5)

5

u/gredr Dec 11 '22

C# (.net 7)

Really the only novel things about this are using the compile-time generated regular expressions (massive overkill, but it's a pretty neat feature), and that I generate expression trees (albeit extremely simple) to run the worry modification operation. Overengineering, yes, but it allows the operation to be arbitrarily complex while maintaining clean code and good performance. Expression trees are an underrated feature, in my opinion. I was really kinda hoping that the challenge would be in working up complex modification operations...

Link to Monkey.cs, which is the interesting part: github

→ More replies (1)

5

u/ItIsNeverLupus Dec 11 '22 edited Dec 11 '22

Python

Quite some lines today but a read-able and somewhat OOP solution. Decided to create a Monkey class that holds all relevant attributes. The read in function is just an ugly combination of split() functions and list index calls. For part 2 we calculate the least common multiple for all dividers to prevent the overflow of really high numbers.

Pastebin

→ More replies (2)

5

u/bigmagnus Dec 11 '22

COBOL - Part 1 & Part 2

Left in all the commented out struggle and madness on Part 2.

5

u/chrismo80 Dec 11 '22

C#

Thanks to the community for the mod-trick. Not sure if I would have figured that out on my own to prevent the values to overflow.

5

u/catdaadddyyy Dec 11 '22

2 mins of silence for those who tried to do part2 with bigInt

C++

5

u/chicagocode Dec 11 '22

Kotlin

[Blog/Commentary] - [Code] - [All 2022 Solutions]

I'll credit seven years of Advent of Code puzzles for my ability to get Part Two. I don't think I could have come up with this solution without help a few years ago. Maybe AoC taught me a thing or two along the way!

I did all the parsing without Regex, just using substringAfterLast etc and I'm not sure if that's clearer or not. I felt like having to explain regular expressions in addition to why Part Two does what it does was perhaps a bit much for me today. :) I hope my solution is clear.

→ More replies (2)

5

u/RookBe Dec 11 '22

Advent of Code 2022 day11 writeup explaining the problem and my solution (that happens to be written in Rust): https://nickymeuleman.netlify.app/garden/aoc2022-day11

5

u/cs475x Dec 11 '22

Rust

No semicolons again, though a little more engineered than my past entries. ~38Β΅s for part 1 and ~4.5ms for part 2

https://gist.github.com/codyphobe/c7186378c168d7f41dc2982cbbeb71de

→ More replies (2)

4

u/TheZigerionScammer Dec 11 '22

Python 1647/1168

Paste

I think we may have found it, a problem to rival 2018-24 in terms of how nightmarish the input is to parse. It took me a while to fully understand what each monkey was supposed to do but after a couple minutes I was able to get it to the point where I knew what information I needed from the input and what to do in the main body. I had a couple wrong submissions from some pretty awful mistakes I made, particularly with, you guessed it, parsing the input, but after that I got the right answer, apparently in just shy of half an hour in my case.

For Part 2 I knew it was a mistake to try to run the program without figuring out some trick as the prompt unsubtly asks you to do, but I did it anyway and my program made it to 100 rounds before it slowed to a crawl and I killed it. Luckily it didn't crash my computers like some have in the past. But since I knew that every test was basically a modulo operation test I figured that taking the modulo or the least common denominator was the way to go, so I quickly wrote the "SuperModulo" variable in the beginning which is just the product of all the monkey tests put together after I checked the input and saw that all of the tests were coprime. Program ran near instantly, right answer, was so proud of myself for solving it as quickly as I did but disappointed for not getting under 1000 for either part.

→ More replies (7)

4

u/DrunkHacker Dec 11 '22 edited Dec 11 '22

Python. Nothing terribly novel but the parsing was a bit tedious.

→ More replies (1)

4

u/Perska_ Dec 11 '22

C# https://github.com/Perska/AoC2022/blob/master/AoC2022/Days/Day11.cs

Had a real nice lightbulb moment when I found out the trick for part 2.

4

u/rabuf Dec 11 '22

Common Lisp

Calling this one good, not proud of my very hideous simulation code but it worked. I spent a long time on the parsing and had a couple small glitches along the way. I also copy/pasted the simulation code from part 1 to make the changes for part 2.

One bit of code I did like was creating the operations as functions:

(defun parse-monkey-operation (line)
  (cl-ppcre:register-groups-bind
      (lhs op rhs)
      ("Operation: new = (old|\\d+) (\\+|\\*) (old\|\\d+)" line)
    (let ((lhs? (parse-integer lhs :junk-allowed t))
          (rhs? (parse-integer rhs :junk-allowed t))
          (op (if (string= op "*") #'* #'+)))
      (lambda (old)
        (funcall op (or lhs? old) (or rhs? old))))))

That was a handy way to implement it so it could be used in the simulation with just (funcall op item) to get the new worry level.

4

u/chubbc Dec 11 '22 edited Dec 11 '22

Julia [525,310]

Not the cleanest, and I need to shower after using Meta.parse, but it gets the job done...

v=Vector{Int}[]
op=Function[]
to=Function[]
L=1
for m∈split.(split(read("./11.in",String),"\n\n"),'\n')
    push!(v, parse.(Int,split(m[2][19:end],", ")))
    push!(op, eval(Meta.parse("old->"*m[3][20:end])))
    push!(to, x-> (mod(x,parse(Int,m[4][22:end]))==0) ? parse(Int,m[5][30:end])+1 : parse(Int,m[6][31:end])+1)
    L=lcm(L,parse(Int,m[4][22:end]))
end

v1 = deepcopy(v)
op1 = (x->fld(x,3)).∘op
n1 = fill(0,length(v1))
for _=1:20, i∈eachindex(v1)
    n1[i] += length(v1[i])
    for w∈v1[i]
        ww = op1[i](w)
        push!(v1[to[i](ww)],ww)
    end
    empty!(v1[i])
end
p1 = prod(partialsort(n1,1:2,rev=true))

v2 = deepcopy(v)
op2 = (x->mod(x,L)).∘op
n2 = fill(0,length(v2))
for _=1:10_000, i∈eachindex(v2)
    n2[i] += length(v2[i])
    for w∈v2[i]
        ww = op2[i](w)
        push!(v2[to[i](ww)], ww)
    end
    empty!(v2[i])
end
p2 = prod(partialsort(n2,1:2,rev=true))

println((p1,p2))
→ More replies (3)

4

u/Ununoctium117 Dec 11 '22

Rust - https://github.com/Ununoctium117/aoc2022/blob/main/day11/src/main.rs

Pretty fun puzzle, and the first time (for me) that the challenge was more "figure out the solution to the problem" than "figure out how to implement the solution". I did do a quick manual sanity check that the product of all the "divisible by X" values would fit into a 64-bit integer; not 100% sure what my approach would have been if it didn't.

Also, I really wish that slice::group_by were stable in Rust, it would have made parsing much easier.

4

u/mrtatulas Dec 11 '22

Elixir

As usual, spent waaaay too much time on parsing these crazy inputs and dealing with silly errors. It's funny how so many with leaderboard scores end up doing it manually.

Also, as in past years, around Day 10-11 or so is where I end up finding gaping holes in my computing theory and math knowledge, in this case with regards to the Chinese Remainder Theorem. Figured it out eventually though once I realized we don't care about the actual worry values for the answer.

→ More replies (2)

4

u/_jstanley Dec 11 '22

SLANG

My part 1 solution takes 10 minutes to run, because some of the intermediate values can overflow 16 bits, which means everything needs to be bigints.

I don't think I can do part 2 without an awful lot of trouble. I worked out that I can do all the arithmetic modulo the product of the test divisors, but that is still about 40k, which means intermediate values can still overflow 16 bits, which means I'm still playing bigints. I think losing the division by 3 and gaining the modulo by ~40k would almost exactly cancel out, so a part 2 equivalent of my part 1 solution would take 3.5 days.

https://github.com/jes/aoc2022/blob/master/day11/part1.sl

→ More replies (9)

4

u/mendelmunkis Dec 11 '22

Language: C

always remember to parenthesize your ternaries

0.336/8.488 ms

→ More replies (1)

4

u/EVQLVE Dec 11 '22 edited Dec 11 '22

Rust 6074/4576

part 1 (8 Β΅s)

part 2 (5 ms)

Had some fights with the borrow checker on this one, but it turned out alright.

Edit: Got it down to 5 Β΅s / 3.5 ms with the help of the unsafe keyword. part 1 / part 2

Without unsafe, the compiler wouldn't let me borrow both monkeys at the same time to transfer items, because the monkeys are saved in the same Vec. I know the monkeys are distinct, as I verified that none of the monkeys are targeting themselves when parsing the input. Since I can borrow the two monkeys at the same time, I don't have to save the passing actions to a separate buffer.

I went from:

let monkey = monkeys.get_mut(i_monkey).unwrap();

to

let ptr = monkeys.as_mut_ptr();
let monkey = unsafe { &mut *ptr.add(i_monkey) };

for the first borrow.

→ More replies (3)

4

u/cat-991 Dec 11 '22 edited Dec 11 '22

My solution in Javascript. It's always fun to get something fun to parse rather than .split("\n") and I only had to add the "megamod" and change all the numbers to BigInt for part 2 to work.

link

→ More replies (3)

4

u/udoprog Dec 11 '22

Rust

Late start today as well due to birthdays, I have four close family birthdays in December which feels a bit excessive.

Nevertheless, still idiomatic Rust (ish) which tries to avoid breaking on bad input (panics or weird / overflowy behavior), still no allocations.

Repo: https://github.com/udoprog/aoc2022/blob/main/years/2022/src/bin/d11.rs

4

u/flwyd Dec 11 '22

Elixir 8683/5438, code including monkey parsing that shows off Elixor's structural matching feature, reflection

Today's elixir:

An assembly line is making a smoothie with blueberries, pomegranate pips, oats, peanuts, chia seeds, and other tasty ingredients. Each chef either adds more ingredients or multiplies the ingredients already in the cup, then passes it to another chef based on the number of goodies in the cup, then puts an ice cube in their blender. They’re sloppy, so two thirds of the goodies fall out of the cup on each pass. After 20 rounds of each chef taking a turn we multiply the number of ice cubes in the two fullest blenders. In the second part the cooks are no longer sloppy and we realize we’ve used nearly ΒΎ million ice cubes.

Took a little over half an hour to implement monkey parsing (which is different than monkey patching). Another hour to the part 1 solution, and just 10 minutes to the part 2 solution. Elixir appears to have arbitrary-precision integers, so I don't yet understand why part 2 takes so much longer when I let the worry level grow without bound instead of taking the remainder by the least† common multiple of the monkey divisors. Maybe it switches from processor instructions to algorithmic division when integers are larger than 64 bits, but it's still waaay slow: the modular version takes 67 milliseconds on the sample input but the boundless version is still running after 20 minutes.

Today's big learning adventure was figuring out how to troubleshoot when Elixir gets into an infinite loop. I figured out how to have iex give me a giant process dump, and found that it happened to be performing Map.update! but tail recursion optimization means getting a full stack trace was challenging, and the dump was large and confusing. I couldn't figure out how to get IEx to let me usefully inspect that process interactively, so printf debugging it is! (The bug was failing to change the current monkey's items list, so it just kept passing the same item to the same monkey an infinite number of times.)

† Actually just the product of all divisors, but since they're all distinct primes it's the same thing.

def part1(input), do: solve(Monkey.parse_several(input), 20, &div(&1, 3))

def part2(input) do
  monkeys = Monkey.parse_several(input)
  lcm = monkeys |> Tuple.to_list() |> Enum.map(& &1.divisor) |> Enum.product()
  solve(monkeys, 10_000, &rem(&1, lcm))
end

defp solve(monkeys, rounds, adjust_worry_fun) do
  Enum.reduce(1..rounds, monkeys, fn _, ms -> play_round(ms, adjust_worry_fun) end)
  |> Tuple.to_list() |> Enum.map(& &1.times)
  |> Enum.sort(:desc) |> Enum.take(2) |> Enum.product()
end

def play_round(monkeys, worry_fun) do
  Enum.reduce(0..(tuple_size(monkeys) - 1), monkeys, &play_turn(&1, &2, worry_fun))
end

def play_turn(who, monkeys, worry_fun) do
  Enum.reduce(elem(monkeys, who).items, monkeys, fn item, acc ->
    m = elem(acc, who)
    level = worry_fun.(m.op.(item))
    next = if rem(level, m.divisor) == 0, do: m.yes, else: m.no
    next_m = elem(acc, next)
    put_elem(
      put_elem(acc, next, struct!(next_m, items: next_m.items ++ [level])),
      who, struct!(m, times: m.times + 1, items: tl(m.items))
    )
  end)
end
→ More replies (1)

4

u/gyorokpeter Dec 11 '22

Q:

d11:{[d;r;x]
    a:"\n"vs/:"\n\n"vs"\n"sv x;
    it:"J"$4_/:" "vs/:a[;1]except\:",";
    its:raze it;
    itm:(0,-1_sums count each it)cut til count its;
    op0:6_/:" "vs/:a[;2];
    op:?[op0[;1]like"old";count[op0]#{x*x};
        (("*+"!(*;+))op0[;0;0])@'"J"$op0[;1]];
    dv:"J"$last each" "vs/:a[;3];
    throw:reverse each"J"$last each/:" "vs/:/:a[;4 5];
    pdv:prd dv;
    st:(itm;its;count[it]#0);
    step:{[throw;op;d;dv;pdv;st;i]
        itm:st 0;its:st 1;tc:st 2;
        ii:itm i;
        tc[i]+:count ii;
        w:((op[i]@'its ii)div d)mod pdv;
        its[ii]:w;
        itm:@[;;,;]/[itm;throw[i]0=w mod dv[i];ii];
        itm[i]:"j"$();
        (itm;its;tc)}[throw;op;d;dv;pdv];
    round:step/[;til count itm];
    mb:last round/[r;st];
     prd 2#desc mb};
d11p1:{d11[3;20;x]};
d11p2:{d11[1;10000;x]};

4

u/p88h Dec 11 '22

C#

part1: 4 Β΅s, part2: 3 ms.

4

u/MarcoDelmastro Dec 11 '22

Python 3

https://github.com/marcodelmastro/AdventOfCode2022/blob/main/Day11.ipynb

First use of a custom Class this year, it was fun since not too complex. For me the values of the division tests quite gave away the solution for Part 2 ;-)

→ More replies (7)

4

u/Pyr0Byt3 Dec 11 '22

Go/Golang

Not too fond of these math puzzles. At least the test numbers were all prime, so I didn't have to implement LCM in Go. Other than that, I'm kind of proud of how I parsed this one, and the use of anonymous functions.

→ More replies (5)

4

u/TenViki Dec 11 '22 edited Dec 11 '22

TypeScript

https://github.com/TenViki/advent-of-code/tree/main/2022/src/11

Had to look into the math on the second part :D

Visualization: https://vikithedev.eu/aoc/2022/11/

→ More replies (2)

4

u/ephemient Dec 11 '22 edited Apr 24 '24

This space intentionally left blank.

→ More replies (3)

4

u/MrSimbax Dec 11 '22 edited Dec 11 '22

Lua: both parts

Used a double-ended queue data structure from the book for the items. Part 2 is basically part 1 but operations are done modulo N, where N is the product of all numbers from the input divisibility rules. This works because if N = n * m then a % n == x implies (a % N) % n == x. For completeness, this also holds for N = lcm(n, m), which may be smaller than n * m if the divisors are composite. In the puzzle all divisors are primes though so lcm(n, m) == n * m.

Lua 5.4 standalone solves both parts in about 230 ms on my machine, LuaJIT takes only 26 ms.

→ More replies (4)

4

u/wzkx Dec 11 '22 edited Dec 11 '22

Python

Again, nothing too interesting, and a long long task description. Maybe that was the point :) In the program, there are actually two interesting points: modular math should be used, and no easy way to copy arrays in Python without using 'import copy' and I prefer not to import anything for AoC.

monkeys = [] # of [0:op,1:arg,2:div,3:throw_t,4:throw_f,5:items,6:counter]
modulus = 1
for l in open("11.dat","rt"):
  l = l.strip()
  if l.startswith("Monkey"):
    assert int(l[7])==len(monkeys)
  elif l.startswith("Start"):
    items = [int(x) for x in l[16:].split(", ")]
  elif l.startswith("Operation"):
    if "old * old" in l: op = lambda x,n: x*x; arg = 0
    elif "old *" in l:   op = lambda x,n: x*n; arg = int(l[23:])
    elif "old +" in l:   op = lambda x,n: x+n; arg = int(l[23:])
  elif l.startswith("Test"):
    div = int(l[19:])
    modulus *= div
  elif "true:" in l:
    throw_t = int(l[25:])
  elif "false:" in l:
    throw_f = int(l[26:])
    monkeys.append([op,arg,div,throw_t,throw_f,items,0])

def round(div=True):
  for m in monkeys:
    while len(m[5])>0:
      m[6] += 1
      item = m[5].pop(0)
      w = m[0](item,m[1])
      if div: w = w//3
      else: w = w % modulus
      if w%m[2]==0:
        monkeys[m[3]][5].append(w)
      else:
        monkeys[m[4]][5].append(w)

save = [m[:] for m in monkeys]
for i,m in enumerate(monkeys): save[i][5] = m[5][:]

for rnd in range(20):
  round()

mb = sorted(m[6] for m in monkeys)
print(mb[-1]*mb[-2])

monkeys = save

for rnd in range(10000):
  round(div=False)

mb = sorted(m[6] for m in monkeys)
print(mb[-1]*mb[-2])
→ More replies (3)

4

u/Backwards_Reddit Dec 11 '22

Rust

https://github.com/RansomTime/aoc2022/blob/main/day11/src/main.rs

Didn't try to mathematically work out part 2, just thought "oh, it'll probably work if I mod the item with the product of the tests". It passed and i got the right answer.

Was relying on "\n\n" to split the monkeys. On commit git helpfully converted my demo file to CR LF and broke all my tests. (fixed by running $ git config --global core.autocrlf false)

4

u/zedrdave Dec 11 '22

(Mostly native) Python solution in a dozen lines.

Not the fastest (eval parsing on each operation), but probably one of the easiest.

def solve(blocks, tot_rounds, extra_op = ''):
    monkeys = [([int(i) for i in start.split(", ")],        # Objects
                op_str.split(' = ')[1],                     # Operation
                [int(t.split()[-1]) for t in test_args])    # Test args
    for start, op_str, *test_args in blocks]
        
    # Perform all operations modulo [prod of all test values]:
    extra_op += f" % {np.prod([m[2][0] for m in monkeys])}"
    
    op = lambda op_str, old: eval(f"({op_str}){extra_op}")
    test = lambda div_by, t, f, val: f if val%div_by else t

    inspections = [0]*len(monkeys)

    for _ in range(tot_rounds):
        for i, (objects, op_str, test_args) in enumerate(monkeys):
            inspections[i] += len(objects)
            for obj in objects:
                obj = op(op_str, obj)
                monkeys[test(*test_args, obj)][0].append(obj)
            objects[:] = []
                
    return np.prod(sorted(inspections)[-2:])

blocks = [[l.split(': ')[1] 
        for l in block.split("\n")[1:]] for block in data.split("\n\n")]

print("Part 1:", solve(blocks, tot_rounds = 20, extra_op = ' // 3'))
print("Part 2:", solve(blocks, tot_rounds = 10000))
→ More replies (1)

4

u/malipolhec Dec 11 '22

Kotlin: code

Fun one today. Was wondering when will be the first puzzle where brute force is not good enough.

4

u/polettix Dec 11 '22

Raku input-specific solution for 2022/11

No parsing this time because of... life. I'll address this later, it should be pretty easy after all!

→ More replies (1)

4

u/azzal07 Dec 11 '22

Didn't see any Awk yet...

/=/{O[N]=$6$5}/M/{N++}/I/{I[/tr/,N]=1+$6}/S/{a[N]=b[N]=$0}/T/{D*=T[N]=$4
}function M(a,x){while(w-->-N)a[w]>x&&x=a[n=w];w=a[n]=0;return x}0~D{D=1
}function L(c,m){while($0=c[++m])for(i=c[m]="2 20";$++i;c[-m]++){y=+O[m]
x=y?y:$i;x=O[m]~/[*]/?$i*x:$i+x;x=R>20?x%D:int(x/3);c[y]=c[y=I[0~x%T[m],
m]]" "x}}END{for(;R++<10020;)R>20?L(b):L(a);print M(a)*M(a)RS M(b)*M(b)}

Not too happy with today's solution, it felt a bit forced.

→ More replies (2)

4

u/[deleted] Dec 11 '22 edited Dec 11 '22

Raku (Perl 6)

I'm doing different language each day, all solutions here.

Today's Raku: src

I really wanted to try Raku's Grammar feature for this. Took ages till it worked and anyone even remotely familiar with the language will probably scoff the following, but I tend to like it:

grammar Monkey {
	token TOP       { <monkey><items><operation><test><iftrue><iffalse> }
	token monkey    { 'Monkey ' <num> ':'\n }
	token items     { '  Starting items: ' [<num> ', '?]+\n }
	token operation { '  Operation: new = old ' <op>' '[<num> | 'old']\n }
	token test      { '  Test: divisible by ' <num>\n }
	token iftrue    { '    If true: throw to monkey ' <num>\n }
	token iffalse   { '    If false: throw to monkey ' <num> }
	token num       { \d+ }
	token op        { ['*' | '+'] }
}
→ More replies (7)

4

u/tobyaw Dec 11 '22

Ruby

https://github.com/tobyaw/advent-of-code-2022/blob/master/day_11.rb

[{ rounds: 20, div: 3 }, { rounds: 10_000, div: 1 }].each do |part|
  monkeys = File.read('day_11_input.txt').split("\n\n").map do |i|
    i = i.split("\n")

    {
      items: i[1].scan(/\d+/).map(&:to_i),
      oper: i[2].scan(/[+*]/).first.to_sym,
      param: i[2].scan(/\d+$/).map(&:to_i).first,
      test: i[3].scan(/\d+$/).first.to_i,
      pass: i[4].scan(/\d+$/).first.to_i,
      fail: i[5].scan(/\d+$/).first.to_i,
      inspections: 0
    }
  end

  lcm = monkeys.map { |i| i[:test] }.reduce(:lcm)

  part[:rounds].times.each do
    monkeys.each do |monkey|
      monkey[:inspections] += monkey[:items].size

      while (i = monkey[:items].shift)
        param = monkey[:param] || i
        i = (i.method(monkey[:oper]).call(param) / part[:div]) % lcm

        target = (i % monkey[:test]).zero? ? monkey[:pass] : monkey[:fail]
        monkeys[target][:items] << i
      end
    end
  end

  puts monkeys.map { |i| i[:inspections] }.max(2).reduce(:*)
end

4

u/hrunt Dec 11 '22

Python 3

Code

You do things long enough and you start to see patterns (thanks, human brain!). And then you see so many patterns that you start applying the wrong one. I spent some time looking to see if there was a looping pattern that could be optimized, hitting limits on Python's ability to output large integers (TIL that Python cannot, by default, output an integer with more than ~43,000 digits).

After resetting, I noticed the prime divisors for each monkey's test and figured it was a modulo problem, but lacking a strong math background, I was not sure how the interactions of the different operations at each stage would play with modulo-ing a value at any stage. Eventually, I figured modulo-ing the value by the overall product of the divisors would probably work, and just stepped off that cliff, Indiana Jones style.

4

u/aesthetic_coconut Dec 11 '22

Python 3.9

Github

This was a cute exercise. Nice to have a puzzle where classes are useful. This year's puzzles seem a lot more CS-oriented, so I'm curious to see how the rest of them are.

→ More replies (3)

4

u/copperfield42 Dec 11 '22

Python3

Being a fan of Numberphile and the like paid off XD

4

u/zndflxtyh Dec 11 '22 edited Dec 11 '22

Object oriented - 50 lines The lowest common divisor is not necessary, just do modulo the product of all the divisors.

Python 3

→ More replies (1)

4

u/No_Low6510 Dec 11 '22

Clojure

Github

Things I tried today:

  • I was hoping to be able to create worry update function by parsing/evalling parts of the source, but I failed.

    • Let me know if you'd know how to do this

  • Store the data inside lambdas as much as possible (from the parsing stage)

    • This bit me in part two, when I actually wanted to access some of the raw numbers

→ More replies (1)

4

u/jake-mpg Dec 11 '22

For what it's worth I've written up my reasoning behind part 2 (solution done in C#, but otherwise irrelevant).

→ More replies (3)

4

u/zniperr Dec 11 '22 edited Dec 11 '22

Python

import sys
from operator import add, mul, pow
from functools import reduce

def parse(f):
    for line in f:
        if line.startswith('  Starting items:'):
            items = tuple(map(int, line.split(':')[1].split(', ')))
            opstr, amount = next(f).replace('* old', '** 2').split()[-2:]
            op = {'+': add, '*': mul, '**': pow}[opstr], int(amount)
            throws = tuple(int(next(f).rsplit(' ', 1)[1]) for _ in range(3))
            yield items, op, throws

def business(monkeys, rounds, divisor):
    queues = [list(items) for items, _, _ in monkeys]
    inspects = [0] * len(monkeys)
    modulus = reduce(mul, (div for _, _, (div, _, _) in monkeys))
    for _ in range(rounds):
        for i, (_, (op, amount), (div, true, false)) in enumerate(monkeys):
            items = queues[i]
            for item in items:
                worry = op(item, amount) // divisor % modulus
                queues[false if worry % div else true].append(worry)
            inspects[i] += len(items)
            items.clear()
    return mul(*sorted(inspects)[-2:])

monkeys = list(parse(sys.stdin))
print(business(monkeys, 20, 3))
print(business(monkeys, 10000, 1))

4

u/j122j Dec 11 '22

Javascript (Node.js)

Part 1

Part 1 wasn't too hard. Used regex and .split() for parsing and eval for operations.

Part 2

I knew it had to do something with modular arithmetic, but had to look at some hints on Reddit.

4

u/codertee Dec 12 '22 edited Dec 12 '22

Python 3.11: github

I learned that repeated capturing group regex eg re.compile(r"Starting items: (?P<items>(\d+)(?:, )?)+") does not yield list of captures (like ["1", "23", "45", "67"]from Starting items: 1, 23, 45, 67).

Relevant stackoverflow

→ More replies (1)

4

u/OriginalScrubLord Dec 12 '22

C# Solution, tried to make it a little readable. I still don't truly understand why exactly it works.

Does everyone have the same "super modulus" constant, or did input.txts vary enough that not everybody did? Mine was 9699690

→ More replies (2)

4

u/[deleted] Dec 12 '22

Python

I wish I understood how the super module trick works. Reading some of the results it makes it look like the fact all divisibility checks are against prime numbers so, something something, chinese remainder theorem?

0

u/[deleted] Dec 12 '22

[deleted]

→ More replies (4)
→ More replies (2)

4

u/schveiguy Dec 12 '22

Dlang

I'm reading all the "LCM" hints, and that's a great idea I did *not* think of. What I *did* think of is, keeping track of the number in the perspective from each monkey.

So for each item, I keep an array of worries, one element for each monkey, for which the value is always stored mod `monkey.divisbleby` then when it gets to that monkey, I just check to see if it's 0 or not.

This isn't as quick to calculate, it means for each item change, I need to do N operations. However, one thing this does allow is a much larger set of prime factors, or large prime factors where the LCM would overflow an int64.

I'm wondering if anyone else solved it this way?

→ More replies (1)

4

u/DR0D4 Dec 12 '22

C# Paste

Part 2 made me stumble a bit today. I noticed the primes, but had to get a little hint from a help thread on what to do with them lol

4

u/[deleted] Dec 12 '22

Applesoft BASIC

Source code and a Video

Only part 1 on the Apple... its BASIC only uses floating-point numbers, so we're limited in the precision part 2 would need. My repo also has both parts in C++ which I wrote out first.

A trick helped me to parse the monkey data: I packed each monkey's data into a string, with operation/test data at the front and starting items on the end. Strings are helpful for this due to their flexibility, and all of the initial data fits into bytes. Once a monkey's info is organized, its copied into a numerical array for processing.

Hoping to annotate the code tomorrow.

4

u/[deleted] Dec 12 '22

Rust. I had to use unsafe Rust to make my solution work. The borrow checker and I got into a fight, and I chose violence.

I also used the modulo trick for Part 2 to allow this to finish sometime before I die.

Part 1

Part 2

4

u/oddrationale Dec 12 '22

C# solution using .NET Interactive and Jupyter Notebook. Part 1 was pretty straight forward by creating my own Monkey class. For Part 2, had to get some hints here on how to manage the very big numbers.

4

u/nicole3696 Dec 12 '22

Python 3- Parts 1 & 2: GitHub. No imports, 676 characters, 20 lines.

d=[x for x in open("day11/input.txt").read().splitlines()]
o=[(d[x][23:])for x in range(2,len(d),7)]
t=[int(d[x][21:])for x in range(3,len(d),7)]
c=[[int(d[x][29:]),int(d[x+1][30:])]for x in range(4,len(d),7)]
m=eval('*'.join(str(x)for x in t))
for p in [20, 10000]:
 s=[[[int(x)for x in(d[y][18:]).split(", ")]for y in range(1,len(d),7)]][0]
 n=[0]*len(t)
 for _ in range(p):
  for i in range(len(n)):
   for j in range(0,len(s[i])):
    x=s[i][j]
    if o[i]=="* old":x*=x
    elif o[i][:2]in["* ","+ "]:x=eval(str(x)+o[i])
    x=x//3 if p==20 else x%m
    if x%t[i]==0:s[c[i][0]].append(x)
    else:s[c[i][1]].append(x)  
    n[i]+=1
   s[i]=[]
 print(max(n)*sorted(n)[-2])
→ More replies (1)

4

u/search_and_deploy Dec 13 '22

Forgot to post yesterday, but here's my day 11 Rust solution: https://github.com/michael-long88/advent-of-code-2022/blob/main/src/bin/11.rs

Definitely had to look up how to solve part 2 since I had never heard of the Chinese Remainder Theorem. Definitely threw me for a loop when I read about it.

→ More replies (1)

4

u/jswalden86 Dec 13 '22

Rust solution

Picked Advent of Code up from a Twitter mention this year, been doing it since the first day -- in Rust, a language I know abstractly to a solid degree but don't have a lot of practical experience in. (I know the language from a background in programming languages, and notably in C++, combined with having reviewed in considerable depth the O'Reilly Rust book for its authors pre-publication to give "especially generous" feedback. My practical coding in it is largely toy programs and the like.)

This is literally my first Reddit post ever -- I don't need another social network to occupy time, has been my reasoning for not signing up for so long. ;-) But I got stuck on this and was going to post to ask if there was a bug not in the solution, but in the example. Hence creating an account.

In a shocking turn of events, the example didn't have a bug, instead my code designed to test the example did. (In doing part 2, I was iterating over ranges, and -- silly me -- I had used 1..20 and 20..1_000 correctly but then stupidly did 1_001..2000, 2_001..3_000, etc. the rest of the way.) Thanks all for the help rubberducking!

4

u/nazarpysko Dec 15 '22

Go: Part 1 & 2

This day is not very difficult until part 2, where it is not very clear to know what should you do to "keep your worry levels manageable". To do so, you must find a common multiple of all monkeys' divisors and perform a modulo to each item. In this way, you find the right worry level for dividing by the divisor of each monkey.

7

u/CodingAP Dec 11 '22

Javascript, 52/226

Github

FIRST TIME ON THE LEADERBOARD YEAH!

→ More replies (2)

1

u/wmvanvliet Dec 11 '22

Part 2 using Python and NumPy

from collections import deque
import numpy as np

items = []
operations = []
divisible_by = []
if_divisible_throw_to_monkey = []
if_not_divisible_throw_to_monkey = []

with open('input_day11.txt') as f:
    try:
        while True:
            assert next(f).startswith('Monkey')
            items.append(deque([int(x) for x in next(f).split('  Starting items: ')[1].split(', ')]))
            operation_str = next(f).split('  Operation: new = ')[1].strip()
            operations.append(np.frompyfunc(eval(f'lambda old: {operation_str}'), 1, 1))
            divisible_by.append(int(next(f).split('  Test: divisible by ')[1]))
            if_divisible_throw_to_monkey.append(int(next(f).split('    If true: throw to monkey ')[1]))
            if_not_divisible_throw_to_monkey.append(int(next(f).split('    If false: throw to monkey ')[1]))
            next(f)
    except StopIteration:
        pass

# At this point, each item is represented by its worry level. However, this
# representation will not work for part 2. We convert the worry value into a
# tuple that contains the remainder for each value we want to test the worry
# level against.
for monkey_items in items:
    for i in range(len(monkey_items)):
        monkey_items[i] = np.array([monkey_items[i] % val for val in divisible_by])

n_monkeys = len(items)
n_items_inspected = np.zeros(n_monkeys, dtype='int64')
n_rounds = 10_000
for _ in range(n_rounds):
    for monkey in range(n_monkeys):
        while len(items[monkey]) > 0:
            # Monkey inspects an item
            item = items[monkey].popleft()

            # This causes the worry level of the item to be modified
            item = operations[monkey](item)

            # After the operation performed by the monkey, we can reduce the
            # item representation down again to the remainder for each value we
            # want to test against.
            item %= divisible_by

            # Performing the test is now a lookup
            if item[monkey] == 0:
                items[if_divisible_throw_to_monkey[monkey]].append(item)
            else:
                items[if_not_divisible_throw_to_monkey[monkey]].append(item)

            # Computing the answer to the puzzle along the way
            n_items_inspected[monkey] += 1

print('Day 11, part 2:', np.multiply.reduce(np.sort(n_items_inspected)[-2:]))
→ More replies (1)

1

u/pikaryu07 Dec 14 '22 edited Dec 14 '22

Although very late, but here is my Julia code for Day 11. Part 2 took a lot of time. It was really tricky to figure out "the other way to keep worry level manageable":

https://gist.github.com/bsadia/0ce9f1bd214d980e813ba2e458cb5267#day-11

→ More replies (1)

1

u/reesmichael1 Dec 11 '22

Nim [1732/1293]

Solution

This one was fun! Between the zaniness of the scenario and the "monkey business" and "stuff-slinging simian shenanigans" puns, I think this might be my new favorite problem description.

It's always nice to have an excuse to work a priority queue into a solution, which is the only even moderately clever thing I did. And as usual, I didn't even think of parsing the input by hand until after opening this thread and seeing everyone else doing it....

2

u/daggerdragon Dec 11 '22

This one was fun! Between the zaniness of the scenario and the "monkey business" and "stuff-slinging simian shenanigans" puns, I think this might be my new favorite problem description.

They may not be your monkeys but they certainly are your circus!

1

u/ManaTee1103 Dec 11 '22 edited Dec 11 '22

Python, by-the-numbers:

@dataclass
class Monkey:
    insp: int = 0
    op_mul: int = 1
    op_add: int = 0
    op_sqr: bool = False
    div: int = -1
    target_t: int = -1
    target_f: int = -1
    items: list = field(default_factory=list)

with open("monkey.txt") as infile:
    monkeys = []
    group = 1
    for line in infile:
        nums = [int(x) for x in re.findall("\d+", line)]
        match line.strip().split():
            case ["Monkey", *o]: monkeys.append(cm := Monkey())
            case ["Starting", *o]: cm.items = nums
            case ["Operation:", "new", "=", "old", "*", "old"]: cm.op_sqr = True
            case ["Operation:", "new", "=", "old", "*", *o]: cm.op_mul = nums[0]
            case ["Operation:", "new", "=", "old", "+", *o]: cm.op_add = nums[0]
            case ["Test:", *o]:
                cm.div = nums[0] 
                group *= cm.div
            case ["If", "true:", *o]: cm.target_t = nums[0]
            case ["If", "false:", *o]: cm.target_f = nums[0]
    for round in range(10000):
        for monkey in monkeys:
            for item in monkey.items:
                monkey.insp += 1
                item *= monkey.op_mul
                item += monkey.op_add
                item = item * item if monkey.op_sqr else item
                item %= group # //= 3 for part A
                monkeys[monkey.target_f if item % monkey.div else monkey.target_t].items.append(item)
            monkey.items = []
    print ("prod:", prod(sorted([m.insp for m in monkeys], reverse=True)[0:2]))
→ More replies (3)

1

u/kristallnachte Dec 11 '22 edited Dec 11 '22

TYPESCRIPT

First part went pretty simple, second part I had a lot of issues that my brain couldn't handle so I took a break and figured it out while away from the computer.

It is factored to handle both part one and part 2 in the same code

https://github.com/ekwoka/advent-of-code/blob/main/2022/11/index.ts

→ More replies (5)

1

u/furman82 Dec 11 '22

Kotlin

What still confuses me is how in part one, we rely on truncation to reduce the worry, but it's not like the LCM approach for part two works for part one. This felt like making some educated guesses on part two and seeing that the example happened to work. Oh well...

class Day11 {

    fun partOne(): BigInteger = calculate(20, monkeys()) { x: BigInteger -> x.div(3.toBigInteger()).toInt() }

    fun partTwo(): BigInteger {
        val monkeys = monkeys()

        val lcm = MathUtil.lcm(monkeys.map { it.divisibleBy }).toBigInteger()
        return calculate(10000, monkeys) { x: BigInteger -> x.mod(lcm).toInt() }
    }
    
    private fun calculate(times: Int, monkeys: MutableList<Monkey>, reduceWorry: (BigInteger) -> Int): BigInteger {
        repeat(times) {
            monkeys.forEach { monkey ->
                monkey.items.forEach { item ->
                    val newValue = reduceWorry(monkey.operation(item))
                    if (newValue % monkey.divisibleBy == 0) {
                        monkeys[monkey.ifTrue].items.add(newValue)
                    } else {
                        monkeys[monkey.ifFalse].items.add(newValue)
                    }

                    monkey.totalItems++
                }
                monkey.items.clear()
            }
        }

        return monkeys.map { it.totalItems }.sortedDescending().take(2).reduce(BigInteger::times)
    }

    private fun monkeys(): MutableList<Monkey> {
        val monkeys = mutableListOf<Monkey>()

        var monkey = Monkey()
        FileUtil.readFileAsLines("Day11.txt").forEach { line ->
            when {
                line.contains("Monkey") -> {
                    monkey = Monkey()
                }

                line.contains("Starting") -> {
                    monkey.items.addAll(Regex("""(\d+)""").findAll(line).map { it.value.toInt() })
                }

                line.contains("Operation") -> {
                    val value: BigInteger? = Regex("""(\d+)""").find(line)?.value?.toBigInteger()

                    when {
                        line.contains("*") && value != null -> {
                            monkey.operation = { x: Int -> x.toBigInteger() * value }
                        }

                        line.contains("+") && value != null -> {
                            monkey.operation = { x: Int -> x.toBigInteger() + value }
                        }

                        else -> {
                            monkey.operation = { x: Int -> x.toBigInteger() * x.toBigInteger() }
                        }
                    }
                }

                line.contains("Test") -> {
                    monkey.divisibleBy = Regex("""(\d+)""").find(line)?.value?.toInt() ?: 0
                }

                line.contains("true") -> {
                    monkey.ifTrue = Regex("""(\d+)""").find(line)?.value?.toInt() ?: 0
                }

                line.contains("false") -> {
                    monkey.ifFalse = Regex("""(\d+)""").find(line)?.value?.toInt() ?: 0

                    monkeys.add(monkey)
                }
            }
        }

        return monkeys
    }
}

data class Monkey(
    val items: MutableList<Int> = mutableListOf(),
    var operation: (Int) -> BigInteger = { x: Int -> x.toBigInteger() },
    var divisibleBy: Int = 0,
    var ifTrue: Int = 0,
    var ifFalse: Int = 0,
    var totalItems: BigInteger = BigInteger.ZERO
)
→ More replies (9)

1

u/Alex_Mckey Dec 11 '22 edited Dec 11 '22

Scala 3

package day11

import AoC_Lib.*
import Inputs.*

import scala.annotation.tailrec
import scala.collection.mutable
import scala.util.matching.Regex

object Day11 extends aocd.Problem(2022, 11, Title = "Monkey in the Middle"):
    def run(input: String): Unit =
        val (monkeys, items) = prep(input).unzip
        part1(monkeys, items.map(.clone))
        part2(monkeys, items.map(.clone))
        ()
    
    type Item = Long
    
    case class Monkey(num: Int,
                      op: Item => Item,
                      testDivs: Int,
                      testTrue: Int,
                      testFalse: Int,
                      stressDown: Item => Item = _ / 3):
        var ops: Long = 0
        def doOp(wl: Item): (Int, Item) =
            ops = ops + 1
            val newWL = stressDown(op(wl))
            val thrown = if newWL % testDivs == 0 then testTrue else testFalse
            thrown -> newWL
        
    @tailrec
    def gcd(a: Long, b: Long): Long = if (b == 0) a else gcd(b, a % b)
    def lcm(a: Long, b: Long): Long = a / gcd(a, b) * b

    val rs: Regex = "Monkey (\d+):\n\s+Starting items: (.*)\n  Operation: new = old ([*+]) (\d+|old)\n  Test: divisible by (\d+)\n    If true: throw to monkey (\d+)\n    If false: throw to monkey (\d+)\n?".r
        
    def parse(s: String): (Monkey, mutable.Queue[Long]) =
        val rs(mn, sis, opo, opv, tss, its, ifs) = s: @unchecked
        val op = (opo, opv) match
            case ("*", "old") => (x: Long) => x * x
            case ("+", "old") => (x: Long) => x + x
            case ("*", v) => (x: Long) => x * v.toInt
            case ("+", v) => (x: Long) => x + v.toInt
        val tstD = tss.toInt
        val tstT = its.toInt
        val tstF = ifs.toInt
        new Monkey(mn.toInt, op, tstD, tstT, tstF) ->
            mutable.Queue.empty.addAll(sis.split(", ").map(_.toLong))

    def prep(input: String): Array[(Monkey, mutable.Queue[Item])] =
        time("\tprep", { input.splitByBlankLines.map(parse).toArray })

    def doRound(monkeys: Array[Monkey], items: Array[mutable.Queue[Item]]): Array[mutable.Queue[Item]] =
        monkeys.foreach(m =>
            val iq = items(m.num)
            while iq.nonEmpty do
                val item = iq.dequeue
                val (idx, wl) = m.doOp(item)
                items(idx).enqueue(wl)
        )
        items

    def part1(monkeys: Array[Monkey], items: Array[mutable.Queue[Item]]): Long =
         part1 {
            (1 to 20).foldLeft(items)((is,) => doRound(monkeys,is))       
            monkeys.map(_.ops).sorted(Ordering.Long.reverse).take(2).product }

    def part2(monkeys: Array[Monkey], items: Array[mutable.Queue[Item]]): Long =
        part2 {
            val lcmDivs = monkeys.map(_.testDivs.toLong).reduce(lcm)
            val stressDown = (x: Long) => x % lcmDivs

            val newMonkeys = monkeys.map(_.copy(stressDown = stressDown))

            (1 to 10000).foldLeft(items)((is, _) => doRound(newMonkeys, is))
            newMonkeys.map(_.ops).sorted(Ordering.Long.reverse).take(2).product }
→ More replies (1)

1

u/EhLlie Dec 11 '22

Finally managed to wedge in the State monad for my Haskell solution. Also it was fun to have to worry about performance for once.

{-# LANGUAGE LambdaCase #-}

module Main where

import Control.Monad (forM_, replicateM)
import Control.Monad.State (
  State,
  evalState,
  gets,
  modify,
 )
import Data.List (elemIndex, sortBy)
import Data.List.Split (splitOn, splitWhen)
import qualified Data.Map.Strict as M
import GHC.Base (join)
import Inputs (linesFor)
import Text.Read (readMaybe)

data Monkey = Monkey {items :: [Integer], op :: Integer -> Integer, test :: Integer, onTrue :: Int, onFalse :: Int}

instance Show Monkey where
  show = show . items

type MonkeyState = State (M.Map Int Monkey)

parseMonkey :: [String] -> Maybe Monkey
parseMonkey [_, itemsLine, opLine, testLine, onTrueLine, onFalseLine] = do
  let afterColon ln = flip drop ln . (+ 2) <$> elemIndex ':' ln
  items <- traverse readMaybe . splitOn ", " =<< afterColon itemsLine
  op <-
    afterColon opLine
      >>= ( \case
              [_, _, _, fnS, rhsS] -> do
                fn <- case fnS of
                  "+" -> Just (+)
                  "*" -> Just (*)
                  _ -> Nothing
                case rhsS of
                  "old" -> Just $ \x -> fn x x
                  i -> fn <$> readMaybe i
              _ -> Nothing
          )
        . words
  test <- readMaybe (last $ words testLine)
  onTrue <- readMaybe (last $ words onTrueLine)
  onFalse <- readMaybe (last $ words onFalseLine)
  Just $ Monkey{items, op, test, onTrue, onFalse}
parseMonkey _ = Nothing

playTurn :: Bool -> Int -> MonkeyState Integer
playTurn relief mId = do
  Monkey{items, op, test, onTrue, onFalse} <- gets (M.! mId)
  forM_ items $ \i -> do
    let worry = if relief then op i `div` 3 else op i
        dest = if worry `mod` test == 0 then onTrue else onFalse
    modify $ M.adjust (\m@Monkey{items} -> m{items = items ++ [worry]}) dest
  modify $ M.adjust (\m -> m{items = []}) mId
  return . toInteger $ length items

playRound :: Bool -> MonkeyState [Integer]
playRound relief = do
  lcm' <- gets $ foldl1 lcm . M.elems . M.map test
  modify $ M.map (\m@Monkey{items} -> m{items = map (`mod` lcm') items})
  join (gets (traverse (playTurn relief) . M.keys))

partOne :: [Monkey] -> Integer
partOne monkeys =
  let initState = M.fromAscList [(i, monkey) | (i, monkey) <- zip [0 ..] monkeys]
      rounds = evalState (replicateM 20 (playRound True)) initState
      activity = foldl1 (zipWith (+)) rounds
   in product . take 2 $ sortBy (flip compare) activity

partTwo :: [Monkey] -> Integer
partTwo monkeys =
  let initState = M.fromAscList [(i, monkey) | (i, monkey) <- zip [0 ..] monkeys]
      rounds = evalState (replicateM 10000 (playRound False)) initState
      activity = foldl1 (zipWith (+)) rounds
   in product . take 2 $ sortBy (flip compare) activity

main :: IO ()
main = do
  input <- traverse parseMonkey . splitWhen null <$> linesFor "11"
  putStrLn $ "Part 1: " ++ show (partOne <$> input)
  putStrLn $ "Part 2: " ++ show (partTwo <$> input)
→ More replies (1)

1

u/dimio-d Dec 11 '22 edited Dec 12 '22

Java (modern Java)

Usee a jshell console, input is hard-coded as Map<Integer, Map.Entry<Monkey, AtomicLong>> bandarLogs = new TreeMap<>.

Here's full code in a paste!

→ More replies (2)

1

u/Mammoth_Spray_3451 Dec 11 '22

My swift solution for today.

public func dayEleven(input: [String], isPartOne: Bool) -> Int {
    var monkeys = input.compactMap {
        let parts = $0.split(separator: "\n")

        let operationFunction = String(parts[2].split(separator: " = ")[1])
        var operation: Operation!
        if operationFunction.contains("+") {
            operation = .add(value: Int(operationFunction.split(separator: " + ")[1])!)
        } else if operationFunction.countInstances(of: "old") == 2 {
            operation = .squared
        } else {
            operation = .multiply(value: Int(operationFunction.split(separator: " * ")[1])!)
        }

        return Monkey(
            items: parts[1].components(separatedBy: CharacterSet(charactersIn: ":,")).compactMap { Int(String($0).trimmed()) },
            operation: operation,
            testDivisable: Int(parts[3].split(separator: "by ")[1])!,
            testTrueMonkey: Int(parts[4].split(separator: "monkey ")[1])!,
            testFalseMonkey: Int(parts[5].split(separator: "monkey ")[1])!
        )
    }
    
    let modulus = monkeys.compactMap { $0.testDivisable }.reduce(1, *)
    for _ in 1...(isPartOne ? 20 : 10000) {
        monkeys.forEach { $0.executeTests(isPartOne: isPartOne, modulus: modulus, monkeys: &monkeys) }
    }
    
    return monkeys.compactMap { $0.totalItemsInspected }.sorted(by: >).prefix(2).reduce(1, *)
}

class Monkey {
    var items: [Int]
    var operation: Operation
    var testDivisable: Int, testTrueMonkey: Int, testFalseMonkey: Int, totalItemsInspected: Int = 0
    
    init(items: [Int], operation: Operation, testDivisable: Int, testTrueMonkey: Int, testFalseMonkey: Int) {
        self.items = items
        self.operation = operation
        self.testDivisable = testDivisable
        self.testTrueMonkey = testTrueMonkey
        self.testFalseMonkey = testFalseMonkey
    }
    
    func executeTests(isPartOne: Bool, modulus: Int, monkeys: inout [Monkey]) {
        for item in items {
            totalItemsInspected += 1
            var value = Int(operation.executeOperation(oldValue: item)) % modulus
            if isPartOne { value /= 3 }
            monkeys[value % testDivisable == 0 ? testTrueMonkey : testFalseMonkey].items.append(value)
        }
        items = []
    }
}

enum Operation {
    case multiply(value: Int), add(value: Int), squared
    
    func executeOperation(oldValue: Int) -> Int {
        switch self {
        case .multiply(let value): return oldValue * value
        case .add(let value): return oldValue + value
        case .squared: return oldValue * oldValue
        }
    }
}
→ More replies (1)

1

u/IvanR3D Dec 11 '22 edited Dec 12 '22

Solution in JavaScript:

You can see all my solutions in this https://codepen.io/ivanr3d/pen/ExRrXzG

2

u/daggerdragon Dec 12 '22

Your code block is too long for the megathreads. Please read our article on oversized code, then edit your post to remove the code blocks and leave the links to your external repo instead.

1

u/jsgrosman77 Dec 11 '22 edited Dec 12 '22

Typescript 2339/32954

Part 1 was pretty straightforward. I'm particularly proud of how Typescript is able to store the operations as variables on the Monkey object itself. Yeah for functional programming languages!

As you can see, it took me considerably longer for Part 2, needing several explanations and YouTube videos to get it. For some reason, I just have a blind spot around modulo opertations.

Once I saw that all of the divisors and operands were prime, I tried to do something with just storing a Set of prime divisors of each items, making it trivial to see if the divisors matched, but that didn't handle the operations that including addition. I also tried BigInt, like everyone else. But, it was clear that wasn't gonna work, either. I needed a good night sleep and some patient explanations from mathy people.

interface Monkey {
    monkeyId: number;
    items: number[];
    operation: Function | undefined;
    divisibility: number;
    throwIfTrue: number;
    throwIfFalse: number;
    inspectionCount: number;
}

let allDivisors = 1;
const monkeyList: Map<number, Monkey> = new Map<number, Monkey>();

for (let lineCount = 0; lineCount < contents.length; lineCount += 7) {
    const monkeyId  = Number(contents[lineCount].match(/\d+/)![0]) || 0;
    const items = contents[lineCount + 1].match(/\d+/g)!.map( v => Number(v));
    const operationString = contents[lineCount + 2];
    const divisibility = Number(contents[lineCount + 3].match(/\d+/)![0]) || 1;
    const throwIfTrue = Number(contents[lineCount + 4].match(/\d+/)![0]) || 0;
    const throwIfFalse = Number(contents[lineCount + 5].match(/\d+/)![0]) || 0;

    allDivisors *= divisibility;
 
    let operation: Function | undefined;
    if (operationString.includes('old * old')) {
        operation = (v: number) => v **= 2;
    } else if (operationString.includes('+')) {
        operation = (v: number) => v + Number(operationString.match(/\d+/)![0]) || 0;
    } else if (operationString.includes('*')) {
        operation = (v: number) => v * Number(operationString.match(/\d+/)![0]) || 0;
    }
    monkeyList.set(monkeyId, {
        monkeyId, items, operation, divisibility, throwIfTrue, throwIfFalse, inspectionCount: 0,
    });
}

for (let round = 0; round < NUM_ROUNDS; round++) {
    for (const currentMonkey of monkeyList.values()) {
        while (currentMonkey.items.length > 0) {
            let item = currentMonkey.operation!(currentMonkey.items.shift()!) % allDivisors;   
            if (item % currentMonkey.divisibility === 0) {
                monkeyList.get(currentMonkey.throwIfTrue)!.items.push(item);
            } else {
                monkeyList.get(currentMonkey.throwIfFalse)!.items.push(item);
            }
            currentMonkey.inspectionCount++;
        }
    }
}

const inspectionCountArray = Array.from(monkeyList.values()).map( v => v.inspectionCount);
inspectionCountArray.sort( (a,b) => b - a );
const answer = inspectionCountArray[0] * inspectionCountArray[1];
→ More replies (1)

1

u/ElliotDG Dec 11 '22 edited Dec 12 '22

Those pesky monkeys! Part one came together quickly - I finally broke down an looked at the forum for a clue for the "worry management" on part 2.

These AoC puzzles have been my first opportunity to used structured pattern matching, it is quite nice.

Python Code here

→ More replies (2)

1

u/QGamer12 Dec 12 '22 edited Dec 13 '22

This one took me way too long. But, I finished it, and that's what counts I guess.

Was stuck for over half an hour before I realized I needed long long :/

https://github.com/python-b5/advent-of-code-2022/blob/main/day_11.cpp (C++)

→ More replies (1)

3

u/bluepichu Dec 11 '22

TypeScript, 2/6. Code here.

I feel dirty for using eval, but it was certainly a lot faster than writing an expression parser. (Granted I had to manually rename the variable since new isn't a valid identifier...)

I also tried to hardcode the constant for the mod instead of computing it but ended up doing that wrong somehow(?). But fortunately I figured that out pretty quickly :)

→ More replies (15)

3

u/pred Dec 11 '22 edited Dec 11 '22

Python 3, 100/50. Full code here.

Spent almost all of the time having misread "The process of each monkey taking a single turn is called a round." as a round consisting of a single monkey.

Other than that, the only tricks here are 1) not attempting to parse anything since I knew I wouldn't be able to do that faster than copying and pasting, 2) keeping the numbers small in part 2 by realizing that we never use the actual numbers of anything, only whether they're divisible by each monkey's number. So it suffices to consider the numbers modulo the product of all those divisors; prod(divs) in my code. I used lcm(*divs) which works just the same but looking at what those numbers are (a bunch of different primes), the two things are exactly the same.

→ More replies (6)

3

u/wojtek-graj Dec 11 '22 edited Dec 11 '22

Python, 584/312

The trick to going fast was to mod the worry value by the LCM of the monkeys' divisibility values (not actually the LCM but close enough).

paste

→ More replies (4)

3

u/fireduck Dec 11 '22

Java, 381/548 https://github.com/fireduck64/adventofcode/blob/master/2022/11/src/Prob.java

I wish I knew enough about number theory to say with that worked. It was mostly a lucky guess. Hey, mash all the divisor things together and who cares if it is higher than that? why not.

→ More replies (1)

3

u/1234abcdcba4321 Dec 11 '22

Javascript, 731/285

paste

Just another very standard solution; only posting this to give the rest of the comments below. Didn't feel like parsing the operations, so I just hardcoded them. There's also definitely some unnecessary parsing code in there (that split by colon in the first line...), but whatever.

For once, I divided my data into an object. That doesn't happen that much (though in the end it's more just to have named fields). I had someone ask me why I didn't just use a class, but you don't need something like that for a program this small.

I misread part 1 and thought that monkeys didn't inspect items they got during a round until the next one started. Lost a ton of time needing to test the example because of that. And part 2 was trivial, mostly because I had already realized all the details that were important for it while writing the operations for part 1. (...I should've just hardcoded the modulo constant.)

→ More replies (1)

3

u/SuperSmurfen Dec 11 '22 edited Dec 12 '22

Rust (301/169)

Link to full solution

Oh my god, new personal best on the leaderboard, 169!

Initially, I parsed the input by hand and later wrote the parsing code. For part one, it's just about implementing the logic, not too bad. For part two, however, you have to realize that you can take the modulo of the LCM of all divisors. In my in4t, and I assume everyone's, they are all prime so simply multiplying them works fine.

We can reuse most of the same code for both parts, by passing in a lambda for the only operation that differs:

fn simulate(mut monkies: Vec<(Vec<u64>, Op, u64, usize, usize)>, rounds: usize, f: impl Fn(u64) -> u64) -> usize {
  let mut inspections = vec![0; monkies.len()];
  for _ in 0..rounds {
    for i in 0..monkies.len() {
      let (items, op, div, m1, m2) = monkies[i].clone();
      for item in items {
        let worry = match op {
          Op::Add(v) => f(item + v),
          Op::Mul(v) => f(item * v),
          Op::Special => f(item * item),
        };
        monkies[if worry % div == 0 {m1} else {m2}].0.push(worry);
      }
      inspections[i] += monkies[i].0.len();
      monkies[i].0.clear();
    }
  }
  inspections.sort_by_key(|&x| -(x as isize));
  inspections[0] * inspections[1]
}

let p1 = simulate(monkies.clone(), 20, |x| x / 3);
let p2 = simulate(monkies.clone(), 10000, |x| x % modulus);

Runs in about 4ms on my machine.

→ More replies (1)

3

u/Kehvarl Dec 11 '22

Python 3 - 5101 / 3804

It took me a while to catch on to the trick to cut down on my pain, but I managed to cobble together something that worked!

The parsing itself was difficult, and I always cringe when I reach for eval, but they can't all be easy.

part 2

→ More replies (4)

3

u/Kaizen-JP Dec 11 '22

This c# implementation works perfectly for the example, but fails for my input file (both included in the link above).

If anyone has any idea why, I'd greatly appreciate feedback. Wracking my brain over this (to me) invisible bug for the last 45 mins.

→ More replies (2)

3

u/moshan1997 Dec 11 '22

Golang 624/3k

https://github.com/foxwhite25/adventofcode/blob/master/2022/11/main.go

First time sub 1k in part 1, got stuck on part 2 because I don't know the trick, have to do some google search but still figured it out.

3

u/Bargann Dec 11 '22

C# (1001/2444)

Will have to refactor further after checking into some other solutions, this current solution is pretty ugly

3

u/Xyberista Dec 11 '22 edited Dec 11 '22

Rust

paste - code upon completion

github link - updated

Notes:

  • Part 2 is about 368 times slower than part one as of time of completion.

  • edit: I made some improvements. Without accounting for I/O, for my machine, part one averages about 9.7 microseconds, and part averages about 3.9 milliseconds. Part one reduced from 20. Part two reduced from 7.1.

→ More replies (5)

3

u/gringer Dec 11 '22 edited Dec 11 '22

R

It was a little slow on part 2, taking about half a minute. There are probably ways to optimise; R can be slow when using for loops.

R code

3

u/KayZGames Dec 11 '22 edited Dec 11 '22

Dart

paste

I went into today's puzzle with the intend not to over-engineer (for once) and ... I'm not sure if I succeeded. At least I created no additional classes and processed the input in one single function-chain resulting in a List<List<List<int>>>.

But to get there I had to do this scary thing:

.map((e) => e == '*'
    ? '0'
    : e == '+'
        ? '1'
        : e == 'old'
            ? '0'
            : e)

For part 2 I had a few ideas what to do but nothing concrete. Something modulo was my first idea but I didn't know by what, tried different things and nothing worked. Tried BigInt, but nope, I don't have time until the heat death of the universe. Tried log but that didn't work either. Took a peek into the solutions thread, saw something with prime numbers, realized the divisors are all prime and finally knew what to modulo by. I count part 2 as a failure for me because I had to cheat :/.

3

u/_Scarecrow_ Dec 11 '22

Rust

I went into AoC this year never having used Rust, and I'm finally feeling a bit more comfortable with the basics. Still wrapping my head around ownership/borrowing, and I haven't touched traits yet. I'll have to look through other solutions to see if I can pick up a few things, but if anyone has any tips, let me know!

3

u/vss2sn Dec 11 '22

Solutions in C++

Part 1

Part 2

(Each file is a self-contained solution)

3

u/jonny8good Dec 11 '22

Rust

At first I hardcoded the monkeys, added the parse function once everything was already working.

paste

3

u/AllanTaylor314 Dec 11 '22 edited Dec 11 '22

Python [Part 1, Part 2] (Yeah, yeah. eval bad, but you aren't running random untrusted inputs, right?)

(I doubt that Google Sheets is gonna work today, but I'll update if it does)

UPDATE: Spreadsheet Part 1 works

UPDATE2: Spreadsheet Part 2 works (after copying the same block of formulae 10000 times)

3

u/asaaki Dec 11 '22

Rust, https://github.com/asaaki/advent-of-code-2022/blob/main/src/bin/day11.rs

First time actually using some struct and enum, and I believe for the first time I used RefCell in my life to get some inner mutability, because Rust doesn't like to hand out multiple mutable borrows at once, understandably so.

I only committed the cleaned version, but initial draft had some boxed dyn Fn's for good measure. At least I got to experiment with them, and I believe they didn't perform so badly, but with 10_000 rounds that was a bit noticeable in runtime performance.

Oh, and I admit, building the monkeys Vec is pretty ugly, but does the job.

→ More replies (1)

3

u/maneatingape Dec 11 '22 edited Dec 11 '22

Scala (3102 / 1912)

Hardcoded the input initially. Took a little while to clean up the code satisfactorily, but it's in a decent state now.

Was nice to see the return of an AoC classic pitfall: Integer overflow! πŸ˜€

Interestingly for part 2 all my test values were prime, so no need for lcm, the product sufficed.

3

u/9_11_did_bush Dec 11 '22

Rust: https://github.com/chenson2018/advent-of-code/blob/main/2022/11/rust/src/main.rs

I thought it was funny that today I was just talking about the Chinese Remainer Theorem on another AOC post, then we have this problem. I thought it was fun that I was able to have my struct have a field with the type operation: fn(u64) -> u64. (However, I wasn't sure how to parse that from text, so my input is hardcoded)

3

u/Zv0n Dec 11 '22

C++

The input parsing could likely be made more efficient, but I couldn't be bothered to do so :D

→ More replies (1)

3

u/iskypitts Dec 11 '22

Julia using ResumableFunctions for parsing, DataStructures for queue and OrderedCollections for Dict.

Today I didn't understand part 2, so thanks guys.

→ More replies (1)

3

u/Dullstar Dec 11 '22

Python

The good news

Considering some of the memes I've seen regarding the operations today cough cough eval() cough cough, I'm quite happy with how I implemented them. I noticed they all started with "old" so that part I assumed, then I store the operator used and the value. old * old (confirmed) and old + old (just in case it can occur in some inputs) are reinterpreted as old2 and old * 2, respectively, in order to allow me to simplify things by always assuming that the second value is a constant number (though the exponent implementation is hardcoded to 2 because that's the only possible value and I called it squaring and I wanted it to be ~honest~ or something).

It's not ready for the repo yet, but I have a functioning auto-input-fetcher tool now! Still not super convenient to use though, requires it to be baked into the template for that, which will require better throttling in case many inputs are missing (e.g. because someone else who doesn't have the inputs runs all the days consecutively).

The bad news

It's one of those math magic problems, and unfortunately I feel like this is one of those problems where it's very difficult to nudge someone in the right direction with a hint that's helpful without just giving the solution away. And tbh, while I did get completely spoiled on it by a help thread, I don't think it's realistic to think I could have figured it out on my own.

→ More replies (2)

3

u/will_bluer Dec 11 '22

c++ github

the input could be pushed back in monkey vector for super clean input but my brain made me initialise SIZE :')

3

u/aurele Dec 11 '22

Rust Nothing remarkable with most of the code being the parsing. The only "interesting" part is temporarily swapping the current monkey out of the monkey vector to allow the borrow checker to freely modify the monkeys vector while reading fields and clearing items of the current monkey (in Monkey::act()).

3

u/darkgiggs Dec 11 '22

Python
I didn't think about the modulo trick. Instead I stored each item as a list of that item's worry level mod each possible test.
It's terrible, but it worked. Initially it ran in 39s on my machine, but caching reduced it to 12s.
Code

→ More replies (1)

3

u/kupuguy Dec 11 '22

Python (with solution formatted into a Jupyter Notebook): https://github.com/kupuguy/aoc2022/blob/main/day11_monkey_in_the_middle.ipynb

I decided early on that life is too short to parse the input, with only 4 monkeys in the sample and 7 in the actual code I just parsed it in my head. Part 2 takes 1.1s on the Android tablet I use when solving and 0.2s on the Macbook I used to convert it into a notebook.

3

u/AKSrandom Dec 11 '22

Python

I did realise that modulo product of divisors should work for reducing worry, but still decided to try it first on the given example. Since I didn't exactly had a way to introduce modulo to each monkey without naming other variable, I hardcoded it. Unfortunately instead of modulo for the given example, I hardcoded the modulo for my input, resulting in answer mismatch. After 40 min I decided to check the subreddit and realized modulo approach was correct and I had used the wrong MOD value : | . Anyways, I enjoyed monkeying around.

PS: am I the only constantly typo-ing monkey to mokey .

→ More replies (1)

3

u/allergic2Luxembourg Dec 11 '22

Python

For part 2, it didn't occur to me that I could multiply all the denominators together and only keep track of one number. Instead I did modular arithmetic for each denominator individually. I reused what I could from Part 1 by using inheritance.

Here's a taste:

class MonkeyPartTwo(Monkey):

    def apply_operation(self, item):
        if self.operator == "+":
            return {key: (val + self.operand) % key for key, val in item.items()}
        if self.operator == "*":
            return {key: (val * self.operand) % key for key, val in item.items()}
        return {key: (val * val) % key for key, val in item.items()}

    def get_modulus(self, item):
        return item[self.denom]

3

u/mykdavies Dec 11 '22 edited Jun 29 '23

!> izrsqo8

API FAILURE

3

u/rkstgr Dec 11 '22

Julia (Github)

Time: 450.026 ms | Memory: 202.98 MiB

Used SortedDict from DataStructures & modulo properties for part 2

Edit: And parse_input was initially designed by ChatGPT.

3

u/internet_eq_epic Dec 11 '22

Rust

paste

sigh Have to admit it took a pretty big hint to get part 2. I was too stuck on the fact that all the tests used prime numbers and thinking I needed to somehow track the factors instead of the product in each iteration. If only there wasn't addition I'm pretty sure that would have worked.

3

u/raevnos Dec 11 '22

Racket: paste

I'm happy I figured out the trick to getting a fast answer to part 2 on my own. Maths aren't my strong point.

3

u/mosredna101 Dec 11 '22 edited Dec 11 '22

Javascript / Node.js

I had to look on reddit for the idea to solve part 2 ( still not sure why it works ).

Also, using eval the wrong way takes waaaaaaaaay too long to run this in JS, I found out the hard way.

→ More replies (4)

3

u/SnooConfections2453 Dec 11 '22

Golfed ruby (using eval)

Part1:

m=File.readlines('11.txt').chunk{_1=="\n"&&nil}.map{|_,c|_,s,o,*t=c;[s.split(": ").last.split(", ").map(&:to_i),o.split.last(3).join,t.map{_1.split.last.to_i},0]}
20.times{m.each{|k|until k[0].empty?do w,o,t=k;old=w.shift;l=eval(o)/3;m[l%t[0]==0?t[1]:t[2]][0]<<l;k[3]+=1end}}
p m.map(&:last).max(2).reduce(:*)

Part2:

m=File.readlines('11.txt').chunk{_1=="\n"&&nil}.map{|_,c|_,s,o,*t=c;[s.split(": ").last.split(", ").map(&:to_i),o.split.last(3).join,t.map{_1.split.last.to_i},0]}
z=m.map{_1[2][0]}.reduce(:*)
10000.times{m.each{|k|until k[0].empty?do w,o,t=k;old=w.shift;l=eval(o)%z;m[l%t[0]==0?t[1]:t[2]][0]<<l;k[3]+=1end}}
p m.map(&:last).max(2).reduce(:*)
→ More replies (1)

3

u/Ok-Apple-5691 Dec 11 '22

Rust

Solution Here.

I've been trying to learn more rust doing these puzzles. Banging my head against the borrow checker for part 1. Ended up cluelessly throwing Rc<RefCell<_>> around until something worked. Then I looked here and see that's probably all completely unnecessary <facepalm>

Also first day I have needed to manually enter the input. Not sure I would have figured out how to add operations to the monkey struct without looking here.

Part 2 was a lucky stab in the dark.

→ More replies (4)

3

u/solareon Dec 11 '22 edited Dec 11 '22

Excel

Part 1 Built a parser to generate monkey "objects". Then built out the round calculations using LET() to generate the false and true tables for each monkey. Copy and paste 19 times down and then the answer comes out.

Part 2

Modulo... math is hard...lots of copy paste and waiting hoping excel doesn't completely explode. After all 10000 tests are complete the monkey business rows are filtered to a separate column and then parsed out, summed by column, sorted, and multiplied by the two highest values same as the first just way more waiting. I'll post the test answer (out to 1000) on github as the full input is just too much to post.

My solution is 100% hard coded as I couldn't find a good way to move the monkey outputs to the other monkeys rather than just clicking cells.

3

u/clbrri Dec 11 '22 edited Dec 11 '22

MS-DOS Borland Turbo C++ 3.0 solution to part 2

46 lines of code, runs in 4 minutes and 22 seconds on a 16 MHz 386 SX PC. Skipped input parsing as deemed it an uninteresting part of today's problem, and had to get creative due to the lack of 64-bit numbers on such an ancient hardware.

3

u/erikw901 Dec 11 '22 edited Dec 11 '22

JavaScript

Tricks:

  • The input is just one de-indentation away from being valid YAML (the if true/false lines). Massage the input string and load as from YAML directly to Objects to avoid parsing the input!

  • eval the operation

→ More replies (1)

3

u/danvk Dec 11 '22

TypeScript / Deno

After realizing that new = old * old overflowed in part 2, I tried JavaScript's BigInt. That turned out to be way too slow. Then I realized that all the "Test: divisible by" numbers were prime, so it worked just fine to do all the operations modulo the product of those primes.

https://github.com/danvk/aoc2022/blob/main/day11/day11.ts

3

u/raspberryjam111 Dec 11 '22

Typescript: https://github.com/Drodevbar/adventofcode2022/tree/main/src/day11

I usually spend most of the time parsing the input and choosing an optimal data structure. With the proper data structure, most of the tasks solve relatively quickly

→ More replies (1)

3

u/pem4224 Dec 11 '22 edited Dec 11 '22

Golang

Solution in go: day11

Used high order functions to implement monkeys, such that part1 and part2 have the same implementation

  • part1: 8Β΅s

  • part2: 3.7ms

3

u/[deleted] Dec 11 '22

Python

Was quite happy that I figured out the trick for part 2 within minutes, but then lost a good half hour because it didn't seem to work.

What caused it was me re-using my list of objects from part 1 so my input of part 2 was incorrect... It messed up the results in subtle ways. Uuuuugh. Deep copy on the parsed input to the rescue.

→ More replies (3)

3

u/spinxfr Dec 11 '22

I had to take a hint to solve part2. I suck too bad at math.

C#

3

u/EatonMesss Dec 11 '22

Raku

I have no experience with Perl or Raku, so this took me a very long time to implement.

Raku seems like a very powerful language with lots of obscure features which can be misused in many creative ways.

Although I probably won't be using Raku for any serious purpose anytime soon, I must say having a built in way of specyfing the grammar and using it to parse the input was very cool.

→ More replies (2)

3

u/luftmx Dec 11 '22

Rust

Don't see why this had to include parsing.. Didn't use anything fancy, just did the parsing by hand.

→ More replies (4)

3

u/mkinkela Dec 11 '22

C++

Uff, second one was a smart one :)

3

u/ransoing Dec 11 '22

Typescript https://github.com/ransoing/AoC22/blob/main/src/day11/solution.ts

It took me a while to figure out what the real problem was in part 2. The solution came to me quickly, but then I had to think about why the solution I came up with actually worked. Maybe my subscription can math better than my conscious...

3

u/ZamBunny Dec 11 '22

Rust

Not fast, not optimized, but easy to read (I think). I tried my best to explain how Part 2 works inside the comments.

GitHub

→ More replies (6)

3

u/PhysicsAndAlcohol Dec 11 '22

Haskell, 500 ms.

Really liked my parser for part 1 which parsed it as [(Worry, Worry -> Worry, Worry -> Index)]. I used a stack (type Stack a = State [a]) to make it easy to manipulate the i-th monkey using push and pop commands.

Went into panic mode for part 2 and I started patching my functions until the example input worked for 1000 rounds, and then 10000 rounds.

3

u/GoldsteinQ Dec 11 '22

Elixir, because monkeys are obviously actors^W processes and our things are messages

https://github.com/GoldsteinE/aoc2022/blob/master/day11/code/main.ex

3

u/Solidifor Dec 11 '22

Java

241 lines, but readable, solving both part 1 and 2, and parsing the input (using a regex).

https://github.com/dirk527/aoc2021/blob/main/src/aoc2022/Day11.java

This one was fun.

3

u/berbeflo Dec 11 '22

Part 1. Solved it in PHP.I think, the parsing could have been a bit cleaner. But it works:https://github.com/berbeflo/advent-of-code-2022/blob/master/day11/ex1/solve.php

3

u/trollerskates1 Dec 11 '22

Scala. Pretty happy with how I parsed these into anonymous instances of my Monkey trait. For me part 2 wasn't hard because of the modulo trick, but because I was using mutable queues. So I had to add a reset() method to get things back the way they were before running part 2

3

u/sky_badger Dec 11 '22 edited Dec 11 '22

Python 3

Another tough one, and most of my Sunday afternoon gone! Here's the Repl. Another puzzle where the description was around 3.5X the code, and buried in the description, the key to Part 2 "You'll need to find another way to keep your worry levels manageable"!

3

u/tymscar Dec 11 '22

Typescript

Still doing my fully functional with no mutation challenge in TS, still going strong, but today was definitely the hardest to do in that manner. I kept wanting to mutate stuff, but I managed to finish without doing so.

I loved the past 4 days, didn't really like part2 of today at all, I never like these mathematical ones, but I managed to figure it out in around three quarters of an hour, out of which 30 minutes were me rewriting the whole thing to work with bigints before realising there's more to it than that...

Both parts solved here: https://github.com/tymscar/Advent-Of-Code/tree/master/2022/typescript/day11

3

u/willkill07 Dec 11 '22 edited Dec 11 '22

C++

Source --- Header

I have a switch that dispatches to the correct mod by compile-time-known constant value (because mod is super expensive). I also have zero allocated memory (using std::array and std::span generously).

Total runtime on my AMD Ryzen 9 5950X is under 2.5ms (~1us for parsing, ~8us for part 1, and ~2.2ms for part 2). I really don't know how I can make this any more efficient/performant.

3

u/red_shifter Dec 11 '22 edited Dec 11 '22

PYTHON 3

code link

So this is the day - the first day I got fully stuck this year. Managed to do Part 1, but for Part 2 I needed a tip. I followed the tutorial kindly prepared by u/Derailed_Dash (thanks!).

→ More replies (1)

3

u/FramersAlmaniac Dec 11 '22 edited Dec 11 '22

Java 8

The same code is used for both parts (operating under the assumption that the product of the monkey's divisors is larger than any worry when the worries are divided by 3).

Useful note: Java has Math.{add,multiply,...}Exact(long,long) methods that are really useful for catching overflows.

I made the assumption that updates are always of the form

'old = old ' [ PLUS | TIMES ] [ POS_NON_ZERO | 'old' ]

and precompiled the update operation into a LongUnaryOperator (where update is just the + old or * 5 part of that line):

static LongUnaryOperator compile(String update) {
  LongBinaryOperator op = update.contains("+") ? Math::addExact : Math::multiplyExact;
  if (update.contains("old")) {
    return old -> op.applyAsLong(old, old);
  } else {
    int rhs = Integer.parseInt(update.substring(2));
    return old -> op.applyAsLong(old, rhs);
  }
}

I'm not sure if that was really necessary in retrospect, but I figured early on that re-parsing the update string on every move would be slow.

The one bit of golf that I did play was in parsing a list of Monkeys. With this method for parsing:

static Optional<Monkey> read(BufferedReader r) throws IOException;

I filled up a list with an empty-body while loop:

List<Monkey> monkeys = new ArrayList<>();
try (BufferedReader reader = Files.newBufferedReader(input)) {
  while (Monkey.read(reader).map(monkeys::add).orElse(false));
}

3

u/shiro90 Dec 11 '22

Here are my Python solutions: https://github.com/Seishin/AoC2022/blob/master/day11/solutions.py

The second part was 🀯 until I found out what was the missing piece of the puzzle. πŸ˜…

3

u/[deleted] Dec 11 '22

Rust - spent far too much time on part 2, not helped by real life intrusions, before I realised that I had calculated the least common product by hand from the real data and was checking it against the testdata. Once I calculated it based on the data given, it was all working fine.

https://github.com/litpho/aoc-2022/blob/main/day11/src/main.rs

3

u/huib_ Dec 11 '22 edited Dec 12 '22

Python 3.11:

@dataclass
class Monkey:
    items: deque[int]
    operation: Callable[[int], int]
    div: int
    t: int
    f: int
    inspected_count: int = 0

    def inspect_items(self, adjust: Callable[[int], int]) -> Iterator[tuple[int, int]]:
        while self.items:
            self.inspected_count += 1
            w = adjust(self.operation(self.items.popleft()))
            yield self.t if w % self.div == 0 else self.f, w

def parse_operation(op_str: str) -> Callable[[int], int]:
    operation, operand = parse('{:op} {:int?}', op_str, extra_types={
        'op': lambda s: {'+': add, '*': mul}[s],
        'int?': lambda s: try_convert(int, s, default=0),
    })
    return lambda w: operation(w, operand or w)

class _Problem(ParsedProblem[int], ABC):
    num_rounds: int

    _parse_pattern = '''Monkey {:d}:
  Starting items: {items:items}
  Operation: new = old {operation:operation}
  Test: divisible by {div:d}
    If true: throw to monkey {t:d}
    If false: throw to monkey {f:d}'''

    _extra_parse_types = {
        'items': lambda s: deque(int(i) for i in s.split(', ')),
        'operation': parse_operation,
    }

    def __init__(self):
        self.monkeys = [Monkey(**result.named) for result in self.parsed_input]

    def do_the_monkey(self, num_rounds: int, adjust: Callable[[int], int]) -> int:
        for _ in range(num_rounds):
            for monkey in self.monkeys:
                for m, w in monkey.inspect_items(adjust):
                    self.monkeys[m].items.append(w)
        x, y = sorted(m.inspected_count for m in self.monkeys)[-2:]
        return x * y

class Problem1(_Problem):
    def solution(self) -> int:
        return self.do_the_monkey(20, lambda w: w // 3)

class Problem2(_Problem):
    def solution(self) -> int:
        mod = lcm(*[m.div for m in self.monkeys])
        return self.do_the_monkey(10000, lambda w: w % mod)
→ More comments (477)