For Day 9, I used Rust.
Parsing
The input is one very long line of digits, making parsing very simple. We trim the input, iterate over its characters, convert each character into an integer, and then convert that into a list of numbers.
fn parse_input(input: String) -> Vec<u8> {
input.trim().chars().map(|ch| ch.to_digit(10).unwrap() as u8).collect()
}Part One
The digits represent the length of files and the length of free space present on a hypothetical computer’s disk. The first digit represents the length of file 0, the second digit represents the free space between file 0 and file 1, the third digit represents the length of file 1, the fourth the length of free space between file 1 and file 2, and so on.
For part one, we need to get rid of free space by taking file blocks from the end of disk and moving them to the first free space available from the start of the disk and continuing to do so until there is no free space left.
Once that has been done, we need to compute a checksum, which is the sum over the product of the file id and the index of the block.
In my solution, I start by creating an expanded representation of the disk (called memory in the code) as a list of Option<usize> where a None represents free space and a Some(id) represents a file block with id id.
Then, I remove from the end of the list and if that is a file block, I insert the value of that into the first free space in the disk and continue doing so until the no free spaces are left. I check that no free spaces are left by comparing the total length of the disk with the combined length of all the files which was computed when creating the expanded representation.
Finally, I compute the checksum of the disk and return it.
fn part1(input: &[u8]) -> usize {
let mut memory = Vec::new();
let mut files_size : usize= 0;
for (i, num) in input.iter().copied().enumerate() {
if i % 2 == 0 {
for _ in 0..num {
memory.push(Some(i/2));
files_size += 1;
}
} else {
for _ in 0..num {
memory.push(None);
}
}
}
while memory.len() > files_size {
let last = memory.pop();
match last {
None => {},
Some(None) => {},
Some(Some(id)) => {
memory.iter_mut().find(|x| x.is_none()).unwrap().insert(id);
},
}
}
memory.iter().enumerate().map(|(i, id)| i * id.unwrap()).sum()
}Part Two
It turns out that our first approach led to poor performance due to disk fragmentation, so this time we transfer entire files from the end into the first free space to the left of that file that is big enough instead of transferring block by block.
Once again I start by creating an expanded representation of the disk. After that, my solution iterates over file ids, going down from the last id to 0. Then for each id I find the length and start of that file in the expanded representation then find the leftmost free space that can accomodate the file and finally move the file to start of that free space.
To find the length and start of each file, I iterate over the expanded representation and filter only the blocks with that id. This, combined with the enumerate method lets me find the start index of the file.
To find the leftmost free space that can accomodate the current file, I iterate from 0 until the start of the file. When I encounter a free space at a position, I count the number of free spaces including and to the right of that position. If this count is greater than or equal to the file length, we have found the free space to put our file in and I record that position and break from the loop. Otherwise, I skip over the free space, continuing until the loop terminates.
To move the file, there is a handy method in the std library called swap_with_slice. However, if we tried to directly swap memory[file_start..][..file.len()] with memory[blank_start..][..file.len()], we would get a borrow checker error since both borrow mutably from the same variable and it is invalid to have two mutable borrows to the same thing at the same time. Rust doesn’t realize that this is actually fine since the two borrows point to different sections of memory. To deal with this problem, the split_at_mut method is used to get two different mutable references that are guaranteed to point to different sections of memory.
At the end, I compute and return the checksum of the disk.
fn part2(input: &[u8]) -> usize {
let mut memory = Vec::new();
let mut last_id = 0;
for (i, num) in input.iter().copied().enumerate() {
if i % 2 == 0 {
for _ in 0..num {
memory.push(Some(i/2));
}
last_id = i/2;
} else {
for _ in 0..num {
memory.push(None);
}
}
}
for id in (0..=last_id).rev() {
// find length of file
let file = memory.iter().copied().enumerate().filter(|&(i, x)| x == Some(id)).collect::<Vec<_>>();
let file_start = file[0].0;
// find space that can accomodate file
let mut i = 0;
let mut blank_start = None;
while i < file_start {
if memory[i].is_none() {
let blank_len = memory[i..].iter().copied().take_while(|x| x.is_none()).count();
if blank_len >= file.len() {
blank_start = Some(i);
break;
}
i += blank_len;
} else {
i += 1;
}
}
// swap slices
if let Some(blank_start) = blank_start {
let (mut blank_slice, mut file_slice) = memory.split_at_mut(file_start);
blank_slice = &mut blank_slice[blank_start..][..file.len()];
file_slice = &mut file_slice[..file.len()];
blank_slice.swap_with_slice(file_slice)
}
}
memory.iter().enumerate().map(|(i, id)| i * id.unwrap_or(0)).sum()
}