🎄

Advent of Code 2020 day08

2020/12/15に公開

Rust

adventofcode

tech

https://adventofcode.com/2020/day/8

part1

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

といった入力が与えられる。nop は何もせずに次の行へ、acc はaccumulatorに値を加算してから次の行へ。jmp は次の行ではなく現在行から相対的な値の行へjumpする。

実際に0行目から順に実行してみると無限ループになるので、そのループにより2周目に入る直前時点でのaccumulatorの値を返せ、というもの。

愚直にsimulationして実行していく、で良さそう。実行済みの行を保存するVecだけ作成し、そこに記録しながら1行ずつparseしながら実行していく。実行済みの行に辿り着いたらそのときのaccumulatorの値を返せば良い。

struct Solution {
    inputs: Vec<String>,
}

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        Self { inputs }
    }
    fn solve_1(&self) -> i32 {
        let mut visited: Vec<bool> = vec![false; self.inputs.len()];
        let (mut i, mut acc) = (0, 0);
        loop {
            if visited[i as usize] {
                return acc;
            }
            visited[i as usize] = true;
            let instruction = &self.inputs[i as usize];
            if let Ok(arg) = instruction[4..].parse::<i32>() {
                match &instruction[..3] {
                    "acc" => acc += arg,
                    "jmp" => i += arg - 1,
                    _ => {}
                }
            }
            i += 1;
        }
    }
}

part2

実はどこか1箇所だけ nop と jmp が入れ替わってしまっていることが原因で無限ループになっており、そこを直せば正しく最終行に到達できるはず、とのこと。どうやってそういう問題入力を生成したんだ…

part1同様にsimulation実行するメソッドを用意した。引数に Option<i32> を渡し指定されていたらその行だけ nop と jmp を入れ替えて実行する。メソッドの返り値は Result<i32, i32> にし、正しく最終行まで実行されたら Ok, ループに突入したら Err を返すようにした。
あと入力は予め全行parse済みにしておいた方が効率良さそうだった。

struct Solution {
    instructions: Vec<(String, i32)>,
}

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        Self {
            instructions: inputs
                .iter()
                .map(|input| (input[..3].to_string(), input[4..].parse().unwrap()))
                .collect(),
        }
    }
    fn run(&self, change: Option<i32>) -> Result<i32, i32> {
        let mut visited: Vec<bool> = vec![false; self.instructions.len()];
        let (mut i, mut acc) = (0, 0);
        while i < self.instructions.len() as i32 {
            if visited[i as usize] {
                return Err(acc);
            }
            visited[i as usize] = true;
            let instruction = &self.instructions[i as usize];
            match instruction.0.as_str() {
                "acc" => acc += instruction.1,
                "jmp" if change != Some(i) => i += instruction.1 - 1,
                "nop" if change == Some(i) => i += instruction.1 - 1,
                _ => {}
            }
            i += 1;
        }
        Ok(acc)
    }
}

part1 はこれを使って None を指定しどこも変更せずに実行して得た Err の値を使えばよい。part2 は acc ではない行をbrute forceで指定して試してみて、Ok が返ってきたらそれで終了、とする。
入力は600行程度なので一応こんな方法でもとりあえず解は得られる。

より効率的にやるなら backtracking的な方法で途中まで実行した状態を保持しておいて失敗した場合はそこまで戻るだけ、にするのが良いのかな。

code

    fn solve_1(&self) -> i32 {
        self.run(None).unwrap_err()
    }
    fn solve_2(&self) -> i32 {
        for (i, input) in self.inputs.iter().enumerate() {
            if !input.starts_with("acc") {
                if let Ok(n) = self.run(Some(i as i32)) {
                    return n;
                }
            }
        }
        0
    }

part1

part2

code

Discussion