代碼日到來鍵盤難題

第 21 天：鍵盤難題

GitHub 儲存庫 - 解決方案

今天的挑戰很難，我花了兩天才解決，也完全理解了邏輯。今年我發現，我很難理解這些說明的意圖。

我希望您能像我一樣從這個挑戰和解決方案中學到了一些東西。我發現每年參加“Advent of Code”，我都會學到很多東西，這就是為什麼我喜歡嘗試不同的語言或推動自己走出舒適圈。我認為 Advent of Code 更多的是一個學習/發展的機會，開發者應該分享他們的知識和想法，而不是僅僅將其視為一場競賽。

今天再次嘗試 Python，我對這個解決方案很滿意。我今天學到的東西是；在類別聲明上使用 @dataclass(frozen=True) 註解的不可變類別。

我創建了 Location 類別作為輔助類別來導航和更新座標（有點像我之前在某些 C# 解決方案中使用 Point 類別所做的那樣。

作為具有 C# / .Net 強類型背景的人，我嘗試在程式碼中新增類型，以幫助我視覺化在這個複雜問題中我正在處理的內容。我在編寫 TypeScript 時也習慣這樣做，所以幾乎是第二天性。

今天的問題

**第一部分**介紹了導航和控制多個機器人以將指令傳遞給下一個機器人以在數字鍵盤上輸入代碼的問題。

第二部分透過一系列機器人和方向鍵盤增加複雜性來解決這個問題，展示了多級依賴關係的指數性質。

演練

由於我們已經知道方向和鍵盤的佈局，我們可以建立所有位置映射和他們可以移動的方向的字典。

快取（cache 和 move_cache）

快取：儲存先前計算的最短序列，以避免冗餘運算，提高效能。

moves_cache：儲存鍵盤上任兩個按鈕之間的所有有效移動序列，預先計算以便快速尋找。

最短長度計算（shortest_length）

遞歸計算輸入給定程式碼的最短按鍵順序。

透過迭代等級 (cur_深度) 直到極限 (深度_限制) 來處理鍵盤的多層連結。

*在位置之間移動 (moves_ Between_positions)
*

計算鍵盤上兩個按鈕之間的所有有效運動序列，確保機器人不會透過指向無效位置（間隙）來恐慌。

快取初始化（create_cache_moves）

預先計算數字鍵盤和方向鍵盤上所有按鈕對的有效移動序列，從而節省運行時計算。

求解函數，然後循環輸入，透過將序列長度乘以程式碼的數字部分來計算其複雜性，然後根據謎題的要求簡單地總結所有程式碼的複雜性。

排列

排列有什麼作用？

Python 中的排列函數（來自 itertools 模組）產生項目集合的所有可能的有序排列。

例如：

from itertools import permutations

items = ['a', 'b', 'c']
list(permutations(items))

這將產生：

[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

每個排列都是一個唯一的序列，包含原始集合中的所有項目，但順序不同。

為什麼使用排列而不是組合？

排列：

產生項目集合的所有可能的有序排列。
項目的順序很重要。

然而，
組合：

產生項目集合的所有可能的無序選擇。

項目的順序並不重要。

為什麼順序在這種情況下很重要？

鍵盤導航：每次移動後，機器人在鍵盤上的位置都會發生變化，因此執行移動的順序會直接影響結果。

有效移動檢查： 此功能檢查導航過程中中間位置的有效性。更改移動順序可能會導致無效路徑。

組合何時有用？

在移動順序無關緊要的情況下或您選擇移動或按鈕的子集而不關心其順序的情況下，組合可能很有用。

目前使用排列是必要的，因為移動順序對於鍵盤導航很重要。用組合替換它會破壞程式的邏輯。如果任務需要找到所有獨特的動作或按鍵組（無論順序如何），那麼組合會更合適。

這個難題中最困難的部分是想出一種漂亮而乾淨的方法來追蹤機器人指令的深度（初始）等級——花了我一些時間，以便我可以全神貫注於它。

以上是代碼日到來鍵盤難題的詳細內容。更多資訊請關注PHP中文網其他相關文章！