Day 5

2 files changed, 466 insertions, 9 deletions

diff --git a/2023/inputs/day_5.txt b/2023/inputs/day_5.txt
new file mode 100644
index 0000000..3a01983
--- /dev/null
+++ b/2023/inputs/day_5.txt
@@ -0,0 +1,219 @@
+seeds: 4106085912 135215567 529248892 159537194 1281459911 114322341 1857095529 814584370 2999858074 50388481 3362084117 37744902 3471634344 240133599 3737494864 346615684 1585884643 142273098 917169654 286257440
+
+seed-to-soil map:
+1640984363 3136305987 77225710
+3469528922 1857474741 56096642
+278465165 2901870617 105516220
+1442950910 1913571383 198033453
+463085535 1458252975 13696838
+1718210073 1686050230 171424511
+383981385 3064707638 71598349
+1267048154 3759577328 175902756
+3262934306 1479455614 206594616
+2493001016 200414015 157177749
+3885112776 411057950 157348766
+4042461542 1181162257 199039568
+476782373 2111604836 790265781
+455579734 1471949813 7505801
+1889634584 3213531697 546045631
+4241501110 357591764 53466186
+3525625564 3935480084 359487212
+2650178765 568406716 612755541
+200414015 1380201825 78051150
+2435680215 3007386837 57320801
+
+soil-to-fertilizer map:
+513693437 1166448955 406316429
+3977989337 1831898517 148449061
+2857616419 1749713256 55966993
+2245899978 767737007 398711948
+3462028551 3402487827 258322330
+1207747701 2246116788 274586148
+1857449833 2520702936 106524473
+950443356 290304833 224196260
+2913583412 1805680249 26218268
+290304833 3849361293 119346889
+3720350881 3244527156 157960671
+920009866 1634093064 30433490
+409651722 2627227409 104041715
+3916661657 1572765384 61327680
+1624788708 2115889182 130227606
+1963974306 3695907849 9066861
+1755016314 1980347578 102433519
+1973041167 3151152620 93374536
+1482333849 710468850 57268157
+2644611926 2899798022 213004493
+1539602006 1664526554 85186702
+2210802286 3660810157 35097692
+3135769437 3968708182 326259114
+1174639616 2082781097 33108085
+3878311552 3112802515 38350105
+2066415703 3704974710 144386583
+2939801680 514501093 195967757
+4126438398 2731269124 168528898
+
+fertilizer-to-water map:
+1274667249 2789153677 35498097
+1119124697 1423189114 4201717
+1775973674 127038866 409949870
+2636872711 677641697 238584014
+998550357 2708616519 80537158
+1613168083 3037802277 162805591
+1123326414 2618446916 90169603
+2516959328 2034731526 119913383
+3879305887 3993605604 147788774
+1213496017 2616229293 2217623
+3412445194 3202949622 62545934
+2875456725 2194682091 362593593
+1079087515 2154644909 40037182
+2468026227 3426058027 48933101
+0 1427390831 607340695
+2185923544 0 127038866
+1310165346 916225711 76820908
+2312962410 993046619 155063817
+607340695 1369464790 53724324
+1389328008 536988736 140652961
+1386986254 3200607868 2341754
+4241108893 3701026057 53858403
+661065019 2824651774 213150503
+1529980969 3342870913 83187114
+921175000 3265495556 77375357
+874215522 1148110436 46959478
+4180667579 3914761609 60441314
+3238050318 1195069914 174394876
+3701026057 3754884460 159877149
+4027094661 4141394378 153572918
+3860903206 3975202923 18402681
+1215713640 2557275684 58953609
+
+water-to-light map:
+3346671099 2139469351 253535694
+3600206793 4187771498 107195798
+1271601308 936374322 163567625
+3890528820 1799438963 144160054
+1731948725 3256631615 148580525
+3859991790 2573461247 250171
+389304550 1099941947 124474859
+2322259245 1445947039 39679535
+1544278612 1943599017 46211136
+1124738947 789511961 146862361
+3860946526 2109887057 29582294
+891137223 173339870 233601724
+3044858977 1485626574 301812122
+627354019 0 173339870
+800693889 1224416806 90443334
+4046689141 2034661517 75225540
+4166766045 4059570247 128201251
+0 1314860140 120308793
+4034688874 1787438696 12000267
+2294392242 2393005045 27867003
+2361938780 2573711418 682920197
+4121914681 1989810153 44851364
+1674653431 3705039670 14123300
+1445242474 3719162970 99036138
+513779409 406941594 113574610
+3707402591 2420872048 152589199
+2053021103 3818199108 241371139
+3860241961 1445242474 704565
+1880529250 3489375823 172491853
+1688776731 3661867676 43171994
+120308793 520516204 268995757
+1590489748 3405212140 84163683
+
+light-to-temperature map:
+1711282888 1572780528 87721767
+154126417 0 43277112
+950353983 1343526858 179094373
+2607445049 2714989532 110883165
+197403529 400138402 104876963
+302280492 43277112 202734873
+2990325458 1942480091 22763517
+2203652414 1550069916 22710612
+3347561974 4075093920 130901113
+1328424170 3514387681 17133869
+3187047160 4220120429 74846867
+3555672228 4205995033 676520
+555737175 2292503071 178861674
+936905107 4206671553 13448876
+2718328214 2825872697 25755942
+2042629442 945726244 118907923
+2161537365 3027858084 42115049
+1657501024 1888698227 53781864
+2943656210 3804007444 46669248
+2226363026 2004226072 108596129
+0 246011985 154126417
+734598849 2928837780 99020304
+833619153 1660502295 103285954
+2744084156 3436875901 77511780
+1299692440 2112822201 28731730
+2821595936 782812975 122060274
+1799004655 2471364745 95185072
+3082783503 1965243608 38982464
+2334959155 3531521550 272485894
+3121765967 2227221878 65281193
+1392230801 3850676692 224417228
+3013088975 528288490 69694528
+1616648029 904873249 40852995
+1345558039 3069973133 46672762
+3681258726 1064634167 278892691
+1894189727 2566549817 148439715
+1129448356 597983018 170244084
+3261894027 2141553931 85667947
+3478463087 2851628639 77209141
+3556348748 1763788249 124909978
+4280381423 768227102 14585873
+528288490 1522621231 27448685
+3960151417 3116645895 320230006
+
+temperature-to-humidity map:
+2401309547 2063893326 5931150
+4081820678 1536756293 195703517
+3389837279 4114880485 97950323
+67647704 537880870 95615044
+3487787602 2069824476 16209316
+212366581 0 210367924
+0 470233166 67647704
+163262748 331958016 49103833
+3921228390 3754997923 26024946
+1883070873 986328296 29590327
+1844673227 4256569650 38397646
+422734505 381061849 89171317
+3835004067 4212830808 43738842
+1753523088 1732459810 63479835
+4277524195 3781022869 17443101
+926010074 3798465970 316414515
+511905822 210367924 31838014
+3565158997 3485152853 269845070
+3878742909 776643827 42485481
+3352296690 1795939645 37540589
+2877358153 2512426556 474938537
+1419995251 1068661114 304321846
+1348461498 705110074 71533753
+1724317097 1372982960 29205991
+1974916783 2086033792 426392764
+2407240697 3015035397 470117456
+1242424589 880291387 106036909
+642854491 1833480234 230413092
+3503996918 819129308 61162079
+543743836 242205938 89752078
+873267583 1015918623 52742491
+1817002923 2987365093 27670304
+1912661200 642854491 62255583
+3947253336 1402188951 134567342
+
+humidity-to-location map:
+2955816171 2260659770 927037009
+1906648752 2188942242 71717528
+848878920 35928575 8026852
+4100692468 1994667414 194274828
+2066384942 3405536067 889431229
+559945395 1052613350 288933525
+3882853180 3187696779 217839288
+856905772 1341546875 164300625
+0 528596530 524016820
+1978366280 1723924810 88018662
+1044385850 67134880 400987760
+524016820 0 35928575
+1021206397 43955427 23179453
+1445373610 468122640 60473890
+1723924810 1811943472 182723942
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]
+        }
     }
 }