Skip to content

Latest commit

 

History

History
361 lines (316 loc) · 9.83 KB

25.advent-of-code-2020-day10.md

File metadata and controls

361 lines (316 loc) · 9.83 KB
Raw

酷熊：第 10 天，第 10 天，第 10 天！

好吧，到第 10 天了。

同样，问题描述看起来令人困惑 —— 但问题本来就是如此。有一串数字:

16
10
15
5
1
11
7
19
6
12
4

我们需要向其中加入 0，并且不管最大值是多少，最大值加 3:

16
10
15
5
1
11
7
19
6
12
4
0
22

至此，如果我们给它们排序，会发现它们之间间隔为 1，或者 3：

0
1 // 1
4 // 3
5 // 1
6 // 1
7 // 1
10 // 3
11 // 1
12 // 1
15 // 3
16 // 1
19 // 3
22 // 3

我们需要把间隔为 1 的数乘以我们找到的间隔为 3 的数。

我们可以使用一些我们最近看到的技术: 使用一些类型来表示结果，使用 slice 的 windows 方法来处理连续的项，还有一些其他技巧，如下:

#[derive(Default, Clone, Copy, Debug)]
struct Results {
    ones: usize,
    threes: usize,
}

fn main() {
    let mut numbers: Vec<_> = std::iter::once(0)
        .chain(
            include_str!("input.txt")
                .lines()
                .map(|x| x.parse::<usize>().unwrap()),
        )
        .collect();
    // clippy told me to use `sort_unstable`
    numbers.sort_unstable();

    if let Some(&max) = numbers.iter().max() {
        // numbers is still sorted after this
        numbers.push(max + 3);
    }

    let results = numbers.windows(2).fold(Results::default(), |acc, s| {
        if let [x, y] = s {
            match y - x {
                1 => Results {
                    ones: acc.ones + 1,
                    ..acc
                },
                3 => Results {
                    threes: acc.threes + 1,
                    ..acc
                },
                gap => panic!("invalid input (found {} gap)", gap),
            }
        } else {
            unreachable!()
        }
    });
    dbg!(results, results.ones * results.threes);
}
  • 酷熊热辣小贴士 注意，如果我们使用 nightly Rust，我们可以使用 array_windows，它给我们提供一个 [usize; 2]，这时我们不需要用 if let，这是一个非常适合的模式！
$ cargo run --quiet
[src/main.rs:40] results = Results {
    ones: 7,
    threes: 5,
}
[src/main.rs:40] results.ones * results.threes = 35

让我们试试题目的输入:

$ cargo run --quiet
[src/main.rs:40] results = Results {
    ones: 75,
    threes: 37,
}
[src/main.rs:40] results.ones * results.threes = 2775

第一部分已经完成了！

第二部分

下一个问题是: 连接适配器的所有可能方式是哪些？它们都是有效的链条吗？

假设我们有:

1
2
3
5
6

我们可以有 [1,2,3,5,6] ，[1,2,3,6] ，[1,2,5,6] ，[1,3,5,6] ，或 [1,3,6]。

类似于第 7 天中的 DAG，这里也可视为一个 DAG：

但是，与第 7 天不同，我们对遍历子图的所有节点不感兴趣，我们感兴趣的是遍历该图的所有不同方式！

但是我们对这些路径到底是什么并不感兴趣，我们感兴趣的是有多少条路径存在 —— 所以我认为这次我们可以聪明一点（使用之前的解题经验）。把它作为一种享受。

思考最后一个节点，6 —— 只有一条路径经过它，因为没有从节点 6 开始的边。

再思考节点 5，只有一种方法（路径）可以从这里遍历图表: 我们只能到达节点 6。

对于节点 3，我们可以选择到 5 或者到 6，所以从 3 开始遍历图的方法的数量就是从 5 遍历图以及从 6 遍历图的方法的总和，例如：1 + 1 = 2。

我们一开始，有从“node”到“数值”的映射 key，数值表示遍历图的方法（路径）数量:

node_6 = 1
node_5 = node_6 = 1
node_3 = node_5 + node_6 = 1 + 1 = 2
node_2 = node_3 + node_5 = 2 + 1 = 3
node_1 = node_2 + node_3 = 3 + 2 = 5

这听起来像是一些既高效又不复杂的计算！请注意，我们的结果将略有不同，因为我们需要考虑额外的初始节点 0 和最终节点 max + 3，所以我们最后会有更多的路径数:

