Advent of Code 2020 Day8 译文（用 Rust 实现 Advent of Code 2020 第8天）

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

原文作者：Amos

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

译者：suhanyujie

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

标签：Rust，advent of code, algo

又一个 Advent of Code 2020 问题时间。

这题听起来会很有趣，我们的输入有点像汇编指令，类似于这样:

nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6

我们先定义类型。

方法可能不止一种，但是我们看看这种:

#[derive(Debug, Clone, Copy)]
enum InstructionKind {
    Nop,
    Acc,
    Jmp,
}

#[derive(Debug, Clone, Copy)]
struct Instruction {
    kind: InstructionKind,
    operand: isize,
}

type Program = Vec<Instruction>;

那么让我们编写一个非常快速的解析器 —— 这次我们甚至不需要使用 peg。

fn parse_program(input: &str) -> Program {
    input
        .lines()
        .map(|l| {
            let mut tokens = l.split(' ');
            Instruction {
                kind: match tokens.next() {
                    Some(tok) => match tok {
                        "nop" => InstructionKind::Nop,
                        "acc" => InstructionKind::Acc,
                        "jmp" => InstructionKind::Jmp,
                        _ => panic!("unknown instruction kind {}", tok),
                    },
                    None => panic!("for line {}, expected instruction kind", l),
                },
                operand: match tokens.next() {
                    Some(tok) => tok.parse().unwrap(),
                    None => panic!("for line {}, expected operand", l),
                },
            }
        })
        .collect()
}

fn main() {
    let program = parse_program(include_str!("input.txt"));
    dbg!(program);
}

$ cargo run --quiet
[src/main.rs:42] program = [
    Instruction {
        kind: Nop,
        operand: 0,
    },
    Instruction {
        kind: Acc,
        operand: 1,
    },
    Instruction {
        kind: Jmp,
        operand: 4,
    },
    Instruction {
        kind: Acc,
        operand: 3,
    },
    Instruction {
        kind: Jmp,
        operand: -3,
    },
    Instruction {
        kind: Acc,
        operand: -99,
    },
    Instruction {
        kind: Acc,
        operand: 1,
    },
    Instruction {
        kind: Jmp,
        operand: -4,
    },
    Instruction {
        kind: Acc,
        operand: 6,
    },
]

下一步 —— 我们要模拟一台机器，那么我们的机器状态是什么样的？

我们有一个累加器和一个程序计数器 —— 它们都从 0 开始，所以我们可以很容易地派生 Default trait。

#[derive(Debug, Clone, Copy, Default)]
struct State {
    /// Program counter
    pc: usize,
    /// Accumulator
    acc: isize,
}

我们可以在 State 上实现一个 .next() 方法，它接受一个程序，并返回下一个 State！

我们的 State 很小巧，而且可 Copy，所以我们可以通过值获取它，并通过值返回它。我不想做错误处理，所以我们只能 panic! 了！如果我们遇到一个无效的指令，比如跳转到 0 之前或者跳转到程序结束后的位置。

use std::convert::TryInto;

impl State {
    fn next(self, program: &Program) -> Self {
        let ins = program[self.pc];
        match ins.kind {
            InstructionKind::Nop => Self {
                pc: self.pc + 1,
                ..self
            },
            InstructionKind::Acc => Self {
                pc: self.pc + 1,
                acc: self.acc + ins.operand,
            },
            InstructionKind::Jmp => Self {
                pc: (self.pc as isize + ins.operand).try_into().unwrap(),
                ..self
            },
        }
    }
}

我们可以试试！

fn main() {
    let program = parse_program(include_str!("input.txt"));

    let mut state: State = Default::default();
    dbg!("initial state", state);

    for _ in 0..5 {
        println!("will execute {:?}", program[state.pc]);
        state = state.next(&program);
        dbg!(state);
    }
}

