Day 11: Monkey in the Middle

ms = (ls > p
      | (split_at, X, ~(X == ""))
      | fe(p
           | "\n".join
           | (re.match, inspect.cleandoc(
             r"""
             Monkey \d+:
               Starting items: (.*)
               Operation: new = (.*)
               Test: divisible by (\d+)
                 If true: throw to monkey (\d+)
                 If false: throw to monkey (\d+)"""))
           | X.groups()
           | (λ gs: {"ws": gs[0].split(", ") > fe(int) | deque,
                     "op": eval(f"λ old: {gs[1]}"),
                     "mod": int(gs[2]),
                     "br": (int(gs[3]), int(gs[4])),
                     "i": 0}))
      | tuple)
for _ in range(20):
    for m in ms:
        m["i"] += len(m["ws"])
        while m["ws"]:
            w = m["op"](m["ws"].popleft()) // 3
            ms[m["br"][bool(w % m["mod"])]]["ws"].append(w)
ms > fe(X["i"]) | sort | (tail, 2) | (reduce, mul)

from collections import deque
from functools import reduce
from more_itertools import split_at
from more_itertools import tail
from operator import mul
from pipetools import X
from pipetools import foreach
from pipetools import pipe
from pipetools import sort
import inspect
import re
import sys
from pyp import pypprint
p = pipe
fe = foreach
lines = [x.rstrip('\n') for x in sys.stdin]
ls = lines
ms = ls > p | (split_at, X, ~(X == '')) | fe(p | '\n'.join | (re.match, inspect.cleandoc('\n             Monkey \\d+:\n               Starting items: (.*)\n               Operation: new = (.*)\n               Test: divisible by (\\d+)\n                 If true: throw to monkey (\\d+)\n                 If false: throw to monkey (\\d+)')) | X.groups() | (lambda gs: {'ws': gs[0].split(', ') > fe(int) | deque, 'op': eval(f'lambda old: {gs[1]}'), 'mod': int(gs[2]), 'br': (int(gs[3]), int(gs[4])), 'i': 0})) | tuple
for _ in range(20):
    for m in ms:
        m['i'] += len(m['ws'])
        while m['ws']:
            w = m['op'](m['ws'].popleft()) // 3
            ms[m['br'][bool(w % m['mod'])]]['ws'].append(w)
output = ms > fe(X['i']) | sort | (tail, 2) | (reduce, mul)
if output is not None:
    pypprint(output)

ms = (ls > p
      | (split_at, X, ~(X == ""))
      | fe(p
           | "\n".join
           | (re.match, inspect.cleandoc(
             r"""
             Monkey \d+:
               Starting items: (.*)
               Operation: new = (.*)
               Test: divisible by (\d+)
                 If true: throw to monkey (\d+)
                 If false: throw to monkey (\d+)"""))
           | X.groups()
           | (λ gs: {"ws": gs[0].split(", ") > fe(int) | deque,
                     "op": eval(f"λ old: {gs[1]}"),
                     "mod": int(gs[2]),
                     "br": (int(gs[3]), int(gs[4])),
                     "i": 0}))
      | tuple)
mod = ms > fe(X["mod"]) | as_args(lcm)
for _ in range(10_000):
    for m in ms:
        m["i"] += len(m["ws"])
        while m["ws"]:
            w = m["op"](m["ws"].popleft()) % mod
            ms[m["br"][bool(w % m["mod"])]]["ws"].append(w)
ms > fe(X["i"]) | sort | (tail, 2) | (reduce, mul)

from collections import deque
from functools import reduce
from math import lcm
from more_itertools import split_at
from more_itertools import tail
from operator import mul
from pipetools import X
from pipetools import as_args
from pipetools import foreach
from pipetools import pipe
from pipetools import sort
import inspect
import re
import sys
from pyp import pypprint
p = pipe
fe = foreach
lines = [x.rstrip('\n') for x in sys.stdin]
ls = lines
ms = ls > p | (split_at, X, ~(X == '')) | fe(p | '\n'.join | (re.match, inspect.cleandoc('\n             Monkey \\d+:\n               Starting items: (.*)\n               Operation: new = (.*)\n               Test: divisible by (\\d+)\n                 If true: throw to monkey (\\d+)\n                 If false: throw to monkey (\\d+)')) | X.groups() | (lambda gs: {'ws': gs[0].split(', ') > fe(int) | deque, 'op': eval(f'lambda old: {gs[1]}'), 'mod': int(gs[2]), 'br': (int(gs[3]), int(gs[4])), 'i': 0})) | tuple
mod = ms > fe(X['mod']) | as_args(lcm)
for _ in range(10000):
    for m in ms:
        m['i'] += len(m['ws'])
        while m['ws']:
            w = m['op'](m['ws'].popleft()) % mod
            ms[m['br'][bool(w % m['mod'])]]['ws'].append(w)
