codetrotter_aoc_2019_solutions 0.9.0

/*
 * Copyright (c) 2019, 2020 Erik Nordstrøm <erik@nordstroem.no>
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

use std::sync::mpsc::{Sender, Receiver};
use std::sync::mpsc;
use std::thread;
use std::thread::JoinHandle;
use std::convert::TryFrom;
use std::collections::HashMap;

solution_printer!(9, print_solution, input_generator, INPUT, solve_part_1, solve_part_2);

pub const INPUT: &str = include_str!("../input/2019/day9.txt");

/// ### Day 9: Sensor Boost
///
/// [https://adventofcode.com/2019/day/9](https://adventofcode.com/2019/day/9)
///
/// You've just said goodbye to the rebooted rover and left Mars when you
/// receive a faint distress signal coming from the asteroid belt.  It must be
/// the Ceres monitoring station!
///
/// In order to lock on to the signal, you'll need to boost your sensors. The
/// Elves send up the latest *BOOST* program - Basic Operation Of System Test.
///
/// While BOOST (your puzzle input) is capable of boosting your sensors, for
/// tenuous safety reasons, it refuses to do so until the computer it runs on
/// passes some checks to demonstrate it is a *complete Intcode computer*.
///
/// [Your existing Intcode computer](https://adventofcode.com/2019/day/5) is missing one key feature: it needs support
/// for parameters in *relative mode*.
///
/// Parameters in mode `2`, *relative mode*, behave very similarly to parameters in
/// *position mode*: the parameter is interpreted as a position.  Like position
/// mode, parameters in relative mode can be read from or written to.
///
/// The important difference is that relative mode parameters don't count from
/// address `0`.  Instead, they count from a value called the *relative base*. The
/// *relative base* starts at `0`.
///
/// The address a relative mode parameter refers to is itself *plus* the current
/// *relative base*. When the relative base is `0`, relative mode parameters and
/// position mode parameters with the same value refer to the same address.
///
/// For example, given a relative base of `50`, a relative mode parameter of `-7`
/// refers to memory address `50 + -7 = 43`.
///
/// The relative base is modified with the *relative base offset* instruction:
///
///   - Opcode `9` *adjusts the relative base* by the value of its only parameter.
///     The relative base increases (or decreases, if the value is negative)
///     by the value of the parameter.
///
/// For example, if the relative base is `2000`, then after the instruction
/// `109,19`, the relative base would be `2019`. If the next instruction were
/// `204,-34`, then the value at address `1985` would be output.
///
/// Your Intcode computer will also need a few other capabilities:
///
///   - The computer's available memory should be much larger than the initial
///     program. Memory beyond the initial program starts with the value `0` and
///     can be read or written like any other memory. (It is invalid to try to
///     access memory at a negative address, though.)
///   - The computer should have support for large numbers. Some instructions
///     near the beginning of the BOOST program will verify this capability.
///
/// Here are some example programs that use these features:
///
///   - `109,1,204,-1,1001,100,1,100,1008,100,16,101,1006,101,0,99` takes no
///     input and produces a [copy of itself](https://en.wikipedia.org/wiki/Quine_(computing)) as output.
///   - `1102,34915192,34915192,7,4,7,99,0` should output a 16-digit number.
///   - `104,1125899906842624,99` should output the large number in the middle.
///
/// The BOOST program will ask for a single input; run it in test mode by
/// providing it the value `1`. It will perform a series of checks on each
/// opcode, output any opcodes (and the associated parameter modes) that seem
/// to be functioning incorrectly, and finally output a BOOST keycode.
///
/// Once your Intcode computer is fully functional, the BOOST program should
/// report no malfunctioning opcodes when run in test mode; it should only
/// output a single value, the BOOST keycode. *What BOOST keycode does it
/// produce?*
///
/// ### Examples
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_09::{input_generator, run_single_program_with_predefined_inputs};
/// const EX1PROG: &'static str = "109,1,204,-1,1001,100,1,100,1008,100,16,101,1006,101,0,99";
/// assert_eq!(run_single_program_with_predefined_inputs(&input_generator(EX1PROG), &[]),
///   vec![109,1,204,-1,1001,100,1,100,1008,100,16,101,1006,101,0,99]);
/// ```
///
/// ```
/// # use codetrotter_aoc_2019_solutions::day_09::{input_generator, run_single_program_with_predefined_inputs};
/// const EX2PROG: &'static str = "1102,34915192,34915192,7,4,7,99,0";
/// let number_str = run_single_program_with_predefined_inputs(&input_generator(EX2PROG), &[])[0].to_string();
/// assert_eq!(number_str.len(), 16);
/// ```
///
/// ```
/// # use codetrotter_aoc_2019_solutions::day_09::{input_generator, run_single_program_with_predefined_inputs};
/// const EX3PROG: &'static str = "104,1125899906842624,99";
/// assert_eq!(run_single_program_with_predefined_inputs(&input_generator(EX3PROG), &[]),
///   vec![1125899906842624]);
/// ```
///
/// ### Solution
///
/// ⚠️ SPOILER ALERT ⚠️
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_09::{INPUT, input_generator, solve_part_1};
/// assert_eq!(solve_part_1(&mut input_generator(INPUT)), 3533056970);
/// ```
pub fn solve_part_1 (program_image: &Memory) -> Intcode
{
  let outputs = run_single_program_with_predefined_inputs(program_image, &[1]);
  assert_eq!(outputs.len(), 1);
  outputs[0]
}

pub type Intcode = i64;
pub type Memory = Vec<Intcode>;
pub type InputsPortA = [Intcode];
pub type OutputsPortB = Vec<Intcode>;

pub fn input_generator (input: &str) -> Memory
{
  input.trim_end_matches('\n').split(',').map(|intcode_str| intcode_str.parse::<Intcode>().unwrap()).collect()
}

#[derive(Debug)]
enum Instruction
{
  Add,
  Multiply,
  ReadFromPortA,
  WriteToPortB,
  JumpIfTrue,
  JumpIfFalse,
  LessThan,
  Equals,
  AdjustRelativeBase,
  Exit,
}

pub fn run_single_program_with_predefined_inputs (program_image: &Memory, inputs: &'static InputsPortA) -> OutputsPortB
{
  let (emulator_input_tx,  emulator_input_rx)  = mpsc::channel();
  let (emulator_output_tx, emulator_output_rx) = mpsc::channel();
  let (output_reader_signal_tx, output_reader_signal_rx) = mpsc::channel();

  //debug_log!("Start output reader");
  let output_reader_handle = thread::spawn(move ||
  {
    //debug_log!("Output reader started");
    let mut outputs = vec![];
    loop
    {
      match emulator_output_rx.try_recv()
      {
        Ok(value) =>
        {
          //debug_log!(format_args!("Output reader read {}", value));
          outputs.push(value);
        },
        Err(_) => if let Ok(_) = output_reader_signal_rx.try_recv()
        {
          break;
        }
      }
    }
    //debug_log!("Output reader shutting down");
    outputs
  });

  //debug_log!("Start Intcode computer emulator");
  let emulator_handle =
    run_intcode_computer_emulator_thread(program_image, emulator_input_rx,  emulator_output_tx);

  //debug_log!("Start input writer");
  let input_writer_handle = thread::spawn(move ||
  {
    //debug_log!("Input writer started");
    for &input in inputs
    {
      emulator_input_tx.send(input).unwrap();
      //debug_log!(format_args!("Input writer wrote {}", input));
    }
    //debug_log!("Input writer shutting down");
  });

  //debug_log!("Join threads");

  input_writer_handle.join().unwrap();
  emulator_handle.join().unwrap();
  output_reader_signal_tx.send(true).unwrap();
  output_reader_handle.join().unwrap()
}

pub struct EmulationFinished
{
  pub virtual_memory: VirtualMemory,
  pub pc: usize,
  pub rb: usize,
  pub num_cpu_cycles_emulated: u64,
  pub num_inputs_read: u64,
  pub num_outputs_written: u64,
}

pub struct VirtualMemory
{
  real_memory: Memory,
  program_image_len: usize,
  virtual_address_mapping: HashMap<usize, usize>,
}

impl From<Memory> for VirtualMemory
{
  fn from (program_image: Memory) -> Self
  {
    let program_image_len = program_image.len();
    Self
    {
      real_memory: program_image,
      program_image_len,
      virtual_address_mapping: Default::default(),
    }
  }
}

impl VirtualMemory
{
  fn read (&self, address: usize) -> Intcode
  {
    if address < self.program_image_len
    {
      self.real_memory[address]
    }
    else
    {
      match self.virtual_address_mapping.get(&address)
      {
        Some(&real_address) => self.real_memory[real_address],
        None => 0, // XXX: "Memory beyond the initial program starts with the value 0
                   //       and can be read or written like any other memory."
      }
    }
  }

  fn write (&mut self, address: usize, value: Intcode)
  {
    if address < self.program_image_len
    {
      self.real_memory[address] = value;
    }
    else if let Some(&real_address) = self.virtual_address_mapping.get(&address)
    {
      self.real_memory[real_address] = value;
    }
    else
    {
      self.real_memory.push(value);
      self.virtual_address_mapping.insert(address, self.real_memory.len() - 1);
    }
  }
}

#[derive(Debug)]
enum ParamMode
{
  PositionMode,
  ImmediateMode,
  RelativeMode,
}

impl TryFrom<Intcode> for ParamMode
{
  type Error = &'static str;

  fn try_from (value: Intcode) -> Result<Self, Self::Error>
  {
    match value
    {
      0 => Ok(Self::PositionMode),
      1 => Ok(Self::ImmediateMode),
      2 => Ok(Self::RelativeMode),
      _ => Err("Invalid mode for parameter."),
    }
  }
}

pub fn run_intcode_computer_emulator_thread (program_image: &Memory, inputs_port_a_rx: Receiver<Intcode>, outputs_port_b_tx: Sender<Intcode>) -> JoinHandle<EmulationFinished>
{
  let mut vmem = VirtualMemory::from(program_image.clone());

  thread::spawn(move ||
  {
    //debug_log!("Intcode computer emulator started");

    let mut pc = 0; // Program Counter
    let mut rb = 0; // Relative Base

    let mut num_cpu_cycles_emulated = 0;
    let mut num_inputs_read = 0;
    let mut num_outputs_written = 0;

    loop
    {
      //debug_log!(format_args!("Loop #{}. pc: {}, rb: {}", num_cpu_cycles_emulated + 1, pc, rb));
      num_cpu_cycles_emulated += 1;

      let opcode = vmem.read(pc);
      //debug_log!(format_args!("  Opcode: {}", opcode));

      let mut param_modes = opcode / 100;

      let (instruction, (input_param_1, input_param_2), output_addr_param) = match opcode % 100
      {
         1 => (Instruction::Add,                (Some(vmem.read(pc+1)), Some(vmem.read(pc+2))), Some(vmem.read(pc+3))),
         2 => (Instruction::Multiply,           (Some(vmem.read(pc+1)), Some(vmem.read(pc+2))), Some(vmem.read(pc+3))),
         3 => (Instruction::ReadFromPortA,      (None,                  None),                  Some(vmem.read(pc+1))),
         4 => (Instruction::WriteToPortB,       (Some(vmem.read(pc+1)), None),                  None),
         5 => (Instruction::JumpIfTrue,         (Some(vmem.read(pc+1)), Some(vmem.read(pc+2))), None),
         6 => (Instruction::JumpIfFalse,        (Some(vmem.read(pc+1)), Some(vmem.read(pc+2))), None),
         7 => (Instruction::LessThan,           (Some(vmem.read(pc+1)), Some(vmem.read(pc+2))), Some(vmem.read(pc+3))),
         8 => (Instruction::Equals,             (Some(vmem.read(pc+1)), Some(vmem.read(pc+2))), Some(vmem.read(pc+3))),
         9 => (Instruction::AdjustRelativeBase, (Some(vmem.read(pc+1)), None),                  None),
        99 => (Instruction::Exit,               (None,                  None),                  None),
         _ => panic!("Invalid opcode {} at position {}", opcode, pc),
      };
      //debug_log!(format_args!("  instruction: {:?}, input_param_1: {:?}, input_param_2: {:?}, output_addr_param: {:?}", instruction, input_param_1, input_param_2, output_addr_param));

      let input_param_1 = match input_param_1
      {
        None => None,
        Some(ip1_value) =>
        {
          let ip1m = ParamMode::try_from(param_modes % 10).unwrap(); // Mode of input parameter 1
          param_modes /= 10;
          //debug_log!(format_args!("  ip1m: {:?}. Param modes remaining: {}", ip1m, param_modes));
          match ip1m
          {
            ParamMode::PositionMode  => Some(vmem.read(usize::try_from(ip1_value).unwrap())),
            ParamMode::ImmediateMode => Some(ip1_value),
            ParamMode::RelativeMode  => Some(vmem.read(usize::try_from(Intcode::try_from(rb).unwrap() + ip1_value).unwrap())),
          }
        }
      };

      let input_param_2 = match input_param_2
      {
        None => None,
        Some(ip2_value) =>
        {
          let ip2m = ParamMode::try_from(param_modes % 20).unwrap(); // Mode of input parameter 2
          param_modes /= 10;
          //debug_log!(format_args!("  ip2m: {:?}. Param modes remaining: {}", ip2m, param_modes));
          match ip2m
          {
            ParamMode::PositionMode  => Some(vmem.read(usize::try_from(ip2_value).unwrap())),
            ParamMode::ImmediateMode => Some(ip2_value),
            ParamMode::RelativeMode  => Some(vmem.read(usize::try_from(Intcode::try_from(rb).unwrap() + ip2_value).unwrap())),
          }
        }
      };

      let output_addr_param = match output_addr_param
      {
        None => None,
        Some(oap_value) =>
        {
          let oapm = ParamMode::try_from(param_modes % 10).unwrap(); // Mode of output addr parameter
          param_modes /= 10;
          //debug_log!(format_args!("  oapm: {:?}. Param modes remaining: {}", oapm, param_modes));
          match oapm
          {
            ParamMode::PositionMode  => Some(oap_value),
            ParamMode::ImmediateMode => panic!("Illegal mode for output address parameter: Immediate mode!"),
            ParamMode::RelativeMode  => Some(Intcode::try_from(rb).unwrap() + oap_value),
          }
        }
      };

      assert_eq!(param_modes, 0);

      //debug_log!(format_args!("  input_param_1: {:?}, input_param_2: {:?}", input_param_1, input_param_2));

      pc += usize::from(input_param_1.is_some()) + usize::from(input_param_2.is_some()) + usize::from(output_addr_param.is_some()) + 1;

      match instruction
      {
        Instruction::Add                => vmem.write(usize::try_from(output_addr_param.unwrap()).unwrap(), input_param_1.unwrap() + input_param_2.unwrap()),
        Instruction::Multiply           => vmem.write(usize::try_from(output_addr_param.unwrap()).unwrap(), input_param_1.unwrap() * input_param_2.unwrap()),
        Instruction::ReadFromPortA      => { vmem.write(usize::try_from(output_addr_param.unwrap()).unwrap(), inputs_port_a_rx.recv().unwrap()); num_inputs_read += 1; },
        Instruction::WriteToPortB       => { outputs_port_b_tx.send(input_param_1.unwrap()).unwrap(); num_outputs_written += 1; },
        Instruction::JumpIfTrue         => if input_param_1.unwrap() != 0 { pc = usize::try_from(input_param_2.unwrap()).unwrap(); },
        Instruction::JumpIfFalse        => if input_param_1.unwrap() == 0 { pc = usize::try_from(input_param_2.unwrap()).unwrap(); },
        Instruction::LessThan           => vmem.write(usize::try_from(output_addr_param.unwrap()).unwrap(), Intcode::from(input_param_1.unwrap()  < input_param_2.unwrap())),
        Instruction::Equals             => vmem.write(usize::try_from(output_addr_param.unwrap()).unwrap(), Intcode::from(input_param_1.unwrap() == input_param_2.unwrap())),
        Instruction::AdjustRelativeBase => rb = usize::try_from(Intcode::try_from(rb).unwrap() + input_param_1.unwrap()).unwrap(),
        Instruction::Exit               => break,
      }
    }

    EmulationFinished
    {
      virtual_memory: vmem,
      pc,
      rb,
      num_cpu_cycles_emulated,
      num_inputs_read,
      num_outputs_written,
    }
  })
}

/// ### Day 9, Part Two
///
/// [https://adventofcode.com/2019/day/9#part2](https://adventofcode.com/2019/day/9#part2)
///
/// *You now have a complete Intcode computer.*
///
/// Finally, you can lock on to the Ceres distress signal! You just need to
/// boost your sensors using the BOOST program.
///
/// The program runs in sensor boost mode by providing the input instruction
/// the value `2`.  Once run, it will boost the sensors automatically, but it
/// might take a few seconds to complete the operation on slower hardware.  In
/// sensor boost mode, the program will output a single value: *the coordinates
/// of the distress signal*.
///
/// Run the BOOST program in sensor boost mode.  *What are the coordinates of the
/// distress signal?*
///
/// ### Solution
///
/// ⚠️ SPOILER ALERT ⚠️
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_09::{INPUT, input_generator, solve_part_2};
/// assert_eq!(solve_part_2(&input_generator(INPUT)), 72852);
/// ```
pub fn solve_part_2 (program_image: &Memory) -> Intcode
{
  let outputs = run_single_program_with_predefined_inputs(program_image, &[2]);
  assert_eq!(outputs.len(), 1);
  outputs[0]
}