Spaces:
Running
Running
File size: 2,738 Bytes
a4da721 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
def parse_disk_map(disk_map):
disk = []
file_id = 0
for i in range(0, len(disk_map), 2):
file_length = int(disk_map[i])
free_space_length = int(disk_map[i+1])
disk.extend([str(file_id)] * file_length)
disk.extend(['.'] * free_space_length)
file_id += 1
return disk
def compact_disk_individual_blocks(disk):
# Move individual blocks to the leftmost free space
for i in range(len(disk)):
if disk[i] == '.':
# Find the next file block to move
for j in range(i + 1, len(disk)):
if disk[j] != '.':
# Move the block
disk[i], disk[j] = disk[j], disk[i]
break
return disk
def compact_disk_whole_files(disk):
# Move whole files to the leftmost free space
file_positions = []
current_pos = 0
while current_pos < len(disk):
if disk[current_pos] != '.':
file_id = disk[current_pos]
file_start = current_pos
while current_pos < len(disk) and disk[current_pos] == file_id:
current_pos += 1
file_positions.append((file_id, file_start, current_pos - file_start))
else:
current_pos += 1
# Move files in reverse order of file ID
for file_id, file_start, file_length in sorted(file_positions, key=lambda x: -int(x[0])):
# Find the leftmost free space that can fit the file
free_start = 0
while free_start < len(disk):
if disk[free_start] == '.':
free_end = free_start
while free_end < len(disk) and disk[free_end] == '.':
free_end += 1
if free_end - free_start >= file_length:
# Move the file
for i in range(file_length):
disk[free_start + i] = file_id
for i in range(file_length):
disk[file_start + i] = '.'
break
free_start = free_end + 1
return disk
def calculate_checksum(disk):
checksum = 0
for position, block in enumerate(disk):
if block != '.':
checksum += position * int(block)
return checksum
def main():
with open("input.txt", "r") as file:
disk_map = file.readline().strip()
# Part 1
disk = parse_disk_map(disk_map)
compacted_disk = compact_disk_individual_blocks(disk)
checksum_part1 = calculate_checksum(compacted_disk)
print(checksum_part1)
# Part 2
disk = parse_disk_map(disk_map)
compacted_disk = compact_disk_whole_files(disk)
checksum_part2 = calculate_checksum(compacted_disk)
print(checksum_part2)
main() |