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    input
30        .seeds
31        .iter()
32        .map(|&seed| {
33            input.stages.iter().fold(seed, |seed, stage| {
34                stage
35                    .iter()
36                    .find(|&&[_, start, end]| (start..end).contains(&seed))
37                    .map_or(seed, |&[dest, start, _]| seed - start + dest)
38            })
39        })
40        .min()
41        .unwrap()
42}
43
44/// Process ranges.
45pub fn part2(input: &Input) -> u64 {
46    // Convert input pairs to ranges.
47    let mut current: Vec<_> =
48        input.seeds.chunks_exact(2).map(|pair| [pair[0], pair[0] + pair[1]]).collect();
49    let mut next = Vec::new();
50    let mut next_stage = Vec::new();
51
52    for stage in &input.stages {
53        for &[dest, s2, e2] in stage {
54            for [s1, e1] in current.drain(..) {
55                // Split ranges that overlap into 1, 2 or 3 new ranges.
56                // x1 and x2 are the possible overlap.
57                let x1 = s1.max(s2);
58                let x2 = e1.min(e2);
59
60                if x1 >= x2 {
61                    // No overlap.
62                    next.push([s1, e1]);
63                } else {
64                    // Move overlap to new destination. Only compare with next range.
65                    next_stage.push([x1 - s2 + dest, x2 - s2 + dest]);
66
67                    // Check remnants with remaining ranges.
68                    if s1 < x1 {
69                        next.push([s1, x1]);
70                    }
71                    if x2 < e1 {
72                        next.push([x2, e1]);
73                    }
74                }
75            }
76
77            (current, next) = (next, current);
78        }
79
80        // Combine elements for the next stage.
81        current.append(&mut next_stage);
82    }
83
84    current.iter().map(|r| r[0]).min().unwrap()
85}
aoc/year2023/day05.rs

aoc/year2023/
day05.rs
