year2024/
day05.rs

1use std::cmp::Ordering;
2use utils::prelude::*;
3
4/// Sorting lists using constraints.
5///
6/// The solution assumes that the rules form a total order for the elements in each sequence.
7#[derive(Clone, Debug)]
8pub struct Day05 {
9    before: Rules,
10    sorted: Vec<Vec<u32>>,
11    unsorted: Vec<Vec<u32>>,
12}
13
14const MIN_NUM: usize = 10;
15const MAX_NUM: usize = 99;
16const RANGE: usize = MAX_NUM - MIN_NUM + 1;
17type Rules = [[bool; RANGE]; RANGE];
18
19impl Day05 {
20    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
21        let num = parser::number_range(MIN_NUM as u32..=MAX_NUM as u32);
22        let rules_parser = num.then(num.with_prefix(b'|')).repeat(b'\n', 1);
23        let updates_parser = num.repeat(b',', 1).repeat(b'\n', 1);
24
25        let (rule_list, updates) = rules_parser
26            .then(updates_parser.with_prefix(b'\n'))
27            .parse_complete(input)?;
28
29        let mut before: Rules = [[false; RANGE]; RANGE];
30        for (a, b) in rule_list {
31            if before[a as usize - MIN_NUM][b as usize - MIN_NUM] {
32                return Err(InputError::new(input, 0, "duplicate rule"));
33            } else if before[b as usize - MIN_NUM][a as usize - MIN_NUM] {
34                return Err(InputError::new(input, 0, "contradictory pair of rules"));
35            }
36
37            before[a as usize - MIN_NUM][b as usize - MIN_NUM] = true;
38        }
39
40        let (sorted, unsorted) = updates.into_iter().partition(|update| {
41            update.is_sorted_by(|&a, &b| before[a as usize - MIN_NUM][b as usize - MIN_NUM])
42        });
43
44        Ok(Self {
45            before,
46            sorted,
47            unsorted,
48        })
49    }
50
51    #[must_use]
52    pub fn part1(&self) -> u32 {
53        self.sorted
54            .iter()
55            .map(|update| update[update.len() / 2])
56            .sum()
57    }
58
59    #[must_use]
60    pub fn part2(&self) -> u32 {
61        self.unsorted
62            .iter()
63            .cloned()
64            .map(|mut update| {
65                let index = update.len() / 2;
66                // Will panic if the provided rules are not a total order
67                let (_, middle, _) = update.select_nth_unstable_by(index, |&a, &b| {
68                    if a == b {
69                        Ordering::Equal
70                    } else if self.before[a as usize - MIN_NUM][b as usize - MIN_NUM] {
71                        Ordering::Less
72                    } else {
73                        Ordering::Greater
74                    }
75                });
76                *middle
77            })
78            .sum()
79    }
80}
81
82examples!(Day05 -> (u32, u32) [
83    {file: "day05_example0.txt", part1: 143, part2: 123},
84]);
year2024/day05.rs

year2024/
day05.rs
