09
https://adventofcode.com/2024/day/9
Prob1
題目
在使用硬碟寫檔刪檔時,有時會讓硬碟連續空間中間出現空缺。簡單來說如下:
111xxxx333
111
和 333
是目前仍然活著的檔案,xxxx
是之前使用,但是被刪掉的檔案,這樣會降低硬碟使用效率。(當然,一個字母可能代表的不只是一個 byte,可能是 1kb,這件事在這題不重要)
所以我們會需要定期做「磁碟重組」。現在考慮以下「磁碟重組」方式:不斷地把最後一個字母移動到當前第一個沒有使用的點,直到沒辦法這樣做。
例如:
11xxx2222xxxx3333xxx4444
會這樣:
0: 11xxx2222xxxx3333xxx4444
1: 114xx2222xxxx3333xxx444x
...
4: 1144422224xxx3333xxxxxxx
...
7: 11444222243333xxxxxxxxxx
輸入是個由數字組成的字串
例如: 133,這樣的意思是 1 格檔案, 3 格空格, 3 格檔案
1xxx222
最後輸出結果的 checksum:
範例
Input
122
Output
輸入的硬碟是這樣 1xx22
,重組後變成結果變成 122xx
, checksum =
5
解法
two-pointers: 一個指標從前面跑,找到最小的空的點。一個從後面跑,找到有檔案的點就往前放。
時間複雜度:
python
import sys
line = sys.stdin.readline().strip()
arr = []
for idx, cnt_str in enumerate(line):
cnt = int(cnt_str)
if idx % 2 == 0:
arr.extend([idx//2]*cnt)
else:
arr.extend([-1]*cnt)
print(arr)
lptr = 0
rptr = len(arr) - 1
while lptr < rptr:
while lptr < rptr and arr[lptr] != -1:
lptr += 1
if lptr >= rptr:
break
while lptr < rptr and arr[rptr] == -1:
rptr -= 1
if lptr >= rptr:
break
arr[lptr] = arr[rptr]
lptr += 1
rptr -= 1
arr = arr[:rptr + 1]
print(arr)
checksum = 0
for idx, x in enumerate(arr):
if x == -1:
continue
checksum += idx*x
print(checksum)
Prob2
上面的方式顯然增加了大量的檔案碎片,讓檔案系統變得更慢了!
所以我們這次只考慮不讓檔案碎片化的移動方法:
- 從後面的檔案往前決定
- 一樣讓檔案開始的 index 越小越好
- 沒有辦法移動就跳過
例如:
11xxx2222xxxx33xxxxx4444
移動 4
檔案
11xxx2222444433xxxxxxxxx
移動 3
檔案
1133x22224444xxxxxxxxxxx
輸出 checksum:
範例
Input
1223113
Output
輸入表示:1xx22xxx3x444
。結果變成 13x22444xxxxx
。
checksum =
99
解法
python
import sys
from typing import List, Tuple
line = sys.stdin.readline().strip()
files: List[Tuple[int, int]] = []
# (l, r)
holes: List[Tuple[int, int]] = []
ptr = 0
for idx, cnt_str in enumerate(line):
cnt = int(cnt_str)
if cnt == 0:
continue
if idx % 2 == 0:
files.append((ptr, ptr + cnt))
else:
#if holes and holes[-1][1] == ptr:
# holes[-1][1] += cnt
#else:
holes.append((ptr, ptr + cnt))
ptr += cnt
for fidx in range(len(files) - 1, -1, -1):
fl, fr = files[fidx]
flen = fr - fl
for hidx, hole in enumerate(holes):
l, r = hole
if l > fl:
continue
if flen > r - l:
continue
holes[hidx] = (l + flen, r)
files[fidx] = (l, l + flen)
break
check_sum = 0
for fidx, file in enumerate(files):
l, r = file
check_sum += fidx*((r-1)*r - (l-1)*l)//2
print(check_sum)