advent-of-code/source/year_2020/day_08/mod.rs

//! Day 08 of 2020.

use crate::prelude::*;

/// Get the solution for day 08 of 2020.
pub fn solution() -> Solution {
  Solution::new(Day::new(8, 2020), part_1, part_2).with_expected(1814, 1056)
}

/// The possible operations an instruction can perform.
#[derive(Debug, Eq, PartialEq, Hash, Clone)]
enum Operation {
  /// Increase or decrease the accumulator.
  Acc,
  /// Jump to a new instruction.
  Jmp,
  /// Do nothing, no operation.
  Nop,
}

impl From<&str> for Operation {
  fn from(input: &str) -> Self {
    match input {
      "acc" => Self::Acc,
      "jmp" => Self::Jmp,
      "nop" => Self::Nop,
      _ => unreachable!("{input}"),
    }
  }
}

/// Type alias for the arguments of operations.
type Argument = i32;

/// A single instruction.
#[derive(Debug, Eq, PartialEq, Hash, Clone)]
struct Instruction {
  /// The line the instruction was parsed from, used for debugging.
  line: usize,
  /// The operation to perform.
  op: Operation,
  /// The argument for the operation.
  arg: Argument,
}

impl From<(usize, &str)> for Instruction {
  fn from((line, input): (usize, &str)) -> Self {
    let mut split = input.split(' ');

    let op = split.next().map(Into::into).unwrap();
    let arg = split.next().map(|arg| arg.parse().unwrap()).unwrap();

    Self { line, op, arg }
  }
}

/// Execute the list of instructions and return the accumulator and whether or
/// not an infinite loop was encountered.
fn execute(instructions: &[Instruction]) -> (i32, bool) {
  let mut seen_instructions = HashSet::new();

  let mut accumulator = 0;
  let mut encountered_infinite_loop = false;
  let mut instruction_position = 0;

  while let Some(instruction) = instructions.get(instruction_position as usize)
  {
    if !seen_instructions.insert(instruction) {
      encountered_infinite_loop = true;
      break;
    }

    let mut increment_position = 1;
    match instruction.op {
      Operation::Acc => accumulator += instruction.arg,
      Operation::Jmp => increment_position = instruction.arg,
      Operation::Nop => (),
    };

    instruction_position += increment_position;
  }

  (accumulator, encountered_infinite_loop)
}

/// Parse the list of instructions from the puzzle input.
fn parse_instructions(input: &str) -> Vec<Instruction> {
  input.lines().enumerate().map(Into::into).collect()
}

/// The logic to solve part one.
fn part_1(input: &str) -> Result<String> {
  Ok(execute(&parse_instructions(input)).0.to_string())
}

/// The logic to solve part two.
fn part_2(input: &str) -> Result<String> {
  let instructions = parse_instructions(input);
  let mut part_2_result = None;

  for (index, instruction) in instructions.iter().enumerate() {
    let mut new_instructions = instructions.clone();

    if instruction.op == Operation::Jmp || instruction.op == Operation::Nop {
      let mut new_instruction = instruction.clone();
      new_instruction.op = match instruction.op {
        Operation::Jmp => Operation::Nop,
        Operation::Nop => Operation::Jmp,
        Operation::Acc => Operation::Acc,
      };
      new_instructions[index] = new_instruction;
    }

    let (result, encountered_infinite_loop) = execute(&new_instructions);
    if !encountered_infinite_loop {
      part_2_result = Some(result.to_string());
      break;
    }
  }

  Ok(part_2_result.unwrap())
}