output = ms > fe(X['i']) | sort | (tail, 2) | (reduce, mul)
if output is not None:
    pypprint(output)

#!/usr/bin/awk -f
function eval(expr, old) {
	gsub(/old/, old, expr)
	split(expr, e, " ")

	if (e[2] == "+")
		return e[1] + e[3]
	else if (e[2] == "-")
		return e[1] - e[3]
	else if (e[2] == "*")
		return e[1] * e[3]
	else if (e[2] == "/")
		return e[1] / e[3]
}

/Monkey/ {
	sub(/:/, "")
	n = $2
}
/Starting/ {
	sub(/.*: /, "")
	items[n] = $0
}
/Operation/ {
	sub(/.*new = /, "")
	expr[n] = $0
}
/Test/ { test[n] = $(NF) }
/If true/ { true[n] = $(NF) }
/If false/ { false[n] = $(NF) }

END {
	for (i = 1; i <= 20; ++i)
		for (j = 0; j <= n; ++j) {
			split(items[j], item, ", ")
			for (k in item) {
				sum[j] += 1
				w = item[k]
				w = eval(expr[j], w)
				w = int(w/3)

				if (w % test[j] == 0)
					l = true[j]
				else
					l = false[j]

				if (items[l])
					items[l] = items[l] ", " w
				else
					items[l] = w
			}

			items[j] = ""
		}
	
	for (i in sum)
		if (sum[i] > max[0]) {
			max[1] = max[0]
			max[0] = sum[i]
		} else if (sum[i] > max[1]) {
			max[1] = sum[i]
		}

	print(max[0] * max[1])
}

#!/usr/bin/awk -f
function eval(expr, old) {
	gsub(/old/, old, expr)
	split(expr, e, " ")

	if (e[2] == "+")
		return e[1] + e[3]
	else if (e[2] == "-")
		return e[1] - e[3]
	else if (e[2] == "*")
		return e[1] * e[3]
	else if (e[2] == "/")
		return e[1] / e[3]
}

/Monkey/ {
	sub(/:/, "")
	n = $2
}
/Starting/ {
	sub(/.*: /, "")
	items[n] = $0
}
/Operation/ {
	sub(/.*new = /, "")
	expr[n] = $0
}
/Test/ { test[n] = $(NF) }
/If true/ { true[n] = $(NF) }
/If false/ { false[n] = $(NF) }

END {
	prime = 1

	for (i in test)
		prime *= test[i]

	for (i = 1; i <= 10000; ++i)
		for (j = 0; j <= n; ++j) {
			split(items[j], item, ", ")
			for (k in item) {
				sum[j] += 1
				w = item[k]
				w = eval(expr[j], w)
				w = w % prime

				if (w % test[j] == 0)
					l = true[j]
				else
					l = false[j]

				if (items[l])
					items[l] = items[l] ", " w
				else
					items[l] = w
			}

			items[j] = ""
		}
	
	for (i in sum)
		if (sum[i] > max[0]) {
			max[1] = max[0]
			max[0] = sum[i]
		} else if (sum[i] > max[1]) {
			max[1] = sum[i]
		}

	print(max[0] * max[1])
}

Each monkey is a struct with 2 mutable fields.
The struct stores:

• seen: inspections count
• items:
• op: the operation
• test: a divisibility test
• pass: who gets the item when the test is true
• fail: who gets the item when the test is false

These monkeys are held in a vector.
op and test are functions take an item value (before or after inspection)

