script (⏱,💰)

以下のテキストを日本語に翻訳してください：

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

Racing Riverboats は、Cairo データ構造とアルゴリズムのタスクである Think Cairo の 3 番目のタスクであり、配列内の重複値を検索するための辞書クエリの問題を扱います。2 つの小問題があります。

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

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

比較する必要のある配列のサブ要素は、u32、u32、felt252 からなる struct です。初期データは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 回以下の比較しかできません。一方、上記のアルゴリズムでは、すべての Obstacle を比較するために 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 つの落とし穴は、index が 0 で値も 0 の場合、dict.get(0)とdict.get(存在しないインデックス)の両方が 0 を返すため、判断が誤ってしまい、後の問題の関連するテストに合格できなくなることです。

これには、use nullable::{NullableTrait, match_nullable, FromNullableResult};ライブラリを使用して解決する必要があります。この部分は、nullable のソースコードを参照して学習することをお勧めします。

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

• 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 のメモリは不変であり、スロットを上書きすることはできないため、辞書の効果を得るためにはいくつかのテクニックが必要です。関連する操作に慣れることは、将来の開発に役立ちます。