day05 reverse search

1 files changed, 28 insertions, 18 deletions

diff --git a/2023/day05.rs b/2023/day05.rs
index c879d49..1a74980 100644
--- a/2023/day05.rs
+++ b/2023/day05.rs
@@ -14,13 +14,22 @@ struct SeedMap {
 
 fn do_map(val: u64, sms: &Vec<SeedMap>) -> u64 {
     for sm in sms.iter() {
-        if (sm.src..sm.src + sm.len).contains(&val) {
+        if (sm.src <= val) && (val < sm.src + sm.len) {
             return val + sm.dest - sm.src;
         }
     }
     return val;
 }
 
+fn do_reverse_map(val: u64, sms: &Vec<SeedMap>) -> u64 {
+    for sm in sms.iter() {
+        if (sm.dest <= val) && (val < sm.dest + sm.len) {
+            return val + sm.src - sm.dest;
+        }
+    }
+    return val;
+}
+
 fn main() {
     // let filename = "in/day05.ref";
     let filename = "in/day05.pzl";
@@ -31,9 +40,6 @@ fn main() {
     let mut chunks = content.trim_end().split("\n\n");
     // println!("{:?}", chunks);
 
-    let mut res1;
-    let mut res2 = 999999999999;
-
     let mut seeds: Vec<u64> = chunks
         .next()
         .unwrap()
@@ -63,30 +69,34 @@ fn main() {
         all_maps.push(map_vec);
     }
 
-    let mut final_seed1 = Vec::new();
-    for mut seed in seeds.clone().into_iter() {
-        for m in all_maps.iter() {
-            seed = do_map(seed, m);
-        }
-        final_seed1.push(seed);
+    let mut res1 = 999999999999;
+    for seed in seeds.clone().into_iter() {
+        res1 = min(res1, all_maps.iter().fold(seed, |s, m| do_map(s, m)));
     }
-    final_seed1.sort();
-    res1 = final_seed1[0];
 
     let seed_pairs: Vec<_> = seeds
         .chunks_exact(2)
         .map(|x| (x[0] as u64, x[1] as u64))
         .collect();
 
-    for (start, len) in seed_pairs.clone().into_iter() {
-        for mut seed in start..(start + len) {
-            for m in all_maps.iter() {
-                seed = do_map(seed, m);
-            }
-            res2 = min(res2, seed);
+    let mut res2 = 0;
+    for i in 0.. {
+        let a = all_maps.iter().rev().fold(i, |s, m| do_reverse_map(s, m));
+        if seed_pairs
+            .clone()
+            .into_iter()
+            .filter(|&(start, len)|
+                    (start <= a) && (a < start + len))
+            .next()
+            .is_some()
+        {
+            res2 = i;
+            break;
         }
     }
 
     println!("res1: {}", res1);
     println!("res2: {}", res2);
+    assert_eq!(res1, 196167384);
+    assert_eq!(res2, 125742456);
 }