列印佇列

代碼來臨 2024 年第 5 天

第 1 部分

會有秩序！

這將會是一件很酷的事。

我喜歡新增的警告，即不應考慮未包含在更新中的頁面規則。

我對如何解決這個難題有一個模糊的想法。

但是我需要在這裡制定我的策略以保持清晰並確保我準備好編寫實際程式碼。

我希望跌跌撞撞地制定策略

這很有趣。我覺得我知道如何以過度檢查的方式解決這個問題。

這就是我的想法。

將兩個清單中的第一個轉換為頁碼目錄，其前面必須有任何/所有頁面：

來自此：

47|53
97|13
97|61
...

對此：

{
  47: [53],
  97: [13, 61],
  ...
}

但是我該如何使用它？

等等。旋轉！ ！

查看第一個範例頁面更新：

75,47,61,53,29

並檢視其正確順序的深入證明...

...讓我想到了過於無聊的方法：

Find all page ordering rules whose two pages are both in the page update list
Find the index of each page
If the first is less than the second
  The order is correct

性能方面的缺點：

• 這需要遍歷每個清單的整套頁面順序規則
• 似乎是檢查所有可能的數字對的任務中的階乘

不太確定這種方法。

返回我的鍵物件和「之前」列表。

如果我讓物件更全面怎麼辦：

47|53
97|13
97|61
...

becomes:

{
  47: [ [53], [] ],
  53: [ [], [47] ],
  97: [ [13, 61], [] ],
  13: [ [], [97] ],
  61: [ [], [97] ]
}

• 第一個嵌套清單列出了必須位於其先前的數字
• 第二個嵌套清單列出了其後必須出現的數字

理論上（和偽代碼）：

For each number in the list
  Create an ordered list of the previous numbers
    Check each one for inclusion in the catalogued list associated with that number
      If they are all in there
        Set a flag to true
  Create an ordered list of the subsequent numbers
    Check each one for inclusion in the catalogued list associated with that number
      If they are all in there
        Set a flag to true
  If both flags are true
    Number is in the correct order

範例演練：

75

Before: []
After: [47,61,53,29]

Catalog:
{
  75: [ [29, 47, 53, 61, 13], [97] ]
}

Before: Empty - success

After: [True, True, True, True]

All True? Yes - success

Correct Order

我絕對認為是時候編寫一個至少可以建立我的目錄物件的演算法了。

建構編目演算法

將規則從更新清單中分離出來：

let [rules, updates] = input.split('\n\n')

將輸入解析為包含 2 項的列表，其中每個項目都是一個數字：

rules = rules.split('\n').map(el => el.split('|').map(Number))

將該列表縮減為一個充滿鍵和列表值的物件：

rules = rules.reduce((obj, item) => {
  if (!(item[0] in obj)) {
    obj[item[0]] = []
  }
  obj[item[0]].push(item[1])
  return obj
}, {})

這是否如預期般運作？

是的，它輸出這個物件：

{
  '29': [ 13 ],
  '47': [ 53, 13, 61, 29 ],
  '53': [ 29, 13 ],
  '61': [ 13, 53, 29 ],
  '75': [ 29, 53, 47, 61, 13 ],
  '97': [ 13, 61, 47, 29, 53, 75 ]
}

請注意，我回到只記錄必須在任何給定數字之後的數字。

那是因為我認為我不必檢查雙方。

我可能錯了。

但我將在這個假設下繼續。

檢查每個數字後面的所有數字

我將處理第一個範例更新，它應該顯示為正確的。

首先，我需要將輸入解析為數字列表：

updates = updates.split("\n").map((el) => el.split(",").map(Number));

然後，提取第一個清單進行測試：

let test = updates[0];

現在開始真正的工作。

第一次嘗試：

47|53
97|13
97|61
...

它似乎一直有效，直到我在第五個範例清單項目上嘗試它：

{
  47: [53],
  97: [13, 61],
  ...
}

我的演算法檢查每個數字是否作為目錄中的鍵存在，並檢查其關聯列表中的所有數字是否匹配。

但是13不在目錄中。我的演算法錯誤地假設了正確的判決。

當它達到 29 時，由於沒有更多的數字，它也假設是正確的。

所以，我需要調整我的策略。

第二次嘗試：

75,47,61,53,29

這將為每個範例清單產生正確的答案！

它正確檢查每個數字後面出現的數字子清單中的每個數字是否包含正在檢查的數字（緊鄰子清單之前的數字）。

因此，在下列情況下：

Find all page ordering rules whose two pages are both in the page update list
Find the index of each page
If the first is less than the second
  The order is correct

當遇到 13 時，它會尋找 29 並看到 13，這表示它們的順序錯誤。

將其插入歸約並將中間數字相加

沒有我想的那麼難：

47|53
97|13
97|61
...

becomes:

{
  47: [ [53], [] ],
  53: [ [], [47] ],
  97: [ [13, 61], [] ],
  13: [ [], [97] ],
  61: [ [], [97] ]
}

它為範例輸入產生正確的答案！

它會如何處理我的拼圖輸入？ ？ ？

它再次產生了正確答案！ ！ ！

嗚呼！ ！ ！

我覺得我有一段時間想太多了。當我看到什麼不起作用時，答案就變得清晰了。

有趣的東西！

第二部會帶來哪些新挑戰......？

第2部分

排序練習

我可能應該預見到這一點。

值得慶幸的是，我認為我的演算法已經為此做好了準備。

我必須對每個清單進行排序。

排序的工作原理是比較兩個值並根據三個結果之一執行兩件事之一：

• 如果排序函數傳回 -1，則第一個值位於第二個值之前
• 如果傳回 1，則第二個值應位於第一個值之前
• 如果傳回 0，則不會移動任何值，因為它們相等

我的演算法產生布林值列表。

當所有布林值都為 true 時，正確產生它們的數字位於所有布林值之前。

但是，如果任何布林值為 false，則其中一個數字應位於目前數字之前。

但是如果我要比較兩個數字，而且它們的兩個清單都有錯誤值，我怎麼知道哪個應該排在第一位？

我真的只有一種方法來解決一個列表全部為真而另一個列表不為真，或者兩者都為真的情況。

嗯嗯。

我認為我需要一次對兩個數字而不是數字列表執行測試。

與排序的工作原理完全相同：a 與 b

將我的演算法調整為一對一戰鬥而不是一對多戰鬥

經過一些令人費解的、三元檢查和事後猜測，我得出了一個可行的演算法：

47|53
97|13
97|61
...

在每個順序不正確的範例更新上運行它會產生一個正確排序的清單！

我很高興能在兩個輸入的所有清單上運行它，並希望今天能獲得兩顆當之無愧的金星！

俯瞰巨大...小細節

我在範例輸入上運行了演算法，得到的數字比顯示的要大。

我不知道為什麼。列印出每個正確排序的列表，證明其元素的順序正確。

然後我重新閱讀了說明：

僅限順序錯誤的更新

說得有道理！我正在將每個列表的中間值相加！

修正此問題需要進行一點 slice() 來複製列表，然後比較字串化版本：

{
  47: [53],
  97: [13, 61],
  ...
}

中提琴！我得到了示例輸入的正確答案。

手指交叉，我得到它作為我的拼圖輸入！

確實！ ！ ！

甜甜！ ！

兩顆金星。都是我的！

又一個有趣的謎題。

花了幾天時間思考並得出一些策略。

但我最後在迷霧中找到了出路。

進入第六天！

以上是列印佇列的詳細內容。更多資訊請關注PHP中文網其他相關文章！