You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

109 lines
2.7 KiB

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;
}
}