Skip to content

Latest commit

 

History

History
742 lines (547 loc) · 19.3 KB

13.advent-of-code-2020-day2.md

File metadata and controls

742 lines (547 loc) · 19.3 KB

酷熊:第二天,第二天啦!

Advent of Code 2020 第 2 天的问题描述的是密码相关。听起来有点熟悉。

基本上,输入是这样的:

1-3 a: abcde
1-3 b: cdefg
2-9 c: ccccccccc

每一行包含一个“password policy”和一个“password”。对于第一行,策略是密码必须是 1~3(包括 3)次字母“a”。

酷熊:那么,会有更多的解析吧? Amos: 更多解析。

好吧,和第一天一样,我们创建一个新项目:

$ cargo new day2
     Created binary (application) `day2` package
$ cd day2
$ cargo add anyhow
      Adding anyhow v1.0.35 to dependencies

将我们的输入添加到 day2/src/input.txt,然后:

// in `day2/src/main.rs`

fn main() -> anyhow::Result<()> {
    let input = include_str!("input.txt");

    Ok(())
}

因此,每一行都包含一个密码策略和一个密码。让我们开始考虑如何用类型来表示它。

策略有一定的范围和一个字符。

酷熊:它是一个字符吗? 输入难道不都是我们的 ASCII?

Amos: 是的!

酷熊:所以我们可以只用字节,对吧?

Amos: 我想是的!

use std::ops::RangeInclusive;

struct PasswordPolicy {
    byte: u8,
    range: RangeInclusive<usize>,
}

接下来,我们可能需要一个函数来解析一行,并返回 PasswordPolicy 和(我猜想) 应该是 &str

酷熊:是啊,如果我们处理的是字节,没问题。

fn parse_line(s: &str) -> anyhow::Result<(PasswordPolicy, &str)> {
    todo!()
}

我们还需要一些方法来确保密码与给定的 PasswordPolicy 匹配:

impl PasswordPolicy {
    fn is_valid(&self, password: &str) -> bool {
        todo!()
    }
}

酷熊:好多 todo 啊!我们能不能至少勾勒出所有这些函数的主要功能?

第 1 部分的问题是,根据它们的策略,有多少密码是有效的,因此,当然,现在我们已经掌握了所有的已知条件,我们可以这样做:

fn main() -> anyhow::Result<()> {
    let count = include_str!("input.txt")
        .lines()
        .map(parse_line)
        .map(Result::unwrap)
        .filter(|(policy, password)| policy.is_valid(password))
        .count();
    println!("{} passwords are valid", count);

    Ok(())
}

酷熊:啊,太棒了! lines 是干什么用的? 是不是类似于 split('\n')

Amos: 差不多! 它也适用于 \r\n(CRLF) ,也就是“Windows 风格的行结尾”。

酷熊:这次我们没有 collectResult 吗?

Amos: 不,我想强调的是,我们可以使用 filtercount 来解答问题,而不需要收集任何数据。全都是流式操作!

酷熊:我们接下来要实现什么?

我们试一下 is_valid

一般来说我们只关心字节,因为输入只是 ASCII 字符,所以我们不必关心 UTF-8 编码

str::as_bytes 方法返回了 &[u8] ,从那里我们可以使用我们所熟悉的迭代器方法:

impl PasswordPolicy {
    fn is_valid(&self, password: &str) -> bool {
        self.range.contains(
            &password
                .as_bytes()
                .iter()
                .copied()
                .filter(|&b| b == self.byte)
                .count(),
        )
    }
}

酷熊:等一下,.copied() 是什么?

Amos: 好的,password.as_bytes().iter() 提供了迭代器 Iterator<Item = &u8>

而且碰巧 u8 是一个 Copy 类型-我们不必担心它的所有权,而且它的开销比较小,嗯,复制的开销。

酷熊:啊,那么 .copied() 将其转换为 Iterator<Item = u8>?然后我们可以直接操作 u8 值,而不是像 &u8 这样的引用?

Amos: 差不多,是的! 还有一点是当 iter 是迭代器 Iterator<Item = T> 时,iter.filter() 会传递 &T

酷熊:啊,因为我们在过滤,所以我们不能“消费”这些项,我们只是想读取它们,然后决定是否保留它们。 Amos: 没错!

酷熊:我不明白为什么会是 &b —— 难道不应该是 *b 吗? 因为我们解引用了?

我们的 filter 调用:

.filter(|&b| b == self.byte)

也可以这样写:

.filter(|b| *b == self.byte)

