Spaces:
Running
Running
| 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() |