Skip to content

09

https://adventofcode.com/2024/day/9

Prob1

題目

在使用硬碟寫檔刪檔時,有時會讓硬碟連續空間中間出現空缺。簡單來說如下:

111xxxx333

111333 是目前仍然活著的檔案,xxxx是之前使用,但是被刪掉的檔案,這樣會降低硬碟使用效率。(當然,一個字母可能代表的不只是一個 byte,可能是 1kb,這件事在這題不重要)

所以我們會需要定期做「磁碟重組」。現在考慮以下「磁碟重組」方式:不斷地把最後一個字母移動到當前第一個沒有使用的點,直到沒辦法這樣做。

例如:

11xxx2222xxxx3333xxx4444

會這樣:

0: 11xxx2222xxxx3333xxx4444
1: 114xx2222xxxx3333xxx444x
...
4: 1144422224xxx3333xxxxxxx
...
7: 11444222243333xxxxxxxxxx

輸入是個由數字組成的字串

例如: 133,這樣的意思是 1 格檔案, 3 格空格, 3 格檔案

1xxx222

最後輸出結果的 checksum: ixi

範例

Input

122

Output

輸入的硬碟是這樣 1xx22,重組後變成結果變成 122xx, checksum = 1×0+2×1+2×2=5

5

解法

two-pointers: 一個指標從前面跑,找到最小的空的點。一個從後面跑,找到有檔案的點就往前放。

時間複雜度: O(N)

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

上面的方式顯然增加了大量的檔案碎片,讓檔案系統變得更慢了!

所以我們這次只考慮不讓檔案碎片化的移動方法:

  1. 從後面的檔案往前決定
  2. 一樣讓檔案開始的 index 越小越好
  3. 沒有辦法移動就跳過

例如:

11xxx2222xxxx33xxxxx4444

移動 4 檔案

11xxx2222444433xxxxxxxxx

移動 3 檔案

1133x22224444xxxxxxxxxxx

輸出 checksum: ixi

範例

Input

1223113

Output

輸入表示:1xx22xxx3x444。結果變成 13x22444xxxxx

checksum = 1×0+3×1+2×(3+4)+4×(5+6+7)=99

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)

Changelog

Just observe 👀