(struct monkey ([seen #:mutable] [items #:mutable] op test pass fail))

(define (part-01 input)
  (define-values (ms limit) (read-monkeys input))
  (monkey-inspection ms 20 reduce-worry limit)
  (monkey-business ms))

(define (reduce-worry n)
  (quotient n 3))

(define (monkey-inspection ms n dont-worry limit)
  (for ([_ (in-range n)])
    (monkey-round ms dont-worry limit)))

(define (read-monkeys input)
  (define limit 1)
  (define ms
    (for/vector ([desc (in-list (groups input))])
      (define-values (m l) (parse-monkey (lines desc)))
      (set! limit (* limit l))
      m))
  (values ms limit))

(define (parse-monkey m)
  (define items (integers (second m)))
  (define op (make-operation (third m)))
  (define div (first (integers (fourth m))))
  (define test (make-test div))
  (define t (first (integers (fifth m))))
  (define f (first (integers (sixth m))))
  (values (monkey 0 items op test t f) div))

(define (make-operation line)
  (match (string-split line)
    [(list _ _ _ _ "*" "old") sqr]
    [(list _ _ _ _ "+" "old") (mul 2)]
    [(list _ _ _ _ "*" n)     (mul (string->number n))]
    [(list _ _ _ _ "+" n)     (plus (string->number n))]
    [_ (error 'parse-operation "bad operation ~a" line)]))

;; each function takes a single item 
(define (sqr n) (* n n))
(define ((plus n) m) (+ n m))
(define ((mul n) m) (* n m))
;; the divisibility test
(define ((make-test n) m) (zero? (remainder m n)))

(define (monkey-round ms reduce-worry limit)
  (for ([m (in-vector ms)])
    (match-define (monkey seen items op test t f) m)
    (set-monkey-seen! m (+ seen (length items)))
    (set-monkey-items! m null)
    (define worry
      (for/list ([item (in-list items)])
        (reduce-worry (modulo (op item) limit))))
    (for ([item (in-list worry)])
      (define target (vector-ref ms (if (test item) t f)))
      (set-monkey-items! target
                         (append (monkey-items target) (list item))))))

(define (monkey-business ms)
  (define seen
    (take (sort (vector->list ms) > #:key monkey-seen) 2))
  (apply * (map monkey-seen seen)))

define (part-02 input)
  (define-values (ms limit) (read-monkeys input))
  (monkey-inspection ms 10000 values limit)
  (monkey-business ms)

use std::env;
use std::io::{self};

extern crate regex;
use regex::Regex;

#[derive(Debug)]
enum Operation {
    Add(i64),
    Multiply(i64),
    Square,
}
#[derive(Debug)]
struct Monkey {
    pub items: Vec<i64>,
    pub operation: Operation,
    pub test_value: i64,
    pub target_true: i64,
    pub target_false: i64,
    pub inspections: i64,
}
impl From<&str> for Monkey {
    fn from(s: &str) -> Self {
        let lines: Vec<_> = s.split("\n").collect();

        // Regexes
        let re_starting  = Regex::new(r"Starting items: ([0-9 ,]+)").unwrap();
        let re_operation = Regex::new(r"Operation: new = old (\+|\*) (old|[\d]+)").unwrap();
        let re_test      = Regex::new(r"Test: divisible by ([\d]+)").unwrap();
        let re_true      = Regex::new(r"If true: throw to monkey ([\d]+)").unwrap();
        let re_false     = Regex::new(r"If false: throw to monkey ([\d]+)").unwrap();

        // Captures
        let starting_captures = re_starting.captures(&lines[1]).unwrap();
        let operate_captures = re_operation.captures(&lines[2]).unwrap();
        let test_captures = re_test.captures(&lines[3]).unwrap();
        let true_captures = re_true.captures(&lines[4]).unwrap();
        let false_captures = re_false.captures(&lines[5]).unwrap();

        // Data extractions
        let starting_items: Vec<i64> = starting_captures[1].split(",").map(|x| x.trim().parse().unwrap()).collect();
        let operation = if &operate_captures[2] == "old" {
            Operation::Square
        } else {
            match &operate_captures[1] {
                "+" => Operation::Add     (operate_captures[2].parse().unwrap()),
                "*" => Operation::Multiply(operate_captures[2].parse().unwrap()),
                other => panic!("Error: Unknown operation {other}"),
            }
        };

        let test_value: i64 = test_captures[1].parse().unwrap();
        let target_true  = true_captures[1].parse().unwrap();
        let target_false = false_captures[1].parse().unwrap();

        // Construct object
        Self {
            items: starting_items,
            operation: operation,
            test_value: test_value,
            target_true: target_true,
            target_false: target_false,
            inspections: 0,
        }
    }
}

fn solve(input: &str, part2: bool) -> io::Result<()> {
    let input_str = std::fs::read_to_string(input).unwrap();
    let input_str = input_str.trim();
    let input: Vec<_> = input_str.split("\n\n").collect();

    // Initialize
    let mut monkeys: Vec<_> = input.iter().map(|x| Monkey::from(*x)).collect();
    let num_monkeys = &monkeys.len();
    let lcm = &monkeys.iter().map(|x| x.test_value).product::<i64>();

    // Turns
    let lcm = &monkeys.iter().map(|x| x.test_value).product::<i64>();
    let rounds = if part2 { 10_000 } else { 20 };
    for round in 0..rounds {
        for m_id in 0..*num_monkeys {
            for item_id in 0..monkeys[m_id].items.len() {
                monkeys[m_id].inspections += 1;
                match monkeys[m_id].operation {
                    Operation::Add(v) => monkeys[m_id].items[item_id] += v,
                    Operation::Multiply(v) => monkeys[m_id].items[item_id] *= v,
                    Operation::Square => monkeys[m_id].items[item_id] *= monkeys[m_id].items[item_id],
                }
                if !part2 { monkeys[m_id].items[item_id] /= 3; }
                let target_monkey = if monkeys[m_id].items[item_id] % monkeys[m_id].test_value == 0 {
                    monkeys[m_id].target_true
                } else {
                    monkeys[m_id].target_false
                };
                if part2 { monkeys[m_id].items[item_id] %= lcm; }
                let item_transferred = monkeys[m_id].items[item_id];
                monkeys[target_monkey as usize].items.push(item_transferred);
            }
            monkeys[m_id].items.clear();
        }
    }

    // Monkey Business
    monkeys.sort_by(|a, b| b.inspections.cmp(&a.inspections));
    let top_two: i64 = monkeys.iter().take(2).map(|x| x.inspections).product();
    let part = if part2 { 2 } else { 1 };
    println!("Part {part}: {top_two}");
    // Part 1: 120384
    // Part 2: 32059801242

    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    solve(&filename,false).unwrap();
    solve(&filename,true).unwrap();
}

import copy, math, operator, re

monkeys = []

for line in open("input.txt").readlines():
    line = line.strip()

    if line.startswith("Monkey"):
        monkeys.append([])
        continue

    if line.startswith("Start"):
        monkeys[-1].append(list(map(int, re.findall("\d+", line))))
        continue

    if line.startswith(("Test", "If")):
        monkeys[-1].append(int(re.search(r"\d+", line).group()))
        continue

    if line == "":
        continue

    monkeys[-1].append(line.split("= old ")[-1].split(" "))

ops = {
    "+": operator.add,
    "-": operator.sub,
    "*": operator.mul,
    "/": operator.truediv,
}


def operation(old, new):
    op, val = new
    val = old if val == "old" else int(val)
    return ops[op](old, val)


def inspecting(isridiculous: bool = True):
    inspectors = copy.deepcopy(monkeys)
    activities = [0] * len(inspectors)
    magic = math.prod([inspector[2] for inspector in inspectors]) if isridiculous else 3

    for _ in range(10_000 if isridiculous else 20):
        for m, (worries, new, isdiv, yeah, nope) in enumerate(inspectors):
            if len(worries) == 0:
                continue

            activities[m] += len(worries)

            for worry in worries:
                worry = operation(worry, new)
                worry = worry % magic if isridiculous else worry // magic
                inspectors[nope if worry % isdiv else yeah][0].append(worry)

            inspectors[m][0] = []

    activities = sorted(activities)
    print(activities[-1] * activities[-2])

inspecting(False) # Part One: 56120
inspecting() # Part Two: 24389045529