110 lines
2.7 KiB
Rust
110 lines
2.7 KiB
Rust
const INPUT: &str = include_str!("../../data/day8");
|
|
|
|
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
|
|
enum Instruction {
|
|
Acc(i64),
|
|
Jmp(isize),
|
|
Nop(isize),
|
|
}
|
|
|
|
impl Instruction {
|
|
fn parse(line: &str) -> Self {
|
|
let line = line.trim();
|
|
if let Some(param) = line.strip_prefix("acc ") {
|
|
Instruction::Acc(param.parse().unwrap())
|
|
} else if let Some(param) = line.strip_prefix("jmp ") {
|
|
Instruction::Jmp(param.parse().unwrap())
|
|
} else if let Some(param) = line.strip_prefix("nop ") {
|
|
Instruction::Nop(param.parse().unwrap())
|
|
} else {
|
|
panic!("Unknown instructin: {:?}", line);
|
|
}
|
|
}
|
|
|
|
fn parse_list(input: &str) -> Vec<Self> {
|
|
input.lines().map(Self::parse).collect()
|
|
}
|
|
}
|
|
|
|
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
|
|
enum EmulationStepResult {
|
|
Success,
|
|
EndOfCode,
|
|
InfiniteLoop,
|
|
}
|
|
|
|
#[derive(Clone, Debug)]
|
|
struct Emulator<'a> {
|
|
instructions: &'a [Instruction],
|
|
visited: Vec<bool>,
|
|
accumulator: i64,
|
|
next_instruction: usize,
|
|
}
|
|
|
|
impl<'a> Emulator<'a> {
|
|
fn new(instructions: &'a [Instruction]) -> Self {
|
|
let mut visited = Vec::new();
|
|
visited.resize(instructions.len(), false);
|
|
Self { instructions, visited, accumulator: 0, next_instruction: 0 }
|
|
}
|
|
|
|
fn step(&mut self) -> EmulationStepResult {
|
|
if self.next_instruction >= self.instructions.len() {
|
|
return EmulationStepResult::EndOfCode;
|
|
}
|
|
if self.visited[self.next_instruction] {
|
|
return EmulationStepResult::InfiniteLoop;
|
|
}
|
|
self.visited[self.next_instruction] = true;
|
|
match self.instructions[self.next_instruction] {
|
|
Instruction::Acc(inc) => {
|
|
self.accumulator += inc;
|
|
},
|
|
Instruction::Jmp(offset) => {
|
|
let ip = self.next_instruction as isize + offset;
|
|
assert!(ip >= 0);
|
|
self.next_instruction = ip as usize;
|
|
return EmulationStepResult::Success; // don't increment again below
|
|
},
|
|
Instruction::Nop(_) => (),
|
|
}
|
|
self.next_instruction += 1;
|
|
EmulationStepResult::Success
|
|
}
|
|
|
|
fn run(&mut self) -> bool {
|
|
loop {
|
|
match self.step() {
|
|
EmulationStepResult::Success => (), // continue
|
|
EmulationStepResult::InfiniteLoop => return false,
|
|
EmulationStepResult::EndOfCode => return true,
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
fn main() {
|
|
let mut instructions = Instruction::parse_list(INPUT);
|
|
{
|
|
let mut emu = Emulator::new(&instructions);
|
|
assert!(!emu.run()); // expecting infinite loop
|
|
println!("Accumulator at loop: {}", emu.accumulator);
|
|
}
|
|
for i in 0..instructions.len() {
|
|
let orig = instructions[i];
|
|
instructions[i] = match orig {
|
|
Instruction::Acc(_) => continue,
|
|
Instruction::Jmp(a) => Instruction::Nop(a),
|
|
Instruction::Nop(a) => Instruction::Jmp(a),
|
|
};
|
|
{
|
|
let mut emu = Emulator::new(&instructions);
|
|
if emu.run() {
|
|
println!("Found fixed program (modified at {}), accumulator at end: {}", i, emu.accumulator);
|
|
break;
|
|
}
|
|
}
|
|
instructions[i] = orig;
|
|
}
|
|
}
|