From e0033c52a4f7d8f86da915155a65d87a6d273c9f Mon Sep 17 00:00:00 2001 From: Toby Vincent Date: Sat, 9 Dec 2023 18:59:08 -0600 Subject: perf: refactor day 5 part 2 --- src/day_05.rs | 182 +++++++++++++++++++++++++++++++++------------------------- 1 file changed, 105 insertions(+), 77 deletions(-) (limited to 'src/day_05.rs') 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::>()?; + .try_collect::>()? + .into_iter() + .map(|n| n..(n + 1)) + .collect::>(); - let value_maps = rest + for set in rest .trim() .split("\n\n") - .map(parse_value_maps) - .try_collect::>()?; - - 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::>()? + { + 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 { 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> = 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::>()? .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::>(); - let value_maps = rest + for set in rest .trim() .split("\n\n") - .map(parse_value_maps) - .try_collect::>()?; - - (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::>()? + { + seeds = seeds + .into_iter() + .flat_map(|seed_range| set.transform(seed_range)) + .collect(); + } -fn parse_value_maps(s: &str) -> anyhow::Result> { - s.trim() - .lines() - .skip(1) - .map(FromStr::from_str) - .try_collect::>() + 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, - destination: Range, - offset: isize, + dest: usize, + src: usize, + length: usize, } impl ValueMap { - fn map_value(&self, value: usize) -> Option { - self.source - .contains(&value) - .then_some((value as isize + self.offset) as usize) - } - - fn r_map_value(&self, value: usize) -> Option { - self.destination - .contains(&value) - .then_some((value as isize - self.offset) as usize) + fn intersect(&self, seed: &Range) -> Range { + 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 { - 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); + +impl ValueMapSet { + fn transform(&self, seed_range: Range) -> Vec> { + 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 { + s.trim() + .lines() + .skip(1) + .map(FromStr::from_str) + .try_collect::>() + .map(Self) } } -- cgit v1.2.3-70-g09d2