From bb77ed16fd632551adeebb7b5463aac99ce59726 Mon Sep 17 00:00:00 2001 From: Greg Burri Date: Thu, 5 Dec 2024 16:09:17 +0100 Subject: [PATCH] Day 05 --- src/day02.rs | 9 ++-- src/day05.rs | 149 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/days.rs | 10 ++++ src/main.rs | 5 +- src/utils.rs | 9 ++++ 5 files changed, 174 insertions(+), 8 deletions(-) create mode 100644 src/day05.rs create mode 100644 src/utils.rs diff --git a/src/day02.rs b/src/day02.rs index 1b88e99..60c558b 100644 --- a/src/day02.rs +++ b/src/day02.rs @@ -2,6 +2,8 @@ use std::io::BufRead; use itertools::{self, Itertools}; +use crate::utils; + type Reports = Vec>; pub fn read_reports(reader: R) -> Reports @@ -10,12 +12,7 @@ where { let mut reports = Vec::>::new(); for l in reader.lines() { - reports.push( - l.unwrap() - .split(' ') - .map(|level| level.parse::().unwrap()) - .collect(), - ); + reports.push(utils::split_to_vec(&l.unwrap(), " ")); } reports } diff --git a/src/day05.rs b/src/day05.rs new file mode 100644 index 0000000..983ceff --- /dev/null +++ b/src/day05.rs @@ -0,0 +1,149 @@ +use std::{io::BufRead, mem::swap}; + +use itertools::{self, Itertools}; + +use crate::utils; + +#[derive(Debug)] +pub struct PageOrdering { + ordering: [Vec; 100], +} + +impl PageOrdering { + pub fn new() -> PageOrdering { + PageOrdering { + ordering: [const { vec![] }; 100], + } + } + + pub fn add_page_order(&mut self, p1: i32, p2: i32) { + let following_page = self.ordering.get_mut(p1 as usize).unwrap(); + if !following_page.contains(&p2) { + following_page.push(p2); + } + } + + pub fn get_followin_page(&self, p: i32) -> &[i32] { + &self.ordering[p as usize] + } +} + +type Updates = Vec>; + +pub fn read_ordering_and_updates(reader: R) -> (PageOrdering, Updates) +where + R: BufRead, +{ + let lines = reader.lines().map(Result::unwrap).collect::>(); + let mut lines_iter = lines.iter(); + + let mut page_ordering = PageOrdering::new(); + while let Some(l) = lines_iter.next() { + if l.is_empty() { + break; + } + let pages = utils::split_to_vec(&l, "|"); + page_ordering.add_page_order(pages[0], pages[1]); + } + + let mut updates: Vec> = vec![]; + while let Some(l) = lines_iter.next() { + updates.push(utils::split_to_vec(&l, ",")); + } + + (page_ordering, updates) +} + +pub fn sum_of_mid_page_from_valid_updates(page_ordering: &PageOrdering, updates: &Updates) -> i32 { + let mut sum = 0; + 'next_update: for update in updates { + for (p1, p2) in update.iter().tuple_windows() { + if !page_ordering.get_followin_page(*p1).contains(p2) { + continue 'next_update; + } + } + sum += update[update.len() / 2]; + } + + sum +} + +pub fn sum_of_mid_page_from_corrected_updates( + page_ordering: &PageOrdering, + updates: &Updates, +) -> i32 { + let mut sum = 0; + for update in updates { + let l = update.len(); + let mut updates_corrected = update.clone(); + let mut modified = false; + let mut i = 0; + while i < l - 1 { + if !page_ordering + .get_followin_page(updates_corrected[i]) + .contains(&updates_corrected[i + 1]) + { + updates_corrected.swap(i, i + 1); + modified = true; + if i > 0 { + i -= 1; + } + } else { + i += 1; + } + } + if modified { + sum += updates_corrected[update.len() / 2]; + } + } + + sum +} + +#[cfg(test)] +mod tests { + use super::*; + + static PAGE_ORDERING_AND_UPDATES: &str = "47|53 +97|13 +97|61 +97|47 +75|29 +61|13 +75|53 +29|13 +97|29 +53|29 +61|53 +97|53 +61|29 +47|13 +75|47 +97|75 +47|61 +75|61 +47|29 +75|13 +53|13 + +75,47,61,53,29 +97,61,53,29,13 +75,29,13 +75,97,47,61,53 +61,13,29 +97,13,75,29,47"; + + #[test] + fn test_part1() { + let (ordering, updates) = read_ordering_and_updates(PAGE_ORDERING_AND_UPDATES.as_bytes()); + let s = sum_of_mid_page_from_valid_updates(&ordering, &updates); + assert_eq!(s, 143); + } + + #[test] + fn test_part2() { + let (ordering, updates) = read_ordering_and_updates(PAGE_ORDERING_AND_UPDATES.as_bytes()); + let s = sum_of_mid_page_from_corrected_updates(&ordering, &updates); + assert_eq!(s, 123); + } +} diff --git a/src/days.rs b/src/days.rs index 5450666..2bc4038 100644 --- a/src/days.rs +++ b/src/days.rs @@ -41,3 +41,13 @@ pub fn day04() -> String { day04::nb_of_mas_cross(&word_search) ) } + +pub fn day05() -> String { + let f = fs::File::open("data/day05.input").unwrap(); + let (ordering, updates) = day05::read_ordering_and_updates(BufReader::new(f)); + format!( + "part1: {}, part2: {}", + day05::sum_of_mid_page_from_valid_updates(&ordering, &updates), + day05::sum_of_mid_page_from_corrected_updates(&ordering, &updates) + ) +} diff --git a/src/main.rs b/src/main.rs index f51a684..c15ed2e 100644 --- a/src/main.rs +++ b/src/main.rs @@ -7,7 +7,7 @@ mod day01; mod day02; mod day03; mod day04; -// mod day05; +mod day05; // mod day06; // mod day07; // mod day08; @@ -28,6 +28,7 @@ mod day04; // mod day23; // mod day24; mod days; +mod utils; #[derive(Parser, Debug)] #[command(author = "Greg Burri", version = "1.0", about = "Advent of Code 2024")] @@ -47,7 +48,7 @@ fn main() { days::day02, days::day03, days::day04, - // days::day05, + days::day05, // days::day06, // days::day07, // days::day08, diff --git a/src/utils.rs b/src/utils.rs new file mode 100644 index 0000000..135bd36 --- /dev/null +++ b/src/utils.rs @@ -0,0 +1,9 @@ +use std::{fmt::Debug, str::FromStr}; + +pub fn split_to_vec(str: &str, pat: &str) -> Vec +where + T: FromStr, + ::Err: Debug, +{ + str.split(pat).map(|v| v.parse::().unwrap()).collect() +} -- 2.45.2