Advent Of Code 2022 第十一天 - 猴子在中间

发表于 2022-12-11 更新于 2023-01-30 分类于计算机科学， Rust

本文是关于 Advent Of Code 2022 的。
编程圣诞日历，圣诞节前每天一个编程问题。

有兴趣的朋友可以在官网答题，用自己喜欢的编程方式去收集星星⭐️。在官网答题需要登陆并下载为你单独生成的谜题输入，每个人的都不一样。

问题

第十一天终于有点难度了，第一第二部分都是模拟猴子的行为，但是要在第二部分注意怎么解决数值越来越大的问题。

第一部分

当你终于开始逆流而上时，你发现你的背包比你记得的要轻得多。就在这时，你背包中的一件物品从头顶飞过。猴子在和你丢失的东西玩Keep Away!

为了找回你的东西，你需要能够预测猴子会把你的东西扔到哪里。经过仔细观察，你发现猴子的操作是基于 你对每件物品的担心程度 。

你做了一些笔记（你的谜题输入），记录了每只猴子目前拥有的物品，你对这些物品的担心程度，以及猴子如何根据你的担心程度做出决定。比如说。

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

每只猴子都有几个属性。

Starting items列出了你对猴子目前持有的每件物品的 担心程度 ，按照它们将被检查的顺序。
Operation显示了当猴子检查物品时，你的担心程度如何变化。(像 new = old * 5 这样的操作意味着在猴子检查完物品后，你的担心程度是检查前担心程度的五倍。)
Test显示了猴子如何使用你的担心程度来决定下一个物品的位置。
- If true显示了如果Test是真的话，物品会发生什么。
- If false显示了如果Test 是假的，物品会发生什么。

在每只猴子检查完一件物品后，但在测试你的担心程度之前，你对猴子的检查没有损坏物品的欣慰会使你的担心程度 除以3 ，并向下舍入到最近的整数。

猴子们轮流检查和投掷物品。在一轮中，它按照所列的顺序，一次检查并抛出它手中的所有物品。猴子 0 先来，然后是猴子 1 ，以此类推，直到每只猴子都转了一圈。

当一只猴子把物品扔给另一只猴子时，该物品就会被放在接受物品的猴子列表的末端。一只猴子如果开始时没有物品，那么在轮到它的时候，它可能已经检查并抛出了许多物品。如果一只猴子在它的回合开始时没有持有任何物品，它的回合就结束了。

在上面的例子中，第一轮的进行情况如下：

猴子 0:
  猴子检查物品时，担心程度为 79。
    担心程度乘以 19 到 1501。
    猴子对物品感到厌烦。担心的程度除以3到 500。
    目前的担心程度不能被 23 整除。
    担心等级为 500 的物品被扔给猴子 3。
  猴子检查物品时，担心程度为 98。
    担心程度乘以 19 到 1862。
    猴子对物品感到厌烦。担心的程度除以3到 620。
    目前的担心程度不能被 23 整除。
    担心等级为 620 的物品被扔给猴子 3。
猴子 1:
  猴子检查物品时，担心程度为 54。
    担心程度增加 6 至 60。
    猴子对物品感到厌烦。担心的程度除以3到 20。
    目前的担心程度不能被 19 整除。
    担心等级为 20 的物品被扔给猴子 0。
  猴子检查物品时，担心程度为 65。
    担心程度增加 6 至 71。
    猴子对物品感到厌烦。担心的程度除以3到 23。
    目前的担心程度不能被 19 整除。
    担心等级为 23 的物品被扔给猴子 0。
  猴子检查物品时，担心程度为 75。
    担心程度增加 6 至 81。
    猴子对物品感到厌烦。担心的程度除以3到 27。
    目前的担心程度不能被 19 整除。
    担心等级为 27 的物品被扔给猴子 0。
  猴子检查物品时，担心程度为 74。
    担心程度增加 6 至 80。
    猴子对物品感到厌烦。担心的程度除以3到 26。
    目前的担心程度不能被 19 整除。
    担心等级为 26 的物品被扔给猴子 0。
猴子 2:
  猴子检查物品时，担心程度为 79。
    担心程度乘以自己到 6241。
    猴子对物品感到厌烦。担心的程度除以3到 2080。
    目前的担心程度能够被 13 整除。
    担心等级为 2080 的物品被扔给猴子 1。
  猴子检查物品时，担心程度为 60。
    担心程度乘以自己到 3600。
    猴子对物品感到厌烦。担心的程度除以3到 1200。
    目前的担心程度不能被 13 整除。
    担心等级为 1200 的物品被扔给猴子 3。
  猴子检查物品时，担心程度为 97。
    担心程度乘以自己到 9409。
    猴子对物品感到厌烦。担心的程度除以3到 3136。
    目前的担心程度不能被 13 整除。
    担心等级为 3136 的物品被扔给猴子 3。
