Advent of Code 2020 day08

3 min read読了の目安(約3100字

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

part1同様にsimulation実行するメソッドを用意した。引数に Option<i32> を渡し 指定されていたらその行だけ nopjmp を入れ替えて実行する。メソッドの返り値は 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
    }