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