diff options
| -rw-r--r-- | input15 | 1 | ||||
| -rw-r--r-- | src/main.rs | 246 |
2 files changed, 246 insertions, 1 deletions
@@ -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,101,0,1034,1039,1001,1036,0,1041,1001,1035,-1,1040,1008,1038,0,1043,102,-1,1043,1032,1,1037,1032,1042,1105,1,124,102,1,1034,1039,1002,1036,1,1041,1001,1035,1,1040,1008,1038,0,1043,1,1037,1038,1042,1106,0,124,1001,1034,-1,1039,1008,1036,0,1041,1002,1035,1,1040,102,1,1038,1043,102,1,1037,1042,1106,0,124,1001,1034,1,1039,1008,1036,0,1041,1001,1035,0,1040,1002,1038,1,1043,101,0,1037,1042,1006,1039,217,1006,1040,217,1008,1039,40,1032,1005,1032,217,1008,1040,40,1032,1005,1032,217,1008,1039,37,1032,1006,1032,165,1008,1040,33,1032,1006,1032,165,1101,0,2,1044,1106,0,224,2,1041,1043,1032,1006,1032,179,1101,0,1,1044,1105,1,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,62,1044,1106,0,224,1101,0,0,1044,1106,0,224,1006,1044,247,101,0,1039,1034,1002,1040,1,1035,102,1,1041,1036,101,0,1043,1038,1001,1042,0,1037,4,1044,1106,0,0,60,10,88,42,71,78,10,10,70,23,65,29,47,58,86,53,77,61,77,63,18,9,20,68,45,15,67,3,95,10,14,30,81,53,3,83,46,31,95,43,94,40,21,54,93,91,35,80,9,17,81,94,59,83,49,96,61,63,24,85,69,82,45,71,48,39,32,69,93,11,90,19,78,54,79,66,6,13,76,2,67,69,10,9,66,43,73,2,92,39,12,99,33,89,18,9,78,11,96,23,55,96,49,12,85,93,49,22,70,93,59,76,68,55,66,54,32,34,36,53,64,84,87,61,43,79,7,9,66,40,69,9,76,92,18,78,49,39,80,32,70,52,74,37,86,11,77,51,15,28,84,19,13,75,28,86,3,82,93,15,79,61,93,93,31,87,43,67,44,83,78,43,46,46,12,89,19,85,44,95,65,24,70,93,50,98,72,66,80,23,87,19,97,40,25,9,49,6,81,35,9,52,71,27,63,3,96,94,21,24,48,79,67,72,72,15,85,93,22,95,34,3,63,21,79,9,51,92,45,87,25,41,80,13,88,68,66,18,85,75,39,80,17,54,93,89,65,21,91,73,53,60,69,29,82,99,5,22,65,9,69,61,80,63,38,71,61,61,11,68,30,74,11,26,53,59,97,2,12,74,79,44,73,72,27,17,34,92,26,27,88,66,5,97,34,81,86,30,35,6,64,36,34,65,80,12,90,65,95,21,90,55,43,71,89,56,97,91,27,27,73,80,34,22,48,89,84,35,88,90,47,4,32,77,31,2,82,66,76,43,74,68,56,78,36,59,66,58,75,89,96,51,51,97,34,49,86,70,26,46,89,43,99,97,66,32,51,32,77,33,86,92,56,68,64,39,83,55,25,98,24,56,73,21,98,39,24,67,21,4,76,10,32,91,53,82,37,59,72,63,78,43,67,2,72,69,50,71,19,72,92,51,12,93,61,88,24,84,35,93,30,63,70,7,78,83,42,63,6,25,24,73,76,22,99,68,14,85,14,75,32,88,42,47,97,2,91,97,51,79,12,71,91,7,1,87,82,21,98,63,37,19,85,1,48,77,54,76,12,92,28,91,25,85,88,8,92,32,67,18,56,51,67,58,80,59,77,76,25,7,73,58,72,96,75,15,27,37,23,83,58,68,83,50,67,41,39,89,24,1,83,63,8,64,54,76,50,3,89,97,74,48,15,91,22,37,71,77,9,1,85,38,23,58,10,75,86,72,80,59,24,64,7,63,85,53,61,89,68,7,80,4,68,56,39,66,31,69,6,7,76,88,17,89,42,64,56,11,97,65,64,71,88,61,31,32,53,88,99,55,73,20,90,10,86,32,50,89,53,83,42,80,28,63,98,38,85,72,57,88,23,52,96,77,39,65,88,40,26,91,56,1,94,51,94,24,20,81,74,23,45,72,56,22,84,70,44,50,68,32,98,51,75,3,61,75,59,3,7,98,76,45,78,47,74,60,69,78,54,67,29,63,47,79,72,57,73,44,63,98,6,93,36,20,27,90,77,39,44,64,68,47,48,69,78,29,76,48,1,81,10,67,32,72,47,89,83,18,39,85,65,97,15,59,13,74,29,84,50,80,94,8,27,83,67,43,75,52,96,17,82,29,83,45,85,82,71,76,44,30,10,91,16,7,31,63,2,68,75,46,70,28,93,91,17,13,81,57,93,32,27,65,61,93,11,84,10,66,14,83,14,77,26,77,13,86,21,84,87,87,34,99,69,88,1,74,61,72,54,93,16,76,54,86,63,94,13,79,24,97,0,0,21,21,1,10,1,0,0,0,0,0,0 diff --git a/src/main.rs b/src/main.rs index 0b51282..d3a56b5 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1356,8 +1356,252 @@ fn day14() { println!("14b: {}", reactions.possible_fuel()); } +#[derive(Copy, Clone, PartialEq)] +#[repr(isize)] +enum DroidDirection { + NORTH = 1, + SOUTH = 2, + WEST = 3, + EAST = 4, +} + +impl DroidDirection { + fn from(val: isize) -> Option<DroidDirection> { + match val { + 1 => Some(DroidDirection::NORTH), + 2 => Some(DroidDirection::SOUTH), + 3 => Some(DroidDirection::WEST), + 4 => Some(DroidDirection::EAST), + _ => None, + } + } + + fn opposite(&self) -> DroidDirection { + match self { + DroidDirection::NORTH => DroidDirection::SOUTH, + DroidDirection::SOUTH => DroidDirection::NORTH, + DroidDirection::WEST => DroidDirection::EAST, + DroidDirection::EAST => DroidDirection::WEST, + } + } + + fn next(&self) -> Option<DroidDirection> { + match self { + DroidDirection::NORTH => Some(DroidDirection::SOUTH), + DroidDirection::SOUTH => Some(DroidDirection::WEST), + DroidDirection::WEST => Some(DroidDirection::EAST), + DroidDirection::EAST => None, + } + } +} + +struct RepairDroid { + computer: IntComputer, + steps: u32, + pos: Point, + map: HashMap<Point, isize>, + direction: DroidDirection, + path: Vec<(Point, DroidDirection)>, +} + +impl RepairDroid { + fn new(program: &[isize]) -> RepairDroid { + let mut tiles_map_ascii = HashMap::new(); + tiles_map_ascii.insert(0, ' '); + tiles_map_ascii.insert(1, '.'); + tiles_map_ascii.insert(2, '#'); + tiles_map_ascii.insert(3, 'O'); + tiles_map_ascii.insert(4, 'D'); + tiles_map_ascii.insert(5, '+'); + + let mut tiles_map_color = HashMap::new(); + tiles_map_color.insert(0, (255, 255, 255)); + tiles_map_color.insert(1, (200, 200, 200)); + tiles_map_color.insert(2, ( 0, 0, 0)); + tiles_map_color.insert(3, ( 0, 0, 255)); + tiles_map_color.insert(4, ( 0, 255, 0)); + tiles_map_color.insert(5, (150, 150, 150)); + + let mut computer = IntComputer::new(&program); + computer.screen.tiles_map_ascii = tiles_map_ascii; + computer.screen.tiles_map_color = tiles_map_color; + + RepairDroid { + computer, + steps: 0, + pos: Point { x: 0, y: 0 }, + map: HashMap::new(), + direction: DroidDirection::NORTH, + path: Vec::new(), + } + } + + fn move_direction(&mut self) { + let mut new_pos = self.pos; + match self.direction { + DroidDirection::NORTH => new_pos.y += 1, + DroidDirection::SOUTH => new_pos.y -= 1, + DroidDirection::WEST => new_pos.x -= 1, + DroidDirection::EAST => new_pos.x += 1, + } + self.map.insert(new_pos, 1); + + /* start next movement to north, except we are coming from there */ + let old_direction = self.direction; + self.direction = if self.direction == DroidDirection::SOUTH { + DroidDirection::SOUTH + } else { + DroidDirection::NORTH + }; + + let mut drop_last = false; + if let Some((pos, _)) = self.path.last() { + /* if the new pos is the same as the previous + on our path, we are tracking back */ + if self.pos != *pos && new_pos == *pos { + self.direction = old_direction.opposite(); + drop_last = true; + self.direction = self.next_direction(); + } + } + if drop_last { + self.pos = new_pos; + return; + } + + /* save the successful movement */ + self.pos = new_pos; + self.path.push((self.pos, old_direction)); + } + + fn mark_wall(&mut self) { + let mut wall = self.pos; + match self.direction { + DroidDirection::NORTH => wall.y += 1, + DroidDirection::SOUTH => wall.y -= 1, + DroidDirection::WEST => wall.x -= 1, + DroidDirection::EAST => wall.x += 1, + } + self.map.insert(wall, 2); + } + + fn draw_map(&mut self) { + for (pos, val) in &self.map { + self.computer.screen.set_pixel(pos.x as isize, pos.y as isize, *val); + } + self.computer.screen.set_pixel(0, 0, 5); + self.computer.screen.set_pixel(self.pos.x as isize, self.pos.y as isize, 4); + self.computer.screen.dump_screen(None); + } + + fn next_direction(&mut self) -> DroidDirection { + let previous_direction = match self.path.last() { + None => DroidDirection::NORTH, + Some(d) => d.1, + }; + + let mut new_direction = self.direction.next(); + if let Some(dir) = new_direction { + if dir == previous_direction.opposite() { + new_direction = dir.next(); + } + } + + if let Some(d) = new_direction { + d + } else { + /* go back */ + self.path.pop(); + previous_direction.opposite() + } + } + + fn set_to_oxygen(&mut self, x: i32, y: i32) { + if let Some(1) = self.map.get(&Point {x, y}) { + self.map.insert(Point {x, y}, 3); + } + } + + fn fill_with_oxygen(&mut self) -> u32 { + self.solve_labyrinth(true); + + let mut count = 0; + while self.map.values().filter(|&x| *x == 1).count() > 0 { + let oxygens: Vec<Point> = self.map.iter() + .filter(|(_, &val)| val == 3) + .map(|(&pos, _)| pos) + .collect(); + + for pos in oxygens { + self.set_to_oxygen(pos.x + 1, pos.y); + self.set_to_oxygen(pos.x - 1, pos.y); + self.set_to_oxygen(pos.x, pos.y + 1); + self.set_to_oxygen(pos.x, pos.y - 1); + } + count += 1; + } + count + } + + fn repair(&mut self) { + self.solve_labyrinth(false); + } + + fn solve_labyrinth(&mut self, map_completely: bool) { + loop { + match self.computer.run_program() { + ProgramState::NEEDINPUT => { + self.computer.input.push_back(self.direction as isize); + } + ProgramState::SUSPENDED => { + match self.computer.output.pop_front().unwrap() { + 0 => { /* hit a wall */ + self.mark_wall(); + self.direction = self.next_direction(); + } + 1 => { /* moving in this direction was successful */ + self.move_direction(); + if self.path.is_empty() { + break; + } + } + 2 => { /* found the destination */ + self.move_direction(); + self.map.insert(self.pos, 3); + if !map_completely { + break; + } + } + _ => panic!("invalid droid state") + } + } + ProgramState::HALTED => break, + _ => {} + } + } + } +} + +fn day15() { + let input = read_file("input15"); + let input = input.trim_end(); + let program : Vec<isize> = input.split(',') + .map(|x| x.parse::<isize>().unwrap()) + .collect(); + + let mut droid = RepairDroid::new(&program); + droid.computer.suspend_on_output = true; + droid.repair(); + println!("15a: {}", droid.path.len()); + + let mut droid = RepairDroid::new(&program); + droid.computer.suspend_on_output = true; + let time = droid.fill_with_oxygen(); + println!("15b: {}", time); +} + fn main() { - day14(); + day15(); } #[cfg(test)] |