From b03bb4f76a03832787bedd7b417cfc0da8ee4b48 Mon Sep 17 00:00:00 2001 From: Greg Burri Date: Mon, 9 Dec 2024 12:26:29 +0100 Subject: [PATCH] Day[09] + fix some little type issues in tests. --- Cargo.toml | 2 +- src/day01.rs | 4 +-- src/day02.rs | 8 +++--- src/day04.rs | 4 +-- src/day05.rs | 6 +++-- src/day06.rs | 14 +++++----- src/day07.rs | 4 +-- src/day08.rs | 4 +-- src/day09.rs | 73 +++++++++++++++++++++++++++++++++++++++++++++++++--- src/days.rs | 3 ++- 10 files changed, 96 insertions(+), 26 deletions(-) diff --git a/Cargo.toml b/Cargo.toml index 97ed99c..ef12e56 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -7,7 +7,7 @@ edition = "2021" # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html [dependencies] -itertools = "0.10" +itertools = "0.13" regex = "1" clap = { version = "4", features = ["derive"] } rayon = "1.10" diff --git a/src/day01.rs b/src/day01.rs index 6c624ca..dcc1522 100644 --- a/src/day01.rs +++ b/src/day01.rs @@ -65,13 +65,13 @@ mod tests { #[test] fn part1() { - let (ids1, ids2) = read_location_ids_as_sorted(IDS.as_bytes()); + let (ids1, ids2) = read_location_ids_as_sorted(&mut IDS.as_bytes()); assert_eq!(sum_distances(&ids1, &ids2), 11); } #[test] fn part2() { - let (ids1, ids2) = read_location_ids_as_sorted(IDS.as_bytes()); + let (ids1, ids2) = read_location_ids_as_sorted(&mut IDS.as_bytes()); assert_eq!(similarity_score(&ids1, &ids2), 31); } } diff --git a/src/day02.rs b/src/day02.rs index d6a5231..25ef44c 100644 --- a/src/day02.rs +++ b/src/day02.rs @@ -93,13 +93,13 @@ mod tests { #[test] fn part1() { - let reports = read_reports(REPORTS.as_bytes()); + let reports = read_reports(&mut REPORTS.as_bytes()); assert_eq!(nb_of_safe_reports(&reports), 2); } #[test] fn part2() { - let reports = read_reports(REPORTS.as_bytes()); + let reports = read_reports(&mut REPORTS.as_bytes()); assert_eq!(nb_of_safe_reports_with_tolerance(&reports), 4); } @@ -116,13 +116,13 @@ mod tests { #[test] fn part2_additional_valid_reports() { - let reports = read_reports(VALID_REPORTS.as_bytes()); + let reports = read_reports(&mut VALID_REPORTS.as_bytes()); assert_eq!(nb_of_safe_reports_with_tolerance(&reports), 4); } #[test] fn part2_additional_invalid_reports() { - let reports = read_reports(INVALID_REPORTS.as_bytes()); + let reports = read_reports(&mut INVALID_REPORTS.as_bytes()); assert_eq!(nb_of_safe_reports_with_tolerance(&reports), 0); } } diff --git a/src/day04.rs b/src/day04.rs index 6184148..a92e9ac 100644 --- a/src/day04.rs +++ b/src/day04.rs @@ -115,14 +115,14 @@ MXMXAXMASX"; #[test] fn test_part1() { - let word_search = read_word_search(WORD_SEARCH.as_bytes()); + let word_search = read_word_search(&mut WORD_SEARCH.as_bytes()); let n = nb_of_word_occurences(&word_search, "XMAS"); assert_eq!(n, 18); } #[test] fn test_part2() { - let word_search = read_word_search(WORD_SEARCH.as_bytes()); + let word_search = read_word_search(&mut WORD_SEARCH.as_bytes()); let n = nb_of_mas_cross(&word_search); assert_eq!(n, 9); } diff --git a/src/day05.rs b/src/day05.rs index c3a267b..10d0915 100644 --- a/src/day05.rs +++ b/src/day05.rs @@ -132,14 +132,16 @@ mod tests { #[test] fn test_part1() { - let (ordering, updates) = read_ordering_and_updates(PAGE_ORDERING_AND_UPDATES.as_bytes()); + let (ordering, updates) = + read_ordering_and_updates(&mut 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 (ordering, updates) = + read_ordering_and_updates(&mut 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/day06.rs b/src/day06.rs index df5d3e7..f027095 100644 --- a/src/day06.rs +++ b/src/day06.rs @@ -150,14 +150,14 @@ mod tests { #[test] fn test_part1() { - let (map, guard_pos) = read_map(MAP.as_bytes()); + let (map, guard_pos) = read_map(&mut MAP.as_bytes()); let n = nb_position_visited_by_guard(&map, guard_pos); assert_eq!(n, 41); } #[test] fn test_part2() { - let (map, guard_pos) = read_map(MAP.as_bytes()); + let (map, guard_pos) = read_map(&mut MAP.as_bytes()); let n = nb_possible_obstruction_position(&map, guard_pos); assert_eq!(n, 6); } @@ -189,19 +189,19 @@ mod tests { #[test] fn test_part2_tiny_maps() { - let (map, guard_pos) = read_map(MAP2.as_bytes()); + let (map, guard_pos) = read_map(&mut MAP2.as_bytes()); assert_eq!(nb_possible_obstruction_position(&map, guard_pos), 1); - let (map, guard_pos) = read_map(MAP3.as_bytes()); + let (map, guard_pos) = read_map(&mut MAP3.as_bytes()); assert_eq!(nb_possible_obstruction_position(&map, guard_pos), 1); - let (map, guard_pos) = read_map(MAP4.as_bytes()); + let (map, guard_pos) = read_map(&mut MAP4.as_bytes()); assert_eq!(nb_possible_obstruction_position(&map, guard_pos), 1); - let (map, guard_pos) = read_map(MAP5.as_bytes()); + let (map, guard_pos) = read_map(&mut MAP5.as_bytes()); assert_eq!(nb_possible_obstruction_position(&map, guard_pos), 1); - let (map, guard_pos) = read_map(MAP6.as_bytes()); + let (map, guard_pos) = read_map(&mut MAP6.as_bytes()); assert_eq!(nb_possible_obstruction_position(&map, guard_pos), 2); } } diff --git a/src/day07.rs b/src/day07.rs index 00c15e2..d1a90d2 100644 --- a/src/day07.rs +++ b/src/day07.rs @@ -116,14 +116,14 @@ mod tests { #[test] fn test_part1() { - let equations = read(EQUATIONS.as_bytes()); + let equations = read(&mut EQUATIONS.as_bytes()); let sum = sum_valid_equations(&equations); assert_eq!(sum, 3749); } #[test] fn test_part2() { - let equations = read(EQUATIONS.as_bytes()); + let equations = read(&mut EQUATIONS.as_bytes()); let sum = sum_valid_equations_with_concat(&equations); assert_eq!(sum, 11387); } diff --git a/src/day08.rs b/src/day08.rs index 8e37a27..55d2816 100644 --- a/src/day08.rs +++ b/src/day08.rs @@ -126,14 +126,14 @@ mod tests { #[test] fn test_part1() { - let antennae = read(ANTENNAE.as_bytes()); + let antennae = read(&mut ANTENNAE.as_bytes()); let n = nb_antinodes(&antennae, AntinodeMode::TwoPerPair); assert_eq!(n, 14); } #[test] fn test_part2() { - let antennae = read(ANTENNAE.as_bytes()); + let antennae = read(&mut ANTENNAE.as_bytes()); let n = nb_antinodes(&antennae, AntinodeMode::Unlimited); assert_eq!(n, 34); } diff --git a/src/day09.rs b/src/day09.rs index 1112347..7dcd8e1 100644 --- a/src/day09.rs +++ b/src/day09.rs @@ -1,14 +1,81 @@ use std::io::BufRead; -pub fn read(reader: &mut dyn BufRead) -> i32 { - 0 +pub fn read(reader: &mut dyn BufRead) -> Vec { + let mut disk_map_str = String::new(); + reader.read_to_string(&mut disk_map_str).unwrap(); + disk_map_str + .chars() + .map(|c| c.to_digit(10).unwrap()) + .collect() +} + +const EMPTY: u32 = u32::MAX; + +pub fn defrag_checksum(disk_map: &[u32]) -> u64 { + let size: u32 = disk_map.iter().sum(); + let mut memory: Vec = Vec::new(); + memory.resize(size as usize, EMPTY); + + let mut current_id = 0; + let mut current_pos: usize = 0; + let mut is_free_space = false; + for n in disk_map { + if !is_free_space { + memory[current_pos..current_pos + *n as usize].fill(current_id); + current_id += 1; + } + current_pos += *n as usize; + is_free_space = !is_free_space; + } + + fn next_empty_space_pos(from: usize, memory: &[u32]) -> usize { + for i in from..memory.len() { + if memory[i] == EMPTY { + return i; + } + } + 0 + } + + fn prev_non_empty_space_pos(from: usize, memory: &[u32]) -> usize { + for i in (0..=from).rev() { + if memory[i] != EMPTY { + return i; + } + } + 0 + } + + let mut first_empty_space_pos = next_empty_space_pos(0, &memory); + let mut last_value_pos = memory.len() - 1; + + while last_value_pos > first_empty_space_pos { + memory[first_empty_space_pos] = memory[last_value_pos]; + memory[last_value_pos] = EMPTY; + first_empty_space_pos = next_empty_space_pos(first_empty_space_pos + 1, &memory); + last_value_pos = prev_non_empty_space_pos(last_value_pos - 1, &memory); + } + + memory + .iter() + .take_while(|v| **v != EMPTY) + .enumerate() + .map(|(i, v)| i as u64 * *v as u64) + .sum() } #[cfg(test)] mod tests { + use super::*; + + static DISK_MAP: &str = "2333133121414131402"; #[test] - fn test_part1() {} + fn test_part1() { + let disk_map = read(&mut DISK_MAP.as_bytes()); + let checksum = defrag_checksum(&disk_map); + assert_eq!(checksum, 1928); + } #[test] fn test_part2() {} diff --git a/src/days.rs b/src/days.rs index 3c1918a..644051e 100644 --- a/src/days.rs +++ b/src/days.rs @@ -75,5 +75,6 @@ pub fn day08(reader: &mut dyn BufRead) -> String { } pub fn day09(reader: &mut dyn BufRead) -> String { - format!("part1: {}, part2: {}", 0, 0,) + let disk_map = day09::read(reader); + format!("part1: {}, part2: {}", day09::defrag_checksum(&disk_map), 0,) } -- 2.45.2