diff options
Diffstat (limited to '2023/src/bin/day_5.rs')
| -rw-r--r-- | 2023/src/bin/day_5.rs | 257 |
1 files changed, 257 insertions, 0 deletions
diff --git a/2023/src/bin/day_5.rs b/2023/src/bin/day_5.rs new file mode 100644 index 0000000..2243bf8 --- /dev/null +++ b/2023/src/bin/day_5.rs @@ -0,0 +1,257 @@ +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_5.txt")?; + let parsed = Almanac::parser(&input).unwrap().1; + dbg!(&parsed.min_location()); + dbg!(&parsed.range_min_location()); + Ok(()) +} + +#[derive(Debug)] +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 + } + } + + 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] + } + } +} |