Advent of Code 2024 Day 9

Author

Nathan Moore

— Day 9: Disk Fragmenter —

We have a dense representation of disk memory.

Compact the amphipod’s hard drive using the process he requested. What is the resulting filesystem checksum?

with open('data-2024-09.txt', 'r') as f:
    inp = f.read().splitlines()

hd = list(inp[0])

hd = [int(x) for x in hd]

len(hd)

Guess I just have to loop, like always

long_map = []
dig = 0

gap = False

for h in hd: 
    # fill in the gaps
    if gap: 
        for i in range(h): 
            long_map.append('.')
        gap = False
    # populate the array      
    else: 
        for i in range(h): 
            long_map.append(dig)
        gap = True
        dig += 1

long_map[:30]
long_map[-30:]

[9997,
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 9998,
 9998,
 9998,
 9998,
 9998,
 9998,
 9998,
 9998,
 9998,
 '.',
 '.',
 '.',
 '.',
 '.',
 9999,
 9999,
 9999,
 9999,
 9999,
 9999,
 9999,
 9999,
 9999]

Good so far, now we have to move from the end to the gaps.

place = 0
back = len(long_map)-1

new_map = []

for m in long_map: 
    if isinstance(m, str):
        # if it is a dot then put numbers in
        if isinstance(long_map[-1], int): 
            # new_map.append(long_map[back])
            new_map.append(long_map.pop())
            # back -= 1
            # place += 1
        else: 
            # reduce the iterator
            while isinstance(long_map[-1], str):
                _ = long_map.pop()
            new_map.append(long_map.pop())
    else: 
        # populate the new array with current array in order
        new_map.append(m)
        # place += 1
    # check for swapping, reached the end
    # if place > back: 
    if len(new_map) == len(long_map):
        break

OK, now, so, create a sumproduct to find the answer

summer = 0

for e,n in enumerate(new_map): 
    summer += e*n
    
summer

# 6398252054886

6398252054886

— Part Two —

We need to move whole blocks of files instead of piece by piece.

Start over, now compacting the amphipod’s hard drive using this new method instead. What is the resulting filesystem checksum?

# check how many blocks of each there are, files and spaces. 
file_len = {}
gap_len = {}

for i in range(0, len(hd), 2):
    if hd[i] in file_len: 
        file_len[hd[i]] += 1
    else: 
        file_len[hd[i]] = 1
        
for j in range(1, len(hd), 2): 
    if hd[j] in gap_len:
        gap_len[hd[j]] += 1
    else: 
        gap_len[hd[j]] = 1
        
dict(sorted(file_len.items()))
dict(sorted(gap_len.items()))

{0: 1032,
 1: 1021,
 2: 961,
 3: 1031,
 4: 995,
 5: 1032,
 6: 1020,
 7: 991,
 8: 961,
 9: 955}

Gaps can be zero, so not everything is going to be able to move.

# go backwards from the end of the long_map
# recreate it first since we popped it for part one

long_map = []
dig = 0

gap = False

for h in hd: 
    # fill in the gaps
    if gap: 
        for i in range(h): 
            long_map.append('.')
        gap = False
    # populate the array      
    else: 
        for i in range(h): 
            long_map.append(dig)
        gap = True
        dig += 1

len(long_map)
long_map[:50]
long_map[-50:]

[9996,
 9996,
 9996,
 9996,
 9996,
 9996,
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 9997,
 9997,
 9997,
 9997,
 9997,
 9997,
 9997,
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 9998,
 9998,
 9998,
 9998,
 9998,
 9998,
 9998,
 9998,
 9998,
 '.',
 '.',
 '.',
 '.',
 '.',
 9999,
 9999,
 9999,
 9999,
 9999,
 9999,
 9999,
 9999,
 9999]

O(n2) sounds like the situation for the looping through the long_map to find the place to put the files.

It’s not massive so not too worried?

Do I need to make a copy of the array or just move the original files around? It is likely that I have to go backwards through the whole loop. Let us assume that we do not have to make a copy to start with.

# loop backwards for the things to move
# repeatedly loop forward through the gaps

from copy import deepcopy

file_pos = len(long_map) - 1

safe = 0


def find_gap(arr, file_len, place):
    # loop forwards
    for i in range(place - file_len): 
        # look for dots as gaps
        if arr[i] == '.':
            # get the length of the gap
            gap_len = get_len(arr[i:i+10])
            # if we have an appropriate length
            if gap_len >= file_len: 
                return i
    # if we cannot find an appropriate gap
    return False
        

def get_len(arr):
    num = arr[0]
    z = 1
    for i in range(1, len(arr)): 
        if arr[i] == num: 
            z += 1
        else: 
            break
    # return our count
    return z


while True:
    # safety
    # safe += 1
    # if safe == 500:
    #     break
    
    # print('file position ', file_pos)
    # store the current value that's looking for a home
    file_val = long_map[file_pos]
    # print('file value ', file_val)
    
    # find the length of the file
    # send the reversed map over to the function
    file_len = get_len(long_map[file_pos-10:file_pos+1][::-1])
    # print('file length ', file_len)
    
    # find a length to fit the thing
    # need to allow for no gap
    gap_num = find_gap(long_map, file_len, file_pos)
    # print('gap number ', gap_num)
    
    # if we don't have a place then we need to leave files in place
    if not gap_num: 
        print(file_pos)
    else: 
        # do the replacement
        long_map[gap_num:gap_num+file_len] = [file_val] * file_len
        
        # remove the values if we were able to move
        long_map[file_pos-file_len:file_pos+1] = ['.'] * file_len
    
    # get our new file_pos
    # at most file_len = 9 and gap_len = 9
    for j in range(20): 
        file_pos -= 1
        if long_map[file_pos] != '.' and long_map[file_pos] != file_val: 
            break
        
    # some kind of safety, expecting to fill the first 100 
    if file_pos < 100: 
        break
    
    

len(long_map)
long_map[:50]
long_map[-50:]

['.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.',
 '.']

Do the check sum again, but we need to account for the dots left behind

summer = 0

for e,n in enumerate(new_map): 
    summer += e*n
    
summer

# 6398252054886

6398252054886