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

aoc/year2023/
day05.rs
