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.
 */

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

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

/// ### Day 5: Sunny with a Chance of Asteroids
///
/// [https://adventofcode.com/2019/day/5](https://adventofcode.com/2019/day/5)
///
/// You're starting to sweat as the ship makes its way toward Mercury.  The
/// Elves suggest that you get the air conditioner working by upgrading your
/// ship computer to support the Thermal Environment Supervision Terminal.
///
/// The Thermal Environment Supervision Terminal (TEST) starts by running a
/// *diagnostic program* (your puzzle input).  The TEST diagnostic program will
/// run on [your existing Intcode computer](https://adventofcode.com/2019/day/2) after a few modifications:
///
/// *First*, you'll need to add *two new instructions*:
///
///   - Opcode `3` takes a single integer as *input* and saves it to the position
///     given by its only parameter. For example, the instruction `3,50` would
///     take an input value and store it at address `50`.
///   - Opcode `4` *outputs* the value of its only parameter. For example, the
///     instruction `4,50` would output the value at address `50`.
///
/// Programs that use these instructions will come with documentation that
/// explains what should be connected to the input and output. The program
/// `3,0,4,0,99` outputs whatever it gets as input, then halts.
///
/// *Second*, you'll need to add support for *parameter modes*:
///
/// Each parameter of an instruction is handled based on its parameter mode.
/// Right now, your ship computer already understands parameter mode `0`,
/// *position mode*, which causes the parameter to be interpreted as a *position*
/// - if the parameter is `50`, its value is *the value stored at address `50` in
/// memory*. Until now, all parameters have been in position mode.
///
/// Now, your ship computer will also need to handle parameters in mode `1`,
/// *immediate mode*. In immediate mode, a parameter is interpreted as a *value*
/// - if the parameter is `50`, its value is simply *`50`*.
///
/// Parameter modes are stored in the same value as the instruction's opcode.
/// The opcode is a two-digit number based only on the ones and tens digit of
/// the value, that is, the opcode is the rightmost two digits of the first
/// value in an instruction. Parameter modes are single digits, one per
/// parameter, read right-to-left from the opcode: the first parameter's mode
/// is in the hundreds digit, the second parameter's mode is in the thousands
/// digit, the third parameter's mode is in the ten-thousands digit, and so
/// on. Any missing modes are `0`.
///
/// For example, consider the program `1002,4,3,4,33`.
///
/// The first instruction, `1002,4,3,4`, is a *multiply* instruction - the
/// rightmost two digits of the first value, `02`, indicate opcode `2`,
/// multiplication.  Then, going right to left, the parameter modes are `0`
/// (hundreds digit), `1` (thousands digit), and `0` (ten-thousands digit, not
/// present and therefore zero):
///
/// ```text
/// ABCDE
///  1002
///
/// DE - two-digit opcode,      02 == opcode 2
///  C - mode of 1st parameter,  0 == position mode
///  B - mode of 2nd parameter,  1 == immediate mode
///  A - mode of 3rd parameter,  0 == position mode,
///                                   omitted due to being a leading zero
/// ```
///
/// This instruction multiplies its first two parameters.  The first
/// parameter, `4` in position mode, works like it did before - its value is
/// the value stored at address `4` (`33`). The second parameter, `3` in immediate
/// mode, simply has value `3`. The result of this operation, `33 * 3 = 99`, is
/// written according to the third parameter, `4` in position mode, which also
/// works like it did before - `99` is written to address `4`.
///
/// Parameters that an instruction writes to will *never be in immediate mode*.
///
/// *Finally*, some notes:
///
///   - It is important to remember that the instruction pointer should
///     increase by *the number of values in the instruction* after the
///     instruction finishes. Because of the new instructions, this amount is
///     no longer always `4`.
///   - Integers can be negative: `1101,100,-1,4,0` is a valid program (find
///     `100 + -1`, store the result in position `4`).
///
/// The TEST diagnostic program will start by requesting from the user the ID
/// of the system to test by running an *input* instruction - provide it `1`, the
/// ID for the ship's air conditioner unit.
///
/// It will then perform a series of diagnostic tests confirming that various
/// parts of the Intcode computer, like parameter modes, function correctly.
/// For each test, it will run an *output* instruction indicating how far the
/// result of the test was from the expected value, where `0` means the test
/// was successful.  Non-zero outputs mean that a function is not working
/// correctly; check the instructions that were run before the output
/// instruction to see which one failed.
///
/// Finally, the program will output a *diagnostic code* and immediately halt.
/// This final output isn't an error; an output followed immediately by a
/// halt means the program finished.  If all outputs were zero except the
/// diagnostic code, the diagnostic program ran successfully.
///
/// After providing `1` to the only input instruction and passing all the
/// tests, *what diagnostic code does the program produce?*
///
/// ### Examples
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_05::{Intcode, input_generator, run_intcode_program};
/// assert_eq!(run_intcode_program(&mut input_generator("3,0,4,0,99"), &[1337]).outputs_port_b, [1337]);
/// ```
///
/// ```
/// # use codetrotter_aoc_2019_solutions::day_05::{Intcode, input_generator, run_intcode_program};
/// assert_eq!(run_intcode_program(&mut input_generator("1002,4,3,4,33"), &[]).memory, &[1002 as Intcode,4,3,4,99]);
/// ```
///
/// ```
/// # use codetrotter_aoc_2019_solutions::day_05::{Intcode, input_generator, run_intcode_program};
/// assert_eq!(run_intcode_program(&mut input_generator("1101,100,-1,4,0"), &[]).memory, &[1101 as Intcode,100,-1,4,99]);
/// ```
///
/// ### Solution
///
/// ⚠️ SPOILER ALERT ⚠️
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_05::{INPUT, input_generator, solve_part_1};
/// assert_eq!(solve_part_1(&mut input_generator(INPUT)), 5182797);
/// ```
pub fn solve_part_1 (input_memory: &mut Memory) -> Intcode
{
  let inputs_port_a = [1];
  let emulation_finished = run_intcode_program(input_memory, &inputs_port_a);
  *(emulation_finished.outputs_port_b.iter().last().unwrap())
}

