Advent of Code 2020 Day3 译文（用 Rust 实现 Advent of Code 2020 第3天）

原文链接：https://fasterthanli.me/series/advent-of-code-2020/part-3

原文作者：Amos

译文来自：https://github.com/suhanyujie/article-transfer-rs/

译者：suhanyujie

ps：水平有限，如有不当之处，欢迎指正

标签：Rust，advent of code, algo

大家好，欢迎回到《Advent of Code 2020》，欢迎主角酷熊。

酷熊：大家好！

我们开门见山吧。

第 3 天的问题陈述如下: 我们有一张地图，看起来像这样:

..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#

我们想象它向右无限重复，就像这样:

..##.........##....... (etc.)
#...#...#..#...#...#.. (etc.)
.#....#..#..#....#..#. (etc.)
..#.#...#.#..#.#...#.# (etc.)
.#...##..#..#...##..#. (etc.)
..#.##.......#.##..... (etc.)
.#.#.#....#.#.#.#....# (etc.)
.#........#.#........# (etc.)
#.##...#...#.##...#... (etc.)
#...##....##...##....# (etc.)
.#..#...#.#.#..#...#.# (etc.)

我们的 sled 从左上角开始，每次向右移动 3 个单位，向下移动 1 个单位。问题是，如果我们沿着那条路走，会遇到多少棵树？

可能有几种方法可以解决这个问题，但是当我看到这样的问题时，我会想到一个 2D 地图(带有 x 的物体)。这让我想起了我的游戏开发时代！

$ cargo new day3
     Created binary (application) `day3` package

让我们再试着从类型的角度来思考。

我们需要以某种方式表示地图上的位置。我们可以给每个函数传递 x、y 或者 col、row，或者我们可以为它创建一个类型。

我们将使用有符号的数字，这样我们就可以从技术上表示 0 左边的位置，假设地图左右两边都有:

#[derive(Debug, Clone, Copy, PartialEq)]
struct Vec2 {
    x: i64,
    y: i64,
}

为了方便起见，我们先从元组（tuple）构建 Vec2:

impl From<(i64, i64)> for Vec2 {
    fn from((x, y): (i64, i64)) -> Self {
        Self { x, y }
    }
}

我们为此编写一个测试:

#[test]
fn test_tuple() {
    let v: Vec2 = (5, 8).into();
    assert_eq!(v.x, 5);
    assert_eq!(v.y, 8);
}

我们还需要一个类型表示 tile:

#[derive(Clone, Copy, PartialEq)]
enum Tile {
    Open,
    Tree,
}

默认情况下，所有 tile 是打开的:

impl Default for Tile {
    fn default() -> Self {
        Self::Open
    }
}

我们还将添加一个 Debug 实现，它将输出 tile 的图形表示:

use std::fmt;

impl fmt::Debug for Tile {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let c = match self {
            Tile::Open => '.',
            Tile::Tree => '#',
        };
        write!(f, "{}", c)
    }
}

Map 类型可以是一个 struct，就两个字段: size，以及保存所有 tile 的 Vec:

struct Map {
    size: Vec2,
    tiles: Vec<Tile>,
}

接下来，我们需要一些方法:

impl Map {
    fn new(size: Vec2) -> Self {
        todo!()
    }

    fn set(&mut self, pos: Vec2, tile: Tile) {
        todo!()
    }

    fn get(&self, pos: Vec2) -> Tile {
        todo!()
    }
}

让我们从最简单的开始: new。

我们将所有的 tile 存储在一个二维数组中，数组的顺序以行为主，这意味着我们首先存储来自第一行的所有 tile，然后是第二行，以此类推。

在 new 中我们需要做的就是用默认值填充它:

impl Map {
    fn new(size: Vec2) -> Self {
        let num_tiles = size.x * size.y;
        Self {
            size,
            tiles: (0..num_tiles)
                .into_iter()
                .map(|_| Default::default())
                .collect(),
        }
    }
}

让我们也为 map 实现 Debug，这样我们就可以知道它上面有什么:

