AoC Day 9 was a lesson in what works fantastic for the first part, fails miserably for the 2nd part. Its one of the frustrations but also challenges of AoC, where you only get half of the final requirements to start. The puzzle input you get is just a string of single digit numbers (i.e. 12345) The digits in the string go back and forth in what they represent. The first digit is the size of a file, followed by the size of free space between that file and the next file. So for my example above, I have a file that is one block big, followed by two free blocks. Followed by a file three blocks big, followed by four free blocks, finally followed by a five block file.
The file IDs are simply the number of the file within the series. For for example using the string above file 0 is one block big, file 1 is three blocks big and file 2 is five blocks big. The challenge with part 1 is to simply defragment the files (although in reality this first part is actually fragmenting the files more but that’s besides the point). We’re were trying to do is fill in the free blocks with contents from the last file. One last thing to mention since its important when it comes to program implementation, the answer was the sum of values produced by multiplying the file ID against the storage block it was in.
My first thought was to do the obvious and great an array that mapped out the memory space. When I looked at my actual input, I found that my string was 20,000 digits long, with each digit representing a maximum of 9 blocks of storage which could get ugly really fast. After thinking about it for a bit though, I realized I didn’t actually need to do that at all. I just needed to figure out what file ID was in a block, and get the product of it.
I started by parsing the input into two lists (one of file sizes, and one of open spaces.
def get_data():
from os import path
data = []
spaces = []
with open(path.join(path.dirname(__file__), 'input.txt'), 'r') as f:
for line in f:
line = line.strip()
for i in range(0, len(line), 2):
data.append(int(line[i]))
for i in range(1, len(line), 2):
spaces.append(int(line[i]))
return data, spaces
I created a Storage class here to help me keep track of the files within my input.
class Storage:
def __init__(self, data):
self.data = {}
for f, q in enumerate(data):
self.data[f] = q
def get_next(self):
if len(list(self.data.keys())) > 0:
f = min(list(self.data.keys()))
q = self.data[f]
self.data.pop(f)
return [f] * q
else:
return None
def get_tail(self):
while len(list(self.data.keys())) > 0:
f = max(list(self.data.keys()))
q = self.data[f]
self.data.pop(f)
ans = [f] * q
for i in ans:
yield i
return None
Let me explain what each function does. The init function is simply fed the list of file sizes (remember each digit in the list represents the size of that file, and its location within the list represents the file ID). That gets saved within the object as a dictionary with File ID as the key and size as the value.
The function get_next() pulls the lowest value key from the list of files within the object that was populated above, and creates a list the size of the quantity of blocks of that file, with the value of file ID. Then it removes that file from the dictionary of files. and returns the list.
The function get_tail() pulls the highest value key from the list of files within the object that was populated above and creates a similar list like get_next. The one difference is that instead of returning the entire list, it instead yields a single element of the list at a time, returning one block of data each call and populating with the next file when it runs out of elements.
Here is the code that I originally used to answer part 1 that I will explain.
def part1(data, spaces):
answer = 0
files = Storage(data)
i = 0
tail = files.get_tail()
more_data = True
more_spaces = True
while more_data and more_spaces:
cur_file = files.get_next()
if cur_file is not None:
for f in cur_file:
answer += i * f
i += 1
else:
more_data = False
if spaces:
s = spaces.pop(0)
if s is not None:
for a in range(s):
try:
f = next(tail)
answer += i * f
i += 1
except:
more_spaces = False
else:
more_spaces = False
print('Part 1: {}'.format(str(answer)))
The first important part occurs on line 3 where we create a variable called files, and initialize it as a Storage object with the list of files that we got from our input. Line 5 takes the next step and initializes the .get_tail() function of the files object that we just created (essentially creating a generator of the tail end of the files list).
Beginning on line 9, we start looping until we run out of files and spaces. On line 10 we get the next file within the regular order and iterate through the elements of the list file blocks for that file. Remember, the list is a list of length file size with each element containing the same File ID number. As we iterate over that list, we add (sum) to our answer variable the block ID times the file ID.
Once we’ve iterated over that file, we check to see if there are still spaces left to work with (line 17). We see how big the next gap is (line 18), and then iterate over each block within that gap, each time trying to pull the last block from the last file using that generator created with our tail variable above. As we do that, we continue to add to our answer variable as we’re dealing with it. We do this until we run out of spaces and data blocks and then spit out the answer.
Fatal Mistakes
This solution worked great for part 1. It was fast, required very little memory and was pretty darn efficient overall. Unfortunately, when I made it to part 2 it became quickly very obvious that I should have gone with my initial idea because I essentially ended up trashing all of the work I had done and started over with my original plan. I’ll go over part 2 in a minute but the short of it is that in order to complete it, I needed the full array of file block and space blocks populated. Because of this, I recreated part 1 with my original idea. I started by creating my big storage object using the below function. Basically it goes back and forth between files and space blocks and creates the full array representation of it as a list. Each element of the list is either the File ID for that block, or a -1 for an open space.
def create_start(data, spaces):
pattern = []
i, j, f = 0, 0, 0
while (i < len(data)) or (j < len(spaces)):
if len(data) > 0:
d = data.pop(0)
pattern += ([f] * d)
f += 1
if len(spaces) > 0:
s = spaces.pop(0)
pattern += ([-1] * s)
return pattern
The new updated code for part 1 is below. Admittedly, its easier to read but not nearly as fast or efficent.
def part1a(the_pattern):
pattern = the_pattern[::]
i = 0
j = len(pattern) - 1
while i < j:
while pattern[i] != -1:
i += 1
while pattern[j] == -1:
j -= 1
if i < j:
pattern[i], pattern[j] = pattern[j], pattern[i]
answer = 0
i = 0
while pattern[i] != -1:
answer += pattern[i] * i
i += 1
print('Part 1: {}'.format(str(answer)))
Beginning on line 6, we start to loop through the entire contents of the disk structure, one block at a time. If the block has a file ID in it (a value >= 0) then we just keep going and checking the next block. On line 10 though if the value of the list item is -1 (open space), we pull in the back variable that tracks the overall length of the disk by one, and swap the values of the black space with the space that we just pulled back. Once the entire data structure has been filled in, then we loop through the entire structure start to finish and do the same math we did before.
Part 2
Part 2 had the same basic idea, but one significant change. If you remember at the start I pointed out how we were actually fragmenting the files even more because as we moved parts of files to fill in the holes, we would break the last file into a bunch of chunks scattered around the drive instead of a clean run of data blocks like you would normally want. For part 2, they fixed that and instead wanted us to move entire files to fill in the holes.
As we hit a gap in files, we have to move the last file available that fills that gap. Once we pass by an end file without moving it (because it’s to big to fit in the current gap) it’s no longer considered any more. Because we were only sometimes moving files, and sometimes leaving gaps, I needed to have the full representation of the drive and its contents.
Before I go into the overall program structure, I want to talk about two helper functions I created.
def find_run(pattern, start):
i = 0
a = pattern[start]
while (start + i <= (len(pattern) - 1)) and (pattern[start + i] == a):
i += 1
return i
The find_run function takes the overall drive image, and a index value (start) for that drive. It looks at the value stored then, and then goes through each of the next values in the drive blocks until it finds a block that changes values from the first one. It then returns the length of the run that it just found.
def find_opening(pattern, required_size):
i = 0
while i < len(pattern):
while pattern[i] != -1:
i += 1
# We found a gap
run = find_run(pattern, i)
if run >= required_size:
return i
else:
i += run
return None
Find_opening() takes the drive pattern, and then the required size of a gap, and loops through using the find_run() function to find the first gap of the required size it can and returns the starting index of that gap. If it can’t find a gap that is big enough, it returns None.
def part2(the_pattern):
pattern = the_pattern[::]
values = list(set(pattern))
values.remove(-1)
values.sort()
while len(values) > 0:
value = values.pop()
value_idx = pattern.index(value)
data_run = find_run(pattern, value_idx)
# Find an opening that will hold the data
space_idx = find_opening(pattern, data_run)
if space_idx is None:
continue
else:
if space_idx < value_idx:
for i in range(data_run):
pattern[value_idx + i], pattern[space_idx + i] = pattern[space_idx + i], pattern[value_idx + i]
answer = 0
i = 0
while i < len(pattern):
answer += max(pattern[i],0) * i
i += 1
print('Part 2: {}'.format(str(answer)))
This is the main program block for part 2. On lines 4 – 6, I created a sorted list of all of the File IDs within the drive. Starting on line 8, I loop through each file ID. Starting at the end of the list (highest file ID), we find the index for the first block with that file ID, and then use the find_run function to see how big that file ID is. Then on line 14, we find the first gap available that fits the file and then move the file into that gap. If there is not a space big enough for us to move the file, then we just skip past it and don’t look for a new spot for it again.
At the end, we once again loop through the entire drive structure and sum up the answer as before.
You can see my entire code on Github.