from misc.helper import verify_answer
example_input_file = "../inputs/example_day_09.txt"
input_file = "../inputs/day_09.txt"Day 9
In today’s task we are helping an amphipod with their computer! And we’re tasked with disk fragmentation nonetheless. Check out the full back story and problem setup on the official Day 9 of Advent of Code 2024 website.
And here’s the ChatGPT generated graphic of how the elves are traveling in their submarine to get us started:
Setting up
Part 1: Fragmentation 101
For the compact string of 1343212, we will get the following notation – 0...1111...22.33. The dots represent the empty spaces. The numbers represent the file IDs. Our task here is move all files into the empty positions (the files can be fragmented, they should fill all the blanks). We should start filling the space by moving the files from the rightmost position to the first leftmost position available (i.e. move the files from the end to the closest to star empty space).
start: 0...1111...22.33
step 1: 03..1111...22.3.
step 2: 033.1111...22...
step 3: 03321111...2....
finally: 033211112.......The output of the function is the sum of the products of the file ID and its current position. In this case, the output is 0*0 + 1*3 + 2*3 + 3*2 + 4*1 + 5*1 + 6*1 + 7*1 + 8*2 = 53.
I will start by reading the input and creating a list of the positions on the drive, the files will be represented by their ID and empthy space will be represented by -1.
def read_input(input):
"""Reads input and returns expanded list"""
file_id = 0
files = []
for i, el in enumerate(input):
if i % 2 == 0:
files.extend([file_id] * int(el))
file_id += 1
else:
files.extend([-1] * int(el))
return files
read_input("1343212")[0, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, 2, 2, -1, 3, 3]Then, I will sort the files by populating all empty spaces. Here, I am iterating over the files from the beginning. If I encounter an empty space, I go to the end of the list and find the rightmost file (if I encounter an empty space, I move my “end” pointer to the space before until I encounter new file). I then move that file into the empty space. I repeat this process until I reach the end of the list.
def sort_files(files):
"""Populates the free space with most right files, returns the dense list"""
new_end = len(files) - 1
for i, el in enumerate(files):
if i == new_end:
break
if el == -1:
while new_end > i and files[new_end] == -1:
new_end -= 1
if new_end >= i:
files[i], files[new_end] = files[new_end], files[i]
new_end -= 1
return files[: (new_end + 1)]
sort_files([0, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, 2, 2, -1, 3, 3])[0, 3, 3, 2, 1, 1, 1, 1, 2]Then, I calculate the checksum by multiplying the file ID by its position and summing all the products.
def calc_checksum(files):
"""Calculate checksum"""
return sum([i * el for i, el in enumerate(files) if el > -1])
calc_checksum([0, 3, 3, 2, 1, 1, 1, 1, 2])53Finaly, I put everything together in a function and test it on the example from the problem statement.
from pathlib import Path
def part_one(input):
"""Reads input, sorts files and calculates checksum."""
if Path(input).exists():
with open(input) as f:
input = f.read().strip()
files = read_input(input)
files = sort_files(files)
return calc_checksum(files)
verify_answer(part_one, "154321", 24)✔️ That's right! The answer is 24.verify_answer(part_one, "1343212", 53)✔️ That's right! The answer is 53.verify_answer(part_one, example_input_file, 1928)✔️ That's right! The answer is 1928.%time part_one(input_file)CPU times: user 13.6 ms, sys: 2.76 ms, total: 16.3 ms
Wall time: 56.2 ms6390180901651That’s the right answer! You are one gold star ⭐ closer to finding the Chief Historian.
Part 2: Don’t split the files!
In the second part we want to move the files again, but we don’t want to split them!
For the compact string of 1343212 we will get the following notation – 0...1111...22.33. The dots represent the empty spaces. The numbers represent the file IDs.
start: 0...1111...22.33
step 2: 033.1111...22...
step 3: 033.111122......The checksum is calculated like in the first part. In this case, the output is 0*0 + 1*3 + 2*3 + 3*0 + 4*1 + 5*1 + 6*1 + 7*1 + 8*2 + 9*2 = 65.
I will start by reading the input. This time, I will track the files and the empty spaces separately. I will keep their position and their size in two different lists of tuples.
def read_input_bis(input):
"""Reads input and returns expanded list"""
files = []
space = []
pos = 0
for i, el in enumerate(input):
if i % 2 == 0:
files.append((pos, int(el)))
else:
space.append((pos, int(el)))
pos += int(el)
return files, space
read_input_bis("1343212")([(0, 1), (4, 4), (11, 2), (14, 2)], [(1, 3), (8, 3), (13, 1)])When sorting the files, I will iterate from the end of files list and move the files to the closest to the start space.
def sort_files_bis(files, space):
"""Move the files to the rightmost available space that can fit it"""
for x, (pos, size) in enumerate(files[::-1]):
i = len(files) - x - 1
for j, (pos_s, size_s) in enumerate(space):
if pos_s >= pos:
break
# if the space can fit the file, I will move it there
if size_s >= size:
if size_s - size > 0:
space[j] = (pos_s + size, size_s - size)
else:
space.pop(j)
files[i] = (pos_s, size)
break
return files
sort_files_bis([(0, 1), (4, 4), (11, 2), (14, 2)], [(1, 3), (8, 3), (13, 1)])[(0, 1), (4, 4), (8, 2), (1, 2)]I need to modify the checksum claculation now that I keep the files in a sparser list.
def calc_checksum_bis(files):
temp = [
sum(id * list(range(pos, pos + size)))
for id, (pos, size) in enumerate(files)
]
return sum(temp)
calc_checksum_bis([(0, 1), (4, 4), (8, 2), (1, 2)])65Now, putting it all together I will read the input, sort the files and calculate the checksum.
def part_two(input):
if Path(input).exists():
with open(input) as f:
input = f.read().strip()
files, space = read_input_bis(input)
files = sort_files_bis(files, space)
return calc_checksum_bis(files)
verify_answer(part_two, "1343212", 65)✔️ That's right! The answer is 65.verify_answer(part_two, example_input_file, 2858)✔️ That's right! The answer is 2858.%time part_two("../inputs/day_09.txt")CPU times: user 1.06 s, sys: 18.6 ms, total: 1.08 s
Wall time: 1.18 s6412390114238That’s the right answer! You are one gold star ⭐ closer to finding the Chief Historian.