- commit
- 43a7385bb73991fa3f0f169ba515678f250af0a1
- parent
- 9fbce5c2cffe0d21d500dbd6c91efc16b840e9dd
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2022-12-11 08:57
2022-12-11
Diffstat
| A | 2022/11/input.txt | 56 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2022/11/solution.rs | 106 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2022/11/test.txt | 28 | ++++++++++++++++++++++++++++ |
3 files changed, 190 insertions, 0 deletions
diff --git a/2022/11/input.txt b/2022/11/input.txt
@@ -0,0 +1,56 @@ -1 1 Monkey 0: -1 2 Starting items: 73, 77 -1 3 Operation: new = old * 5 -1 4 Test: divisible by 11 -1 5 If true: throw to monkey 6 -1 6 If false: throw to monkey 5 -1 7 -1 8 Monkey 1: -1 9 Starting items: 57, 88, 80 -1 10 Operation: new = old + 5 -1 11 Test: divisible by 19 -1 12 If true: throw to monkey 6 -1 13 If false: throw to monkey 0 -1 14 -1 15 Monkey 2: -1 16 Starting items: 61, 81, 84, 69, 77, 88 -1 17 Operation: new = old * 19 -1 18 Test: divisible by 5 -1 19 If true: throw to monkey 3 -1 20 If false: throw to monkey 1 -1 21 -1 22 Monkey 3: -1 23 Starting items: 78, 89, 71, 60, 81, 84, 87, 75 -1 24 Operation: new = old + 7 -1 25 Test: divisible by 3 -1 26 If true: throw to monkey 1 -1 27 If false: throw to monkey 0 -1 28 -1 29 Monkey 4: -1 30 Starting items: 60, 76, 90, 63, 86, 87, 89 -1 31 Operation: new = old + 2 -1 32 Test: divisible by 13 -1 33 If true: throw to monkey 2 -1 34 If false: throw to monkey 7 -1 35 -1 36 Monkey 5: -1 37 Starting items: 88 -1 38 Operation: new = old + 1 -1 39 Test: divisible by 17 -1 40 If true: throw to monkey 4 -1 41 If false: throw to monkey 7 -1 42 -1 43 Monkey 6: -1 44 Starting items: 84, 98, 78, 85 -1 45 Operation: new = old * old -1 46 Test: divisible by 7 -1 47 If true: throw to monkey 5 -1 48 If false: throw to monkey 4 -1 49 -1 50 Monkey 7: -1 51 Starting items: 98, 89, 78, 73, 71 -1 52 Operation: new = old + 4 -1 53 Test: divisible by 2 -1 54 If true: throw to monkey 3 -1 55 If false: throw to monkey 2 -1 56
diff --git a/2022/11/solution.rs b/2022/11/solution.rs
@@ -0,0 +1,106 @@
-1 1 #[path = "../lib.rs"] mod lib;
-1 2
-1 3 struct Monkey {
-1 4 items: Vec<u64>,
-1 5 op_add: u64,
-1 6 op_add_self: bool,
-1 7 op_mul: u64,
-1 8 op_mul_self: bool,
-1 9 div: u64,
-1 10 if_true: usize,
-1 11 if_false: usize,
-1 12 }
-1 13
-1 14 fn cut_prefix(line: &String, prefix: &'static str) -> Option<String> {
-1 15 if line.starts_with(prefix) {
-1 16 return Some(line[prefix.len()..].to_string());
-1 17 } else {
-1 18 return None;
-1 19 }
-1 20 }
-1 21
-1 22 fn get_monkeys() -> Vec<Monkey> {
-1 23 let mut monkeys = vec![];
-1 24 let mut monkey = Monkey {
-1 25 items: vec![],
-1 26 op_add: 0,
-1 27 op_add_self: false,
-1 28 op_mul: 1,
-1 29 op_mul_self: false,
-1 30 div: 1,
-1 31 if_true: 0,
-1 32 if_false: 0,
-1 33 };
-1 34
-1 35 for line in lib::iter_input() {
-1 36 if line.starts_with("Monkey ") {
-1 37 } else if let Some(rest) = cut_prefix(&line, " Starting items: ") {
-1 38 for s in rest.split(", ") {
-1 39 let i = s.parse::<u64>().unwrap();
-1 40 monkey.items.push(i);
-1 41 }
-1 42 } else if let Some(rest) = cut_prefix(&line, " Operation: new = old ") {
-1 43 match lib::split_once(rest.as_str(), ' ').unwrap() {
-1 44 ("+", "old") => { monkey.op_add_self = true; },
-1 45 ("*", "old") => { monkey.op_mul_self = true; },
-1 46 ("+", s) => { monkey.op_add = s.parse().unwrap(); },
-1 47 ("*", s) => { monkey.op_mul = s.parse().unwrap(); },
-1 48 _ => unreachable!(),
-1 49 }
-1 50 } else if let Some(rest) = cut_prefix(&line, " Test: divisible by ") {
-1 51 monkey.div = rest.parse().unwrap();
-1 52 } else if let Some(rest) = cut_prefix(&line, " If true: throw to monkey ") {
-1 53 monkey.if_true = rest.parse().unwrap();
-1 54 } else if let Some(rest) = cut_prefix(&line, " If false: throw to monkey ") {
-1 55 monkey.if_false = rest.parse().unwrap();
-1 56 } else if line == "" {
-1 57 // I cheated slightly by adding a blank line to the end of the input
-1 58 monkeys.push(monkey);
-1 59 monkey = Monkey {
-1 60 items: vec![],
-1 61 op_add: 0,
-1 62 op_add_self: false,
-1 63 op_mul: 1,
-1 64 op_mul_self: false,
-1 65 div: 1,
-1 66 if_true: 0,
-1 67 if_false: 0,
-1 68 };
-1 69 } else {
-1 70 unreachable!();
-1 71 }
-1 72 }
-1 73
-1 74 return monkeys;
-1 75 }
-1 76
-1 77 fn run(rounds: usize, damper: u64) -> u64 {
-1 78 let mut monkeys = get_monkeys();
-1 79 let mut counts = vec![0; monkeys.len()];
-1 80
-1 81 // this keeps the values bounded without changing the results
-1 82 let total_div: u64 = monkeys.iter().map(|m| m.div).product();
-1 83
-1 84 for _ in 0..rounds {
-1 85 for i in 0..monkeys.len() {
-1 86 while !monkeys[i].items.is_empty() {
-1 87 let mut value = monkeys[i].items.remove(0);
-1 88 value += if monkeys[i].op_add_self { value } else { monkeys[i].op_add };
-1 89 value *= if monkeys[i].op_mul_self { value } else { monkeys[i].op_mul };
-1 90 value /= damper;
-1 91 value %= total_div;
-1 92 let other = if value % monkeys[i].div == 0 { monkeys[i].if_true } else { monkeys[i].if_false };
-1 93 monkeys[other].items.push(value);
-1 94 counts[i] += 1;
-1 95 }
-1 96 }
-1 97 }
-1 98
-1 99 counts.sort();
-1 100 return counts.into_iter().rev().take(2).product();
-1 101 }
-1 102
-1 103 fn main() {
-1 104 println!("part1: {}", run(20, 3));
-1 105 println!("part2: {}", run(10000, 1));
-1 106 }
diff --git a/2022/11/test.txt b/2022/11/test.txt
@@ -0,0 +1,28 @@ -1 1 Monkey 0: -1 2 Starting items: 79, 98 -1 3 Operation: new = old * 19 -1 4 Test: divisible by 23 -1 5 If true: throw to monkey 2 -1 6 If false: throw to monkey 3 -1 7 -1 8 Monkey 1: -1 9 Starting items: 54, 65, 75, 74 -1 10 Operation: new = old + 6 -1 11 Test: divisible by 19 -1 12 If true: throw to monkey 2 -1 13 If false: throw to monkey 0 -1 14 -1 15 Monkey 2: -1 16 Starting items: 79, 60, 97 -1 17 Operation: new = old * old -1 18 Test: divisible by 13 -1 19 If true: throw to monkey 1 -1 20 If false: throw to monkey 3 -1 21 -1 22 Monkey 3: -1 23 Starting items: 74 -1 24 Operation: new = old + 3 -1 25 Test: divisible by 17 -1 26 If true: throw to monkey 0 -1 27 If false: throw to monkey 1 -1 28