Advent of code

◂ 9 décembre 2024 ▸

  Disk Fragmenter : Déplacer des valeurs par bloc dans des endroits disponibles.

2378984580121520505930414446619015763552254 … 

1. code.py
2. diff_versionBug_versionCorrigee.diffy

TEST = False
if TEST:
    line = "2333133121414131402"
else:
    with open("input.txt", 'r', encoding='utf-8') as f:
        line = f.read()[:-1]

NOT_FOUND = -1

class File():
    def __init__(self, length=0, id=None):
        self.length = length
        self.id = id

    def is_free_space(self):
        return self.id is None

    # This function converts [4,7] to [7,7,7,7]
    def get_blocks(self):
        return self.length * [self.id]

    def __repr__(self):
        if self.is_free_space():
            return f"{{{self.length} empty block{'s' if self.length > 1 else ''}}}"
        return f"{{File #{self.id} × {self.length} blocks}}"

    # This function converts  files [[2,7], [3,None], [1,5]]  to  blocks [7,7,None,None,None,5]
    @staticmethod
    def to_blocks(files):
        return sum((file.get_blocks() for file in files), [])


system1_blocks = []     # list of blocks of the system
system2 = []            # list of files of the system (file id + number of blocks)
for i,c in enumerate(line):
    file = File(length = int(c))
    if i % 2 == 0:
        file.id = i//2
    system1_blocks.extend(file.get_blocks())
    system2.append(file)

### Could have just created system1_blocks as:   system1_blocks = File.to_blocks(system2)


# Part 1: moving block by block
def defrag_part1(system):
    free_pos = next((k for k in range(len(system)) if system[k] is None), NOT_FOUND)   # like system[k].index(None) but NOT_FOUND (=-1) if nothing found
    last_block = system.pop()
    while free_pos != NOT_FOUND:
        system[free_pos] = last_block
        last_block = system.pop()
        while last_block is None:
            last_block = system.pop()
        free_pos = next((k for k in range(free_pos + 1, len(system)) if system[k] is None), NOT_FOUND)   # search from free_pos+1 to speed things up
    system.append(last_block)
    #print(''.join([str(c)+'/' if c is not None else '.' for c in system]))
    return system


# Part 2: moving whole file segment of blocks
def defrag_part2(files):
    file_index = len(files)

    #### OPTIMIZATION :  if there's no place for some file, there will be no place for later file with same size or more ####
    length_not_available = max(file.length for file in files) + 1   # or just make it 10 as length are 1 digit in the input 
    
    while file_index > 0:
        file_index -= 1
        while files[file_index].is_free_space():
            file_index -= 1
            if file_index == 0:
                return files
        file = files[file_index]
        if file.length >= length_not_available:
            continue
        unalloc_index = next((index for index in range(file_index) if files[index].is_free_space() and files[index].length >= file.length), NOT_FOUND)
        if unalloc_index == NOT_FOUND:
            length_not_available = file.length
            continue
        if files[unalloc_index].length > file.length:   # separate empty blocks into two parts
            files[unalloc_index].length -= file.length
            files.insert(unalloc_index, File(file.length))
            file_index += 1
        files[unalloc_index], files[file_index] = files[file_index], files[unalloc_index]  # move file
    return files


def checksum(blocks):
    return sum(i * blocks[i] for i in range(len(blocks)) if blocks[i] is not None)

print("Réponse partie 1:", checksum(defrag_part1(system1_blocks)))
print("Réponse partie 2:", checksum(File.to_blocks(defrag_part2(system2))))
# should be 63614979355824 and 97898222299196