1use std::cmp::Ordering;
2use utils::prelude::*;
3
4#[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 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]);