$ cargo run --quiet
[src/main.rs:74] "initial state" = "initial state"
[src/main.rs:74] state = State {
    pc: 0,
    acc: 0,
}
will execute Instruction { kind: Nop, operand: 0 }
[src/main.rs:79] state = State {
    pc: 1,
    acc: 0,
}
will execute Instruction { kind: Acc, operand: 1 }
[src/main.rs:79] state = State {
    pc: 2,
    acc: 1,
}
will execute Instruction { kind: Jmp, operand: 4 }
[src/main.rs:79] state = State {
    pc: 6,
    acc: 1,
}
will execute Instruction { kind: Acc, operand: 1 }
[src/main.rs:79] state = State {
    pc: 7,
    acc: 2,
}
will execute Instruction { kind: Jmp, operand: -4 }
[src/main.rs:79] state = State {
    pc: 3,
    acc: 2,
}

我们需要回答的问题是: 在第二次执行指令之前，累加器中的值是多少？（译注：第二次执行是指重复执行时）

我们可以用命令式的方法来解决，或者我们可以把问题硬塞进 Iterator 里，如下所示：

fn main() {
    let program = parse_program(include_str!("input.txt"));

    let mut state: State = Default::default();

    let iter = std::iter::from_fn(|| {
        state = state.next(&program);
        Some(state)
    });

    dbg!(iter.take(5).collect::<Vec<_>>());
}

$ cargo run --quiet
[src/main.rs:81] iter.take(5).collect::<Vec<_>>() = [
    State {
        pc: 1,
        acc: 0,
    },
    State {
        pc: 2,
        acc: 1,
    },
    State {
        pc: 6,
        acc: 1,
    },
    State {
        pc: 7,
        acc: 2,
    },
    State {
        pc: 3,
        acc: 2,
    },
]

然而，还有一种更好的方法来编写这个代码，使用 itertools，我们来试一试:

$ cargo add itertools
      Adding itertools v0.9.0 to dependencies

fn main() {
    let program = parse_program(include_str!("input.txt"));

    let iter = itertools::iterate(State::default(), |s| s.next(&program));
    dbg!(iter.take(5).collect::<Vec<_>>());
}

现在输出中还包括初始的状态:

$ cargo run --quiet
[src/main.rs:74] iter.take(5).collect::<Vec<_>>() = [
    State {
        pc: 0,
        acc: 0,
    },
    State {
        pc: 1,
        acc: 0,
    },
    State {
        pc: 2,
        acc: 1,
    },
    State {
        pc: 6,
        acc: 1,
    },
    State {
        pc: 7,
        acc: 2,
    },
]

现在，由于我们需要确定何时开始第二次运行指令，因此我希望维护一个哈希集（hashset），其中包含我们已经执行的所有指令的位置。

只要 HashSet::insert 返回 false (它已经存在这个值) ，我们就可以停止并返回累加器中的内容。

use std::collections::HashSet;

fn main() {
    let program = parse_program(include_str!("input.txt"));

    let mut iter = itertools::iterate(State::default(), |s| s.next(&program));
    let mut set: HashSet<usize> = Default::default();
    let answer = iter.find(|state| !set.insert(state.pc)).unwrap();

    println!(
        "Before executing {} a second time, the accumulator was {}",
        answer.pc, answer.acc
    );
}

$ cargo run --quiet
Before executing 1 a second time, the accumulator was 5

现在让我们用真正的输入来试试:

$ cargo run --quiet
Before executing 296 a second time, the accumulator was 1594

第二部分

在第 2 部分中，我们需要确定程序何时终止 —— 通过将一个 jmp 转换为 nop，或者将一个 nop 转换为 jmp。

第 1 部分内容中，告诉我们哪个指令将第二次执行，所以我们需要弄清楚我们是如何到达那里。但是根据我们目前的设置，我们只有下一个指令。

为了得到上一条和下一条指令，我们可以使用 itertools 的 tuple_windows 方法:

use itertools::Itertools;

fn main() {
    let program = parse_program(include_str!("input.txt"));

    let iter = itertools::iterate(State::default(), |s| s.next(&program));
    let mut set: HashSet<usize> = Default::default();
    let answer = iter
        .tuple_windows()
        .find(|(_, next)| !set.insert(next.pc))
        .unwrap();

    println!(
        "Before {:?}, we were at state {:?} and executed {:?}",
        answer.1, answer.0, program[answer.0.pc]
    );
}