pub type Intcode = i32;
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()
}

pub struct EmulationFinished<'a>
{
  pub memory:         &'a Memory,
  pub outputs_port_b: OutputsPortB,
}

enum Instruction
{
  Add,
  Multiply,
  ReadFromPortA,
  WriteToPortB,
  JumpIfTrue,
  JumpIfFalse,
  LessThan,
  Equals,
  Exit,
}

pub fn run_intcode_program<'a> (memory: &'a mut Memory, inputs_port_a: &InputsPortA) -> EmulationFinished<'a>
{
  let mut pc = 0;
  let mut outputs_port_b: OutputsPortB = vec![];
  let mut inputs_port_a_iter = inputs_port_a.iter();

  loop
  {
    let opcode = memory[pc];

    let (instruction, input_param_values_in_mem, output_param_value_in_mem) = match opcode % 100
    {
       1 => (Instruction::Add,           &memory[pc+1..=pc+2], Some(memory[pc+3])),
       2 => (Instruction::Multiply,      &memory[pc+1..=pc+2], Some(memory[pc+3])),
       3 => (Instruction::ReadFromPortA, &[][..],              Some(memory[pc+1])),
       4 => (Instruction::WriteToPortB,  &memory[pc+1..=pc+1], None),
       5 => (Instruction::JumpIfTrue,    &memory[pc+1..=pc+2], None),
       6 => (Instruction::JumpIfFalse,   &memory[pc+1..=pc+2], None),
       7 => (Instruction::LessThan,      &memory[pc+1..=pc+2], Some(memory[pc+3])),
       8 => (Instruction::Equals,        &memory[pc+1..=pc+2], Some(memory[pc+3])),
      99 => (Instruction::Exit,          &[][..],              None),
       _ => panic!("Invalid opcode {} at position {}", opcode, pc),
    };

    let mut input_param_modes = opcode / 100;
    let mut input_param_values = Vec::from(input_param_values_in_mem);
    for input_param_value in input_param_values.iter_mut()
    {
      if input_param_modes & 1 == 0 // position mode
        { *input_param_value = memory[*input_param_value as usize]; }
      input_param_modes /= 10;
    }
    assert_eq!(input_param_modes, 0);

    pc += input_param_values.len() + output_param_value_in_mem.is_some() as usize + 1;

    match instruction
    {
      Instruction::Add           => memory[output_param_value_in_mem.unwrap() as usize] = input_param_values[0] + input_param_values[1],
      Instruction::Multiply      => memory[output_param_value_in_mem.unwrap() as usize] = input_param_values[0] * input_param_values[1],
      Instruction::ReadFromPortA => memory[output_param_value_in_mem.unwrap() as usize] = *inputs_port_a_iter.next().unwrap(),
      Instruction::WriteToPortB  => outputs_port_b.push(input_param_values[0]),
      Instruction::JumpIfTrue    => if input_param_values[0] != 0 { pc = input_param_values[1] as usize; },
      Instruction::JumpIfFalse   => if input_param_values[0] == 0 { pc = input_param_values[1] as usize; },
      Instruction::LessThan      => memory[output_param_value_in_mem.unwrap() as usize] = (input_param_values[0]  < input_param_values[1]) as Intcode,
      Instruction::Equals        => memory[output_param_value_in_mem.unwrap() as usize] = (input_param_values[0] == input_param_values[1]) as Intcode,
      Instruction::Exit          => break,
    }
  }

  EmulationFinished
  {
    memory,
    outputs_port_b,
  }
}

