From b0d492ba930a5839f6ad3ae0a0bccf63120ad4bf Mon Sep 17 00:00:00 2001 From: =?utf8?q?Gr=C3=A9gory=20Burri?= Date: Fri, 13 Dec 2019 17:00:15 +0100 Subject: [PATCH] Day 7 part 2 --- src/day07.rs | 113 ++++++++++++++++++++++++++++++++++++++++++++++++++- src/main.rs | 8 +++- 2 files changed, 118 insertions(+), 3 deletions(-) diff --git a/src/day07.rs b/src/day07.rs index fea25ff..9c249e6 100644 --- a/src/day07.rs +++ b/src/day07.rs @@ -1,11 +1,122 @@ +use super::intcode; +use itertools::Itertools; +use std::sync::mpsc::{ self, Sender, Receiver }; +use std::thread::{ self, JoinHandle }; +fn last_thruster_signal(code: &[i64], phase_setting: &[i64]) -> i64 { + phase_setting.iter().fold(0, |last_output, input| intcode::execute_op_code(&code, &[*input, last_output])[0]) +} +pub fn find_largest_last_thruster_signal(code: &[i64]) -> i64 { + (0i64 ..= 4i64).permutations(5).map(|phase_setting| last_thruster_signal(&code, &phase_setting)).max().unwrap() +} + +struct Stage { + input_channel: mpsc::Receiver, + output_channel: mpsc::Sender, + last_produced_value: i64 +} + +impl Stage { + fn new(input_channel: mpsc::Receiver, output_channel: mpsc::Sender) -> Self { + Stage { input_channel, output_channel, last_produced_value: 0 } + } +} + +impl intcode::IO for Stage { + // May block. + fn read(&mut self) -> i64 { + match self.input_channel.recv() { + Ok(value) => value, + Err(_) => 0 + } + } + + // Send to the output channel. + fn write(&mut self, value: i64) { + self.last_produced_value = value; + self.output_channel.send(value); + } +} + +fn last_thruster_signal_with_feedback_loop(code: &[i64], phase_setting: &[i64]) -> i64 { + let n = phase_setting.len(); + + let mut senders = Vec::>::new(); + let mut receivers = Vec::>::new(); + + for (i, (s, r)) in (0 .. n).map(|i| (i, mpsc::channel::())) { + // Initial values. + s.send(phase_setting[i]); + if i == 0 { s.send(0); } + + senders.insert(if i == 0 { 0 } else { i - 1 }, s); + receivers.push(r); + } + + // Prepare each pair of received and sender for the each stages. + let mut channels: Vec<(Receiver, Sender)> = receivers.drain(..).zip(senders.drain(..)).collect(); + + let mut join_handles: Vec> = + channels + .drain(..) + .map( + |(receiver, sender)| { + let code_copy = Vec::::from(code); + thread::spawn( + move || { + let mut stage = Stage::new(receiver, sender); + intcode::execute_op_code_with_custom_io(&code_copy, &mut stage); + stage.last_produced_value + } + ) + } + ) + .collect(); + + join_handles.pop().unwrap().join().unwrap() +} + +pub fn find_largest_last_thruster_signal_with_feedback_loop(code: &[i64]) -> i64 { + (5i64 ..= 9i64).permutations(5).map(|phase_setting| last_thruster_signal_with_feedback_loop(&code, &phase_setting)).max().unwrap() +} #[cfg(test)] mod tests { + use super::*; #[test] - fn part1 () { + fn part1_sample_1() { + let code = vec![3,15,3,16,1002,16,10,16,1,16,15,15,4,15,99,0,0]; + let phase_setting = [4,3,2,1,0]; + assert_eq!(last_thruster_signal(&code, &phase_setting), 43210); + } + #[test] + fn part1_sample_2() { + let code = vec![3,23,3,24,1002,24,10,24,1002,23,-1,23,101,5,23,23,1,24,23,23,4,23,99,0,0]; + let phase_setting = [0,1,2,3,4]; + assert_eq!(last_thruster_signal(&code, &phase_setting), 54321); + } + + #[test] + fn part1_sample_3() { + let code = vec![3,31,3,32,1002,32,10,32,1001,31,-2,31,1007,31,0,33,1002,33,7,33,1,33,31,31,1,32,31,31,4,31,99,0,0,0]; + let phase_setting = [1,0,4,3,2]; + assert_eq!(last_thruster_signal(&code, &phase_setting), 65210); + } + + #[test] + fn part2_sample_1() { + let code = vec![3,26,1001,26,-4,26,3,27,1002,27,2,27,1,27,26,27,4,27,1001,28,-1,28,1005,28,6,99,0,0,5]; + let phase_setting = [9,8,7,6,5]; + assert_eq!(last_thruster_signal_with_feedback_loop(&code, &phase_setting), 139_629_729); + } + + #[test] + fn part2_sample_2() { + let code = vec![3,52,1001,52,-5,52,3,53,1,52,56,54,1007,54,5,55,1005,55,26,1001,54,-5,54,1105,1,12,1,53,54,53,1008,54,0,55,1001,55,1,55,2,53,55,53,4,53,1001,56,-1,56,1005,56,6,99,0,0,0,0,10]; + let phase_setting = [9,7,8,5,6]; + assert_eq!(last_thruster_signal_with_feedback_loop(&code, &phase_setting), 18216); } } \ No newline at end of file diff --git a/src/main.rs b/src/main.rs index 2d8398f..e8266af 100644 --- a/src/main.rs +++ b/src/main.rs @@ -50,7 +50,9 @@ fn day06() -> String { } fn day07() -> String { - format!("") + let code = common::read_list_of_numbers("data/day07.input", ","); + + format!("part1: {}, part2: {}", day07::find_largest_last_thruster_signal(&code), day07::find_largest_last_thruster_signal_with_feedback_loop(&code)) } fn day08() -> String { @@ -122,9 +124,11 @@ fn main() { // No argument -> execute all day problems. if args.is_empty() { - for i in 1..=days.len() { + let now = Instant::now(); + for i in 1 ..= days.len() { do_day(&days, i) } + println!("Time to execute all days: {}", format_micros(now.elapsed().as_micros())); } else { for arg in args { let day = arg.parse::().unwrap(); -- 2.45.2