NG#3 - 字典翻譯： - script (⏱,💰)

racing riverboats start

没有完成入门任务的参考安装入门

Racing Riverboats 是 Cairo 數據結構與算法任務 Think Cairo 的第三個任務，主要是使用字典查詢數組中重複值的問題，共有兩個小題。

列表中重複值的索引#

第一題「尋找鱷魚」，本質上是在 array 中找到重複項，標記出 index 存到另一個 array 中。

array 中需要對比的子元素是個 struct，由 u32, u32, felt252 組成。起始數據是一個Array<Obstacle>

#[derive(Drop)]
struct Obstacle {
    length: u32,
    width: u32,
    description: Array<felt252>
}

直接思路是用 Felt252Dict，循環 Obstacle 並 pop 出來放到 Felt252Dict 中，類似 solidity 中的mapping(index => struct)，如果 get 有值，就記錄 index，沒有就 insert。

寫出第一版代碼後發現由於 Obstacle 子元素Array<felt252>不能 Copy，所以felt252Dict.get(index) -> Obstacle是不合法的。所以得換個思路。

如果不使用字典，採取 2 個循環套嵌，對比 Obstacle 把重複的都加到一個臨時列表裡，然後再找出 index，結果測試時 out of gas 了，實際花了 320 萬，目標 180 萬，需要優化。

分析測試用例的 gas limit ，2 個 Obstacle 直接對比一次的 gas 成本在 26100，測試用例裡有 13 個 Obstacle，計算 1800000 gas 只能對比 69 次以下，而上面的算法全部遍歷需要對比 78 次（1+2...+12)。所以需要減少對比的次數。

然後我採取了核心庫dict 的測試用例方法，用 Felt252Dict 存 index，如果拿到了就跳過，可以減少一些不必要的對比。但最終還是會超 gas，減少對比的次數已經無法再優化。所以需要單次對比的成本，具體來說是優化 Obstacle.description 的比較。

卡了一段時間沒有思路後，找到 NG 的導師私聊，他給了思路先把 Obstacle 進行 hash 後可以複雜度 O (n) 一次達成目標。

那該如何把 struct 轉為 hash 呢？一開始我把 Obstacle 的 #[derive(Drop)]改成了#[derive(Drop,Serde)]，用以下代碼獲取 hash：

let mut raw_data = Default::default();
obs.serialize(ref raw_data);
let hash = poseidon_hash_span(raw_data.span());

後來發現無法通過線上測試，因為 Obstacle 不能修改。

如果不修改 Obstacle，可以把 struct 中的所有屬性手動打包再來 hash。

成功 hash 後，只需要往 dict 裡 insert (index, hash) 和 get(index) 就能得到重複索引了。代碼就能順利通過測試。

中間還有很多 u_size 和 felt252 的互換，需要用into和unwarp，你可以查文檔解決。

這兒的另一坑是，如果 index 是 0 且值也是 0，dict.get(0)和 dict.get(不存在索引)都返回 0，判斷就會錯誤，無法通過後一題的相關測試。

這需要用 use nullable::{NullableTrait, match_nullable, FromNullableResult}; 庫來解決，這部分建議看nullable 的源碼學習。

總結一下，第一題的知識點有：

這題是返回最少需要跳幾步能大於數組（河流），步長不能超過 3。如果第一格和最後一格是鱷魚，返回 None。

思路：通過循環套嵌，每次跳躍判斷 3，2，1，能跳就跳，步數 +=1；如果都不能跳，直接返回 Option::None，多次跳躍達成目標。

這題實現比較簡單，拿到第一題得到的 index array 後，用 2 個 loop 解決。主要是測試會遇到 out of gas 的問題，也就是說判斷空河流和判斷起點終點是鱷魚，都需提前判斷以節省 gas。

建議對比測試用例，活用 print，看看每步跳到哪兒了。

有的坑第一題中已經說過，如果提前寫好就不用再改。

最後提交 verify 後還有個小 bug 無法通過測試，需注意判斷 loop 中斷的條件是 river.len 還是 river.len-1。

這題涉及很多 loop 中返回值，cairo 中沒有 return，容易出錯，需要多修改。

還會練習到很多 Option 相關的操作。

由於 cairo 的內存是不變的，並不能覆蓋 slot，就需要一些技巧來達到 dict 的效果。熟悉相關操作對後續開發會很有幫助。

racing riverboats