script (⏱,💰)

参考入門ガイドを完了していない場合は、参照してください。

Puzzling Pyramids は、Cairo のデータ構造とアルゴリズムのタスクであり、Think Cairo の第 2 回目のタスクです。このタスクでは、バイナリツリーの問題を解決するための 2 つの小さな問題があります。

中序 DFS#

図のように、バイナリツリーを左から右に変換してリストにする必要があります。アルゴリズムに詳しい人なら、これは中序 DFS（深さ優先探索）であることがわかるでしょう。インターネット上には、多くの解説があります。

実際の cairo コードを書く際に、空の配列の定義やインデックスの方法などの問題に遭遇した場合は、https://book.cairo-lang.org/ch03-01-arrays.html を参考にしてください。

lower_chambers は Option 型ですが、Option 型の操作方法がわからない場合は、https://book.cairo-lang.org/ch06-02-the-match-control-flow-construct.html?highlight=Option#matching-with-options を参照してください。

この問題は、再帰的な方法または非再帰的な方法で解決することができます。cairo の組み込みの配列関数が十分ではないため（前のタスクで感じたかもしれません）、実際の書き方はより複雑になるかもしれません。したがって、再帰的な方法をお勧めします。

まず、公式のフィボナッチの再帰バージョンを見てみると、原理は同じです。https://github.com/starkware-libs/cairo/blob/main/examples/fib_array.cairo

再帰関数は、各ノードで「左の葉を判定して再帰的に実行 -> ノードを追加 -> 右の葉を判定して再帰的に実行」というロジックを実行する必要があります。

重要なポイントは次のとおりです：

• 再帰的に要素をリストに追加するためには、そのリストに ref キーワードを追加する必要があります。再帰中に同じ配列を参照するためです。
• 再帰関数には Cloneと Dropも実装する必要があります。PyramidIntoArray と同じように書く必要がありますが、GitHub の cairo の新しいバージョンでは少し異なる書き方をしています。
• chambers を最初にスナップショットに変換すると、所有権の問題が発生せずに複数回参照できます。その後、元の型にクローンしてリストに追加します。
• テストが合格しない場合は、use debug::PrintTrait;と[変数].print();を使用してデバッグできます。

検索パス#

第 2 の小問題では、検索パスを実装する必要があります。これも DFS ですが、最初の問題よりも難しいです。

テストケースは以下のようになります。k を検索し、[h,l,j,k] を返す必要があります。

         h
   d           l
 b    f     j     n
a c  e g   i k   m o

同様に、再帰を使用して解決します。結果を保存するためのリストを作成し、再帰関数を呼び出します。再帰関数は、次のようなロジックを実行する必要があります：

1. 任意のノードで、値がキーと一致する場合は、インデックスを返します。
2. 値がキーと一致しない場合は、left と right を調べて再帰的に実行し、配列または None を返します。
3. 子葉の再帰的な戻り値の配列を取得し、現在のインデックスを追加します。

例えば、上記のテストケースの j を再帰的に実行すると、Option::Noneと **[k].append (j)が得られます。l ノードに戻ると、[k,j].append(l)とOption::Noneが得られます。h に戻ると、[k,j,l].append (h)** となります。（上記のすべてをインデックス操作に変更する必要がある理由は、以下の注意事項を参照してください）

cairo は append_front をサポートしていないため、後ろに追加するしかありません。最後に、取得したパスの配列を反転させるためのループを書きます。

注意事項：

• ガスが不足する場合は、再帰中にインデックスのみを操作し、最後のループでインデックスを使用して実際のアイテムを取得することをお勧めします。
• ループ時に、array を.pop_back するためには、array を.span () する必要があります。詳細については、https://github.com/starkware-libs/cairo/blob/main/corelib/src/array.cairo を参照してください。

結論#

アルゴリズムの基礎がないと、このタスクはかなり難しいです。最初は非再帰的な方法を使用しましたが、最終的には ref array の循環代入に関する言語レベルのエラーバグに遭遇しました。後で再帰的な方法を書いたところ、多くの文法の問題に遭遇し、完成するまでにかなりの時間がかかりましたが、多くのことを学びました。上記のアプローチが役立つことを願っています。