diff options
-rw-r--r-- | answers.txt | 54 | ||||
-rw-r--r-- | src/day_05.rs | 182 |
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) } } |