Skip to main content

aoc/year2024/
day05.rs

1//! # Print Queue
2//!
3//! The input is constructed so that each possible pair that occurs in a row has a defined
4//! ordering that enables sorting with a custom `Ordering` definition. Numbers are always
5//! 2 digits so storing ordering in a fixed-size 100 × 100 array is faster than using a `HashMap`.
6use std::cmp::Ordering::*;
7
8use crate::util::iter::*;
9use crate::util::parse::*;
10
11type Input = (usize, usize);
12
13pub fn parse(input: &str) -> Input {
14    let (prefix, suffix) = input.split_once("\n\n").unwrap();
15    let mut order = [[Greater; 100]; 100];
16
17    for [from, to] in prefix.iter_unsigned::<usize>().chunk::<2>() {
18        order[from][to] = Less;
19    }
20
21    let mut update = Vec::new();
22
23    suffix.lines().fold((0, 0), |(part_one, part_two), line| {
24        update.clear();
25        update.extend(line.iter_unsigned::<usize>());
26        let middle = update.len() / 2;
27
28        if update.is_sorted_by(|&from, &to| order[from][to] == Less) {
29            (part_one + update[middle], part_two)
30        } else {
31            // We only need the middle index so this is slightly faster than "sort_unstable_by"
32            update.select_nth_unstable_by(middle, |&from, &to| order[from][to]);
33            (part_one, part_two + update[middle])
34        }
35    })
36}
37
38pub fn part1(input: &Input) -> usize {
39    input.0
40}
41
42pub fn part2(input: &Input) -> usize {
43    input.1
44}