commit 23009c3a9747510c0bd7047182e256f372fe073d
parent 8b195a355ad62985df7f0b2d17d710ec17d69028
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Sun, 15 Dec 2019 11:05:21 -0500
Add Rust solution for day 15
Diffstat:
3 files changed, 302 insertions(+), 0 deletions(-)
diff --git a/day-15/Makefile b/day-15/Makefile
@@ -0,0 +1,9 @@
+CC := g++
+CCFLAGS := --std=c++17 -Wall
+
+all: day-15-rust day-15.jl
+ julia day-15.jl
+ ./day-15-rust
+
+day-15-rust: day-15.rs
+ rustc $^ -o $@
diff --git a/day-15/day-15.rs b/day-15/day-15.rs
@@ -0,0 +1,292 @@
+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 flip(cmd: &i32) -> i32 {
+ // Returns command in opposite direction.
+ match cmd {
+ 1 => 2,
+ 2 => 1,
+ 3 => 4,
+ 4 => 3,
+ _ => panic!(),
+ }
+}
+
+fn move_to_cmd(coord: (i32, i32), cmd: i32) -> (i32, i32) {
+ // Moves coord by cmd.
+ match cmd {
+ // North
+ 1 => (coord.0, coord.1 + 1),
+ // South
+ 2 => (coord.0, coord.1 - 1),
+ // West
+ 3 => (coord.0 - 1, coord.1),
+ // East
+ 4 => (coord.0 + 1, coord.1),
+ _ => panic!(),
+ }
+}
+
+fn chart_maze(input: &Vec<Op>) -> HashMap<(i32, i32), i32> {
+ // Chart the maze via DFS.
+ 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;
+ // DFS to chart the maze.
+ let mut curr_cmds = Vec::new();
+ let mut curr_path = vec![(0, 0)];
+ let mut map = HashMap::<(i32, i32), i32>::new();
+ map.insert((0, 0), 1);
+ // Start with initial directions.
+ let mut queue = VecDeque::new();
+ for cmd in 1..=4 {
+ queue.push_back((1, cmd, move_to_cmd((0, 0), cmd)));
+ }
+ while let Some((path_len, cmd, coord)) = queue.pop_back() {
+ // Check difference between current path and backtrack.
+ if curr_path.len() > path_len {
+ // Backtrack.
+ for cmd in curr_cmds[(path_len - 1)..].iter().rev().map(flip) {
+ computer_step(
+ &mut program,
+ &mut pc,
+ &mut relative_base,
+ &mut Some(cmd.into()),
+ );
+ }
+ // Clean up path.
+ curr_cmds.truncate(path_len - 1);
+ // Keep the origin.
+ curr_path.truncate(path_len);
+ }
+ // Move in specified direction.
+ let (_, step_output) = computer_step(
+ &mut program,
+ &mut pc,
+ &mut relative_base,
+ &mut Some(cmd.into()),
+ );
+ // Chart the result.
+ map.insert(coord, step_output[0] as i32);
+ // Determine if we proceed in given direction.
+ if step_output[0] != 0 {
+ // Free space, record and plan next moves.
+ // Otherwise, keep original path.
+ curr_cmds.push(cmd);
+ curr_path.push(coord);
+ for next_cmd in 1..=4 {
+ // Only visit uncharted location.
+ let target = move_to_cmd(coord, next_cmd);
+ if !map.contains_key(&target) {
+ queue.push_back((path_len + 1, next_cmd, target));
+ }
+ }
+ }
+ }
+ map
+}
+
+fn find_min_path(map: &HashMap<(i32, i32), i32>) -> usize {
+ // Return shortest path from (0, 0) to space labeled 2.
+ let mut queue = VecDeque::new();
+ let mut visited = HashMap::new();
+ queue.push_back((0, (0, 0)));
+ // BFS to find location.
+ while let Some((path_len, coord)) = queue.pop_front() {
+ visited.insert(coord, true);
+ match map.get(&coord).unwrap_or(&0) {
+ 0 => {
+ continue;
+ }
+ 1 => {
+ // Explore next steps.
+ for cmd in 1..=4 {
+ let next_coord = move_to_cmd(coord, cmd);
+ if !visited.get(&next_coord).unwrap_or(&false) {
+ queue.push_back((path_len + 1, next_coord));
+ }
+ }
+ }
+ 2 => return path_len,
+ _ => panic!(),
+ }
+ }
+ usize::max_value()
+}
+
+fn calc_fill_time(map: &HashMap<(i32, i32), i32>) -> usize {
+ // Computes the fill time for the entire maze.
+ // Find oxygen source.
+ let source_coord = *map.iter().filter(|(_, &v)| v == 2).next().unwrap().0;
+ let mut queue = VecDeque::new();
+ let mut filled = HashMap::new();
+ queue.push_back((0, source_coord));
+ let mut max_time = 0;
+ // BFS to fill the maze.
+ while let Some((time, coord)) = queue.pop_front() {
+ max_time = max_time.max(time);
+ filled.insert(coord, true);
+ if *map.get(&coord).unwrap_or(&0) != 0 {
+ // Walls can't be filled.
+ // Fill the next area.
+ for cmd in 1..=4 {
+ let next_coord = move_to_cmd(coord, cmd);
+ if !filled.get(&next_coord).unwrap_or(&false) {
+ queue.push_back((time + 1, next_coord));
+ }
+ }
+ }
+ }
+ max_time
+}
+
+fn part_1(input: &Vec<Op>) -> usize {
+ let map = chart_maze(input);
+ find_min_path(&map)
+}
+
+fn part_2(input: &Vec<Op>) -> usize {
+ let map = chart_maze(input);
+ calc_fill_time(&map)
+}
diff --git a/day-15/input.txt b/day-15/input.txt
@@ -0,0 +1 @@
+3,1033,1008,1033,1,1032,1005,1032,31,1008,1033,2,1032,1005,1032,58,1008,1033,3,1032,1005,1032,81,1008,1033,4,1032,1005,1032,104,99,1002,1034,1,1039,102,1,1036,1041,1001,1035,-1,1040,1008,1038,0,1043,102,-1,1043,1032,1,1037,1032,1042,1106,0,124,102,1,1034,1039,101,0,1036,1041,1001,1035,1,1040,1008,1038,0,1043,1,1037,1038,1042,1106,0,124,1001,1034,-1,1039,1008,1036,0,1041,1001,1035,0,1040,1002,1038,1,1043,101,0,1037,1042,1106,0,124,1001,1034,1,1039,1008,1036,0,1041,102,1,1035,1040,101,0,1038,1043,1001,1037,0,1042,1006,1039,217,1006,1040,217,1008,1039,40,1032,1005,1032,217,1008,1040,40,1032,1005,1032,217,1008,1039,7,1032,1006,1032,165,1008,1040,37,1032,1006,1032,165,1102,1,2,1044,1106,0,224,2,1041,1043,1032,1006,1032,179,1102,1,1,1044,1106,0,224,1,1041,1043,1032,1006,1032,217,1,1042,1043,1032,1001,1032,-1,1032,1002,1032,39,1032,1,1032,1039,1032,101,-1,1032,1032,101,252,1032,211,1007,0,39,1044,1105,1,224,1101,0,0,1044,1105,1,224,1006,1044,247,102,1,1039,1034,102,1,1040,1035,101,0,1041,1036,102,1,1043,1038,102,1,1042,1037,4,1044,1106,0,0,35,37,2,26,91,30,85,34,87,18,47,29,50,23,7,46,94,2,26,42,36,23,3,32,65,21,63,18,54,31,52,75,4,35,24,24,74,33,81,89,75,50,36,43,7,20,45,9,23,10,70,12,81,62,12,51,3,5,96,7,93,90,12,41,5,52,30,91,12,62,34,44,92,68,9,81,9,6,30,38,63,27,51,3,44,47,27,86,41,1,73,78,15,34,98,9,63,66,21,89,96,5,9,36,21,97,6,26,75,14,86,16,82,21,23,91,25,15,66,33,2,50,26,18,61,73,17,49,15,99,19,68,96,33,23,12,81,11,51,19,30,56,74,27,40,76,15,49,11,24,50,27,50,36,77,36,16,22,80,86,11,85,20,87,24,26,6,64,35,27,65,32,86,42,99,30,78,68,24,67,82,4,76,63,36,4,46,21,72,68,17,21,69,71,36,82,22,57,1,29,95,59,18,48,40,91,7,44,22,64,5,52,20,20,86,34,9,67,74,22,13,31,97,23,19,78,19,12,80,19,82,83,11,26,5,10,74,2,42,5,94,26,79,51,33,15,47,9,12,84,20,37,85,63,27,92,16,10,82,64,15,50,75,12,68,51,37,87,10,51,18,11,13,99,97,30,33,48,2,45,29,22,45,20,49,14,78,33,41,89,4,67,21,40,42,20,4,34,64,98,32,77,28,79,9,51,91,58,19,45,56,4,10,3,52,47,65,11,21,53,25,57,78,33,16,70,88,34,56,37,86,30,4,84,91,86,90,37,37,25,59,2,96,25,19,69,6,11,67,83,38,8,49,18,17,21,56,20,43,89,8,78,30,80,52,29,9,65,1,1,65,27,84,23,8,33,99,71,28,38,45,14,40,31,45,44,12,94,12,65,23,96,5,93,50,35,84,10,34,81,2,51,15,11,92,69,20,65,27,68,86,76,36,49,38,79,92,38,72,8,32,80,29,41,7,15,78,38,5,10,61,24,44,38,19,80,9,60,95,95,33,48,13,51,32,57,84,97,1,51,36,6,51,96,16,62,32,13,93,4,79,40,2,68,74,38,4,30,82,17,67,51,68,29,3,85,13,5,2,30,71,36,77,35,78,23,87,22,7,78,5,60,2,11,42,15,68,89,66,93,31,38,31,81,8,65,22,7,27,83,59,21,12,73,64,72,40,38,59,20,29,92,20,7,65,16,86,81,12,44,77,97,30,19,49,61,24,29,24,31,87,89,31,42,80,17,91,23,18,91,10,53,5,17,53,30,96,96,34,83,34,18,68,79,97,18,4,56,37,33,62,31,79,99,32,14,99,87,83,53,34,26,17,70,59,31,12,42,91,32,93,5,54,8,10,83,20,58,92,30,71,24,34,60,3,9,64,72,12,70,14,22,69,38,27,77,31,84,8,54,44,58,9,30,95,22,12,61,95,21,81,71,5,64,44,7,71,4,17,41,2,89,16,20,93,88,20,31,45,28,49,91,15,72,43,6,21,82,15,25,99,8,11,34,18,93,50,15,15,98,27,34,44,38,15,29,79,42,14,86,68,56,7,3,97,21,58,11,33,67,6,53,23,71,16,58,74,17,92,17,14,98,23,35,60,32,70,54,1,82,2,41,32,68,91,27,80,6,25,55,93,23,52,91,3,95,44,3,42,70,23,16,54,36,36,59,5,63,27,40,11,73,34,48,29,73,36,74,77,58,25,55,25,45,7,58,53,49,8,95,13,84,23,58,37,42,6,70,36,58,73,55,14,51,5,99,95,61,20,65,0,0,21,21,1,10,1,0,0,0,0,0,0