$ cargo run --quiet
Before State { pc: 296, acc: 1594 }, we were at state State { pc: 317, acc: 1594 } and executed Instruction { kind: Jmp, operand: -21 }

因此，如果我的计算是正确的... 在第 318 行（因为在大多数文本编辑器中行是从 1 开始的），我们应该可以找到..

jmp -21

但这真的是导致无限循环的原因吗？如果我们将它改为 nop -21，那么我们只需在其他地方循环:

$ cargo run --quiet
Before State { pc: 345, acc: 1546 }, we were at state State { pc: 322, acc: 1546 } and executed Instruction { kind: Jmp, operand: 23 }

我们只能修改一条指令。

所以，可能有更好的方法来解决这个问题。但是我累了，这个程序只有 656 个指令..

fn main() {
    let program = parse_program(include_str!("input.txt"));

    let num_jmp_and_nop = program
        .iter()
        .filter(|i| matches!(i.kind, InstructionKind::Jmp | InstructionKind::Nop))
        .count();
    dbg!(num_jmp_and_nop);
}

$ [src/main.rs:85] num_jmp_and_nop = 291

其中 291 个是 jmp 和 nop。我有个主意，我们用暴力破解怎么样？我们生成 291 个不同版本的程序，然后并行地模拟它们怎么样？谁先完成，谁就赢得奖品！

首先，我们需要一个指示完成的方法，所以我们将更改 State::next 使其返回 Option:

impl State {
    fn next(self, program: &Program) -> Option<Self> {
        if !(0..program.len()).contains(&self.pc) {
            return None;
        }

        let ins = program[self.pc];
        Some(match ins.kind {
            InstructionKind::Nop => Self {
                pc: self.pc + 1,
                ..self
            },
            InstructionKind::Acc => Self {
                pc: self.pc + 1,
                acc: self.acc + ins.operand,
            },
            InstructionKind::Jmp => Self {
                pc: (self.pc as isize + ins.operand).try_into().unwrap(),
                ..self
            },
        })
    }
}

然后开始比赛:

fn main() {
    let program = parse_program(include_str!("input.txt"));
    find_variant(&program);
}

fn flip_kind(kind: &mut InstructionKind) {
    *kind = match *kind {
        InstructionKind::Jmp => InstructionKind::Nop,
        InstructionKind::Nop => InstructionKind::Jmp,
        x => x,
    };
}

fn find_variant(program: &Program) {
    let mut variants: Vec<_> = program
        .iter()
        .enumerate()
        .filter_map(|(index, ins)| match ins.kind {
            InstructionKind::Jmp | InstructionKind::Nop => Some(index),
            _ => None,
        })
        .map(|i| {
            let mut variant = program.clone();
            flip_kind(&mut variant[i].kind);
            (i, variant)
        })
        .map(|(index, variant)| {
            itertools::iterate(Some(State::default()), move |state| {
                state
                    .unwrap_or_else(|| panic!("variant {} terminated!", index))
                    .next(&variant)
            })
        })
        .collect();

    loop {
        for v in &mut variants {
            v.next();
        }
    }
}

$ cargo run --quiet
thread 'main' panicked at 'variant 364 terminated!', src/main.rs:99:40
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

有意思! 现在我们终于可以回答这个问题了: 当程序终止时，累加器的值是多少？

use itertools::Itertools;

fn eval(program: &Program) -> Option<isize> {
    itertools::iterate(Some(State::default()), |state| {
        state.and_then(|state| state.next(program))
    })
    .while_some()
    .last()
    .map(|s| s.acc)
}

fn main() {
    let mut program = parse_program(include_str!("input.txt"));
    flip_kind(&mut program[364].kind);
    dbg!(eval(&program));
}

$ cargo run --quiet
[src/main.rs:79] eval(&program) = Some(
    758,
)

🎉🎉🎉!

下次见，保重。

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

23.advent-of-code-2020-day8.md

23.advent-of-code-2020-day8.md

第二部分

Files

23.advent-of-code-2020-day8.md

Latest commit

History

23.advent-of-code-2020-day8.md

File metadata and controls

第二部分