酷熊:哦,这是... 一种对称!所以要么在右边用 * 解引用它... 要么在左边加上 &

都是模式匹配。

例如,如果我们想匹配一个 &i32,我们可以这样做:

// (this code is not part of the solution)

let i = &42;
if let 42 = *i {
    println!("yes!");
}

但我们也可以这样做:

let i = &42;
if let &42 = i {
    println!("yes!");
}

酷熊:我明白了,只要保持平衡,就没事?

Amos: 没错!

现在,只需要实现 parse_line 方法。但是最好确保 PasswordPolicy::is_valid 的行为符合预期。

我们编写一个单元测试!

#[cfg(test)]
mod tests {
    use super::PasswordPolicy;

    #[test]
    fn test_is_valid() {
        let pp = PasswordPolicy {
            range: 1..=3,
            byte: b'a',
        };
        assert_eq!(pp.is_valid("zeus"), false, "no 'a's");
        assert_eq!(pp.is_valid("hades"), true, "single 'a'");
        assert_eq!(pp.is_valid("banana"), true, "three 'a's");
        assert_eq!(pp.is_valid("aaaah"), false, "too many 'a's");
    }
}

酷熊:快速提问-这个模块是否在一个单独的文件中?

Amos: 可以! 您可以阅读 Rust 模块 vs 文件获得更多信息。

我们的测试通过了:

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

running 1 test
test tests::test_is_valid ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

酷熊:万岁!

这意味着我们可以继续实现最后一个函数。

酷熊:我们能测试一下这个吗?

Amos: 当然! 我们先写测试。

// in `mod tests`

use super::parse_line;

#[test]
fn test_parse() {
    assert_eq!(
        parse_line("1-3 a: banana").unwrap(),
        (
            PasswordPolicy {
                range: 1..=3,
                byte: b'a',
            },
            "banana"
        )
    );
}

还没编译!对于使用 asser_eq!,需要实现两个 trait: PartialEq (用于判等测试)和 Debug (当它们不相等时,用于格式化左侧和右侧的值)。

我们可以自己实现这些目标:

use std::fmt::Debug;

impl PartialEq for PasswordPolicy {
    fn eq(&self, other: &Self) -> bool {
        self.byte == other.byte && self.range == other.range
    }
}

impl Debug for PasswordPolicy {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("PasswordPolicy")
            .field("byte", &self.byte)
            .field("range", &self.range)
            .finish()
    }
}

或者我们可以直接推导出来:

#[derive(PartialEq, Debug)]
struct PasswordPolicy {
    byte: u8,
    range: RangeInclusive<usize>,
}

酷熊:哇!是否因为 u8RangeInsive<usize> 都实现了 PartialEqDebug 而起作用?

Amos: 没错!而且它们并没有默认为所有结构体实现,因为,如果你不需要它们,那你的二进制文件也无需存在这些代码,否则会很臃肿。

修改代码之后,测试就可以编译,但是用例执行失败:

$ cargo t
    Finished test [unoptimized + debuginfo] target(s) in 0.01s
     Running target/debug/deps/day2-b64ad06ec1d18663

running 2 tests
test tests::test_is_valid ... ok
test tests::test_parse ... FAILED

failures:

---- tests::test_parse stdout ----
thread 'tests::test_parse' panicked at 'not yet implemented', src/main.rs:23:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace


failures:
    tests::test_parse

test result: FAILED. 1 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out

error: test failed, to rerun pass '--bin day2'

小贴士

  • cargo tcargo test 的简称,就像 cargo bcargo build 的简称,cargo ccargo check 的简称,cargo rcargo run 的简称。

所以我们要做的就是实现 parse_line

酷熊:很简单,splitparse,然后搞定。

当然,为什么不呢:

$ cargo add thiserror
      Adding thiserror v1.0.22 to dependencies
