perf: refactor day 5 part 2

2 files changed, 105 insertions, 131 deletions

diff --git a/answers.txt b/answers.txt
deleted file mode 100644
index c60839b..0000000
--- a/answers.txt
+++ /dev/null
@@ -1,54 +0,0 @@
-Day 1.1
-55029
-
-Day 1.2
-55686
-
-Day 2.1
-2449
-
-Day 2.2
-63981
-
-Day 3.1
-525181
-
-Day 3.2
-84289137
-
-Day 4.1
-32609
-
-Day 4.2
-14624680
-
-Day 5.1
-331445006
-
-Day 5.2
-6472060
-
-Day 6.1
-505494
-
-Day 6.2
-23632299
-
-Day 7.1
-253954294
-
-Day 7.2
-254837398
-
-Day 8.1
-11911
-
-Day 8.2
-10151663816849
-
-Day 9.1
-1853145119
-
-Day 9.2
-923
-
diff --git a/src/day_05.rs b/src/day_05.rs
index e9d0b92..cfbd298 100644
--- a/src/day_05.rs
+++ b/src/day_05.rs
@@ -1,5 +1,7 @@
 use std::{ops::Range, str::FromStr};
 
+use anyhow::Context;
+
 use crate::{Problem, Solution};
 
 pub struct Day05;
@@ -19,107 +21,84 @@ impl Solution for Day05 {
         let (first, rest) = input
             .trim()
             .split_once('\n')
-            .ok_or(anyhow::format_err!("Missing value map label"))?;
+            .context("Missing value map label")?;
 
-        let mut values = first
+        let mut seeds = first
             .strip_prefix("seeds: ")
-            .ok_or(anyhow::format_err!("Failed to get seeds"))?
+            .context("Failed to get seeds")?
             .split_whitespace()
             .map(FromStr::from_str)
-            .try_collect::<Vec<usize>>()?;
+            .try_collect::<Vec<usize>>()?
+            .into_iter()
+            .map(|n| n..(n + 1))
+            .collect::<Vec<_>>();
 
-        let value_maps = rest
+        for set in rest
             .trim()
             .split("\n\n")
-            .map(parse_value_maps)
-            .try_collect::<Vec<_>>()?;
-
-        for value_map in value_maps {
-            values.iter_mut().for_each(|value| {
-                if let Some(v) = value_map.iter().find_map(|v| v.map_value(*value)) {
-                    *value = v
-                }
-            })
+            .map(FromStr::from_str)
+            .try_collect::<Vec<ValueMapSet>>()?
+        {
+            seeds = seeds
+                .into_iter()
+                .flat_map(|seed_range| set.transform(seed_range))
+                .collect();
         }
 
-        values
-            .into_iter()
+        seeds
+            .iter()
+            .map(|range| range.start)
             .min()
-            .ok_or(anyhow::format_err!("No values found"))
+            .context("Failed to find min seed")
     }
 
     fn part_2(input: &str) -> anyhow::Result<Self::Answer2> {
         let (first, rest) = input
             .trim()
             .split_once('\n')
-            .ok_or(anyhow::format_err!("Missing value map label"))?;
+            .context("Missing value map label")?;
 
-        let seeds: Vec<Range<usize>> = first
+        let mut seeds = first
             .strip_prefix("seeds: ")
-            .ok_or(anyhow::format_err!("Failed to get seeds"))?
+            .context("Failed to get seeds")?
             .split_whitespace()
             .map(FromStr::from_str)
             .try_collect::<Vec<usize>>()?
             .into_iter()
             .array_chunks()
-            .map(|[n, len]| Range {
-                start: n,
-                end: n + len,
-            })
-            .collect();
-
-        let max = seeds
-            .iter()
-            .map(|r| r.end)
-            .max()
-            .ok_or(anyhow::format_err!("Failed to get max seed"))?;
+            .map(|[n, len]| n..(n + len))
+            .collect::<Vec<_>>();
 
-        let value_maps = rest
+        for set in rest
             .trim()
             .split("\n\n")
-            .map(parse_value_maps)
-            .try_collect::<Vec<_>>()?;
-
-        (0..=max)
-            .find(|location| {
-                let mut value = *location;
-                for value_map in value_maps.iter().rev() {
-                    if let Some(v) = value_map.iter().find_map(|v| v.r_map_value(value)) {
-                        value = v;
-                    }
-                }
-                seeds.iter().any(|s| s.contains(&value))
-            })
-            .ok_or(anyhow::format_err!("Failed to find min seed"))
-    }
-}
+            .map(FromStr::from_str)
+            .try_collect::<Vec<ValueMapSet>>()?
+        {
+            seeds = seeds
+                .into_iter()
+                .flat_map(|seed_range| set.transform(seed_range))
+                .collect();
+        }
 
