Advent of Code 2020 day08

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 값을 accumultator에 추가한 다음 다음 줄로 들어갑니다.acc 현재 줄에서 다음 줄이 아닌 상대값 줄로 이동합니다.
실제로 0줄부터 순서대로 실행하면 무한 순환이 되므로 순환을 통해 2주차에 접어들기 전의 accumulator 값을 되돌려줍니다.
우직한 simulation을 하고 실행하면 됩니다.실행된 줄만 저장 jmp 하면서 한 줄 한 줄 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

실제로 한 곳Vec과 nop만 바뀌었기 때문에 무한순환이 형성되었고, 이 순환을 수정하면 최종행에 정확하게 도달할 수 있을 것이다.이런 질문 입력법을 어떻게 만드는지...
파트1과 마찬가지로 simulation을 실행하는 방법을 준비했습니다.jmp를 매개변수에 전달하도록 지정하면 행Option<i32>과 nop만 대체합니다.방법의 반환값은 jmp이고 마지막 줄Result<i32, i32>까지 정확하게 실행하면 순환에 들어간 후에 되돌아온다Ok.
그리고 입력은 전 줄을 앞당겨 완성하는 것이 좋습니다.

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은 이 지정Err을 사용하여 아무 것도 변경하지 않고 실행한 None의 값을 사용할 수 있습니다.part2는 brute force에서 지정한 Err 이외의 줄을 사용해 보십시오. acc 되돌아오면 끝납니다.
입력은 600줄 정도이기 때문에 이런 방법으로 해결 방안을 먼저 얻을 수 있다.
더 효과적으로 하고 싶다면 백트랙 방법으로 중도 상태로 유지하고, 실패하면 거기로 돌아가는 게 좋겠죠.

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
    }