aoc/year2023/
day05.rs

1//! # If You Give A Seed A Fertilizer
2use crate::util::iter::*;
3use crate::util::parse::*;
4
5pub struct Input {
6    seeds: Vec<u64>,
7    stages: Vec<Vec<[u64; 3]>>,
8}
9
10pub fn parse(input: &str) -> Input {
11    let mut chunks = input.split("\n\n");
12    let seeds = chunks.next().unwrap().iter_unsigned().collect();
13    let stages = chunks
14        .map(|chunk| {
15            // Convert from start and length to start and end.
16            chunk
17                .iter_unsigned()
18                .chunk::<3>()
19                .map(|[dest, start, length]| [dest, start, start + length])
20                .collect()
21        })
22        .collect();
23
24    Input { seeds, stages }
25}
26
27/// Process each seed individually.
28pub fn part1(input: &Input) -> u64 {
29    let mut seeds = input.seeds.clone();
30
31    for stage in &input.stages {
32        for seed in &mut seeds {
33            if let Some(&[dest, start, _]) =
34                stage.iter().find(|&&[_, start, end]| start <= *seed && *seed < end)
35            {
36                *seed = *seed - start + dest;
37            }
38        }
39    }
40
41    seeds.into_iter().min().unwrap()
42}
43
44/// Process ranges.
45pub fn part2(input: &Input) -> u64 {
46    let mut current = Vec::new();
47    let mut next = Vec::new();
48    let mut next_stage = Vec::new();
49
50    // Convert input pairs to ranges.
51    for [start, length] in input.seeds.iter().copied().chunk::<2>() {
52        current.push([start, start + length]);
53    }
54
55    for stage in &input.stages {
56        for &[dest, s2, e2] in stage {
57            for [s1, e1] in current.drain(..) {
58                // Split ranges that overlap into 1, 2 or 3 new ranges.
59                // x1 and x2 are the possible overlap.
60                let x1 = s1.max(s2);
61                let x2 = e1.min(e2);
62
63                if x1 >= x2 {
64                    // No overlap.
65                    next.push([s1, e1]);
66                } else {
67                    // Move overlap to new destination. Only compare with next range.
68                    next_stage.push([x1 - s2 + dest, x2 - s2 + dest]);
69
70                    // Check remnants with remaining ranges.
71                    if s1 < x1 {
72                        next.push([s1, x1]);
73                    }
74                    if x2 < e1 {
75                        next.push([x2, e1]);
76                    }
77                }
78            }
79
80            (current, next) = (next, current);
81        }
82
83        // Combine elements for the next stage.
84        current.append(&mut next_stage);
85    }
86
87    current.iter().map(|r| r[0]).min().unwrap()
88}
aoc/year2023/day05.rs

aoc/year2023/
day05.rs
