diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/day_05.rs | 195 | ||||
| -rw-r--r-- | src/lib.rs | 2 | ||||
| -rw-r--r-- | src/main.rs | 3 |
3 files changed, 199 insertions, 1 deletions
diff --git a/src/day_05.rs b/src/day_05.rs new file mode 100644 index 0000000..e9d0b92 --- /dev/null +++ b/src/day_05.rs @@ -0,0 +1,195 @@ +use std::{ops::Range, str::FromStr}; + +use crate::{Problem, Solution}; + +pub struct Day05; + +impl Problem for Day05 { + const DAY: u8 = 5; + + const INPUT: &'static str = include_str!("../input/day_05.txt"); +} + +impl Solution for Day05 { + type Answer1 = usize; + + type Answer2 = usize; + + fn part_1(input: &str) -> anyhow::Result<Self::Answer1> { + let (first, rest) = input + .trim() + .split_once('\n') + .ok_or(anyhow::format_err!("Missing value map label"))?; + + let mut values = first + .strip_prefix("seeds: ") + .ok_or(anyhow::format_err!("Failed to get seeds"))? + .split_whitespace() + .map(FromStr::from_str) + .try_collect::<Vec<usize>>()?; + + let value_maps = 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 + } + }) + } + + values + .into_iter() + .min() + .ok_or(anyhow::format_err!("No values found")) + } + + 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"))?; + + let seeds: Vec<Range<usize>> = first + .strip_prefix("seeds: ") + .ok_or(anyhow::format_err!("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"))?; + + let value_maps = 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")) + } +} + +fn parse_value_maps(s: &str) -> anyhow::Result<Vec<ValueMap>> { + s.trim() + .lines() + .skip(1) + .map(FromStr::from_str) + .try_collect::<Vec<ValueMap>>() +} + +#[derive(Debug, PartialEq, Eq, Hash)] +struct ValueMap { + source: Range<usize>, + destination: Range<usize>, + offset: isize, +} + +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) + } +} + +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()) + 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)?, + }) + } +} + +#[cfg(test)] +mod tests { + use super::*; + + const INPUT: &str = indoc::indoc! {" + seeds: 79 14 55 13 + + seed-to-soil map: + 50 98 2 + 52 50 48 + + soil-to-fertilizer map: + 0 15 37 + 37 52 2 + 39 0 15 + + fertilizer-to-water map: + 49 53 8 + 0 11 42 + 42 0 7 + 57 7 4 + + water-to-light map: + 88 18 7 + 18 25 70 + + light-to-temperature map: + 45 77 23 + 81 45 19 + 68 64 13 + + temperature-to-humidity map: + 0 69 1 + 1 0 69 + + humidity-to-location map: + 60 56 37 + 56 93 4 + "}; + + #[test] + fn test_part_1() -> anyhow::Result<()> { + Ok(assert_eq!(35, Day05::part_1(INPUT)?)) + } + + #[test] + fn test_part_2() -> anyhow::Result<()> { + Ok(assert_eq!(46, Day05::part_2(INPUT)?)) + } +} @@ -1,9 +1,11 @@ #![feature(iterator_try_collect)] +#![feature(iter_array_chunks)] pub mod day_01; pub mod day_02; pub mod day_03; pub mod day_04; +pub mod day_05; pub trait Problem { const DAY: u8; diff --git a/src/main.rs b/src/main.rs index 3f47fac..feae755 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,10 +1,11 @@ -use aoc_2023::{day_01::Day01, day_02::Day02, day_03::Day03, day_04::Day04, Solution}; +use aoc_2023::{day_01::Day01, day_02::Day02, day_03::Day03, day_04::Day04, Solution, day_05::Day05}; fn main() -> anyhow::Result<()> { Day01::solve()?; Day02::solve()?; Day03::solve()?; Day04::solve()?; + Day05::solve()?; Ok(()) } |