summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--input/day11.txt55
-rw-r--r--input/day11_ex.txt27
-rw-r--r--src/day11.rs159
-rw-r--r--src/main.rs4
4 files changed, 245 insertions, 0 deletions
diff --git a/input/day11.txt b/input/day11.txt
new file mode 100644
index 0000000..d7d0e90
--- /dev/null
+++ b/input/day11.txt
@@ -0,0 +1,55 @@
+Monkey 0:
+ Starting items: 91, 54, 70, 61, 64, 64, 60, 85
+ Operation: new = old * 13
+ Test: divisible by 2
+ If true: throw to monkey 5
+ If false: throw to monkey 2
+
+Monkey 1:
+ Starting items: 82
+ Operation: new = old + 7
+ Test: divisible by 13
+ If true: throw to monkey 4
+ If false: throw to monkey 3
+
+Monkey 2:
+ Starting items: 84, 93, 70
+ Operation: new = old + 2
+ Test: divisible by 5
+ If true: throw to monkey 5
+ If false: throw to monkey 1
+
+Monkey 3:
+ Starting items: 78, 56, 85, 93
+ Operation: new = old * 2
+ Test: divisible by 3
+ If true: throw to monkey 6
+ If false: throw to monkey 7
+
+Monkey 4:
+ Starting items: 64, 57, 81, 95, 52, 71, 58
+ Operation: new = old * old
+ Test: divisible by 11
+ If true: throw to monkey 7
+ If false: throw to monkey 3
+
+Monkey 5:
+ Starting items: 58, 71, 96, 58, 68, 90
+ Operation: new = old + 6
+ Test: divisible by 17
+ If true: throw to monkey 4
+ If false: throw to monkey 1
+
+Monkey 6:
+ Starting items: 56, 99, 89, 97, 81
+ Operation: new = old + 1
+ Test: divisible by 7
+ If true: throw to monkey 0
+ If false: throw to monkey 2
+
+Monkey 7:
+ Starting items: 68, 72
+ Operation: new = old + 8
+ Test: divisible by 19
+ If true: throw to monkey 6
+ If false: throw to monkey 0 \ No newline at end of file
diff --git a/input/day11_ex.txt b/input/day11_ex.txt
new file mode 100644
index 0000000..c04eddb
--- /dev/null
+++ b/input/day11_ex.txt
@@ -0,0 +1,27 @@
+Monkey 0:
+ Starting items: 79, 98
+ Operation: new = old * 19
+ Test: divisible by 23
+ If true: throw to monkey 2
+ If false: throw to monkey 3
+
+Monkey 1:
+ Starting items: 54, 65, 75, 74
+ Operation: new = old + 6
+ Test: divisible by 19
+ If true: throw to monkey 2
+ If false: throw to monkey 0
+
+Monkey 2:
+ Starting items: 79, 60, 97
+ Operation: new = old * old
+ Test: divisible by 13
+ If true: throw to monkey 1
+ If false: throw to monkey 3
+
+Monkey 3:
+ Starting items: 74
+ Operation: new = old + 3
+ Test: divisible by 17
+ If true: throw to monkey 0
+ If false: throw to monkey 1 \ No newline at end of file
diff --git a/src/day11.rs b/src/day11.rs
new file mode 100644
index 0000000..8040ccb
--- /dev/null
+++ b/src/day11.rs
@@ -0,0 +1,159 @@
+use std::{str::FromStr, collections::VecDeque};
+
+use regex::Regex;
+use simple_error::{bail, SimpleError};
+
+#[derive(Debug)]
+enum Op { Add, Sub, Mul, Div }
+
+#[derive(Debug)]
+enum Var { C(u64), A }
+
+#[derive(Debug)]
+struct Monkey {
+ items: VecDeque<u64>,
+ op: Op,
+ arg1: Var,
+ arg2: Var,
+ test: u64, // divisible by this number
+ target_true: usize, // monkey to throw to on true
+ target_false: usize, // monkey to throw to on false
+
+ inspections: usize, // how many inspections has this monkey made?
+}
+
+impl Monkey {
+ fn op(self: &Monkey, x: u64) -> u64 {
+ let a: u64 = match self.arg1 {
+ Var::C(c) => c,
+ Var::A => x,
+ };
+ let b = match self.arg2 {
+ Var::C(c)=> c,
+ Var::A => x,
+ };
+ match self.op {
+ Op::Add => a + b,
+ Op::Sub => a - b,
+ Op::Mul => a * b,
+ Op::Div => a / b,
+ }
+ }
+ fn test(self: &Monkey, x: u64) -> bool {
+ x % self.test == 0
+ }
+ fn business(monkeys: &mut [Monkey]) {
+ let worry_level_modulo: u64 = monkeys.iter().map(|m| {m.test}).product();
+ for ix in 0..monkeys.len() {
+ // TODO can probably change this, use a block
+ // to scope the mutable borrow of the first monkey,
+ // and give it back before mutably borrowing the second.
+ // Instead use nightly API usage to get several mutable monkeys
+ let idxs = [ix, monkeys[ix].target_true, monkeys[ix].target_false];
+ let [m, mut mtt, mut mtf] = monkeys.get_many_mut(idxs).unwrap();
+ // Start turn
+ // Inspect all items, one at a time, from the start of the list
+ while let Some(mut i) = m.items.pop_front() {
+ // Increase the count of inspections this monkey has made
+ m.inspections += 1;
+ // Worry level increases...
+ i = m.op(i);
+ // Worry level decreases...
+ // Uh oh, not any more!
+ //i = i / 3;
+ // instead, modulo the worry level by the ...
+ // prod of all the monkeys divisors? to prevent integer overflow,
+ // without changing the result
+ i = i % worry_level_modulo;
+ // Test the item, decide who it goes to
+ let target = if m.test(i) { &mut mtt } else { &mut mtf };
+ // Throw it to the other monkey, on the end of their list
+ target.items.push_back(i);
+ }
+ }
+ }
+}
+
+fn nfrg<T: FromStr>(c: regex::Captures, index:usize) -> Result<T, SimpleError> {
+ let x = c.get(index).ok_or(SimpleError::new("missed capture group"))?;
+ x.as_str().parse().map_err(|_| { SimpleError::new("wasn't a number")})
+}
+
+impl FromStr for Monkey {
+ type Err = simple_error::SimpleError;
+
+ fn from_str(s: &str) -> Result<Self, Self::Err> {
+ let ll: Vec<&str> = s.lines().collect();
+ if ll.len() != 6 {
+ bail!("expected 6 lines for a monkey!");
+ }
+ // Parse the starting items line
+ let r1 = Regex::new(r"^ Starting items: ([0-9, ]+)$").unwrap();
+ let l1c = r1.captures(ll[1]).ok_or(SimpleError::new("starting regex no match"))?;
+ let l1d = l1c.get(1).ok_or(SimpleError::new("starting no group"))?;
+ let items: VecDeque<u64> = l1d.as_str().split(", ").map(|t| { t.parse() })
+ .try_collect().map_err(|_| SimpleError::new("error parsing items"))?;
+
+ // Parse the operation / args line
+ let r2 = Regex::new(r"^ Operation: new = ([a-z0-9]+) ([+\-*/]) ([a-z0-9]+)$").unwrap();
+ let l2c = r2.captures(ll[2]).ok_or(SimpleError::new("operation/args didn't match regex"))?;
+ let l2t1 = l2c.get(1).ok_or(SimpleError::new("error parsing op"))?;
+ let l2t2 = l2c.get(2).ok_or(SimpleError::new("error parsing op"))?;
+ let l2t3 = l2c.get(3).ok_or(SimpleError::new("error parsing op"))?;
+ let arg1 = match l2t1.as_str() {
+ "old" => Ok(Var::A),
+ st => st.parse().map(|i| {Var::C(i)})
+ }.map_err(|_| {SimpleError::new("error parsing arg1")})?;
+ let op = match l2t2.as_str() {
+ "+" => Ok(Op::Add),
+ "-" => Ok(Op::Sub),
+ "*" => Ok(Op::Mul),
+ "/" => Ok(Op::Div),
+ _ => Err(SimpleError::new("unexpected operator"))
+ }?;
+ let arg2 = match l2t3.as_str() {
+ "old" => Ok(Var::A),
+ st => st.parse().map(|i| {Var::C(i)})
+ }.map_err(|_| {SimpleError::new("error parsing arg1")})?;
+
+ // Parse the test line
+ let r3 = Regex::new(r"^ Test: divisible by (\d+)$").unwrap();
+ let l3c = r3.captures(ll[3]).ok_or(SimpleError::new("no match line 3"))?;
+ let test = nfrg(l3c, 1)?;
+
+ // Parse the target lines
+ let r4 = Regex::new(r"^ If true: throw to monkey (\d+)$").unwrap();
+ let l4c = r4.captures(ll[4]).ok_or(SimpleError::new("no match line 4"))?;
+ let target_true = nfrg(l4c, 1)?;
+ let r5 = Regex::new(r"^ If false: throw to monkey (\d+)$").unwrap();
+ let l5c = r5.captures(ll[5]).ok_or(SimpleError::new("no match line 5"))?;
+ let target_false = nfrg(l5c, 1)?;
+
+ let inspections = 0;
+ Ok(Monkey{
+ items,
+ op,
+ arg1,
+ arg2,
+ test,
+ target_true,
+ target_false,
+ inspections,
+ })
+ }
+}
+
+pub fn run(input: String) {
+ let mut monkeys: Vec<Monkey> = input.split("\n\n")
+ .map(|s| {Monkey::from_str(s).expect("couldn't parse monkey!")})
+ .collect();
+ //println!("{:?}", monkeys);
+ //for _ in 0..20 {
+ for _ in 0..10000 {
+ Monkey::business(&mut monkeys);
+ }
+ monkeys.sort_by(|a, b| { a.inspections.cmp(&b.inspections).reverse() });
+ let m1 = &monkeys[0];
+ let m2 = &monkeys[1];
+ println!("Day 11: {}", m1.inspections*m2.inspections);
+} \ No newline at end of file
diff --git a/src/main.rs b/src/main.rs
index 31bb9ea..0d64697 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,3 +1,5 @@
+#![feature(get_many_mut)]
+#![feature(iterator_try_collect)]
use std::fs;
mod day1;
@@ -10,6 +12,7 @@ mod day7;
mod day8;
mod day9;
mod day10;
+mod day11;
fn main() {
day1::run(fs::read_to_string("input/day1.txt").expect("Failed to read input file!"));
@@ -22,4 +25,5 @@ fn main() {
day8::run(fs::read_to_string("input/day8.txt").expect("Failed to read input file!"));
day9::run(fs::read_to_string("input/day9.txt").expect("Failed to read input file!"));
day10::run(fs::read_to_string("input/day10.txt").expect("Failed to read input file!"));
+ day11::run(fs::read_to_string("input/day11.txt").expect("Failed to read input file!"));
}