磁碟碎片

代碼來臨 2024 年第 9 天

第 1 部分

三相拳套。令人興奮！ ？

我所看到的各個階段的詳細說明：

1. 將記憶體表示為列表
2. 將數值從末尾移到開頭
3. 走線計算校驗和

沒有一個感覺特別困難。

其中一些實際上看起來像是另一個有趣的演算法挑戰！

列清單

我想把這個：

12345

進入此：

0..111....22222

我需要考慮：

• 使用循環
• 檢查偶數和奇數索引
• 從 0 開始將數值加 1

這是我的磁碟產生演算法：

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even 
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

就像魅力一樣！

將值從結束移動到開始

讓這一切變得更容易的是擁有磁碟上所有空位置的清單。

我需要在兩個地方更新我的演算法：

1. 一個新變數：let empty = []
2. 插入 . 後的新操作：empty.push(disk.length - 1)

在範例中測試它會顯示每個 .!

的預期索引號

這是當我將值從列表末尾移動到開頭並向前移動時將迭代的列表。

但是等等。

這可能比我想像的更困難。

我如何知道何時停止嘗試移動值？

• 我是否迭代空索引列表？我什麼時候該停止？
• 我是否向後迭代磁碟？我什麼時候該停止？

頓悟：神奇的數字 10

這是簡短範例的最後狀態：

022111222......

第一個例子：

0099811188827773336446555566..............

這表示有一個點，所有 id 都在左邊，所有空白都在右邊。

我該如何檢查該狀態？

輸入：數字 10。

連續空白空間的數量永遠不會高於 9。

所以，如果我遇到一個空白空間，向前查找 9 個空格（或到磁碟列表的末尾），並看到所有空白空間，我就知道我已經完成了碎片化。

我想我知道如何編寫這個演算法的其餘部分！

編寫我的碎片演算法

這是工作演算法：

let diskI = disk.length - 1
let emptyI = 0
while (true) {
    while (disk[diskI] == '.') {
        diskI--
    }
    disk[empty[emptyI]] = disk[diskI]
    disk[diskI] = '.'
    emptyI++
    diskI--
    if (disk.slice(empty[emptyI],empty[emptyI] + 10).every(el => el == '.')) {
        break;
    }
}

工作原理：

Two trackers: 
- one for my place in the disk
- one for my place in the list of empty slots
Do until manually escaped
  Do as long as the current place in the disk is an empty slot
    Adjust the tracker one to the left
  Swap the values at each tracker
  Decrement the disk tracker
  Increment the empty tracker
  If there are 9 empty slots contiguous with the current empty slot
    Escape the loop

幸運的是，我看到了與兩個範例相同的輸出！

計算校驗和

這看起來相當簡單明了：

let part1 = disk.slice(0, disk.indexOf('.')).reduce((checksum, id, position) => {
    checksum += (+id * position)
    return checksum
}, 0)

偽代碼：

Extract all values up to the first empty cell
Iterate through each value, amassing a total
Increment the accumulator by the product of the value and its index

成功！它為示例輸入生成正確的答案！

它對我的拼圖輸入也會有同樣的作用嗎？

...

是的！ ！ ！

嗚呼！ ！ ！

第二部會有什麼轉折？輕微的規則調整還是規模上的挑戰？

第2部分

一個有趣的轉折

是零件。現在完整了。

這肯定需要對我的演算法進行一些調整。

可能更強大地追蹤間隙和塊的大小。

實施我的第一個策略

我正在追蹤每個空的位置。

我想我需要追蹤每個空的位置以及大小。

那會是什麼樣子？

刮掉那個。也許是新策略。

使用第一個範例：

12345

檔案區塊大小為奇數：

0..111....22222

空白儲存格大小是偶數：

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even 
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

從奇數末尾和偶數開頭開始，找出大於等於奇數的偶數：

022111222......

我立即找到匹配的。

結果：

• 奇數移動
• 偶數減少
• 但是現在兩個奇數沒有間隙了
• 並且我遺失了第二個2s ID

