From c8e9f97fda563573fe61fc2cbacd0a1d0bd5386c Mon Sep 17 00:00:00 2001 From: Jack Kinsey Date: Tue, 10 Dec 2024 23:02:22 -0500 Subject: [PATCH] Complete day 9 part 2 --- src/day09.rs | 155 ++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 148 insertions(+), 7 deletions(-) diff --git a/src/day09.rs b/src/day09.rs index e80700f..34f4202 100644 --- a/src/day09.rs +++ b/src/day09.rs @@ -34,6 +34,57 @@ fn fragment(disk: &mut Vec) { } } +fn compact(disk: &mut [DiskMap]) { + let mut lp = 0; + let mut ls = 0; + let mut rp = disk.len() - 1; + let mut rs = 0; + let mut id = disk[rp]; + loop { + // size up rightmost disk region not yet considered + while disk[rp] == id && rp > 0 { + rs += 1; + rp -= 1; + } + // if we've reached start of disk, quit + if rp == 0 { + break; + } + // size up leftmost free regions + // lp <= rp: cf. '00....1111', can't capture full free region otw + while ls < rs && lp <= rp { + match disk[lp] { + Some(_) => { + ls = 0; + lp += 1; + } + None => { + ls += 1; + lp += 1; + } + } + } + // if we found a region big enough to fit the disk region, move + if ls == rs { + for i in disk.iter_mut().take(lp).skip(lp - ls) { + *i = id; + } + for i in disk.iter_mut().take(rp + rs + 1).skip(rp + 1) { + *i = None; + } + } + // move ptr to next disk region + while disk[rp].is_none() { + rp -= 1; + } + // reset + id = disk[rp]; + lp = 0; + ls = 0; + rs = 0; + } +} + fn checksum(disk: &[DiskMap]) -> u64 { disk.iter() .zip(0..) @@ -52,7 +103,9 @@ pub fn part1() { } pub fn part2() { - let n = 0; + let mut disk = parse(input()); + compact(&mut disk); + let n = checksum(&disk); println!("Day 9 Part 2: {}", n); } @@ -93,10 +146,10 @@ mod test { #[rustfmt::skip] #[test] fn test_fragment() { - let mut map = parse(INPUT_STR); - fragment(&mut map); + let mut disk = parse(INPUT_STR); + fragment(&mut disk); assert_eq!( - map, + disk, vec![ Some(0), Some(0), Some(9), Some(9), @@ -115,10 +168,98 @@ mod test { ) } + #[rustfmt::skip] + #[test] + fn test_compact() { + let mut disk = parse(INPUT_STR); + compact(&mut disk); + assert_eq!( + disk, + vec![ + Some(0), Some(0), + Some(9), Some(9), + Some(2), + Some(1), Some(1), Some(1), + Some(7), Some(7), Some(7), + None, + Some(4), Some(4), + None, + Some(3), Some(3), Some(3), + None, None, None, None, + Some(5), Some(5), Some(5), Some(5), + None, + Some(6), Some(6), Some(6), Some(6), + None, None, None, None, None, + Some(8), Some(8), Some(8), Some(8), + None, None, + ], + ); + + disk = vec![ + Some(0), Some(0), + None, None, None, + Some(1), Some(1), Some(1), + None, None, None, None, + None, None, None, + Some(3), Some(3), Some(3), + None, + Some(4), Some(4), + None, + Some(5), Some(5), Some(5), Some(5), + None, + Some(6), Some(6), Some(6), Some(6), + None, + Some(7), Some(7), Some(7), + None, + Some(8), Some(8), Some(8), Some(8), + Some(9), Some(9) + ]; + compact(&mut disk); + assert_eq!( + disk, + vec![ + Some(0), Some(0), + Some(9), Some(9), + None, + Some(1), Some(1), Some(1), + Some(8), Some(8), Some(8), Some(8), + Some(7), Some(7), Some(7), + Some(3), Some(3), Some(3), + None, + Some(4), Some(4), + None, + Some(5), Some(5), Some(5), Some(5), + None, + Some(6), Some(6), Some(6), Some(6), + None, None, None, None, None, None, + None, None, None, None, None, + ], + ); + + disk = vec![ + Some(0), Some(0), + None, None, None, None, + Some(1), Some(1), Some(1), Some(1), + ]; + compact(&mut disk); + assert_eq!( + disk, + vec![ + Some(0), Some(0), + Some(1), Some(1), Some(1), Some(1), + None, None, None, None, + ], + ); + } + #[test] fn test_checksum() { - let mut map = parse(INPUT_STR); - fragment(&mut map); - assert_eq!(checksum(&map), 1928) + let mut disk = parse(INPUT_STR); + fragment(&mut disk); + assert_eq!(checksum(&disk), 1928); + + disk = parse(INPUT_STR); + compact(&mut disk); + assert_eq!(checksum(&disk), 2858); } } -- 2.38.5