aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorGravatar alecdwm 2019-12-05 17:20:19 +1000
committerGravatar alecdwm 2019-12-05 17:20:19 +1000
commit44b9ea085771da52ce1eb3e690d00b721116a509 (patch)
tree4387c7130273816c934716dd0de6161f1cbe29c8
parent4c1be48b087358c8b5095ad67881b9c233e24125 (diff)
added 2019 day5 part1 solution
-rw-r--r--src/lib.rs1
-rw-r--r--src/main.rs1
-rw-r--r--src/year_2019/day2.rs2
-rw-r--r--src/year_2019/day5.rs94
-rw-r--r--src/year_2019/intcode_computer.rs218
5 files changed, 287 insertions, 29 deletions
diff --git a/src/lib.rs b/src/lib.rs
index ce2767a..7fdef49 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -33,4 +33,5 @@ pub mod year_2019 {
pub mod day2;
pub mod day3;
pub mod day4;
+ pub mod day5;
}
diff --git a/src/main.rs b/src/main.rs
index c0cf188..0ac047a 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -27,6 +27,7 @@ fn main() {
puzzle_solutions.insert("2019::day3::part2", advent_of_code::year_2019::day3::part2);
puzzle_solutions.insert("2019::day4::part1", advent_of_code::year_2019::day4::part1);
puzzle_solutions.insert("2019::day4::part2", advent_of_code::year_2019::day4::part2);
+ puzzle_solutions.insert("2019::day5::part1", advent_of_code::year_2019::day5::part1);
let command = match env::args().skip(1).next() {
Some(command) => command,
diff --git a/src/year_2019/day2.rs b/src/year_2019/day2.rs
index 8cbc82f..136231f 100644
--- a/src/year_2019/day2.rs
+++ b/src/year_2019/day2.rs
@@ -89,7 +89,7 @@ pub fn part2() {
let program = IntcodeProgram::from(input.as_str());
let mut computer = IntcodeComputer::from(&program);
- const DESIRED_OUTPUT: usize = 19690720;
+ const DESIRED_OUTPUT: i64 = 19690720;
let mut result = None;
'outer: for noun in 0..100 {
diff --git a/src/year_2019/day5.rs b/src/year_2019/day5.rs
new file mode 100644
index 0000000..33bd1c9
--- /dev/null
+++ b/src/year_2019/day5.rs
@@ -0,0 +1,94 @@
+//! --- Day 5: Sunny with a Chance of Asteroids ---
+
+use super::IntcodeComputer;
+
+/// 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 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 address 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):
+///
+/// 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?
+pub fn part1() {
+ let input = crate::common::read_stdin_to_string();
+ let mut computer = IntcodeComputer::from(input.as_str());
+
+ let input_tx = computer.create_input();
+ let output_rx = computer.create_output();
+
+ input_tx.send(1).unwrap();
+ computer.run();
+
+ let mut diagnostic_code = 0;
+ for (index, output) in output_rx.iter().enumerate() {
+ if output == 0 {
+ println!("Test {} passed!", index + 1);
+ }
+
+ diagnostic_code = output;
+ }
+
+ println!(
+ "After providing 1 to the only input instruction and passing all the tests, the diagnostic code produced: {}",
+ diagnostic_code
+ );
+}
+
+#[cfg(test)]
+mod tests {
+ use super::*;
+
+ #[test]
+ fn test_intcode_computer_input_output() {
+ let mut computer = IntcodeComputer::from("3,0,4,0,99");
+
+ let input_tx = computer.create_input();
+ let output_rx = computer.create_output();
+
+ input_tx.send(42).unwrap();
+ computer.run();
+
+ assert_eq!(output_rx.recv().unwrap(), 42);
+ }
+}
diff --git a/src/year_2019/intcode_computer.rs b/src/year_2019/intcode_computer.rs
index bfb586d..418e891 100644
--- a/src/year_2019/intcode_computer.rs
+++ b/src/year_2019/intcode_computer.rs
@@ -1,7 +1,12 @@
+use std::convert::TryInto;
+use std::sync::mpsc::{self, Receiver, Sender};
+
#[derive(Debug)]
pub struct IntcodeComputer {
pub memory: IntcodeProgram,
instruction_pointer: usize,
+ input: Option<Receiver<i64>>,
+ output: Option<Sender<i64>>,
}
impl IntcodeComputer {
@@ -10,29 +15,73 @@ impl IntcodeComputer {
self.instruction_pointer = 0;
}
+ pub fn create_input(&mut self) -> Sender<i64> {
+ let (input_tx, input_rx) = mpsc::channel();
+ self.input = Some(input_rx);
+ input_tx
+ }
+
+ pub fn create_output(&mut self) -> Receiver<i64> {
+ let (output_tx, output_rx) = mpsc::channel();
+ self.output = Some(output_tx);
+ output_rx
+ }
+
pub fn run(mut self) -> Self {
loop {
let next_instruction = IntcodeInstruction::from(&self);
+ let instruction_length = next_instruction.length();
match next_instruction {
- IntcodeInstruction::Add(one_address, two_address, output_address) => {
- let one = *self.memory.get(one_address);
- let two = *self.memory.get(two_address);
+ IntcodeInstruction::Add(one, two, output) => {
+ let one = one.get_value(&self.memory);
+ let two = two.get_value(&self.memory);
+ let output_address = output
+ .get_address()
+ .expect("Add 'output' parameter must be an address");
self.memory.replace(output_address, one + two)
}
- IntcodeInstruction::Multiply(one_address, two_address, output_address) => {
- let one = *self.memory.get(one_address);
- let two = *self.memory.get(two_address);
+ IntcodeInstruction::Multiply(one, two, output) => {
+ let one = one.get_value(&self.memory);
+ let two = two.get_value(&self.memory);
+ let output_address = output
+ .get_address()
+ .expect("Multiply 'output' parameter must be an address");
self.memory.replace(output_address, one * two)
}
+ IntcodeInstruction::Input(to) => {
+ let input_value = self
+ .input
+ .as_ref()
+ .expect("Program requires input but no input was connected!")
+ .recv()
+ .expect("Failed to receive from input");
+
+ let to_address = to
+ .get_address()
+ .expect("Input 'to' parameter must be an address");
+
+ self.memory.replace(to_address, input_value);
+ }
+
+ IntcodeInstruction::Output(from) => {
+ let output_value = from.get_value(&self.memory);
+
+ self.output
+ .as_ref()
+ .expect("Program requires output but no output was connected!")
+ .send(output_value)
+ .expect("Failed to send to output");
+ }
+
IntcodeInstruction::Halt => break,
}
- self.instruction_pointer += next_instruction.length()
+ self.instruction_pointer += instruction_length;
}
self
@@ -44,6 +93,8 @@ impl From<&IntcodeProgram> for IntcodeComputer {
Self {
memory: program.clone(),
instruction_pointer: 0,
+ input: None,
+ output: None,
}
}
}
@@ -53,17 +104,25 @@ impl From<&str> for IntcodeComputer {
Self {
memory: IntcodeProgram::from(string),
instruction_pointer: 0,
+ input: None,
+ output: None,
}
}
}
#[derive(Debug)]
enum IntcodeInstruction {
- /// Adds the values from the first two addresses, writes the result to the third address
- Add(usize, usize, usize),
+ /// Adds the values from the first two parameters, writes the result to the third parameter
+ Add(IntcodeParameter, IntcodeParameter, IntcodeParameter),
- /// Multiplies the values from the first two addresses, writes the result to the third address
- Multiply(usize, usize, usize),
+ /// Multiplies the values from the first two parameters, writes the result to the third parameter
+ Multiply(IntcodeParameter, IntcodeParameter, IntcodeParameter),
+
+ /// Takes a single integer from input and writes it to the first parameter
+ Input(IntcodeParameter),
+
+ /// Sends a single integer to output from the first parameter
+ Output(IntcodeParameter),
/// Halts the IntcodeComputer
Halt,
@@ -74,6 +133,8 @@ impl IntcodeInstruction {
match self {
Self::Add(..) => 4,
Self::Multiply(..) => 4,
+ Self::Input(..) => 2,
+ Self::Output(..) => 2,
Self::Halt => 1,
}
}
@@ -81,38 +142,134 @@ impl IntcodeInstruction {
impl From<&IntcodeComputer> for IntcodeInstruction {
fn from(state: &IntcodeComputer) -> Self {
- let opcode = state.memory.get(state.instruction_pointer);
+ let instruction_header = state.memory.get(state.instruction_pointer);
+ let opcode = Opcode::from(*instruction_header);
+ let mut parser = ParameterParser::from(*instruction_header);
match opcode {
- 1 => Self::Add(
- *state.memory.get(state.instruction_pointer + 1),
- *state.memory.get(state.instruction_pointer + 2),
- *state.memory.get(state.instruction_pointer + 3),
+ Opcode(1) => Self::Add(
+ parser.parse_next(state.memory.get(state.instruction_pointer + 1)),
+ parser.parse_next(state.memory.get(state.instruction_pointer + 2)),
+ parser.parse_writeonly(state.memory.get(state.instruction_pointer + 3)),
),
- 2 => Self::Multiply(
- *state.memory.get(state.instruction_pointer + 1),
- *state.memory.get(state.instruction_pointer + 2),
- *state.memory.get(state.instruction_pointer + 3),
+ Opcode(2) => Self::Multiply(
+ parser.parse_next(state.memory.get(state.instruction_pointer + 1)),
+ parser.parse_next(state.memory.get(state.instruction_pointer + 2)),
+ parser.parse_writeonly(state.memory.get(state.instruction_pointer + 3)),
),
- 99 => Self::Halt,
- other => panic!("Invalid Opcode encountered: {}", other),
+ Opcode(3) => {
+ Self::Input(parser.parse_writeonly(state.memory.get(state.instruction_pointer + 1)))
+ }
+ Opcode(4) => {
+ Self::Output(parser.parse_next(state.memory.get(state.instruction_pointer + 1)))
+ }
+ Opcode(99) => Self::Halt,
+ Opcode(other) => panic!("Invalid Opcode encountered: {}", other),
+ }
+ }
+}
+
+#[derive(Debug)]
+struct Opcode(i64);
+impl From<i64> for Opcode {
+ fn from(instruction_header: i64) -> Self {
+ Self(get_digit(instruction_header, 1) * 10 + get_digit(instruction_header, 0))
+ }
+}
+
+#[derive(Debug)]
+enum IntcodeParameter {
+ /// PositionMode
+ Position(usize),
+
+ /// ImmediateMode
+ Value(i64),
+}
+
+impl IntcodeParameter {
+ fn get_address(&self) -> Option<usize> {
+ match self {
+ Self::Position(address) => Some(*address),
+ Self::Value(_) => None,
+ }
+ }
+
+ fn get_value(&self, memory: &IntcodeProgram) -> i64 {
+ match self {
+ Self::Position(address) => *memory.get((*address).try_into().unwrap()),
+ Self::Value(value) => *value,
+ }
+ }
+}
+
+#[derive(Debug)]
+struct ParameterParser {
+ instruction_header: i64,
+ parameters_read: u32,
+}
+
+impl From<i64> for ParameterParser {
+ fn from(instruction_header: i64) -> Self {
+ Self {
+ instruction_header,
+ parameters_read: 0,
+ }
+ }
+}
+
+impl ParameterParser {
+ fn parse_next(&mut self, parameter: &i64) -> IntcodeParameter {
+ let mode = ParameterMode::from(&*self);
+ let parameter = match mode {
+ ParameterMode::PositionMode => {
+ IntcodeParameter::Position((*parameter).try_into().unwrap())
+ }
+ ParameterMode::ImmediateMode => IntcodeParameter::Value(*parameter),
+ };
+
+ self.parameters_read += 1;
+
+ parameter
+ }
+
+ fn parse_writeonly(&mut self, parameter: &i64) -> IntcodeParameter {
+ let parameter = IntcodeParameter::Position((*parameter).try_into().unwrap());
+
+ self.parameters_read += 1;
+
+ parameter
+ }
+}
+
+#[derive(Debug)]
+enum ParameterMode {
+ PositionMode,
+ ImmediateMode,
+}
+
+impl From<&ParameterParser> for ParameterMode {
+ fn from(state: &ParameterParser) -> Self {
+ match get_digit(state.instruction_header, 2 + state.parameters_read) {
+ 0 => Self::PositionMode,
+ 1 => Self::ImmediateMode,
+ other => panic!("Invalid ParameterMode: {}", other),
}
}
}
#[derive(Debug, Clone)]
pub struct IntcodeProgram {
- data: Vec<usize>,
+ data: Vec<i64>,
}
impl IntcodeProgram {
- pub fn get(&self, address: usize) -> &usize {
+ pub fn get(&self, address: usize) -> &i64 {
self.data
.get(address)
.unwrap_or_else(|| panic!("Failed to get data at address {}", address))
}
- pub fn replace(&mut self, address: usize, replacement: usize) {
+ pub fn replace(&mut self, address: usize, replacement: i64) {
let integer = self
.data
.get_mut(address)
@@ -121,7 +278,7 @@ impl IntcodeProgram {
*integer = replacement;
}
- pub fn data(&self) -> &Vec<usize> {
+ pub fn data(&self) -> &Vec<i64> {
&self.data
}
@@ -140,9 +297,14 @@ impl From<&str> for IntcodeProgram {
data: string
.trim()
.split(",")
- .map(|integer| integer.parse::<usize>())
- .map(|parse_result| parse_result.expect("Failed to parse Intcode integer as usize"))
+ .map(|integer| integer.parse::<i64>())
+ .map(|parse_result| parse_result.expect("Failed to parse Intcode integer as i64"))
.collect(),
}
}
}
+
+/// Gets the digit from number at a zero-indexed position from the right (in base 10)
+fn get_digit(number: i64, position: u32) -> i64 {
+ (number / (10_i64.pow(position))) % 10
+}