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(parser::eol(), 1);
23        let updates_parser = num.repeat(b',', 1).repeat(parser::eol(), 1);
24
25        let (rule_list, updates) = rules_parser
26            .with_eol()
27            .with_eol()
28            .then(updates_parser)
29            .parse_complete(input)?;
30
31        let mut before: Rules = [[false; RANGE]; RANGE];
32        for (a, b) in rule_list {
33            if before[a as usize - MIN_NUM][b as usize - MIN_NUM] {
34                return Err(InputError::new(input, 0, "duplicate rule"));
35            } else if before[b as usize - MIN_NUM][a as usize - MIN_NUM] {
36                return Err(InputError::new(input, 0, "contradictory pair of rules"));
37            }
38
39            before[a as usize - MIN_NUM][b as usize - MIN_NUM] = true;
40        }
41
42        let (sorted, unsorted) = updates.into_iter().partition(|update| {
43            update.is_sorted_by(|&a, &b| before[a as usize - MIN_NUM][b as usize - MIN_NUM])
44        });
45
46        Ok(Self {
47            before,
48            sorted,
49            unsorted,
50        })
51    }
52
53    #[must_use]
54    pub fn part1(&self) -> u32 {
55        self.sorted
56            .iter()
57            .map(|update| update[update.len() / 2])
58            .sum()
59    }
60
61    #[must_use]
62    pub fn part2(&self) -> u32 {
63        self.unsorted
64            .iter()
65            .cloned()
66            .map(|mut update| {
67                let index = update.len() / 2;
68                // Will panic if the provided rules are not a total order
69                let (_, middle, _) = update.select_nth_unstable_by(index, |&a, &b| {
70                    if a == b {
71                        Ordering::Equal
72                    } else if self.before[a as usize - MIN_NUM][b as usize - MIN_NUM] {
73                        Ordering::Less
74                    } else {
75                        Ordering::Greater
76                    }
77                });
78                *middle
79            })
80            .sum()
81    }
82}
83
84examples!(Day05 -> (u32, u32) [
85    {file: "day05_example0.txt", part1: 143, part2: 123},
86]);
year2024/day05.rs

year2024/
day05.rs
