From 487eafd13f5d69fd29cdb9be35bfc399d93e52f3 Mon Sep 17 00:00:00 2001
From: Justin Wernick <justin@worthe-it.co.za>
Date: Tue, 5 Dec 2023 10:22:27 +0200
Subject: Day 5

---
 2023/src/bin/day_5.rs | 256 ++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 247 insertions(+), 9 deletions(-)

(limited to '2023/src')

diff --git a/2023/src/bin/day_5.rs b/2023/src/bin/day_5.rs
index b3a610b..2243bf8 100644
--- a/2023/src/bin/day_5.rs
+++ b/2023/src/bin/day_5.rs
@@ -1,19 +1,257 @@
-use nom::IResult;
+use nom::{
+    bytes::complete::tag,
+    character::complete::{line_ending, not_line_ending, space1, u64 as nom_u64},
+    combinator::map,
+    multi::separated_list1,
+    sequence::{pair, tuple},
+    IResult,
+};
 use std::fs;
 
 fn main() -> Result<(), Box<dyn std::error::Error>> {
-    let input = fs::read_to_string("inputs/day_2.txt")?;
-    let parsed = Example::parser(&input).unwrap().1;
-    dbg!(&parsed);
-
+    let input = fs::read_to_string("inputs/day_5.txt")?;
+    let parsed = Almanac::parser(&input).unwrap().1;
+    dbg!(&parsed.min_location());
+    dbg!(&parsed.range_min_location());
     Ok(())
 }
 
 #[derive(Debug)]
-struct Example;
+struct Almanac {
+    seeds: Vec<u64>,
+    seed_ranges: Vec<Range>,
+    mappings: Vec<AlmanacMapping>,
+}
+
+#[derive(Debug)]
+struct AlmanacMapping {
+    _heading: String,
+    maps: Vec<Mapping>,
+}
+
+#[derive(Debug)]
+struct Mapping {
+    source_start: u64,
+    dest_start: u64,
+    len: u64,
+}
+
+#[derive(Debug, Clone, Copy)]
+struct Range {
+    start: u64,
+    len: u64,
+}
+
+impl Almanac {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(
+            tuple((
+                tag("seeds: "),
+                separated_list1(space1, nom_u64),
+                pair(line_ending, line_ending),
+                separated_list1(pair(line_ending, line_ending), AlmanacMapping::parser),
+            )),
+            |(_, seeds, _, mappings)| {
+                let seed_ranges = seeds
+                    .chunks(2)
+                    .map(|chunk| Range {
+                        start: chunk[0],
+                        len: chunk[1],
+                    })
+                    .collect();
+                Almanac {
+                    seeds,
+                    seed_ranges,
+                    mappings,
+                }
+            },
+        )(input)
+    }
+
+    fn locations(&self) -> Vec<u64> {
+        self.mappings
+            .iter()
+            .fold(self.seeds.clone(), |acc, mapping| {
+                acc.into_iter().map(|seed| mapping.convert(seed)).collect()
+            })
+    }
+
+    fn min_location(&self) -> u64 {
+        self.locations().into_iter().min().unwrap()
+    }
+
+    fn range_locations(&self) -> Vec<Range> {
+        self.mappings
+            .iter()
+            .fold(self.seed_ranges.clone(), |acc, mapping| {
+                dbg!(&acc);
+                acc.into_iter()
+                    .flat_map(|seed_range| mapping.convert_range(seed_range))
+                    .collect()
+            })
+    }
+
+    fn range_min_location(&self) -> u64 {
+        self.range_locations()
+            .into_iter()
+            .map(|r| r.start)
+            .min()
+            .unwrap()
+    }
+}
+
+impl AlmanacMapping {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(
+            tuple((
+                not_line_ending,
+                line_ending,
+                separated_list1(line_ending, Mapping::parser),
+            )),
+            |(heading, _, maps)| AlmanacMapping {
+                _heading: heading.to_owned(),
+                maps,
+            },
+        )(input)
+    }
+
+    fn convert(&self, source: u64) -> u64 {
+        self.maps
+            .iter()
+            .filter_map(|mapping| mapping.convert(source))
+            .next()
+            .unwrap_or(source)
+    }
+
+    fn convert_range(&self, source: Range) -> Vec<Range> {
+        let converted_ranges: Vec<(Range, Range)> = self
+            .maps
+            .iter()
+            .filter_map(|mapping| mapping.convert_range(source))
+            .collect();
+
+        let mut result = Vec::new();
+        let mut uncovered_ranges = vec![source];
+        for (covered_source, dest) in converted_ranges {
+            result.push(dest);
+
+            uncovered_ranges = uncovered_ranges
+                .into_iter()
+                .flat_map(|r| r.difference(covered_source))
+                .collect();
+        }
+
+        result.append(&mut uncovered_ranges);
+
+        result
+    }
+}
+
+impl Mapping {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(
+            tuple((nom_u64, space1, nom_u64, space1, nom_u64)),
+            |(dest_start, _, source_start, _, len)| Mapping {
+                source_start,
+                dest_start,
+                len,
+            },
+        )(input)
+    }
+
+    fn source_range(&self) -> Range {
+        Range {
+            start: self.source_start,
+            len: self.len,
+        }
+    }
+
+    fn convert(&self, source: u64) -> Option<u64> {
+        if source >= self.source_start && source < self.source_start + self.len {
+            Some(source - self.source_start + self.dest_start)
+        } else {
+            None
+        }
+    }
+
+    fn convert_range(&self, source: Range) -> Option<(Range, Range)> {
+        if let Some(source_intersection) = source.intersection(self.source_range()) {
+            Some((
+                source_intersection,
+                Range {
+                    start: source_intersection.start - self.source_start + self.dest_start,
+                    len: source_intersection.len,
+                },
+            ))
+        } else {
+            None
+        }
+    }
+}
+
+impl Range {
+    fn end(&self) -> u64 {
+        self.start + self.len
+    }
+
+    fn intersection(self, other: Range) -> Option<Range> {
+        if self.start < other.start {
+            if self.end() <= other.start {
+                None
+            } else if self.end() < other.end() {
+                Some(Range {
+                    start: other.start,
+                    len: self.end() - other.start,
+                })
+            } else {
+                Some(other)
+            }
+        } else if self.start < other.end() {
+            if self.end() < other.end() {
+                Some(self)
+            } else {
+                Some(Range {
+                    start: self.start,
+                    len: other.end() - self.start,
+                })
+            }
+        } else {
+            None
+        }
+    }
 
-impl Example {
-    fn parser(_input: &str) -> IResult<&str, Self> {
-        todo!()
+    fn difference(self, other: Range) -> Vec<Range> {
+        if self.start < other.start {
+            if self.end() <= other.start {
+                vec![self]
+            } else if self.end() <= other.end() {
+                vec![Range {
+                    start: self.start,
+                    len: other.start - self.start,
+                }]
+            } else {
+                vec![
+                    Range {
+                        start: self.start,
+                        len: other.start - self.start,
+                    },
+                    Range {
+                        start: other.end(),
+                        len: self.end() - other.end(),
+                    },
+                ]
+            }
+        } else if self.start < other.end() {
+            if self.end() <= other.end() {
+                vec![]
+            } else {
+                vec![Range {
+                    start: other.end(),
+                    len: self.end() - other.end(),
+                }]
+            }
+        } else {
+            vec![self]
+        }
     }
 }
-- 
cgit v1.2.3