script (⏱,💰)

入門タスクを完了していない場合は、インストールガイドを参照してください。

Racing Riverboats は、Cairo データ構造とアルゴリズムのタスク「Think Cairo」の 3 番目のタスクであり、配列内の重複値を検索する問題を解決します。このタスクには 2 つの小問題があります。

リスト内の重複値のインデックス#

最初の問題「鱷の探索」は、本質的には配列内で重複した項目を見つけ、そのインデックスを別の配列にマークするものです。

比較する必要がある配列のサブ要素は、u32、u32、felt252 からなる構造体であり、初期データはArray<Obstacle>です。

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

最初のアイデアは、Felt252Dictを使用し、Obstacle をループして Felt252Dict に追加することです。これは、Solidity のmapping(index => struct)に似ています。値が存在する場合はインデックスを記録し、存在しない場合は挿入します。

最初のバージョンのコードを書いた後、Obstacle のサブ要素であるArray<felt252>が Copy できないため、felt252Dict.get(index) -> Obstacleは無効です。したがって、アプローチを変える必要があります。

辞書を使用しない場合、2 つのネストされたループを使用して Obstacle を比較し、重複したものを一時リストに追加し、その後インデックスを見つける必要があります。しかし、テストの結果、ガス不足になり、実際には 320 万のガスが必要であり、目標の 180 万を超えてしまいます。最適化が必要です。

テストケースのガスリミットを分析すると、2 つの Obstacle を 1 回比較するガスコストは 26100 です。テストケースには 13 個の Obstacle が含まれているため、1800000 ガスで 69 回以下の比較しかできません。一方、上記のアルゴリズムでは、すべての比較には 78 回（1+2+...+12）の比較が必要です。したがって、比較回数を減らす必要があります。

そのため、dict のテストケースの方法を使用し、Felt252Dict にインデックスを格納して取得することで、不要な比較を減らすことができます。しかし、最終的にはガスが不足するため、比較回数を減らすことはできません。そのため、単一の比較コスト、具体的には Obstacle.description の比較を最適化する必要があります。

しばらくアイデアが浮かばずに詰まってしまったので、NG のチューターに直接相談し、Obstacle をハッシュ化することで O (n) の時間計算量で目標を達成できるというアイデアをもらいました。

では、どのように struct をハッシュ化するのでしょうか？最初に Obstacle の#[derive(Drop)]を#[derive(Drop,Serde)]に変更し、次のコードを使用してハッシュを取得しました。

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

しかし、オンラインテストに合格できないことがわかりました。なぜなら、Obstacle は変更できないからです。

Obstacle を変更せずに struct のすべてのプロパティを手動でパックしてハッシュ化することができます。

ハッシュ化が成功したら、dict にinsert (index, hash)とget(index)を行うだけで、重複するインデックスを取得できます。その後、コードはテストを正常にパスします。

また、u_size と felt252 の相互変換に関しても、intoとunwarpを使用する必要があります。ドキュメントを参照して解決することをお勧めします。

もう 1 つの落とし穴は、インデックスが 0 で値も 0 の場合、dict.get(0)とdict.get(存在しないインデックス)の両方が 0 を返すため、判定が誤ってしまうことです。これには、use nullable::{NullableTrait, match_nullable, FromNullableResult};ライブラリを使用して解決する必要があります。この部分については、nullable のソースコードを参照して学習することをお勧めします。

まとめると、最初の問題のポイントは次のとおりです：

• struct をハッシュ化する方法
• u_size と felt の相互変換
• Felt252Dict の new、get、insert
• nullable の使用

ループ内の条件文で Option を返す#

この問題では、配列（川）を超えるために最小限のジャンプ数を返す必要があります。ジャンプの長さは 3 を超えてはいけません。最初のセルと最後のセルが鱷である場合は、Option::None を返します。

アプローチ：ネストされたループを使用し、ジャンプごとに 3、2、1 を判断し、ジャンプできる場合はジャンプし、ステップ数を + 1 します。ジャンプできない場合は、直接 Option::None を返し、複数回のジャンプで目標を達成します。

この問題の実装は比較的簡単です。最初の問題で取得したインデックス配列を使用して、2 つのループで解決します。主な問題は、テストでガス不足になることです。つまり、空の川を判断することと、始点と終点が鱷であることを判断することを事前に行い、ガスを節約するためです。

テストケースを比較し、print を活用して、どこにジャンプしたかを確認することをお勧めします。

最初の問題で既に述べたいくつかの落とし穴がありますので、事前に修正しておくと良いでしょう。

最後に verify を提出した後、テストに合格できない小さなバグがあります。ループの中断条件は river.len なのか river.len-1 なのかを注意する必要があります。

この問題では、多くのループ内での戻り値を扱う必要がありますが、cairo には return 文がないため、誤りが発生しやすく、多くの修正が必要です。

また、Option に関連する操作にも取り組むことになります。

まとめ#

Cairo のメモリは不変であり、スロットをカバーすることはできないため、いくつかのテクニックが必要です。関連する操作に精通することは、将来の開発に役立ちます。