Day 22: 3D Pathfinding

2 files changed, 150 insertions, 2 deletions

diff --git a/inputs/22.txt b/inputs/22.txt
new file mode 100644
index 0000000..e2e94a0
--- /dev/null
+++ b/inputs/22.txt
@@ -0,0 +1,2 @@
+depth: 7863
+target: 14,760
diff --git a/src/bin/day_22.rs b/src/bin/day_22.rs
index 741e81e..2ac0d82 100644
--- a/src/bin/day_22.rs
+++ b/src/bin/day_22.rs
@@ -4,15 +4,161 @@ use advent_of_code_2018::*;
 use std::error::Error;
 use std::path::PathBuf;
 
+use std::u32;
+use std::cmp;
+use std::collections::{HashMap, HashSet};
+
 // cargo watch -cs "cargo run --release --bin day_22"
 
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+struct Position {
+    x: u32,
+    y: u32,
+    equipment: u32 // 0 = nothing, 1 = torch, 2 = climbing
+}
+
+impl Position {
+    fn adjacent(&self, map: &Vec<Vec<u32>>) -> Vec<(Position, u32)> {
+        let all_adjacent = [
+            (Position {
+                x: self.x.saturating_sub(1),
+                ..*self
+            }, 1),
+            (Position {
+                y: self.y.saturating_sub(1),
+                ..*self
+            }, 1),
+            (Position {
+                x: self.x+1,
+                ..*self
+            }, 1),
+            (Position {
+                y: self.y+1,
+                ..*self
+            }, 1),
+            (Position {
+                equipment: (self.equipment+1)%3,
+                ..*self
+            }, 7),
+            (Position {
+                equipment: (self.equipment+2)%3,
+                ..*self
+            }, 7)
+        ];
+        all_adjacent.iter()
+            .filter(|(p, _)| {
+                let region = map[p.y as usize][p.x as usize];
+                let out_of_bounds = self == p;
+                let invalid_equipment = (region == 0 && p.equipment == 0) ||
+                    (region == 1 && p.equipment == 1) ||
+                    (region == 2 && p.equipment == 2);
+                !out_of_bounds && !invalid_equipment
+            })
+            .cloned()
+            .collect()
+    }
+}
+
 fn main() -> Result<(), Box<Error>> {
-    let input = read_file(&PathBuf::from("inputs/22.txt"))?;
+    let input = &read_file(&PathBuf::from("inputs/22.txt"))?;
+
+    let depth: u32 = input[0].trim_matches(|c: char| !c.is_numeric()).parse().unwrap();
+    debug!(depth);
+    let mut input_target_iter = input[1]
+        .split(|c: char| !c.is_numeric())
+        .filter(|s| !s.is_empty())
+        .map(|s| s.parse::<u32>().unwrap());
+
+    let target_x = input_target_iter.next().unwrap();
+    let target_y = input_target_iter.next().unwrap();
+    
+    debug!((target_x, target_y));
+
+    let mut map_width = target_x;
+    let mut map_height = target_y;
+    let mut map = build_map(map_width, map_height, depth, target_x, target_y);
 
-    println!("Input: {:?}", input);
+    let risk: u32 = map.iter().take((target_y+1) as usize).map(|row| row.iter().take((target_x+1) as usize).sum::<u32>()).sum();
+    debug!(risk);
 
 
+    let mut distances = HashMap::new();
+    let mut unexplored = HashSet::new();
+    let initial = Position {
+        x: 0,
+        y: 0,
+        equipment: 1
+    };
+    let target = Position {
+        x: target_x,
+        y: target_y,
+        equipment: 1
+    };
+    distances.insert(initial, 0);
+    unexplored.insert(initial);
 
+    while !distances.contains_key(&target) || unexplored.contains(&target) {
+        let (current, current_distance) = unexplored.iter()
+            .map(|unexp| (unexp.clone(), distances.get(unexp).cloned().unwrap()))
+            .min_by_key(|(_, d)| *d)
+            .unwrap();
+
+        if current.y+1 >= map_height {
+            map_height *= 2;
+            map = build_map(map_width, map_height, depth, target_x, target_y);
+        }
+        if current.x+1 >= map_width {
+            map_width *= 2;
+            map = build_map(map_width, map_height, depth, target_x, target_y);
+        }
+
+        for (adjacent, further) in current.adjacent(&map) {
+            let distance = current_distance + further;
+            let best_previous_distance = distances.get(&adjacent).cloned().unwrap_or(u32::MAX);
+            if best_previous_distance > distance {
+                distances.insert(adjacent, distance);
+                unexplored.insert(adjacent);
+            }
+            
+        }
+        unexplored.remove(&current);
+    }
+
+    debug!(distances.get(&target));
 
     Ok(())
 }
+
+
+fn build_map(max_x: u32, max_y: u32, depth: u32, target_x: u32, target_y: u32) -> Vec<Vec<u32>> {
+    let mut geologic_index: Vec<Vec<u32>> = Vec::new();
+    let mut erosion_level: Vec<Vec<u32>> = Vec::new();
+    let mut region_type: Vec<Vec<u32>> = Vec::new();
+
+    for y in 0..max_y {
+        let mut geologic_row = Vec::new();
+        let mut erosion_row = Vec::new();
+        let mut type_row = Vec::new();
+        
+        for x in 0..max_x {
+            let index = match (x, y) {
+                (0, 0) => 0,
+                (x, y) if x == target_x && y == target_y => 0,
+                (x, 0) => x*16807,
+                (0, y) => y*48271,
+                (x, y) => erosion_row[(x-1) as usize] * erosion_level[(y-1) as usize][x as usize]
+            };
+            let erosion = (index + depth) % 20183;
+            let block_type = erosion % 3;
+            
+            geologic_row.push(index);
+            erosion_row.push(erosion);
+            type_row.push(block_type);
+        }
+
+        geologic_index.push(geologic_row);
+        erosion_level.push(erosion_row);
+        region_type.push(type_row);
+    }
+    region_type
+}