NG#2 - 二分木 - script (⏱,💰)

入門タスクを完了していない場合の参照入門ガイド

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

中順 DFS#

pyramids_02_cd51837de0

図のように、バイナリツリーを左から右に変換してリストにする必要があります。アルゴリズムに詳しい人なら、これは中順 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();を使用してデバッグできます。

パスの検索#

puzzling_pyramids_04_683fbd4b56

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

テストケースの例を以下に示します。k を検索する場合、[h,l,j,k] を返す必要があります。

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

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

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

上記のテストケースの 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 を使用する前に .span () する必要があります。詳細については、https://github.com/starkware-libs/cairo/blob/main/corelib/src/array.cairo を参照してください。

結論#

ng3_result

アルゴリズムの基礎が不十分な場合、このタスクはかなり難しいです。最初は非再帰的な方法を使用しましたが、最終的には ref array の循環代入に関する言語レベルのエラーバグに遭遇しました。後で再帰的な方法を書いたところ、多くの文法の問題に直面し、長い時間をかけて完成させましたが、非常に有益な経験でした。上記のアイデアが役立つことを願っています。