impl fmt::Debug for Map {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        for row in 0..self.size.y {
            for col in 0..self.size.x {
                write!(f, "{:?}", self.get((col, row).into()))?;
            }
            writeln!(f)?;
        }
        Ok(())
    }
}

这依赖于 get 所以... 我们得开始考虑 get 了。

我们要对传给 get 的 pos 参数做的第一件事是“包装”位置 X，这样理论上地图永远向右延伸。为了保持一致性，我们还将它向左延伸。

让我们使用一个 helper 函数:

impl Map {
    fn normalize_pos(&self, pos: Vec2) -> Option<Vec2> {
        if pos.y < 0 || pos.y >= self.size.y {
            None
        } else {
            let x = if pos.x < 0 {
                // wrap around for positions to the left of 0
                self.size.x - (pos.x % self.size.x)
            } else {
                // wrap around for positions to the right of self.size.x
                pos.x % self.size.x
            };
            Some((x, pos.y).into())
        }
    }
}

注意，对于地图之外的位置，这个函数将返回 None: 因为从概念上讲，地图是无限宽的，但是它的高度是有限的。

然后，我们可以创建第二个 helper 函数，它返回平面存储中一个平铺的索引:

impl Map {
    fn index(&self, pos: Vec2) -> Option<usize> {
        self.normalize_pos(pos)
            .map(|pos| (pos.x + pos.y * self.size.x) as _)
    }
}

就像 normalize_pos 一样，对于地图上不存在的位置(在它上面或下面) ，它将返回 None。

对于 get，我们采用一种更简单的方法，不返回 Option<Tile>，而是返回 Tile —— 我们假设地图（map）外的所有 tile 都是打开（open）的:

impl Map {
    fn get(&self, pos: Vec2) -> Tile {
        self.index(pos).map(|i| self.tiles[i]).unwrap_or_default()
    }
}

至于 set，我们假设地图之外的每一块 tile 都是不变的:

impl Map {
    fn set(&mut self, pos: Vec2, tile: Tile) {
        if let Some(index) = self.index(pos) {
            self.tiles[index] = tile
        }
    }
}

酷熊：好吧，这... 代码不少，问题是什么来着？

Amos: 嘘，小熊，我正在鼓捣地图! 地图很有趣。

让我们构建一个简单的地图并看看我们的 Debug 实现:

fn main() {
    let map = {
        let mut m = Map::new((6, 6).into());
        let points = [(1, 1), (4, 1), (1, 3), (4, 3), (2, 4), (3, 4)];
        for p in (&points).iter().copied() {
            m.set(p.into(), Tile::Tree);
        }
        m
    };
    println!("{:?}", map);
}

$ cargo run --quiet
......
.#..#.
......
.#..#.
..##..
......

酷熊：这是个笑脸吗，太可爱了！

Amos: 我能说什么呢: 我不忙着推广 Rust 的时候，我就不舒服。

酷熊：但是... 你现在在做什么。

Amos: 祝你玩地图玩得开心!

让我们试着回答第一部分的问题。

不过... 我们可以再做几个测试。特别是，我想测试一下我们的 normalize_pos 方法是否能正常工作。

#[test]
fn test_normalize_pos() {
    let m = Map::new((2, 2).into());
    assert_eq!(m.normalize_pos((0, 0).into()), Some((0, 0).into()));
    assert_eq!(m.normalize_pos((1, 0).into()), Some((1, 0).into()));
    assert_eq!(m.normalize_pos((2, 0).into()), Some((0, 0).into()));
    assert_eq!(m.normalize_pos((-1, 0).into()), Some((1, 0).into()));
    assert_eq!(m.normalize_pos((-2, 0).into()), Some((0, 0).into()));
    assert_eq!(m.normalize_pos((0, -1).into()), None);
    assert_eq!(m.normalize_pos((0, 2).into()), None);
}

$ cargo t
   Compiling day3 v0.1.0 (/home/amos/ftl/aoc2020/day3)
    Finished test [unoptimized + debuginfo] target(s) in 0.40s
     Running target/debug/deps/day3-158fe24cc8d106d4

