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

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的源码学习。

总结一下，第一题的知识点有：

• 如何hash一个struct，
• u_size和felt的互相转换，
• Felt252Dict的 new, get 和 insert
• nullable的使用

循环中的条件语句返回Option

这题是返回最少需要跳几步能大于数组（河流），步长不能超过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的效果。熟悉相关操作对后续开发会很有帮助。