From c11b199f148a72337352a72c7bfb15a5bb6a14a0 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Gr=C3=A9gory=20Burri?= Date: Wed, 11 Dec 2019 16:25:37 +0100 Subject: [PATCH] * Day 11 * Merge intcode from day 05 and day09 to 'intcode' module --- data/day11.input | 1 + src/common.rs | 18 +++++ src/day02.rs | 2 +- src/day05.rs | 124 ----------------------------------- src/day06.rs | 2 +- src/day07.rs | 11 ++++ src/day08.rs | 18 ----- src/day11.rs | 116 ++++++++++++++++++++++++++++++++ src/{day09.rs => intcode.rs} | 66 ++++++++++++++++--- src/main.rs | 29 ++++++-- 10 files changed, 228 insertions(+), 159 deletions(-) create mode 100644 data/day11.input delete mode 100644 src/day05.rs create mode 100644 src/day11.rs rename src/{day09.rs => intcode.rs} (74%) diff --git a/data/day11.input b/data/day11.input new file mode 100644 index 0000000..a81f133 --- /dev/null +++ b/data/day11.input @@ -0,0 +1 @@ +3,8,1005,8,305,1106,0,11,0,0,0,104,1,104,0,3,8,1002,8,-1,10,101,1,10,10,4,10,1008,8,0,10,4,10,1002,8,1,29,3,8,102,-1,8,10,1001,10,1,10,4,10,108,1,8,10,4,10,1002,8,1,50,1,104,20,10,1,1102,6,10,1006,0,13,3,8,102,-1,8,10,101,1,10,10,4,10,108,1,8,10,4,10,102,1,8,83,1,1102,0,10,1006,0,96,2,1004,19,10,3,8,1002,8,-1,10,101,1,10,10,4,10,108,0,8,10,4,10,101,0,8,116,3,8,1002,8,-1,10,1001,10,1,10,4,10,108,1,8,10,4,10,102,1,8,138,1006,0,60,1,1008,12,10,3,8,102,-1,8,10,101,1,10,10,4,10,1008,8,0,10,4,10,102,1,8,168,1006,0,14,1006,0,28,3,8,1002,8,-1,10,1001,10,1,10,4,10,108,0,8,10,4,10,101,0,8,195,2,1005,9,10,1006,0,29,3,8,1002,8,-1,10,101,1,10,10,4,10,108,1,8,10,4,10,1002,8,1,224,2,1009,8,10,1,3,5,10,3,8,1002,8,-1,10,101,1,10,10,4,10,108,1,8,10,4,10,102,1,8,254,3,8,102,-1,8,10,1001,10,1,10,4,10,1008,8,0,10,4,10,1002,8,1,277,1,1003,18,10,1,1104,1,10,101,1,9,9,1007,9,957,10,1005,10,15,99,109,627,104,0,104,1,21101,0,666681062292,1,21102,322,1,0,1105,1,426,21101,847073883028,0,1,21102,333,1,0,1105,1,426,3,10,104,0,104,1,3,10,104,0,104,0,3,10,104,0,104,1,3,10,104,0,104,1,3,10,104,0,104,0,3,10,104,0,104,1,21101,0,179356855319,1,21102,1,380,0,1105,1,426,21102,1,179356998696,1,21102,1,391,0,1105,1,426,3,10,104,0,104,0,3,10,104,0,104,0,21101,0,988669698816,1,21101,0,414,0,1106,0,426,21102,1,868494500628,1,21102,425,1,0,1106,0,426,99,109,2,21202,-1,1,1,21102,1,40,2,21102,457,1,3,21102,1,447,0,1105,1,490,109,-2,2105,1,0,0,1,0,0,1,109,2,3,10,204,-1,1001,452,453,468,4,0,1001,452,1,452,108,4,452,10,1006,10,484,1102,0,1,452,109,-2,2105,1,0,0,109,4,1201,-1,0,489,1207,-3,0,10,1006,10,507,21102,0,1,-3,22101,0,-3,1,21202,-2,1,2,21101,1,0,3,21102,1,526,0,1106,0,531,109,-4,2105,1,0,109,5,1207,-3,1,10,1006,10,554,2207,-4,-2,10,1006,10,554,22101,0,-4,-4,1106,0,622,21201,-4,0,1,21201,-3,-1,2,21202,-2,2,3,21102,573,1,0,1106,0,531,21202,1,1,-4,21101,1,0,-1,2207,-4,-2,10,1006,10,592,21102,1,0,-1,22202,-2,-1,-2,2107,0,-3,10,1006,10,614,22101,0,-1,1,21102,614,1,0,105,1,489,21202,-2,-1,-2,22201,-4,-2,-4,109,-5,2105,1,0 \ No newline at end of file diff --git a/src/common.rs b/src/common.rs index 30155d0..b3db167 100644 --- a/src/common.rs +++ b/src/common.rs @@ -10,4 +10,22 @@ where { fs::read_to_string(file).unwrap().split(sep).map(|line| line.parse::().unwrap()).collect() +} + +pub fn layer_to_printable_string(layer: &[u8], width: usize) -> String { + let mut result = String::new(); + let mut i = 0; + + loop { + for _ in 0 .. width { + if layer[i] == 0 { + result += " "; + } else { + result += "█"; + } + i += 1; + if i >= layer.len() { return result } + } + result += "\n"; + } } \ No newline at end of file diff --git a/src/day02.rs b/src/day02.rs index 81dfaaf..fd26331 100644 --- a/src/day02.rs +++ b/src/day02.rs @@ -11,7 +11,7 @@ fn execute_op_code(code: &mut [i32]) -> i32 { 1 => code[code[cursor + 3] as usize] = code[code[cursor + 1] as usize] + code[code[cursor + 2] as usize], 2 => code[code[cursor + 3] as usize] = code[code[cursor + 1] as usize] * code[code[cursor + 2] as usize], 99 => return code[0], - _ => panic!("Unkown code: {}", code[cursor]) + _ => panic!("Unknown code: {}", code[cursor]) } cursor += 4; } diff --git a/src/day05.rs b/src/day05.rs deleted file mode 100644 index 61f6203..0000000 --- a/src/day05.rs +++ /dev/null @@ -1,124 +0,0 @@ -// 'true' -> immediate mode, 'false' -> position mode. -fn read_op_and_modes(mut code: i32) -> (i32, [bool; 3]) { - let mut modes: [bool; 3] = [ false, false, false ]; - - if code >= 10_000 { - modes[2] = true; - code -= 10_000; - } - - if code >= 1_000 { - modes[1] = true; - code -= 1_000; - } - - if code >= 100 { - modes[0] = true; - code -= 100; - } - - (code, modes) -} - -pub fn execute_op_code(code: &mut [i32], input: &[i32]) -> Vec { - let mut cursor = 0; - let mut input_cursor = 0; - let mut output = Vec::::new(); - - fn read(position: usize, code: &[i32], mode: bool) -> i32 { - if mode { code[position] } else { code[code[position] as usize] } - }; - - fn jump_if(cond: bool, cursor: usize, code: &[i32], modes: [bool; 3]) -> usize { - let value = read(cursor + 1, &code, modes[0]); - if cond == (value != 0) { - read(cursor + 2, &code, modes[1]) as usize - } else { - cursor + 3 - } - }; - - loop { - let (op, modes) = read_op_and_modes(code[cursor]); - - match op { - // Sum. - 1 => { - code[code[cursor + 3] as usize] = read(cursor + 1, &code, modes[0]) + read(cursor + 2, &code, modes[1]); - cursor += 4; - }, - - // Multiply. - 2 => { - code[code[cursor + 3] as usize] = read(cursor + 1, &code, modes[0]) * read(cursor + 2, &code, modes[1]); - cursor += 4; - }, - - // Input. - 3 => { - code[code[cursor + 1] as usize] = input[input_cursor]; - input_cursor += 1; - cursor += 2; - } - - // Output. - 4 => { - output.push(read(cursor + 1, &code, modes[0])); - cursor += 2; - } - - // Jump-if-true. - 5 => cursor = jump_if(true, cursor, &code, modes), - - // Jump-if-false. - 6 => cursor = jump_if(false, cursor, &code, modes), - - // Less than. - 7 => { - code[code[cursor + 3] as usize] = - if read(cursor + 1, &code, modes[0]) < read(cursor + 2, &code, modes[1]) { 1 } else { 0 }; - cursor += 4; - }, - - // Equals. - 8 => { - code[code[cursor + 3] as usize] = - if read(cursor + 1, &code, modes[0]) == read(cursor + 2, &code, modes[1]) { 1 } else { 0 }; - cursor += 4; - }, - - 99 => break, - _ => panic!("Unkown code: {}", code[cursor]) - } - } - output -} - -#[cfg(test)] -mod tests { - use super::*; - - #[test] - fn part1() { - let mut c = [1002, 4, 3, 4, 33]; - let _ = execute_op_code(&mut c, &Vec::new()); - assert_eq!(c[4], 99); - } - - #[test] - fn part2() { - let c = [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]; - - let mut c1 = c; - let r1 = execute_op_code(&mut c1, &[7]); - assert_eq!(r1[0], 999); - - let mut c2 = c; - let r2 = execute_op_code(&mut c2, &[8]); - assert_eq!(r2[0], 1000); - - let mut c3 = c; - let r3 = execute_op_code(&mut c3, &[9]); - assert_eq!(r3[0], 1001); - } -} \ No newline at end of file diff --git a/src/day06.rs b/src/day06.rs index fddb899..c0d4ae0 100644 --- a/src/day06.rs +++ b/src/day06.rs @@ -41,7 +41,7 @@ pub fn nb_orbital_transfers(orbits: &Orbits, loc1: &str, loc2: &str) -> usize { } #[cfg(test)] -mod test { +mod tests { use super::*; #[test] diff --git a/src/day07.rs b/src/day07.rs index e69de29..fea25ff 100644 --- a/src/day07.rs +++ b/src/day07.rs @@ -0,0 +1,11 @@ + + + +#[cfg(test)] +mod tests { + + #[test] + fn part1 () { + + } +} \ No newline at end of file diff --git a/src/day08.rs b/src/day08.rs index 95b0385..50fb119 100644 --- a/src/day08.rs +++ b/src/day08.rs @@ -47,24 +47,6 @@ pub fn merge_layers(layers: &[Vec]) -> Vec { result } -pub fn layer_to_printable_string(layer: &[u8], width: u32) -> String { - let mut result = String::new(); - let mut i = 0; - - loop { - for _ in 0 .. width { - if layer[i] == 0 { - result += " "; - } else { - result += "█"; - } - i += 1; - if i >= layer.len() { return result } - } - result += "\n"; - } -} - pub fn one_digits_times_two_digits(layer: &[u8]) -> u32 { count(layer, 1) * count(layer, 2) } diff --git a/src/day11.rs b/src/day11.rs new file mode 100644 index 0000000..e91d813 --- /dev/null +++ b/src/day11.rs @@ -0,0 +1,116 @@ +use std::collections::HashMap; +use super::intcode; + +enum NextCommand { + ColorToPaint, + Turn +} + +struct Robot { + next_command: NextCommand, + current_pos: (i32, i32), + current_dir: i32, // 0: up, 1: right, 2: down, 3: left. + panels: HashMap<(i32, i32), i64> +} + +impl Robot { + fn new() -> Self { + Robot { + next_command: NextCommand::ColorToPaint, + current_pos: (0, 0), + current_dir: 0, + panels: HashMap::new() + } + } +} + +impl intcode::IO for Robot { + fn read(&mut self) -> i64 { + *self.panels.get(&self.current_pos).unwrap_or(&0) + } + + fn write(&mut self, value: i64) { + self.next_command = + match self.next_command { + NextCommand::ColorToPaint => { self.panels.insert(self.current_pos, value); NextCommand::Turn }, + NextCommand::Turn => { + self.current_dir = (self.current_dir + if value == 0 { 3 } else { 1 }) % 4; + self.current_pos = + match self.current_dir { + 0 => (self.current_pos.0, self.current_pos.1 + 1), + 1 => (self.current_pos.0 + 1, self.current_pos.1), + 2 => (self.current_pos.0, self.current_pos.1 - 1), + 3 | _ => (self.current_pos.0 - 1, self.current_pos.1) + }; + NextCommand::ColorToPaint + } + } + } +} + +pub fn run_robot(code: &[i64], initial_value: i64) -> HashMap<(i32, i32), i64> { + let mut robot = Robot::new(); + if initial_value != 0 { + robot.panels.insert((0, 0), initial_value); + } + + intcode::execute_op_code_with_custom_io(code, &mut robot); + robot.panels +} + +pub fn panels_to_layer(panels: &HashMap<(i32, i32), i64>) -> (Vec, usize) { + let coordinates: Vec<&(i32, i32)> = panels.keys().collect(); + let min_x = coordinates.iter().min_by_key(|(x, _)| x).unwrap().0; + let max_x = coordinates.iter().max_by_key(|(x, _)| x).unwrap().0; + let min_y = coordinates.iter().min_by_key(|(_, y)| y).unwrap().1; + let max_y = coordinates.iter().max_by_key(|(_, y)| y).unwrap().1; + + let width = (max_x - min_x) as usize + 1; + let height = (max_y - min_y) as usize + 1; + + let mut layer = Vec::new(); + layer.resize(width * height, 0); + + for x in min_x ..= max_x { + for y in min_y ..= max_y { + let pos = (x - min_x) + ((height as i32 - y + min_y - 1) * width as i32); // Y axis is down. + layer[pos as usize] = *panels.get(&(x, y)).unwrap_or(&0) as u8; + } + } + + (layer, width) +} + +#[cfg(test)] +mod tests { + use super::*; + use super::intcode::IO; + + #[test] + fn part1() { + let mut robot = Robot::new(); + robot.write(1); // Paint white. + robot.write(0); // Turn left. + + robot.write(0); // Paint black. + robot.write(0); // Turn left. + + robot.write(1); // Paint white. + robot.write(0); // Turn left. + + robot.write(1); // Paint white. + robot.write(0); // Turn left. + + robot.write(0); // Paint black. + robot.write(1); // Turn right. + + robot.write(1); // Paint white. + robot.write(0); // Turn left. + + robot.write(1); // Paint white. + robot.write(0); // Turn left. + + assert_eq!(robot.panels.len(), 6); + } + +} \ No newline at end of file diff --git a/src/day09.rs b/src/intcode.rs similarity index 74% rename from src/day09.rs rename to src/intcode.rs index ea234b2..b1968ac 100644 --- a/src/day09.rs +++ b/src/intcode.rs @@ -5,6 +5,35 @@ enum Mode { Relative } +pub trait IO { + fn read(&mut self) -> i64; + fn write(&mut self, value: i64); +} + +struct Buffer { + output: Vec, + input: Vec +} + +impl Buffer { + fn from(input: &[i64]) -> Self { + Buffer { + output: Vec::new(), + input: Vec::from(input) + } + } +} + +impl IO for Buffer { + fn read(&mut self) -> i64 { + self.input.remove(0) + } + + fn write(&mut self, value: i64) { + self.output.push(value) + } +} + // 'true' -> immediate mode, 'false' -> position mode. fn read_op_and_modes(mut code: i64) -> (i64, [Mode; 3]) { let mut modes: [Mode; 3] = [ Mode::Position, Mode::Position, Mode::Position ]; @@ -24,10 +53,14 @@ fn read_op_and_modes(mut code: i64) -> (i64, [Mode; 3]) { } pub fn execute_op_code(code: &[i64], input: &[i64]) -> Vec { + let mut buffer = Buffer::from(input); + execute_op_code_with_custom_io(code, &mut buffer); + buffer.output +} + +pub fn execute_op_code_with_custom_io(code: &[i64], io: &mut dyn IO) { let mut code = Vec::from(code); let mut cursor = 0; - let mut input_cursor = 0; - let mut output = Vec::::new(); let mut relative_base = 0; fn read(position: usize, code: &[i64], mode: Mode, relative_base: i64) -> i64 { @@ -82,14 +115,13 @@ pub fn execute_op_code(code: &[i64], input: &[i64]) -> Vec { // Input. 3 => { - write(cursor + 1, input[input_cursor], &mut code, modes[0], relative_base); - input_cursor += 1; + write(cursor + 1, io.read(), &mut code, modes[0], relative_base); cursor += 2; } // Output. 4 => { - output.push(read(cursor + 1, &code, modes[0], relative_base)); + io.write(read(cursor + 1, &code, modes[0], relative_base)); cursor += 2; } @@ -119,14 +151,32 @@ pub fn execute_op_code(code: &[i64], input: &[i64]) -> Vec { 99 => break, - _ => panic!("Unkown code: {}", code[cursor]) + _ => panic!("Unknown code: {}", code[cursor]) } } - output } #[cfg(test)] -mod tests { +mod tests_day05 { + use super::*; + + #[test] + fn part2() { + let c = [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]; + + let r1 = execute_op_code(&c, &[7]); + assert_eq!(r1[0], 999); + + let r2 = execute_op_code(&c, &[8]); + assert_eq!(r2[0], 1000); + + let r3 = execute_op_code(&c, &[9]); + assert_eq!(r3[0], 1001); + } +} + +#[cfg(test)] +mod tests_day09 { use super::*; #[test] diff --git a/src/main.rs b/src/main.rs index 42699c7..99ea6e0 100644 --- a/src/main.rs +++ b/src/main.rs @@ -2,15 +2,15 @@ use std::env; use std::fs; use std::time::Instant; +mod common; +mod intcode; mod day01; mod day02; mod day03; -mod day05; mod day06; mod day07; mod day08; -mod day09; -mod common; +mod day11; fn day01() -> String { let masses = common::read_list_of_numbers("data/day01.input", "\n"); @@ -38,7 +38,7 @@ fn day04() -> String { fn day05() -> String { let code = common::read_list_of_numbers("data/day05.input", ","); - format!("part1: {:?}, part2: {:?}", day05::execute_op_code(&mut Vec::from(&code[..]), &[1]), day05::execute_op_code(&mut Vec::from(&code[..]), &[5])) + format!("part1: {:?}, part2: {:?}", intcode::execute_op_code(&code, &[1]), intcode::execute_op_code(&code, &[5])) } fn day06() -> String { @@ -61,12 +61,25 @@ fn day08() -> String { let layer = day08::layer_with_fewer_0(&layers[..]); let merged = day08::merge_layers(&layers[..]); - format!("part1: {}, part2:\n{}", day08::one_digits_times_two_digits(layer), day08::layer_to_printable_string(&merged, 25)) + format!("part1: {}, part2:\n{}", day08::one_digits_times_two_digits(layer), common::layer_to_printable_string(&merged, 25)) } fn day09() -> String { let code = common::read_list_of_numbers::<&str, i64>("data/day09.input", ","); - format!("part1: {:?}, part2: {:?}", day09::execute_op_code(&code, &[1]), day09::execute_op_code(&code, &[2])) + + format!("part1: {:?}, part2: {:?}", intcode::execute_op_code(&code, &[1]), intcode::execute_op_code(&code, &[2])) +} + +fn day10() -> String { + format!("") +} + +fn day11() -> String { + let code = common::read_list_of_numbers::<&str, i64>("data/day11.input", ","); + let panels = day11::run_robot(&code, 1); + let (layer, width) = day11::panels_to_layer(&panels); + + format!("part1: {:?}, part2:\n{}", day11::run_robot(&code, 0).len(), common::layer_to_printable_string(&layer, width)) } fn format_micros(t: u128) -> String { @@ -96,7 +109,9 @@ fn main() { day06, day07, day08, - day09 + day09, + day10, + day11 ); let args: Vec = env::args().skip(1).collect(); -- 2.45.2