running 2 tests
test test_normalize_pos ... FAILED
test test_tuple ... ok

failures:

---- test_normalize_pos stdout ----
thread 'test_normalize_pos' panicked at 'assertion failed: `(left == right)`
  left: `Some(Vec2 { x: 3, y: 0 })`,
 right: `Some(Vec2 { x: 1, y: 0 })`', src/main.rs:103:5

不是的。

这一块可能很棘手，尤其是对于负值。让我们试试其他方法:

/// Wrap the x coordinate so the map extends infinitely to the
/// left and the right. Returns `None` for coordinates above 0
/// or below `self.size.y`.
fn normalize_pos(&self, pos: Vec2) -> Option<Vec2> {
    if pos.y < 0 || pos.y >= self.size.y {
        None
    } else {
        let x = pos.x % self.size.x;
        // wrap around for left side (negative X coordinates)
        let x = if x < 0 { self.size.x + x } else { x };
        Some((x, pos.y).into())
    }
}

$ cargo test --quiet

running 2 tests
..
test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

更好! 而且，为了安全，我们还要测试一下 index:

#[test]
fn test_index() {
    let m = Map::new((3, 5).into());
    assert_eq!(m.index((0, 0).into()), Some(0));
    assert_eq!(m.index((2, 0).into()), Some(2));
    assert_eq!(m.index((0, 1).into()), Some(3));
    assert_eq!(m.index((2, 1).into()), Some(5));
}

$ cargo test --quiet

running 3 tests
...
test result: ok. 3 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

很好！

酷熊：是不是你建立了一个抽象的塔，然后问题的解决方案就可以又漂亮又简短？

Amos: 希望如此！在我们解决这个问题之前，我实际上不知道第一部分之外还有什么，所以... 让我们看看它是否有效。

因此，对于这个问题，我们首先需要确定我们的行程，然后计算我们遇到的树的数量。

酷熊：等等，我们不是要先解析地图吗？

Amos: 对了，地图。

让我们像往常一样将输入放在 input.txt 中，这次我们将使用 include_bytes，因此我们得到 &'static [u8]。

接下来，我们要解析地图（map）。同样，可能有很多方法可以做到这一点，但这里有一个比较快速的方法:

fn parse(input: &[u8]) -> Self {
    let mut columns = 0;
    let mut rows = 1;
    for &c in input.iter() {
        if c == b'\n' {
            rows += 1;
            columns = 0;
        } else {
            columns += 1;
        }
    }

    let mut iter = input.iter().copied();
    let mut map = Self::new((columns, rows).into());
    for row in 0..map.size.y {
        for col in 0..map.size.x {
            let tile = match iter.next() {
                Some(b'.') => Tile::Open,
                Some(b'#') => Tile::Tree,
                c => panic!("Expected '.' or '#', but got: {:?}", c),
            };
            map.set((col, row).into(), tile);
        }
        iter.next();
    }
    map
}

酷熊：怎么，今天没有什么特别的错误处理吗？

Amos: 不，今天不行。

我们来试试看:

fn main() {
    let map = Map::parse(include_bytes!("input.txt"));
    dbg!(map.size);
    println!("{:?}", map);
}

看起来够近了！

酷熊：啊，视觉测试，非常棒，非常正确。

Amos: 你在寻我开心吗？

现在回答问题:

fn main() {
    let map = Map::parse(include_bytes!("input.txt"));
    let itinerary = (0..map.size.y).into_iter().map(|y| Vec2::from((y * 3, y)));
    let num_trees = itinerary.filter(|&pos| map.get(pos) == Tile::Tree).count();
    println!("We encountered {} trees", num_trees);
}

$ cargo run --quiet
We encountered 148 trees

酷熊：叮叮叮，我们的冠军诞生了！继续。

第二部分

问题的第二部分实际上更多的是相同的，除了我们有不同的移动模式:

右 1，下 1
右 3，下 1。(我们已经检查过的模式。)
右 5，下 1
右 7，下 1
右 1，下 2