-fn parse_value_maps(s: &str) -> anyhow::Result<Vec<ValueMap>> {
-    s.trim()
-        .lines()
-        .skip(1)
-        .map(FromStr::from_str)
-        .try_collect::<Vec<ValueMap>>()
+        seeds
+            .iter()
+            .map(|range| range.start)
+            .min()
+            .context("Failed to find min seed")
+    }
 }
 
-#[derive(Debug, PartialEq, Eq, Hash)]
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 struct ValueMap {
-    source: Range<usize>,
-    destination: Range<usize>,
-    offset: isize,
+    dest: usize,
+    src: usize,
+    length: usize,
 }
 
 impl ValueMap {
-    fn map_value(&self, value: usize) -> Option<usize> {
-        self.source
-            .contains(&value)
-            .then_some((value as isize + self.offset) as usize)
-    }
-
-    fn r_map_value(&self, value: usize) -> Option<usize> {
-        self.destination
-            .contains(&value)
-            .then_some((value as isize - self.offset) as usize)
+    fn intersect(&self, seed: &Range<usize>) -> Range<usize> {
+        seed.start.max(self.src)..seed.end.min(self.src + self.length)
     }
 }
 
@@ -127,19 +106,68 @@ impl FromStr for ValueMap {
     type Err = anyhow::Error;
 
     fn from_str(s: &str) -> Result<Self, Self::Err> {
-        let mut iter = s.trim().splitn(3, ' ').map(FromStr::from_str);
-
-        let (Some(Ok(destination_start)), Some(Ok(source_start)), Some(Ok(length))) =
-            (iter.next(), iter.next(), iter.next())
+        let Some([Ok(dest), Ok(src), Ok(length)]) = s
+            .split_whitespace()
+            .map(FromStr::from_str)
+            .array_chunks()
+            .next()
         else {
             anyhow::bail!("Invalid value map range");
         };
 
-        Ok(Self {
-            source: source_start..source_start + length,
-            destination: destination_start..destination_start + length,
-            offset: isize::try_from(destination_start)? - isize::try_from(source_start)?,
-        })
+        Ok(Self { dest, src, length })
+    }
+}
+
+struct ValueMapSet(Vec<ValueMap>);
+
+impl ValueMapSet {
+    fn transform(&self, seed_range: Range<usize>) -> Vec<Range<usize>> {
+        let mut queue = Vec::from([seed_range]);
+        let mut mapped = Vec::new();
+
+        while let Some(seed) = queue.pop() {
+            let Some(&map) = self.0.iter().find(|t| !t.intersect(&seed).is_empty()) else {
+                mapped.push(seed);
+                continue;
+            };
+
+            let intersect = map.intersect(&seed);
+
+            mapped.push(Range {
+                start: (intersect.start + map.dest) - map.src,
+                end: (intersect.end + map.dest) - map.src,
+            });
+
+            if seed.start < map.src {
+                queue.push(Range {
+                    start: seed.start,
+                    end: intersect.start - 1,
+                });
+            }
+
+            if seed.end > (map.src + map.length) {
+                queue.push(Range {
+                    start: intersect.end + 1,
+                    end: seed.end,
+                });
+            }
+        }
+
+        mapped.into_iter().collect()
+    }
+}
+
+impl FromStr for ValueMapSet {
+    type Err = anyhow::Error;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        s.trim()
+            .lines()
+            .skip(1)
+            .map(FromStr::from_str)
+            .try_collect::<Vec<ValueMap>>()
+            .map(Self)
     }
 }