commit b3b2b4976d8d0d0ddac2021569d24ec61b628e05
parent 12391979efbcb423aca0f1ea5c4a552e133b5845
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Tue, 17 Dec 2019 10:03:53 -0500
Add Rust solution for day 17
Diffstat:
3 files changed, 272 insertions(+), 0 deletions(-)
diff --git a/day-17/Makefile b/day-17/Makefile
@@ -0,0 +1,9 @@
+CC := g++
+CCFLAGS := --std=c++17 -Wall
+
+all: day-17-rust day-17.jl
+ julia day-17.jl
+ ./day-17-rust
+
+day-17-rust: day-17.rs
+ rustc $^ -o $@
diff --git a/day-17/day-17.rs b/day-17/day-17.rs
@@ -0,0 +1,262 @@
+use std::collections::HashMap;
+use std::collections::VecDeque;
+type Op = i128;
+
+fn main() {
+ let input = std::fs::read_to_string("input.txt")
+ .unwrap()
+ .trim()
+ .split(",")
+ .map(|op| op.parse::<Op>().unwrap())
+ .collect::<Vec<Op>>();
+ println!("Rust:");
+ println!("Part 1: {}", part_1(&input));
+ println!("Part 2: {}", part_2(&input));
+}
+
+fn computer_step(
+ program: &mut HashMap<usize, Op>,
+ pc: &mut usize,
+ relative_base: &mut Op,
+ input: &mut Option<Op>,
+) -> (bool, Vec<Op>) {
+ let mut output = vec![];
+ let get_param = |loc: usize, mode, program: &HashMap<usize, Op>, relative_base: &Op| -> Op {
+ match mode {
+ // Position mode.
+ 0 => *program.get(&(program[&loc] as usize)).unwrap_or(&0),
+ // Immediate mode.
+ 1 => program[&loc],
+ // Relative mode.
+ 2 => *program
+ .get(&((*relative_base + program[&loc]) as usize))
+ .unwrap_or(&0),
+ _ => panic!(),
+ }
+ };
+
+ let get_res_loc =
+ |loc: usize, mode, program: &HashMap<usize, Op>, relative_base: &Op| -> usize {
+ match mode {
+ // Position mode.
+ 0 => program[&loc] as usize,
+ // Immediate mode is banned.
+ // Relative mode.
+ 2 => (relative_base + program[&loc]) as usize,
+ _ => panic!(),
+ }
+ };
+
+ loop {
+ let op_code = program[pc] % 100;
+ let mode_1 = (program[pc] % 1000) / 100;
+ let mode_2 = (program[pc] % 10000) / 1000;
+ let mode_3 = (program[pc] % 100000) / 10000;
+ match op_code {
+ 1 => {
+ let res_loc = get_res_loc(*pc + 3, mode_3, &program, relative_base);
+ let param_1 = get_param(*pc + 1, mode_1, &program, relative_base);
+ let param_2 = get_param(*pc + 2, mode_2, &program, relative_base);
+ *program.entry(res_loc).or_default() = param_1 + param_2;
+ *pc += 4;
+ }
+ 2 => {
+ let res_loc = get_res_loc(*pc + 3, mode_3, &program, relative_base);
+ let param_1 = get_param(*pc + 1, mode_1, &program, relative_base);
+ let param_2 = get_param(*pc + 2, mode_2, &program, relative_base);
+ *program.entry(res_loc as usize).or_default() = param_1 * param_2;
+ *pc += 4;
+ }
+ 3 => {
+ let res_loc = get_res_loc(*pc + 1, mode_1, &program, relative_base);
+ // Only use input once.
+ if input.is_some() {
+ *program.entry(res_loc as usize).or_default() = input.unwrap();
+ *input = None;
+ } else {
+ // Need new input.
+ return (false, output);
+ };
+ *pc += 2;
+ }
+ 4 => {
+ let param_1 = get_param(*pc + 1, mode_1, &program, relative_base);
+ output.push(param_1);
+ *pc += 2;
+ }
+ 5 => {
+ let param_1 = get_param(*pc + 1, mode_1, &program, relative_base);
+ let param_2 = get_param(*pc + 2, mode_2, &program, relative_base);
+ if param_1 != 0 {
+ *pc = param_2 as usize;
+ } else {
+ *pc += 3;
+ }
+ }
+ 6 => {
+ let param_1 = get_param(*pc + 1, mode_1, &program, relative_base);
+ let param_2 = get_param(*pc + 2, mode_2, &program, relative_base);
+ if param_1 == 0 {
+ *pc = param_2 as usize;
+ } else {
+ *pc += 3;
+ }
+ }
+ 7 => {
+ let res_loc = get_res_loc(*pc + 3, mode_3, &program, relative_base);
+ let param_1 = get_param(*pc + 1, mode_1, &program, relative_base);
+ let param_2 = get_param(*pc + 2, mode_2, &program, relative_base);
+ *program.entry(res_loc as usize).or_default() =
+ if param_1 < param_2 { 1 } else { 0 };
+ *pc += 4;
+ }
+ 8 => {
+ let res_loc = get_res_loc(*pc + 3, mode_3, &program, relative_base);
+ let param_1 = get_param(*pc + 1, mode_1, &program, relative_base);
+ let param_2 = get_param(*pc + 2, mode_2, &program, relative_base);
+ *program.entry(res_loc as usize).or_default() =
+ if param_1 == param_2 { 1 } else { 0 };
+ *pc += 4;
+ }
+ 9 => {
+ let param_1 = get_param(*pc + 1, mode_1, &program, relative_base);
+ *relative_base += param_1;
+ *pc += 2;
+ }
+ 99 => {
+ break;
+ }
+ _ => {
+ println!("Unknown op {}", op_code);
+ println!("{}", program[pc]);
+ panic!();
+ }
+ }
+ }
+ (true, output)
+}
+
+fn get_view(input: &Vec<Op>) -> Vec<Vec<char>> {
+ // Get view of the scaffoldings.
+ let mut program = input
+ .iter()
+ .enumerate()
+ .map(|(idx, &op)| (idx, op))
+ .collect::<HashMap<usize, Op>>();
+ // Set program state.
+ let mut pc = 0;
+ let mut relative_base = 0;
+ let (_, output) = computer_step(&mut program, &mut pc, &mut relative_base, &mut None);
+ // Split output into vector of vector.
+ let width = output
+ .iter()
+ .enumerate()
+ .filter(|(_, &op)| op == 10)
+ .next()
+ .unwrap()
+ .0
+ + 1;
+ // No need to include the new lines at the end.
+ output[..(output.len() - 1)]
+ .chunks(width)
+ .map(|chunk| {
+ chunk
+ .iter()
+ .filter(|&&op| op != 10)
+ .map(|&op| op as u8 as char)
+ .collect()
+ })
+ .collect()
+}
+
+fn print_view(view: &Vec<Vec<char>>) {
+ for row in view {
+ for px in row {
+ print!("{}", px);
+ }
+ println!();
+ }
+}
+
+fn calc_alignment_parameter(view: &Vec<Vec<char>>) -> usize {
+ // Get view width.
+ let width = view[0].len();
+ let height = view.len();
+ let mut alignment_param = 0;
+ // Current coordinate.
+ // No intersection can occur on the borders.
+ for x in 1..(width - 1) {
+ for y in 1..(height - 1) {
+ // Check for intersection.
+ // All 5 squares should be scaffolding.
+ if view[y][x] != '.'
+ && view[y][x + 1] != '.'
+ && view[y][x - 1] != '.'
+ && view[y + 1][x] != '.'
+ && view[y - 1][x] != '.'
+ {
+ alignment_param += x * y;
+ }
+ }
+ }
+ alignment_param
+}
+
+fn collect_dust(
+ input: &Vec<Op>,
+ main_routine: &Vec<Op>,
+ func_a: &Vec<Op>,
+ func_b: &Vec<Op>,
+ func_c: &Vec<Op>,
+) -> usize {
+ let mut program = input
+ .iter()
+ .enumerate()
+ .map(|(idx, &op)| (idx, op))
+ .collect::<HashMap<usize, Op>>();
+ // Enable movements.
+ *program.get_mut(&0).unwrap() = 2;
+ // Set program state.
+ let mut pc = 0;
+ let mut relative_base = 0;
+ // Assemble commands.
+ let mut commands = main_routine
+ .iter()
+ .chain(func_a)
+ .chain(func_b)
+ .chain(func_c)
+ .chain(&['n' as u8 as Op, '\n' as u8 as Op]) // No video feeds.
+ .cloned()
+ .collect::<VecDeque<Op>>();
+ // Collect output.
+ let mut output = Vec::new();
+ // Run program.
+ loop {
+ let (finished, mut step_output) = computer_step(
+ &mut program,
+ &mut pc,
+ &mut relative_base,
+ &mut commands.pop_front(),
+ );
+ output.append(&mut step_output);
+ if finished {
+ break;
+ }
+ }
+ *output.last().unwrap() as usize
+}
+
+fn part_1(input: &Vec<Op>) -> usize {
+ let view = get_view(input);
+ print_view(&view);
+ calc_alignment_parameter(&view)
+}
+
+fn part_2(input: &Vec<Op>) -> usize {
+ let cmd_to_ascii = |cmd: &str| -> Vec<Op> { cmd.chars().map(|ch| ch as u8 as Op).collect() };
+ let main_routine = cmd_to_ascii("A,B,A,B,C,A,B,C,A,C\n");
+ let func_a = cmd_to_ascii("R,6,L,6,L,10\n");
+ let func_b = cmd_to_ascii("L,8,L,6,L,10,L,6\n");
+ let func_c = cmd_to_ascii("R,6,L,8,L,10,R,6\n");
+ collect_dust(input, &main_routine, &func_a, &func_b, &func_c)
+}
diff --git a/day-17/input.txt b/day-17/input.txt
@@ -0,0 +1 @@
+1,330,331,332,109,3032,1102,1,1182,16,1101,0,1433,24,102,1,0,570,1006,570,36,1001,571,0,0,1001,570,-1,570,1001,24,1,24,1106,0,18,1008,571,0,571,1001,16,1,16,1008,16,1433,570,1006,570,14,21102,1,58,0,1105,1,786,1006,332,62,99,21101,333,0,1,21101,73,0,0,1106,0,579,1101,0,0,572,1102,0,1,573,3,574,101,1,573,573,1007,574,65,570,1005,570,151,107,67,574,570,1005,570,151,1001,574,-64,574,1002,574,-1,574,1001,572,1,572,1007,572,11,570,1006,570,165,101,1182,572,127,101,0,574,0,3,574,101,1,573,573,1008,574,10,570,1005,570,189,1008,574,44,570,1006,570,158,1105,1,81,21102,1,340,1,1106,0,177,21102,1,477,1,1105,1,177,21102,514,1,1,21101,0,176,0,1106,0,579,99,21101,184,0,0,1105,1,579,4,574,104,10,99,1007,573,22,570,1006,570,165,102,1,572,1182,21101,375,0,1,21101,0,211,0,1105,1,579,21101,1182,11,1,21102,222,1,0,1105,1,979,21101,388,0,1,21101,233,0,0,1105,1,579,21101,1182,22,1,21101,244,0,0,1105,1,979,21101,0,401,1,21102,255,1,0,1105,1,579,21101,1182,33,1,21102,1,266,0,1106,0,979,21102,1,414,1,21102,1,277,0,1106,0,579,3,575,1008,575,89,570,1008,575,121,575,1,575,570,575,3,574,1008,574,10,570,1006,570,291,104,10,21101,0,1182,1,21102,1,313,0,1105,1,622,1005,575,327,1102,1,1,575,21102,1,327,0,1105,1,786,4,438,99,0,1,1,6,77,97,105,110,58,10,33,10,69,120,112,101,99,116,101,100,32,102,117,110,99,116,105,111,110,32,110,97,109,101,32,98,117,116,32,103,111,116,58,32,0,12,70,117,110,99,116,105,111,110,32,65,58,10,12,70,117,110,99,116,105,111,110,32,66,58,10,12,70,117,110,99,116,105,111,110,32,67,58,10,23,67,111,110,116,105,110,117,111,117,115,32,118,105,100,101,111,32,102,101,101,100,63,10,0,37,10,69,120,112,101,99,116,101,100,32,82,44,32,76,44,32,111,114,32,100,105,115,116,97,110,99,101,32,98,117,116,32,103,111,116,58,32,36,10,69,120,112,101,99,116,101,100,32,99,111,109,109,97,32,111,114,32,110,101,119,108,105,110,101,32,98,117,116,32,103,111,116,58,32,43,10,68,101,102,105,110,105,116,105,111,110,115,32,109,97,121,32,98,101,32,97,116,32,109,111,115,116,32,50,48,32,99,104,97,114,97,99,116,101,114,115,33,10,94,62,118,60,0,1,0,-1,-1,0,1,0,0,0,0,0,0,1,18,14,0,109,4,2102,1,-3,587,20101,0,0,-1,22101,1,-3,-3,21102,0,1,-2,2208,-2,-1,570,1005,570,617,2201,-3,-2,609,4,0,21201,-2,1,-2,1106,0,597,109,-4,2106,0,0,109,5,1201,-4,0,630,20102,1,0,-2,22101,1,-4,-4,21101,0,0,-3,2208,-3,-2,570,1005,570,781,2201,-4,-3,652,21001,0,0,-1,1208,-1,-4,570,1005,570,709,1208,-1,-5,570,1005,570,734,1207,-1,0,570,1005,570,759,1206,-1,774,1001,578,562,684,1,0,576,576,1001,578,566,692,1,0,577,577,21101,0,702,0,1105,1,786,21201,-1,-1,-1,1106,0,676,1001,578,1,578,1008,578,4,570,1006,570,724,1001,578,-4,578,21101,0,731,0,1106,0,786,1106,0,774,1001,578,-1,578,1008,578,-1,570,1006,570,749,1001,578,4,578,21101,0,756,0,1105,1,786,1105,1,774,21202,-1,-11,1,22101,1182,1,1,21101,774,0,0,1105,1,622,21201,-3,1,-3,1106,0,640,109,-5,2105,1,0,109,7,1005,575,802,20101,0,576,-6,20101,0,577,-5,1106,0,814,21102,0,1,-1,21102,1,0,-5,21102,0,1,-6,20208,-6,576,-2,208,-5,577,570,22002,570,-2,-2,21202,-5,41,-3,22201,-6,-3,-3,22101,1433,-3,-3,2102,1,-3,843,1005,0,863,21202,-2,42,-4,22101,46,-4,-4,1206,-2,924,21102,1,1,-1,1105,1,924,1205,-2,873,21102,1,35,-4,1105,1,924,1202,-3,1,878,1008,0,1,570,1006,570,916,1001,374,1,374,1201,-3,0,895,1102,2,1,0,1202,-3,1,902,1001,438,0,438,2202,-6,-5,570,1,570,374,570,1,570,438,438,1001,578,558,922,20101,0,0,-4,1006,575,959,204,-4,22101,1,-6,-6,1208,-6,41,570,1006,570,814,104,10,22101,1,-5,-5,1208,-5,39,570,1006,570,810,104,10,1206,-1,974,99,1206,-1,974,1101,0,1,575,21101,973,0,0,1106,0,786,99,109,-7,2105,1,0,109,6,21101,0,0,-4,21102,1,0,-3,203,-2,22101,1,-3,-3,21208,-2,82,-1,1205,-1,1030,21208,-2,76,-1,1205,-1,1037,21207,-2,48,-1,1205,-1,1124,22107,57,-2,-1,1205,-1,1124,21201,-2,-48,-2,1105,1,1041,21101,0,-4,-2,1105,1,1041,21101,-5,0,-2,21201,-4,1,-4,21207,-4,11,-1,1206,-1,1138,2201,-5,-4,1059,2101,0,-2,0,203,-2,22101,1,-3,-3,21207,-2,48,-1,1205,-1,1107,22107,57,-2,-1,1205,-1,1107,21201,-2,-48,-2,2201,-5,-4,1090,20102,10,0,-1,22201,-2,-1,-2,2201,-5,-4,1103,2101,0,-2,0,1106,0,1060,21208,-2,10,-1,1205,-1,1162,21208,-2,44,-1,1206,-1,1131,1105,1,989,21102,1,439,1,1106,0,1150,21102,1,477,1,1105,1,1150,21101,514,0,1,21101,0,1149,0,1106,0,579,99,21102,1,1157,0,1105,1,579,204,-2,104,10,99,21207,-3,22,-1,1206,-1,1138,2101,0,-5,1176,2101,0,-4,0,109,-6,2105,1,0,8,7,34,1,5,1,34,1,5,1,34,1,5,1,32,11,30,1,1,1,5,1,1,1,30,1,1,1,5,7,26,1,1,1,7,1,3,1,26,1,1,1,5,11,22,1,1,1,5,1,1,1,3,1,3,1,16,7,1,9,3,1,3,1,5,1,10,1,13,1,5,1,3,1,5,1,10,1,13,1,5,1,3,1,5,1,10,1,13,1,5,1,3,1,5,1,10,1,13,1,3,7,5,1,10,1,13,1,5,1,9,1,10,1,13,7,9,12,39,12,29,1,10,1,29,1,10,1,29,1,10,1,29,1,8,7,25,1,8,1,1,1,3,1,25,1,4,7,3,1,19,7,4,1,3,1,5,1,19,1,10,1,3,1,5,1,19,1,10,1,3,1,5,1,19,1,10,1,3,1,5,1,7,7,5,1,10,1,3,1,5,1,7,1,5,1,5,1,10,11,7,1,5,1,5,1,14,1,13,1,5,1,5,1,14,7,7,1,5,1,5,1,20,1,7,1,5,1,5,1,20,1,7,1,5,7,20,1,7,1,32,1,7,1,32,1,7,1,32,9,18