fn main() {
    let mut numbers: Vec<_> = std::iter::once(0)
        .chain(
            // this file contains 1, 2, 3, 5, 6
            include_str!("input2.txt")
                .lines()
                .map(|x| x.parse::<usize>().unwrap()),
        )
        .collect();
    numbers.sort_unstable();

    // numbers is still sorted after this
    numbers.push(numbers.iter().max().unwrap() + 3);

    let mut num_paths = HashMap::new();

    let n = numbers.len();
    num_paths.insert(numbers.last().copied().unwrap(), 1);
    for i in (0..(numbers.len() - 1)).into_iter().rev() {
        let i_val = numbers[i];
        let range = (i + 1)..=std::cmp::min(i + 3, n - 1);

        let num_neighbors: usize = range
            .filter_map(|j| {
                let j_val = numbers[j];
                let gap = j_val - i_val;
                if (1..=3).contains(&gap) {
                    Some(num_paths.get(&j_val).unwrap())
                } else {
                    None
                }
            })
            .sum();
        num_paths.insert(i_val, num_neighbors);
    }

    for &n in numbers.iter().rev() {
        let &m = num_paths.get(&n).unwrap();
        println!(
            "from {}, there's {} {}",
            n,
            m,
            if m == 1 { "path" } else { "paths" }
        );
    }
}
$ cargo run --quiet
from 9, there's 1 path
from 6, there's 1 path
from 5, there's 1 path
from 3, there's 2 paths
from 2, there's 3 paths
from 1, there's 5 paths
from 0, there's 10 paths

我们用题目提供的输入，运行程序:

$ cargo run --quiet
from 186, there's 1 path
from 183, there's 1 path
from 182, there's 1 path
from 181, there's 2 paths
from 180, there's 4 paths
from 177, there's 4 paths
from 176, there's 4 paths
from 173, there's 4 paths
from 170, there's 4 paths
from 167, there's 4 paths
from 166, there's 4 paths
from 165, there's 8 paths
from 164, there's 16 paths
from 163, there's 28 paths
from 160, there's 28 paths
from 157, there's 28 paths
from 154, there's 28 paths
from 153, there's 28 paths
from 152, there's 56 paths
from 151, there's 112 paths
from 148, there's 112 paths
from 145, there's 112 paths
from 144, there's 112 paths
from 143, there's 224 paths
from 142, there's 448 paths
from 141, there's 784 paths
from 138, there's 784 paths
from 137, there's 784 paths
from 136, there's 1568 paths
from 135, there's 3136 paths
from 134, there's 5488 paths
from 131, there's 5488 paths
from 128, there's 5488 paths
from 127, there's 5488 paths
from 126, there's 10976 paths
from 125, there's 21952 paths
from 122, there's 21952 paths
from 121, there's 21952 paths
from 118, there's 21952 paths
from 115, there's 21952 paths
from 114, there's 21952 paths
from 113, there's 43904 paths
from 112, there's 87808 paths
from 111, there's 153664 paths
from 108, there's 153664 paths
from 107, there's 153664 paths
from 106, there's 307328 paths
from 103, there's 307328 paths
from 102, there's 307328 paths
from 101, there's 614656 paths
from 100, there's 1229312 paths
from 99, there's 2151296 paths
from 96, there's 2151296 paths
from 95, there's 2151296 paths
from 94, there's 4302592 paths
from 93, there's 8605184 paths
from 92, there's 15059072 paths
from 89, there's 15059072 paths
from 86, there's 15059072 paths
from 85, there's 15059072 paths
from 84, there's 30118144 paths
from 83, there's 60236288 paths
from 82, there's 105413504 paths
from 79, there's 105413504 paths
from 78, there's 105413504 paths
from 77, there's 210827008 paths
from 76, there's 421654016 paths
from 73, there's 421654016 paths
from 72, there's 421654016 paths
from 71, there's 843308032 paths
from 70, there's 1686616064 paths
from 69, there's 2951578112 paths
from 66, there's 2951578112 paths
from 63, there's 2951578112 paths
from 60, there's 2951578112 paths
from 59, there's 2951578112 paths
from 58, there's 5903156224 paths
from 57, there's 11806312448 paths
from 54, there's 11806312448 paths
from 53, there's 11806312448 paths
from 52, there's 23612624896 paths
from 51, there's 47225249792 paths
from 48, there's 47225249792 paths
from 45, there's 47225249792 paths
from 42, there's 47225249792 paths
from 41, there's 47225249792 paths
from 40, there's 94450499584 paths
from 39, there's 188900999168 paths
from 38, there's 330576748544 paths
from 35, there's 330576748544 paths
from 34, there's 330576748544 paths
from 33, there's 661153497088 paths
from 32, there's 1322306994176 paths
from 31, there's 2314037239808 paths
from 28, there's 2314037239808 paths
from 25, there's 2314037239808 paths
from 24, there's 2314037239808 paths
from 23, there's 4628074479616 paths
from 22, there's 9256148959232 paths
from 19, there's 9256148959232 paths
from 18, there's 9256148959232 paths
from 17, there's 18512297918464 paths
from 14, there's 18512297918464 paths
from 13, there's 18512297918464 paths
from 12, there's 37024595836928 paths
from 11, there's 74049191673856 paths
from 10, there's 129586085429248 paths
from 7, there's 129586085429248 paths
from 6, there's 129586085429248 paths
from 3, there's 129586085429248 paths
from 2, there's 129586085429248 paths
from 1, there's 259172170858496 paths
from 0, there's 518344341716992 paths

就是这样! 518344341716992 是我们的最终答案。

下次再见，保重！