9 votes

Day 11: Monkey in the Middle

Today's problem description: https://adventofcode.com/2022/day/11

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

5 comments

  1. primordial-soup
    Link
    Part 1, in Python-ish 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...
    Part 1, in Python-ish
    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)
    
    Python code generated from the above
    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)
    
    Part 2, in Python-ish
    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)
    
    Python code generated from the above
    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)
    
    3 votes
  2. Crestwave
    Link
    We just can't catch a break, huh. This had quite a few rules, and some worrying moments. But it was fun and never got too overwhelming as everything is pretty tidy despite all the monkey business....

    An operation like new = old * 5 means that your worry level after the monkey inspected the item is five times whatever your worry level was before inspection.

    We just can't catch a break, huh.

    This had quite a few rules, and some worrying moments. But it was fun and never got too overwhelming as everything is pretty tidy despite all the monkey business.

    Part 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 {
    	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])
    }
    
    Part 2
    #!/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])
    }
    
    2 votes
  3. bhrgunatha
    Link
    Data Structures 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...
    Data Structures

    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))
    
    Part 1
    (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)))
    
    Part 2 So you get the refactored code, which makes part 2 look very much like part 1 :) - `values` is the built-in identity function.
    define (part-02 input)
      (define-values (ms limit) (read-monkeys input))
      (monkey-inspection ms 10000 values limit)
      (monkey-business ms)
    
    2 votes
  4. wycy
    Link
    Rust Rust 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:...

    Rust

    Rust
    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();
    }
    
    1 vote
  5. asterisk
    (edited )
    Link
    Python import copy, math, operator, re monkeys = [] for line in open("input.txt").readlines(): line = line.strip() if line.startswith("Monkey"): monkeys.append([]) continue if...
    Python
    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
    
    1 vote