猴子 3:
  猴子检查物品时，担心程度为 74。
    担心程度增加 3 至 77。
    猴子对物品感到厌烦。担心的程度除以3到 25。
    目前的担心程度不能被 17 整除。
    担心等级为 25 的物品被扔给猴子 1。
  猴子检查物品时，担心程度为 500。
    担心程度增加 3 至 503。
    猴子对物品感到厌烦。担心的程度除以3到 167。
    目前的担心程度不能被 17 整除。
    担心等级为 167 的物品被扔给猴子 1。
  猴子检查物品时，担心程度为 620。
    担心程度增加 3 至 623。
    猴子对物品感到厌烦。担心的程度除以3到 207。
    目前的担心程度不能被 17 整除。
    担心等级为 207 的物品被扔给猴子 1。
  猴子检查物品时，担心程度为 1200。
    担心程度增加 3 至 1203。
    猴子对物品感到厌烦。担心的程度除以3到 401。
    目前的担心程度不能被 17 整除。
    担心等级为 401 的物品被扔给猴子 1。
  猴子检查物品时，担心程度为 3136。
    担心程度增加 3 至 3139。
    猴子对物品感到厌烦。担心的程度除以3到 1046。
    目前的担心程度不能被 17 整除。
    担心等级为 1046 的物品被扔给猴子 1。

第一轮结束后，猴子们持有的物品都有这些担心程度：

Monkey 0: 20, 23, 27, 26
Monkey 1: 2080, 25, 167, 207, 401, 1046
Monkey 2:
Monkey 3:

猴子2和3在这一轮结束时并没有拿着任何物品；它们都在这一轮中检查了物品，并在这一轮结束前把它们都扔了。

这个过程又持续了几轮。

同时追赶所有的猴子是不可能的；如果你想拿回你的东西，你必须集中精力对付 两只最活跃的猴子 。在20个回合中计算每只猴子检查物品的 总次数 。

Monkey 0 inspected items 101 times.
Monkey 1 inspected items 95 times.
Monkey 2 inspected items 7 times.
Monkey 3 inspected items 105 times.

在这个例子中，两只最活跃的猴子检查了101和105次物品。在这种情况下， 猴子的业务水平 可以通过相乘这些来找到 10605 。

通过计算猴子在20个回合内检查了多少件物品来计算出要追赶的猴子。 在20轮抡东西之后，猴子的业务水平是多少？

第二部分

你担心你可能永远无法拿回你的物品。事实上，你非常担心，以至于你因为猴子的检查没有损坏物品 不再使你的担心程度被除以3 。

不幸的是，这种松了一口气的感觉让你的担心程度没有达到 可笑的程度 。你需要 找到另一种方法来保持你的担心程度可控 。

按照这个速度，你可能要忍受这些猴子 很长一段时间 —— 可能是 10000个回合 !

有了这些新规则，你仍然可以在10000轮之后弄清猴子的事情。使用上述同样的例子：

== 第 1 轮之后 ==
Monkey 0 inspected items 2 times.
Monkey 1 inspected items 4 times.
Monkey 2 inspected items 3 times.
Monkey 3 inspected items 6 times.

== 第 20 轮之后 ==
Monkey 0 inspected items 99 times.
Monkey 1 inspected items 97 times.
Monkey 2 inspected items 8 times.
Monkey 3 inspected items 103 times.

== 第 1000 轮之后 ==
Monkey 0 inspected items 5204 times.
Monkey 1 inspected items 4792 times.
Monkey 2 inspected items 199 times.
Monkey 3 inspected items 5192 times.

== 第 2000 轮之后 ==
Monkey 0 inspected items 10419 times.
Monkey 1 inspected items 9577 times.
Monkey 2 inspected items 392 times.
Monkey 3 inspected items 10391 times.

== 第 3000 轮之后 ==
Monkey 0 inspected items 15638 times.
Monkey 1 inspected items 14358 times.
Monkey 2 inspected items 587 times.
Monkey 3 inspected items 15593 times.

== 第 4000 轮之后 ==
Monkey 0 inspected items 20858 times.
Monkey 1 inspected items 19138 times.
Monkey 2 inspected items 780 times.
Monkey 3 inspected items 20797 times.

== 第 5000 轮之后 ==
Monkey 0 inspected items 26075 times.
Monkey 1 inspected items 23921 times.
Monkey 2 inspected items 974 times.
Monkey 3 inspected items 26000 times.

== 第 6000 轮之后 ==
Monkey 0 inspected items 31294 times.
Monkey 1 inspected items 28702 times.
Monkey 2 inspected items 1165 times.
Monkey 3 inspected items 31204 times.

== 第 7000 轮之后 ==
Monkey 0 inspected items 36508 times.
Monkey 1 inspected items 33488 times.
Monkey 2 inspected items 1360 times.
Monkey 3 inspected items 36400 times.

== 第 8000 轮之后 ==
Monkey 0 inspected items 41728 times.
Monkey 1 inspected items 38268 times.
Monkey 2 inspected items 1553 times.
Monkey 3 inspected items 41606 times.

