1from __future__ import annotations
2
3def get_data(path: str) -> str:
4 with open(path) as f:
5 return f.read().strip()
6
7def main(data: str):
8 intermediate = []
9 is_disk = False
10 counter = -1
11 for char in data:
12 is_disk = not(is_disk)
13 if is_disk:
14 counter += 1
15 intermediate.extend([str(counter)] * int(char))
16 else:
17 intermediate.extend(['.'] * int(char))
18
19 left = 0
20 right = len(intermediate) - 1
21 while True:
22 while intermediate[left] != ".":
23 left += 1
24 while intermediate[right] == ".":
25 right -= 1
26 if left >= right:
27 break
28 intermediate[left] = intermediate[right]
29 intermediate[right] = "."
30
31 total = 0
32 for base, char in enumerate(intermediate):
33 if char == ".":
34 break
35 total += int(char) * base
36
37 return total
38
39
40
41if __name__ == "__main__":
42 # print(main(get_data("day_9_input_test.txt")))
43 print(main(get_data("day_9_input.txt")))
1from __future__ import annotations
2
3import dataclasses
4
5
6def get_data(path: str) -> str:
7 with open(path) as f:
8 return f.read().strip()
9
10@dataclasses.dataclass
11class Region:
12 is_disk: bool
13 size: int
14 name: str = "."
15
16def main(data: str):
17 intermediate: list[Region] = []
18 is_disk = False
19 counter = -1
20 for datum in data:
21 is_disk = not(is_disk)
22 if is_disk:
23 counter += 1
24 intermediate.append(Region(True, int(datum), str(counter)))
25 else:
26 intermediate.append(Region(False, int(datum)))
27
28 for i in range(len(intermediate) - 1, -1, -1):
29 disk_region = intermediate[i]
30 if disk_region.is_disk:
31 for j in range(i):
32 free_region = intermediate[j]
33 if not free_region.is_disk and free_region.size >= disk_region.size:
34 intermediate.insert(j, disk_region)
35 free_region.size -= disk_region.size
36 intermediate[i + 1] = Region(False, disk_region.size)
37 break
38
39 final_intermediate = []
40 for region in intermediate:
41 if region.size:
42 final_intermediate.extend([region.name] * region.size)
43 print("".join(final_intermediate))
44
45 total = 0
46 for base, char in enumerate(final_intermediate):
47 if char == ".":
48 continue
49 total += int(char) * base
50
51 return total
52
53
54
55if __name__ == "__main__":
56 print(main(get_data("day_9_input_test.txt")))
57 # print(main(get_data("day_9_input.txt")))
1from __future__ import annotations
2
3import dataclasses
4
5
6def get_data(path: str) -> str:
7 with open(path) as f:
8 return f.read().strip()
9
10@dataclasses.dataclass
11class Region:
12 is_disk: bool
13 size: int
14 name: str = "."
15 prev_r: Region | None = None
16 next_r: Region | None = None
17
18def main(data: str):
19 first_region = None
20 last_region = None
21 is_disk = False
22 counter = -1
23
24 for datum in data:
25 is_disk = not(is_disk)
26 if is_disk:
27 counter += 1
28 if first_region and last_region:
29 last_region.next_r = Region(True, int(datum), str(counter), last_region)
30 last_region = last_region.next_r
31 else:
32 first_region = Region(True, int(datum), str(counter))
33 last_region = first_region
34 else:
35 assert last_region
36 last_region.next_r = Region(False, int(datum), prev_r=last_region)
37 last_region = last_region.next_r
38
39 assert first_region
40 assert last_region
41
42 right = last_region
43 while right:
44 next_right = right.prev_r
45
46 if right.is_disk:
47 left = first_region
48 while left and left != right:
49 #
50 # We've found a spot where an insertion works
51 #
52 if not left.is_disk and left.size >= right.size:
53 left.size -= right.size
54
55 #
56 # Insert a new empty region where the right region was
57 #
58 new_region = Region(False, right.size, prev_r=right.prev_r, next_r=right.next_r)
59 if right.next_r:
60 right.next_r.prev_r = new_region
61 if right.prev_r:
62 right.prev_r.next_r = new_region
63
64 #
65 # Insert the right_region before the left_region
66 #
67 right.next_r = left
68 right.prev_r = left.prev_r
69 if left.prev_r:
70 left.prev_r.next_r = right
71 left.prev_r = right
72
73 break
74 left = left.next_r
75
76 right = next_right
77
78
79 final_intermediate = []
80 region = first_region
81 while region:
82 if region.size:
83 final_intermediate.extend([region.name] * region.size)
84 region = region.next_r
85
86 total = 0
87 for base, char in enumerate(final_intermediate):
88 if char == ".":
89 continue
90 total += int(char) * base
91
92 return total
93
94
95
96if __name__ == "__main__":
97 # print(main(get_data("day_9_input_test.txt")))
98 print(main(get_data("day_9_input.txt")))