summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJustin Worthe <justin@worthe-it.co.za>2018-12-22 08:19:13 +0200
committerJustin Worthe <justin@worthe-it.co.za>2018-12-22 08:19:13 +0200
commit5ced5ee5696770b793d1137a6cebc7b934205e9d (patch)
tree84c672f17d3dc07e6fac6d3ff4e1b94e83eb8512
parent551629a62bee37e33c3430272f1eb602324bf841 (diff)
Day 22: 3D Pathfinding
-rw-r--r--inputs/22.txt2
-rw-r--r--src/bin/day_22.rs150
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
+}