day20 part2

1 files changed, 46 insertions, 7 deletions

diff --git a/2024/day20.rs b/2024/day20.rs
index a0549ef..06ecbd4 100644
--- a/2024/day20.rs
+++ b/2024/day20.rs
@@ -79,12 +79,10 @@ fn main() {
     }
     let width = m.len();
     let height = m[0].len();
-    println!("{} {}", width, height);
 
+    let mut res1 = 0;
     let mut lut: HashMap<(i64, i64), i64> = HashMap::new();
     let ref_score = dfs(0, sx, sy, ex, ey, &m, &mut lut);
-
-    let mut res1 = 0;
     for y in 1..height - 1 {
         for x in 1..width - 1 {
             if m[y][x] == true {
@@ -97,15 +95,56 @@ fn main() {
             if score + 100 <= ref_score {
                 res1 += 1;
             }
-            println!("{}", score);
         }
     }
 
-    //print(&m, &hs);
+    let mut from_start: HashMap<(i64, i64), i64> = HashMap::new();
+    let mut to_end: HashMap<(i64, i64), i64> = HashMap::new();
+    for y in 1..height - 1 {
+        for x in 1..width - 1 {
+            if m[y][x] == false {
+                continue;
+            }
+            let x = x as i64;
+            let y = y as i64;
+            lut.clear();
+            let score = dfs(0, sx, sy, x, y, &m, &mut lut);
+            from_start.insert((x, y), score);
+
+            lut.clear();
+            let score = dfs(0, x, y, ex, ey, &m, &mut lut);
+            to_end.insert((x, y), score);
+        }
+    }
+
     let mut res2 = 0;
+    for y in 1..height - 1 {
+        for x in 1..width - 1 {
+            if m[y][x] == false {
+                continue;
+            }
+            let x = x as i64;
+            let y = y as i64;
+
+            let s1 = from_start.get(&(x, y)).unwrap();
+            for dx in -20..=20 {
+                for dy in -20..=20 {
+                    let s2 = (dx as i64).abs() + (dy as i64).abs();
+                    if s2 > 20 {
+                        continue;
+                    }
+                    if let Some(s3) = to_end.get(&(x + dx, y + dy)) {
+                        if s1 + s2 + s3 + 100 <= ref_score {
+                            res2 += 1;
+                        }
+                    }
+                }
+            }
+        }
+    }
 
     println!("res1: {}", res1);
     println!("res2: {}", res2);
-    //assert_eq!(res1, 1422);
-    //assert_eq!(res2, );
+    assert_eq!(res1, 1422);
+    assert_eq!(res2, 1009299);
 }