commit 6a1814ede3084bebd115916cdda6ea163c960198
parent cd603c791ced3af0f30452a976a620aab0612b78
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Sat, 7 Dec 2019 16:31:41 -0500
Add Rust solution for day 07
Diffstat:
3 files changed, 256 insertions(+), 0 deletions(-)
diff --git a/day-07/Makefile b/day-07/Makefile
@@ -0,0 +1,9 @@
+CC := g++
+CCFLAGS := --std=c++17 -Wall
+
+all: day-07-rust day-07.jl
+ julia day-07.jl
+ ./day-07-rust
+
+day-07-rust: day-07.rs
+ rustc $^ -o $@
diff --git a/day-07/day-07.rs b/day-07/day-07.rs
@@ -0,0 +1,246 @@
+use std::collections::VecDeque;
+
+fn main() {
+ let input = std::fs::read_to_string("input.txt")
+ .unwrap()
+ .trim()
+ .split(",")
+ .map(|op| op.parse::<i32>().unwrap())
+ .collect::<Vec<i32>>();
+ println!("Rust:");
+ println!("Part 1: {}", part_1(&input));
+ println!("Part 2: {}", part_2(&input));
+}
+
+fn computer(program: &Vec<i32>, input: &Vec<i32>) -> Vec<i32> {
+ let mut program = program.clone();
+ let mut input = input.clone().into_iter().collect::<VecDeque<i32>>();
+ let mut output = vec![];
+ let mut pc = 0;
+
+ loop {
+ let (finished, mut step_output) = computer_step(&mut program, &mut pc, input.pop_front());
+ output.append(&mut step_output);
+ if finished {
+ break;
+ }
+ }
+
+ output
+}
+
+fn computer_step(
+ program: &mut Vec<i32>,
+ pc: &mut usize,
+ mut input: Option<i32>,
+) -> (bool, Vec<i32>) {
+ // Runs from given pc until completion or next request for input.
+ // Modifies program and pc.
+ // Returns if the program has terminated and the output.
+ let mut output = vec![];
+
+ let get_param = |loc: usize, im_mode: bool, program: &Vec<i32>| -> i32 {
+ if im_mode {
+ program[loc]
+ } else {
+ program[program[loc] as usize]
+ }
+ };
+
+ loop {
+ let op_code = program[*pc] % 100;
+ let im_mode_1 = (program[*pc] % 1000) / 100 > 0;
+ let im_mode_2 = (program[*pc] % 10000) / 1000 > 0;
+ // Third parameter is location to write to, and will never be immediate
+ // mode.
+ match op_code {
+ 1 => {
+ let res_loc = program[*pc + 3];
+ let param_1 = get_param(*pc + 1, im_mode_1, &program);
+ let param_2 = get_param(*pc + 2, im_mode_2, &program);
+ program[res_loc as usize] = param_1 + param_2;
+ *pc += 4;
+ }
+ 2 => {
+ let res_loc = program[*pc + 3];
+ let param_1 = get_param(*pc + 1, im_mode_1, &program);
+ let param_2 = get_param(*pc + 2, im_mode_2, &program);
+ program[res_loc as usize] = param_1 * param_2;
+ *pc += 4;
+ }
+ 3 => {
+ let res_loc = program[*pc + 1];
+ // Only use input once.
+ if input.is_some() {
+ program[res_loc as usize] = input.unwrap();
+ input = None;
+ } else {
+ // Need new input.
+ return (false, output);
+ };
+ *pc += 2;
+ }
+ 4 => {
+ let param_1 = get_param(*pc + 1, im_mode_1, &program);
+ output.push(param_1);
+ *pc += 2;
+ }
+ 5 => {
+ let param_1 = get_param(*pc + 1, im_mode_1, &program);
+ let param_2 = get_param(*pc + 2, im_mode_2, &program);
+ if param_1 != 0 {
+ *pc = param_2 as usize;
+ } else {
+ *pc += 3;
+ }
+ }
+ 6 => {
+ let param_1 = get_param(*pc + 1, im_mode_1, &program);
+ let param_2 = get_param(*pc + 2, im_mode_2, &program);
+ if param_1 == 0 {
+ *pc = param_2 as usize;
+ } else {
+ *pc += 3;
+ }
+ }
+ 7 => {
+ let res_loc = program[*pc + 3];
+ let param_1 = get_param(*pc + 1, im_mode_1, &program);
+ let param_2 = get_param(*pc + 2, im_mode_2, &program);
+ program[res_loc as usize] = if param_1 < param_2 { 1 } else { 0 };
+ *pc += 4;
+ }
+ 8 => {
+ let res_loc = program[*pc + 3];
+ let param_1 = get_param(*pc + 1, im_mode_1, &program);
+ let param_2 = get_param(*pc + 2, im_mode_2, &program);
+ program[res_loc as usize] = if param_1 == param_2 { 1 } else { 0 };
+ *pc += 4;
+ }
+ 99 => {
+ break;
+ }
+ _ => {
+ println!("Unknown op {}", op_code);
+ println!("{}", program[*pc]);
+ panic!();
+ }
+ }
+ }
+
+ (true, output)
+}
+
+fn feedback_amp(program: &Vec<i32>, phase: &Vec<i32>) -> i32 {
+ let num_amps = phase.len();
+ let mut programs = vec![program.clone(); num_amps];
+ let mut pcs = vec![0; num_amps];
+ let mut inputs = phase
+ .iter()
+ .map(|&x| {
+ let mut input = VecDeque::<i32>::new();
+ input.push_back(x);
+ input
+ })
+ .collect::<Vec<VecDeque<i32>>>();
+
+ // Additional input for first amplifier.
+ inputs[0].push_back(0);
+ // Index of currently working amp.
+ let mut work_idx = 0;
+ loop {
+ // Run current amp.
+ let (finished, step_output) = computer_step(
+ &mut programs[work_idx],
+ &mut pcs[work_idx],
+ inputs[work_idx].pop_front(),
+ );
+ // Pipe output to next amp.
+ step_output
+ .into_iter()
+ .for_each(|x| inputs[(work_idx + 1) % num_amps].push_back(x));
+ // Check for completion.
+ if finished && work_idx + 1 == num_amps {
+ break;
+ }
+ // Move to next amp.
+ work_idx = (work_idx + 1) % num_amps;
+ }
+
+ *inputs[0].back().unwrap()
+}
+
+fn part_1(input: &Vec<i32>) -> i32 {
+ let mut max_output = 0;
+ for phase_1 in 0..=4 {
+ let out_1 = computer(input, &vec![phase_1, 0])[0];
+ for phase_2 in 0..=4 {
+ if phase_2 == phase_1 {
+ continue;
+ }
+ let out_2 = computer(input, &vec![phase_2, out_1])[0];
+ for phase_3 in 0..=4 {
+ if phase_3 == phase_1 || phase_3 == phase_2 {
+ continue;
+ }
+ let out_3 = computer(input, &vec![phase_3, out_2])[0];
+ for phase_4 in 0..=4 {
+ if phase_4 == phase_1 || phase_4 == phase_2 || phase_4 == phase_3 {
+ continue;
+ }
+ let out_4 = computer(input, &vec![phase_4, out_3])[0];
+ for phase_5 in 0..=4 {
+ if phase_5 == phase_1
+ || phase_5 == phase_2
+ || phase_5 == phase_3
+ || phase_5 == phase_4
+ {
+ continue;
+ }
+ let out_5 = computer(input, &vec![phase_5, out_4])[0];
+ max_output = max_output.max(out_5);
+ }
+ }
+ }
+ }
+ }
+
+ max_output
+}
+
+fn part_2(input: &Vec<i32>) -> i32 {
+ let mut max_output = 0;
+
+ for phase_1 in 5..=9 {
+ for phase_2 in 5..=9 {
+ if phase_2 == phase_1 {
+ continue;
+ }
+ for phase_3 in 5..=9 {
+ if phase_3 == phase_1 || phase_3 == phase_2 {
+ continue;
+ }
+ for phase_4 in 5..=9 {
+ if phase_4 == phase_1 || phase_4 == phase_2 || phase_4 == phase_3 {
+ continue;
+ }
+ for phase_5 in 5..=9 {
+ if phase_5 == phase_1
+ || phase_5 == phase_2
+ || phase_5 == phase_3
+ || phase_5 == phase_4
+ {
+ continue;
+ }
+ max_output = max_output.max(feedback_amp(
+ input,
+ &vec![phase_1, phase_2, phase_3, phase_4, phase_5],
+ ));
+ }
+ }
+ }
+ }
+ }
+
+ max_output
+}
diff --git a/day-07/input.txt b/day-07/input.txt
@@ -0,0 +1 @@
+3,8,1001,8,10,8,105,1,0,0,21,34,51,64,73,98,179,260,341,422,99999,3,9,102,4,9,9,1001,9,4,9,4,9,99,3,9,1001,9,4,9,1002,9,3,9,1001,9,5,9,4,9,99,3,9,101,5,9,9,102,5,9,9,4,9,99,3,9,101,5,9,9,4,9,99,3,9,1002,9,5,9,1001,9,3,9,102,2,9,9,101,5,9,9,1002,9,2,9,4,9,99,3,9,1001,9,1,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,2,9,4,9,3,9,1001,9,2,9,4,9,3,9,102,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,101,1,9,9,4,9,3,9,101,1,9,9,4,9,3,9,102,2,9,9,4,9,3,9,101,2,9,9,4,9,99,3,9,101,1,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,102,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,101,2,9,9,4,9,3,9,101,1,9,9,4,9,3,9,101,1,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,2,9,4,9,99,3,9,101,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,1001,9,2,9,4,9,3,9,1001,9,2,9,4,9,3,9,1001,9,2,9,4,9,3,9,101,2,9,9,4,9,3,9,1001,9,1,9,4,9,3,9,102,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,101,2,9,9,4,9,99,3,9,1002,9,2,9,4,9,3,9,102,2,9,9,4,9,3,9,1001,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,102,2,9,9,4,9,3,9,102,2,9,9,4,9,3,9,101,2,9,9,4,9,3,9,1001,9,2,9,4,9,99,3,9,1001,9,1,9,4,9,3,9,101,1,9,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,2,9,4,9,3,9,1001,9,1,9,4,9,3,9,101,1,9,9,4,9,3,9,102,2,9,9,4,9,3,9,1001,9,2,9,4,9,3,9,1002,9,2,9,4,9,3,9,1001,9,2,9,4,9,99