== 第 9000 轮之后 ==
Monkey 0 inspected items 46945 times.
Monkey 1 inspected items 43051 times.
Monkey 2 inspected items 1746 times.
Monkey 3 inspected items 46807 times.

== 第 10000 轮之后 ==
Monkey 0 inspected items 52166 times.
Monkey 1 inspected items 47830 times.
Monkey 2 inspected items 1938 times.
Monkey 3 inspected items 52013 times.

10000轮之后，两只最活跃的猴子检查了52166和52013次物品。把这些乘起来，这种情况下的 猴子业务水平 现在是 2713310158 。

在每件物品被检查后，担心程度不再被三除以；你需要找到另一种方法来保持你的担心程度可控。再从你的谜题输入中的初始状态开始， 10000轮后的猴子业务水平是多少？

代码

完整的代码可以在这里找到。

11.rs

type Input = Vec<Monkey>;
// type Input = Vec<u32>;

#[derive(Clone, Debug)]
pub enum Op {
    Add(u64),
    Multi(u64),
    MultiSelf,
}

impl Op {
    fn apply(&self, x: u64) -> u64 {
        match self {
            Self::Add(k) => x + k,
            Self::Multi(k) => x * k,
            Self::MultiSelf => x * x,
        }
    }
}

#[derive(Clone, Debug)]
pub struct Monkey {
    init_item: Vec<u64>,
    operation: Op,
    divide_by: u64,
    if_true: usize,
    if_false: usize,
}

fn parse(input: &str) -> Input {
    input
        .split("\n\n")
        .filter_map(|chunk| {
            let pieces: Vec<&str> = chunk.split(|x| x == ':' || x == '\n').map(|x| x.trim()).collect();
            if pieces.len() < 11 {
                return None;
            }

            let op = pieces[5].strip_prefix("new = old ").unwrap().split_once(" ").unwrap();

            Some(
                Monkey {
                    init_item: pieces[3]
                        .split(", ")
                        .map(|x| x.parse().unwrap())
                        .collect(),
                    operation: match op {
                        ("+", arg) => Op::Add(arg.parse().unwrap()),
                        ("*", "old") => Op::MultiSelf,
                        ("*", arg) => Op::Multi(arg.parse().unwrap()),
                        _ => unreachable!()
                    },
                    divide_by: pieces[7].strip_prefix("divisible by ").unwrap().parse().unwrap(),
                    if_true: pieces[9].strip_prefix("throw to monkey ").unwrap().parse().unwrap(),
                    if_false: pieces[11].strip_prefix("throw to monkey ").unwrap().parse().unwrap(),
                }
            )
        })
        .collect()
}

fn simulate(monkeys: Input, round: usize, part_one: bool) -> usize {
    let mut inspection = vec![0; monkeys.len()];
    let mut items = monkeys.iter().map(|x| x.init_item.clone()).collect::<Vec<_>>();
    let base: u64 = monkeys.iter().map(|m| m.divide_by).product();

    (0..round)
        .for_each(|_| {
            monkeys
                .iter()
                .enumerate()
                .for_each(|(i, monkey)| {
                    let item = items[i]
                        .drain(..)
                        .map(|x| {
                            if part_one { monkey.operation.apply(x) / 3 } else { monkey.operation.apply(x) % base }
                        })
                        .collect::<Vec<_>>();

                    inspection[i] += item.len();

                    for x in item {
                        if x % monkey.divide_by == 0 {
                            items[monkey.if_true].push(x);
                        } else {
                            items[monkey.if_false].push(x);
                        }
                    }
                })
        });

    inspection.sort_unstable();
    inspection[inspection.len() - 1] * inspection[inspection.len() - 2]
}

pub fn part_one(input: Input) -> Option<usize> {
    Some(simulate(input, 20, true))
}

pub fn part_two(input: Input) -> Option<usize> {
    Some(simulate(input, 10000, false))
}

解析器

把每个猴子对每一行进行判断是哪个参数的。

第一部分

只是为第二部分做铺垫的，根据操作模拟就好了。

第二部分

如果你尝试不做任何修改就直接运行，你的担心水平很快就会超出一切数据类型的限制，就算你用大整数计算的速度也会非常的慢。

这里的技巧是我们 不需要知道最后你的担心等级 到底是多少，你只需要知道猴子检查的次数。既然如此我们只需要知道这数字在经过乘法和加法之后是否能够被某个数整除。

如果我们找出这些需要检查能否整除的数的乘积，并且 每次担心等级改变之后都 mod 这个数字 ，之后检查能否被整除的结果也不会改变。因为能够被 乘积整除的部分都被去掉了 ，而那部分肯定能够被这个数整除。

经过这样的处理我们就能把担心等级保持在 u64 的限制下。

运行时间

所有时间由我这垃圾笔记本电脑进行(不科学的)测试，均以 --release 启动。

Day 11
------
Parser: ✓ (15.7µs)
Part 1: 76728 (27.8µs)
Part 2: 21553910156 (9.3ms)