#[derive(thiserror::Error, Debug)]
enum ParseError {
    #[error("expected {0}")]
    Expected(&'static str),
}

fn parse_line(s: &str) -> anyhow::Result<(PasswordPolicy, &str)> {
    let (policy, password) = {
        let mut tokens = s.split(':');
        (
            tokens
                .next()
                .ok_or(ParseError::Expected("password policy"))?,
            tokens
                .next()
                .ok_or(ParseError::Expected("password"))?
                .trim(),
        )
    };

    let (range, byte) = {
        let mut tokens = policy.split(' ');
        (
            tokens.next().ok_or(ParseError::Expected("policy range"))?,
            tokens.next().ok_or(ParseError::Expected("policy byte"))?,
        )
    };

    let byte = if byte.as_bytes().len() == 1 {
        byte.as_bytes()[0]
    } else {
        return Err(ParseError::Expected("password policy byte to be exactly 1 byte").into());
    };

    let (min, max) = {
        let mut tokens = range.split('-');
        (
            tokens
                .next()
                .ok_or(ParseError::Expected("policy range (lower bound)"))?,
            tokens
                .next()
                .ok_or(ParseError::Expected("policy range (upper bound)"))?,
        )
    };

    let range = (min.parse()?)..=(max.parse()?);

    Ok((PasswordPolicy { range, byte }, password))
}

酷熊:这...代码比我想象的要多。

Amos: 哈哈,还真管用!

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

running 2 tests
test tests::test_is_valid ... ok
test tests::test_parse ... ok

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

酷熊:是的,但是我们真的需要所有的错误处理吗?

Amos: 我不知道,我有点喜欢它! 我们甚至可以为它编写测试。

// in `mod tests`

#[test]
fn test_parse() {
    assert_eq!(
        parse_line("1-3 a: banana").unwrap(),
        (
            PasswordPolicy {
                range: 1..=3,
                byte: b'a',
            },
            "banana"
        )
    );

    assert_eq!(
        parse_line("1-3 a").unwrap_err().to_string(),
        "expected password"
    );
    assert_eq!(
        parse_line("1-3 : banana").unwrap_err().to_string(),
        "expected password policy byte to be exactly 1 byte"
    );

    // feel free to add more tests!
}

酷熊:我想是的!

“酷熊”的犹豫是可以理解的。我不想一直编写解析部分。

这就是为什么,通常在这种场景下,我会尝试 nom crate

但是今天我们要看一些不同的东西!

让我们试一试 peg

酷熊:试试什么?

Amos:解析表达文法。(Parsing expression grammar)

酷熊:哦,额。。!

Amos:什么?

酷熊:没什么,没什么。

$ cargo add peg
      Adding peg v0.6.3 to dependencies
// note: we don't need the `ParseError` type anymore

fn parse_line(s: &str) -> anyhow::Result<(PasswordPolicy, &str)> {
    peg::parser! {
      grammar parser() for str {
        rule number() -> usize
          = n:$(['0'..='9']+) { n.parse().unwrap() }

        rule range() -> RangeInclusive<usize>
          = min:number() "-" max:number() { min..=max }

        rule byte() -> u8
          = letter:$(['a'..='z']) { letter.as_bytes()[0] }

        rule password() -> &'input str
          = letters:$([_]*) { letters }

        pub(crate) rule line() -> (PasswordPolicy, &'input str)
          = range:range() " " byte:byte() ": " password:password() {
              (PasswordPolicy { range, byte }, password)
          }
      }
    }

    Ok(parser::line(s)?)
}

酷熊:这才像话嘛,不过它有用吗?

Amos:这些测试没有通过,但那是因为我们接收到了不同的错误消息:

$ cargo t -q

running 2 tests
.F
failures:

---- tests::test_parse stdout ----
thread 'tests::test_parse' panicked at 'assertion failed: `(left == right)`
  left: `"error at 1:6: expected \": \""`,
 right: `"expected password"`', src/main.rs:90:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

酷熊:好吧。我想我们现在可以摆脱这些测试了,因为语法是声明性的(而且相当短)?不过,我们确实得到了一些即时的报错,这很好。

Amos:我们当然可以,砰,他们走了。

让我们实际运行我们的解决方案:

$ cargo run --quiet
546 passwords are valid

看来答案是正确的,继续。

第二部分

对于第 2 部分,《Advent of Code》的作者给我们抛出了一个曲线球。

结果那 1-3 不是范围,而是位置! 索引 1 的位置,雪上加霜。

因此,如果我们有:

1-3 a: abcde

密码只有在位置 1 或位置 3 有 a 时才有效,但不能两者都有。

酷熊:我们不应该再使用 InclusiveRange 了!

Amos: 好吧,我们该用什么?

酷熊:我们将使用这两个位置... 也许是一个固定大小的数组,这样我们就可以迭代它?

Amos: 当然!

#[derive(PartialEq, Debug)]
struct PasswordPolicy {
    byte: u8,
    positions: [usize; 2],
}

让我们用 todo!() 替代 is_valid 占位,因为语义发生了变化:

impl PasswordPolicy {
    fn is_valid(&self, password: &str) -> bool {
        todo!()
    }
}

调整解析器:

fn parse_line(s: &str) -> anyhow::Result<(PasswordPolicy, &str)> {
    peg::parser! {
      grammar parser() for str {
        rule number() -> usize
          = n:$(['0'..='9']+) { n.parse().unwrap() }

        // was: range
        rule positions() -> [usize; 2]
          = first:number() "-" second:number() { [first, second] }

        rule byte() -> u8
          = letter:$(['a'..='z']) { letter.as_bytes()[0] }

        rule password() -> &'input str
          = letters:$([_]*) { letters }

        pub(crate) rule line() -> (PasswordPolicy, &'input str)
          // this now uses `positions`, rather than `range`
          = positions:positions() " " byte:byte() ": " password:password() {
              (PasswordPolicy { positions, byte }, password)
          }
      }
    }

    Ok(parser::line(s)?)
}

我们可以这样调整我们的解析测试:

#[test]
fn test_parse() {
    assert_eq!(
        parse_line("1-3 a: banana").unwrap(),
        (
            PasswordPolicy {
                positions: [1, 3],
                byte: b'a',
            },
            "banana"
        )
    );
}

我们的有效性测试是这样的:

#[test]
fn test_is_valid() {
    let pp = PasswordPolicy {
        positions: [1, 3],
        byte: b'a',
    };
    assert_eq!(pp.is_valid("abcde"), true, "'a' in position 1");
    assert_eq!(pp.is_valid("bcade"), true, "'a' in position 3");
    assert_eq!(pp.is_valid("food"), false, "no 'a' whatsoever");
    assert_eq!(pp.is_valid("abacus"), false, "'a' in both positions");
}

我们的解析测试已经通过了,让我们考虑一下新的 PasswordPolicy::is_valid

酷熊:我们还能使用基于迭代器的方法吗?

我觉得我们可以!我们所要做的就是... ... 迭代这些位置,并计算其中有多少实际“匹配”,也就是说,输入中的字节与策略指定的字节相同。然后计数必须正好是一。

酷熊:我们不是有失误的危险吗?因为输入给我们的是基于 1 的索引,而 Rust 使用基于 0 的索引。

Amos: 对,我们可以直接在解析器中“标准化”它们,开始吧。

// in `grammar parser()`

rule number() -> usize
    = n:$(['0'..='9']+) { n.parse().unwrap() }

/// Positions are 1-based indices in the input
rule position() -> usize
    = n:number() { n - 1 }

rule positions() -> [usize; 2]
    // now using `position()` rather than `number()`
    = first:position() "-" second:position() { [first, second] }

酷熊:酷! 现在 PasswordPolicy::positions 中的索引是从 0 开始的了,所以我们可以直接使用它们。

直接使用它们,代码如下:

impl PasswordPolicy {
    fn is_valid(&self, password: &str) -> bool {
        self.positions
            .iter()
            .copied()
            .filter(|&index| password.as_bytes()[index] == self.byte)
            .count()
            == 1
    }
}

这有用吗? 我们测试:

$ cargo test --quiet

running 2 tests
FF
failures:

---- tests::test_is_valid stdout ----
thread 'tests::test_is_valid' panicked at 'assertion failed: `(left == right)`
  left: `false`,
 right: `true`: 'a' in position 1', src/main.rs:72:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

---- tests::test_parse stdout ----
thread 'tests::test_parse' panicked at 'assertion failed: `(left == right)`
  left: `(PasswordPolicy { byte: 97, positions: [0, 2] }, "banana")`,
 right: `(PasswordPolicy { byte: 97, positions: [1, 3] }, "banana")`', src/main.rs:82:9

忘了调整我们的测试了,讨厌。

#[cfg(test)]
mod tests {
    use super::PasswordPolicy;

    #[test]
    fn test_is_valid() {
        let pp = PasswordPolicy {
            positions: [0, 2], // now 0-based
            byte: b'a',
        };
        assert_eq!(pp.is_valid("abcde"), true, "'a' in position 1");
        assert_eq!(pp.is_valid("bcade"), true, "'a' in position 3");
        assert_eq!(pp.is_valid("food"), false, "no 'a' whatsoever");
        assert_eq!(pp.is_valid("abacus"), false, "'a' in both positions");
    }

    use super::parse_line;

    #[test]
    fn test_parse() {
        assert_eq!(
            parse_line("1-3 a: banana").unwrap(),
            (
                PasswordPolicy {
                    positions: [0, 2], // now 0-based
                    byte: b'a',
                },
                "banana"
            )
        );
    }
}

最后,我们执行结果:

$ cargo run --quiet
275 passwords are valid

酷熊:这正是我们期望的答案!

下次见,保重!