/// ### Day 5, Part Two
///
/// [https://adventofcode.com/2019/day/5#part2](https://adventofcode.com/2019/day/5#part2)
///
/// The air conditioner comes online! Its cold air feels good for a while,
/// but then the TEST alarms start to go off. Since the air conditioner can't
/// vent its heat anywhere but back into the spacecraft, it's actually making
/// the air inside the ship *warmer*.
///
/// Instead, you'll need to use the TEST to extend the [thermal radiators](https://en.wikipedia.org/wiki/Spacecraft_thermal_control).
/// Fortunately, the diagnostic program (your puzzle input) is already
/// equipped for this.  Unfortunately, your Intcode computer is not.
///
/// Your computer is only missing a few opcodes:
///
///   - Opcode `5` is *jump-if-true*: if the first parameter is *non-zero*, it sets
///     the instruction pointer to the value from the second parameter.
///     Otherwise, it does nothing.
///   - Opcode `6` is *jump-if-false*: if the first parameter *is zero*, it sets
///     the instruction pointer to the value from the second parameter.
///     Otherwise, it does nothing.
///   - Opcode `7` is *less than*: if the first parameter is *less than* the second
///     parameter, it stores `1` in the position given by the third parameter.
///     Otherwise, it stores `0`.
///   - Opcode `8` is *equals*: if the first parameter is *equal to* the second
///     parameter, it stores `1` in the position given by the third parameter.
///     Otherwise, it stores `0`.
///
/// Like all instructions, these instructions need to support *parameter modes*
/// as described above.
///
/// Normally, after an instruction is finished, the instruction pointer
/// increases by the number of values in that instruction. *However*, if the
/// instruction modifies the instruction pointer, that value is used and the
/// instruction pointer is *not automatically increased*.
///
/// For example, here are several programs that take one input, compare it to
/// the value `8`, and then produce one output:
///
///   - `3,9,8,9,10,9,4,9,99,-1,8` - Using *position mode*, consider whether the
///     input is *equal to* `8`; output `1` (if it is) or `0` (if it is not).
///   - `3,9,7,9,10,9,4,9,99,-1,8` - Using *position mode*, consider whether the
///     input is *less than* `8`; output `1` (if it is) or `0` (if it is not).
///   - `3,3,1108,-1,8,3,4,3,99` - Using *immediate mode*, consider whether the
///     input is *equal to* `8`; output `1` (if it is) or `0` (if it is not).
///   - `3,3,1107,-1,8,3,4,3,99` - Using *immediate mode*, consider whether the
///     input is *less than *`8`; output `1` (if it is) or `0` (if it is not).
///
/// Here are some jump tests that take an input, then output `0` if the input
/// was zero or `1` if the input was non-zero:
///
///   - `3,12,6,12,15,1,13,14,13,4,13,99,-1,0,1,9` (using *position mode*)
///   - `3,3,1105,-1,9,1101,0,0,12,4,12,99,1` (using *immediate mode*)
///
/// Here's a larger example:
///
/// ```text
/// 3,21,1008,21,8,20,1005,20,22,107,8,21,20,1006,20,31,
/// 1106,0,36,98,0,0,1002,21,125,20,4,20,1105,1,46,104,
/// 999,1105,1,46,1101,1000,1,20,4,20,1105,1,46,98,99
/// ```
///
/// The above example program uses an input instruction to ask for a single
/// number.  The program will then output `999` if the input value is below `8`,
/// output `1000` if the input value is equal to `8`, or output `1001` if the input
/// value is greater than `8`.
///
/// This time, when the TEST diagnostic program runs its input instruction to
/// get the ID of the system to test, *provide it `5`*, the ID for the ship's
/// thermal radiator controller. This diagnostic test suite only outputs one
/// number, the *diagnostic code*.
///
/// *What is the diagnostic code for system ID `5`?*
///
/// ### Examples
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_05::{input_generator, run_intcode_program};
/// let memory_compare_input_to_8_1 = input_generator("3,9,8,9,10,9,4,9,99,-1,8");
/// assert_eq!(run_intcode_program(&mut memory_compare_input_to_8_1.clone(), &[8]).outputs_port_b, [1]);
/// assert_eq!(run_intcode_program(&mut memory_compare_input_to_8_1.clone(), &[9]).outputs_port_b, [0]);
/// ```
///
/// ```
/// # use codetrotter_aoc_2019_solutions::day_05::{input_generator, run_intcode_program};
/// let memory_compare_input_to_8_2 = input_generator("3,9,7,9,10,9,4,9,99,-1,8");
/// assert_eq!(run_intcode_program(&mut memory_compare_input_to_8_2.clone(), &[7]).outputs_port_b, [1]);
/// assert_eq!(run_intcode_program(&mut memory_compare_input_to_8_2.clone(), &[8]).outputs_port_b, [0]);
/// ```
///
/// ```
/// # use codetrotter_aoc_2019_solutions::day_05::{input_generator, run_intcode_program};
/// let memory_compare_input_to_8_3 = input_generator("3,3,1108,-1,8,3,4,3,99");
/// assert_eq!(run_intcode_program(&mut memory_compare_input_to_8_3.clone(), &[8]).outputs_port_b, [1]);
/// assert_eq!(run_intcode_program(&mut memory_compare_input_to_8_3.clone(), &[9]).outputs_port_b, [0]);
/// ```
///
/// ```
/// # use codetrotter_aoc_2019_solutions::day_05::{input_generator, run_intcode_program};
/// let memory_compare_input_to_8_4 = input_generator("3,3,1107,-1,8,3,4,3,99");
/// assert_eq!(run_intcode_program(&mut memory_compare_input_to_8_4.clone(), &[7]).outputs_port_b, [1]);
/// assert_eq!(run_intcode_program(&mut memory_compare_input_to_8_4.clone(), &[8]).outputs_port_b, [0]);
/// ```
///
/// ```
/// # use codetrotter_aoc_2019_solutions::day_05::{input_generator, run_intcode_program};
/// let memory_jump_compare_to_zero_1 = input_generator("3,12,6,12,15,1,13,14,13,4,13,99,-1,0,1,9");
/// assert_eq!(run_intcode_program(&mut memory_jump_compare_to_zero_1.clone(), &[0]).outputs_port_b, [0]);
/// assert_eq!(run_intcode_program(&mut memory_jump_compare_to_zero_1.clone(), &[2]).outputs_port_b, [1]);
/// ```
///
/// ```
/// # use codetrotter_aoc_2019_solutions::day_05::{input_generator, run_intcode_program};
/// let memory_jump_compare_to_zero_2 = input_generator("3,3,1105,-1,9,1101,0,0,12,4,12,99,1");
/// assert_eq!(run_intcode_program(&mut memory_jump_compare_to_zero_2.clone(), &[0]).outputs_port_b, [0]);
/// assert_eq!(run_intcode_program(&mut memory_jump_compare_to_zero_2.clone(), &[2]).outputs_port_b, [1]);
/// ```
///
/// ```
/// # use codetrotter_aoc_2019_solutions::day_05::{input_generator, run_intcode_program};
/// let memory_larger_example = input_generator("\
///   3,21,1008,21,8,20,1005,20,22,107,8,21,20,1006,20,31,\
///   1106,0,36,98,0,0,1002,21,125,20,4,20,1105,1,46,104,\
///   999,1105,1,46,1101,1000,1,20,4,20,1105,1,46,98,99");
/// assert_eq!(run_intcode_program(&mut memory_larger_example.clone(), &[7]).outputs_port_b, [ 999]);
/// assert_eq!(run_intcode_program(&mut memory_larger_example.clone(), &[8]).outputs_port_b, [1000]);
/// assert_eq!(run_intcode_program(&mut memory_larger_example.clone(), &[9]).outputs_port_b, [1001]);
/// ```
///
/// ### Solution
///
/// ⚠️ SPOILER ALERT ⚠️
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_05::{INPUT, input_generator, solve_part_2};
/// assert_eq!(solve_part_2(&mut input_generator(INPUT)), 12077198);
/// ```
pub fn solve_part_2 (input_memory: &mut Memory) -> Intcode
{
  let inputs_port_a = [5];
  let emulation_finished = run_intcode_program(input_memory, &inputs_port_a);
  *(emulation_finished.outputs_port_b.iter().last().unwrap())
}