0099811188827773336446555566..............

這個策略肯定行不通。

實施我的第二個策略

我不喜歡這個對效能的影響。

但我相信它會起作用......只要它完成運行。

對於磁碟輸入中的每個數字，我將記錄為清單項目：

1. 檔案區塊或空白儲存格
2. 長度
3. ID

舉例：

let diskI = disk.length - 1
let emptyI = 0
while (true) {
    while (disk[diskI] == '.') {
        diskI--
    }
    disk[empty[emptyI]] = disk[diskI]
    disk[diskI] = '.'
    emptyI++
    diskI--
    if (disk.slice(empty[emptyI],empty[emptyI] + 10).every(el => el == '.')) {
        break;
    }
}

將成為：

Two trackers: 
- one for my place in the disk
- one for my place in the list of empty slots
Do until manually escaped
  Do as long as the current place in the disk is an empty slot
    Adjust the tracker one to the left
  Swap the values at each tracker
  Decrement the disk tracker
  Increment the empty tracker
  If there are 9 empty slots contiguous with the current empty slot
    Escape the loop

呃，讓我們清理一下：

let part1 = disk.slice(0, disk.indexOf('.')).reduce((checksum, id, position) => {
    checksum += (+id * position)
    return checksum
}, 0)

我將透過資料類型區分間隙和檔案區塊。

移動檔案區塊在變更後的範例輸入中將如下所示：

Extract all values up to the first empty cell
Iterate through each value, amassing a total
Increment the accumulator by the product of the value and its index

每 10 萬次迭代都會涉及：

• 在大數組中搜尋項目
• 就地改數組

兩者都是非常昂貴的任務。

但這是我能想到解決這個難題的唯一方法。

所以，這就是我的方法。

編寫我的策略

這是取得上述資料架構的 JavaScript：

2333133121414131402

我將如何開始和結束我的主循環？

從檔案 ID 號碼最高的檔案開始，依照檔案 ID 號碼遞減的順序嘗試將每個檔案移動一次

似乎從後到前移動就可以滿足我的需要。

這個 for 迴圈骨架應該可以運作：

[2,4,1,4,2,5,5,3,5,2]

尋找、移動和替換

[3,3,3,1,1,1,1,1,0]

if 中的第二個子句是我最後一次除錯。太早設定最低 ID 了。

編碼磁碟印表機

我意識到我必須近乎即時地看到我的磁碟碎片。至少有一個日誌，就像範例演練一樣。

值得慶幸的是，編碼並不困難。只是我混合了兩個索引並看到一些真正奇怪的輸出的部分：

12345

• 我建立了一個字串
• 基於磁碟中項目的類型
• 無論哪種方式，我都會建立一個陣列並用 .s 或區塊的 ID 填充它

效果很好！我可以看到文件被移動到的位置，並更輕鬆地排除程式碼故障！

喜歡我所看到的

0..111....22222

看起來我的文件移動演算法有效！

最後一步是計算新的校驗和。

最後，更多數學

透過雙重歸約：

let id = 0
let disk = []
for (let i = 0; i < input.length; i++) {
    if (i % 2 == 1) {
        // Odd
        for (let j = 0; j < +input[i]; j++) {
            disk.push('.')
        }
    } else {
        // Even 
        for (let j = 0; j < +input[i]; j++) {
            disk.push(id)
        }
        id++
    }
}

• 第一個reduce為我提供了一個由ids和.s組成的分散數組
• 當項目是 id 時，第二個reduce 執行適當的數學計算，當項目是 .

有效嗎？

關於範例拼圖輸入？是的！

關於我的拼圖輸入？

...

是啊SSSS！

哇。我很驚訝。我為第 2 部分提交的數字幾乎與第 1 部分相同。我認為會更高。

我沒有興趣進一步調查。

我寧願帶著我的兩顆來之不易的金星一起走到第十天。

再見第九天！

以上是磁碟碎片的詳細內容。更多資訊請關注PHP中文網其他相關文章！