对于这些模式中的每一种，我们都会遇到不同数量的树 —— 我们应该找到所有这些树的数量，然后将它们相乘。

酷熊：我们可以创建一个函数来生成给定模式的位置列表吗？

Amos: 当然! 这种函数是什么类型的？

酷熊：可能需要一个 Vec2... 然后返回一个 Vec<Vec2>？

Amos: 你是不是忘了什么? 我们什么时候能停下来？

酷熊：哦，对了! 我想它还需要一个 Map，这样我们就知道它有多高了。

Amos: 拥有 Map 的所有权? 或者只是通过使用 &Map 来借用？

酷熊：只是借用一下？

有了！

fn generate_itinerary(map: &Map, delta: Vec2) -> Vec<Vec2> {
    let mut pos = Vec2::from((0, 0));
    let mut res: Vec<_> = Default::default();

    while map.normalize_pos(pos).is_some() {
        res.push(pos);
        pos.x += delta.x;
        pos.y += delta.y;
    }
    res
}

酷熊：我们能在 Vec2 上实现 += 吗？

Amos: 当然，为什么不能呢。

use std::ops::AddAssign;

impl AddAssign for Vec2 {
    fn add_assign(&mut self, rhs: Self) {
        self.x += rhs.x;
        self.y += rhs.y;
    }
}

然后:

fn generate_itinerary(map: &Map, delta: Vec2) -> Vec<Vec2> {
    let mut pos = Vec2::from((0, 0));
    let mut res: Vec<_> = Default::default();

    while map.normalize_pos(pos).is_some() {
        res.push(pos);
        pos += delta;
    }
    res
}

我们最好也测试一下这个函数:

#[test]
fn test_generate_itinerary() {
    assert_eq!(
        &generate_itinerary(&Map::new((5, 5).into()), (1, 1).into()),
        &[
            (0, 0).into(),
            (1, 1).into(),
            (2, 2).into(),
            (3, 3).into(),
            (4, 4).into(),
        ],
        "right 1 down 1, 5x5 map"
    );

    assert_eq!(
        &generate_itinerary(&Map::new((5, 5).into()), (3, 1).into()),
        &[
            (0, 0).into(),
            (3, 1).into(),
            (6, 2).into(),
            (9, 3).into(),
            (12, 4).into(),
        ],
        "right 3 down 1, 5x5 map"
    );

    assert_eq!(
        &generate_itinerary(&Map::new((5, 5).into()), (2, 2).into()),
        &[(0, 0).into(), (2, 2).into(), (4, 4).into(),],
        "right 2 down 2, 5x5 map"
    );
    assert_eq!(
        &generate_itinerary(&Map::new((9, 9).into()), (2, 5).into()),
        &[(0, 0).into(), (2, 5).into(),],
        "right 2 down 5, 9x9 map"
    )
}

$ cargo test --quiet

running 4 tests
....
test result: ok. 4 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

酷！

现在，回答问题:

fn main() {
    let map = Map::parse(include_bytes!("input.txt"));

    // from the problem statement
    let deltas: &[Vec2] = &[
        (1, 1).into(),
        (3, 1).into(),
        (5, 1).into(),
        (7, 1).into(),
        (1, 2).into(),
    ];
    let answer = deltas
        .iter()
        .copied()
        // generate all itineraries
        .map(|delta| generate_itinerary(&map, delta))
        // count trees
        .map(|itin| {
            itin.into_iter()
                .filter(|&pos| map.get(pos) == Tile::Tree)
                .count()
        })
        // multiply everything together
        .product::<usize>();

    println!("The answer is {}", answer);
}

$ cargo run --quiet
The answer is 727923200

酷熊：又答对了！

今天就到这里! 下次见，保重。

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

14.advent-of-code-2020-day3.md

14.advent-of-code-2020-day3.md

第二部分

Files

14.advent-of-code-2020-day3.md

Latest commit

History

14.advent-of-code-2020-day3.md

File metadata and controls

第二部分