day17HEADmaster

4 files changed, 162 insertions, 5 deletions

diff --git a/src/day12pt1.rs b/src/day12pt1.rs
index bdf4027..dbc7011 100644
--- a/src/day12pt1.rs
+++ b/src/day12pt1.rs
@@ -7,7 +7,10 @@ pub fn main() {
 
     for line in input {
         let s = line[0];
-        let n = line[1].split(",").map(|s| s.parse::<u64>().unwrap()).collect::<Vec<_>>();
+        let n = line[1]
+            .split(",")
+            .map(|s| s.parse::<u64>().unwrap())
+            .collect::<Vec<_>>();
         println!("{} {:?}", s, n);
     }
 }
diff --git a/src/day17pt1.rs b/src/day17pt1.rs
new file mode 100644
index 0000000..959012c
--- /dev/null
+++ b/src/day17pt1.rs
@@ -0,0 +1,74 @@
+use std::cmp::Reverse;
+use std::collections::BinaryHeap;
+use std::collections::HashMap;
+const N: usize = 200;
+const M: usize = 200;
+
+pub fn dist(input: &Vec<Vec<u32>>, y1: i32, x1: i32, y2: i32, x2: i32) -> i32 {
+    let ind1 = (y1 - y2).abs();
+    let ind2 = (x1 - x2).abs();
+
+    if (ind1 == 1 && ind2 == 0) || (ind1 == 0 && ind2 == 1) {
+        return input[y2 as usize][x2 as usize] as i32;
+    }
+
+    return i32::MAX;
+}
+
+pub fn main() {
+    let txt = std::fs::read_to_string("./input/day17.txt").unwrap();
+    let input = txt
+        .lines()
+        .map(|s| {
+            s.split("")
+                .filter_map(|c| c.parse::<u32>().ok())
+                .collect::<Vec<_>>()
+        })
+        .collect::<Vec<Vec<_>>>();
+
+    let n = input.len();
+    let m = input[0].len();
+    let mut d = [[i32::MAX; M]; N];
+
+    // (dist, y, x, dy, dx, cnt)
+    let mut bh: BinaryHeap<Reverse<(i32, i32, i32, i32, i32, i32)>> = Default::default();
+    // (y, x, dy, dx, cnt)
+    let mut hm: HashMap<(i32, i32, i32, i32, i32), bool> = Default::default();
+
+    bh.push(Reverse((0, 0, 0, 0, 0, 0)));
+    hm.insert((0, 0, 0, 0, 0), true);
+
+    while !bh.is_empty() {
+        let Reverse(x) = bh.pop().unwrap();
+        let (ndist, i, j, odi, odj, cnt) = x;
+
+        if ndist < d[i as usize][j as usize] {
+            d[i as usize][j as usize] = ndist;
+        }
+
+        for (di, dj) in [(0, 1), (0, -1), (1, 0), (-1, 0)] {
+            if odi == -di && odj == -dj {
+                continue;
+            }
+
+            let ni = i + di;
+            let nj = j + dj;
+            if ni < 0 || ni >= n as i32 || nj < 0 || nj >= m as i32 {
+                continue;
+            }
+
+            let ncnt = (cnt + 1) * (di == odi && dj == odj) as i32;
+            let ndst = ndist + dist(&input, i, j, ni, nj);
+
+            if hm.contains_key(&(ni, nj, di, dj, ncnt)) || ncnt == 3 {
+                continue;
+            } else {
+                hm.insert((ni, nj, di, dj, ncnt), true);
+            }
+
+            bh.push(Reverse((ndst, ni, nj, di, dj, ncnt)));
+        }
+    }
+
+    println!("{}", d[n - 1][m - 1]);
+}
diff --git a/src/day17pt2.rs b/src/day17pt2.rs
new file mode 100644
index 0000000..2ace59f
--- /dev/null
+++ b/src/day17pt2.rs
@@ -0,0 +1,80 @@
+use std::cmp::Reverse;
+use std::collections::BinaryHeap;
+use std::collections::HashMap;
+const N: usize = 200;
+const M: usize = 200;
+
+pub fn dist(input: &Vec<Vec<u32>>, y1: i32, x1: i32, y2: i32, x2: i32) -> i32 {
+    let ind1 = (y1 - y2).abs();
+    let ind2 = (x1 - x2).abs();
+
+    if (ind1 == 1 && ind2 == 0) || (ind1 == 0 && ind2 == 1) {
+        return input[y2 as usize][x2 as usize] as i32;
+    }
+
+    return i32::MAX;
+}
+
+pub fn main() {
+    let txt = std::fs::read_to_string("./input/day17.txt").unwrap();
+    let input = txt
+        .lines()
+        .map(|s| {
+            s.split("")
+                .filter_map(|c| c.parse::<u32>().ok())
+                .collect::<Vec<_>>()
+        })
+        .collect::<Vec<Vec<_>>>();
+
+    let n = input.len();
+    let m = input[0].len();
+    let mut d = [[i32::MAX; M]; N];
+
+    // (dist, y, x, dy, dx, cnt)
+    let mut bh: BinaryHeap<Reverse<(i32, i32, i32, i32, i32, i32)>> = Default::default();
+    // (y, x, dy, dx, cnt)
+    let mut hm: HashMap<(i32, i32, i32, i32, i32), bool> = Default::default();
+
+    bh.push(Reverse((0, 0, 0, 0, 1, 0)));
+    bh.push(Reverse((0, 0, 0, 1, 0, 0)));
+    hm.insert((0, 0, 0, 1, 0), true);
+    hm.insert((0, 0, 1, 0, 0), true);
+
+    while !bh.is_empty() {
+        let Reverse(x) = bh.pop().unwrap();
+        let (ndist, i, j, odi, odj, cnt) = x;
+
+        if ndist < d[i as usize][j as usize] && cnt >= 4 {
+            d[i as usize][j as usize] = ndist;
+        }
+
+        for (di, dj) in [(0, 1), (0, -1), (1, 0), (-1, 0)] {
+            if odi == -di && odj == -dj {
+                continue;
+            }
+
+            if cnt < 4 && !(odi == di && odj == dj) {
+                continue;
+            }
+
+            let ni = i + di;
+            let nj = j + dj;
+            if ni < 0 || ni >= n as i32 || nj < 0 || nj >= m as i32 {
+                continue;
+            }
+
+            let ncnt = if di == odi && dj == odj { cnt + 1 } else { 1 };
+            let ndst = ndist + dist(&input, i, j, ni, nj);
+
+            if hm.contains_key(&(ni, nj, di, dj, ncnt)) || ncnt == 11 {
+                continue;
+            } else {
+                hm.insert((ni, nj, di, dj, ncnt), true);
+            }
+
+            bh.push(Reverse((ndst, ni, nj, di, dj, ncnt)));
+        }
+    }
+
+    println!("{}", d[n - 1][m - 1]);
+}
diff --git a/src/main.rs b/src/main.rs
index 3c60b82..e3e41ae 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,7 +1,7 @@
-mod day16pt1;
-mod day16pt2;
+mod day17pt1;
+mod day17pt2;
 
 fn main() {
-    day16pt1::main();
-    day16pt2::main();
+    day17pt1::main();
+    day17pt2::main();
 }