script (⏱,💰)

script (⏱,💰)

HomeStarkNetMyShell

NG#2 - Binary Tree

#StarkNet321
AI Translation
This post is translated from Chinese into English through AI.View Original
AI-generated summary
The text discusses the Puzzling Pyramids task in Cairo, which involves solving binary tree problems. It suggests using the in-order depth-first search (DFS) algorithm to convert the binary tree into a list. It provides references for defining empty arrays and working with Option types in Cairo. The task can be solved using either recursive or non-recursive methods, with the recursive approach being recommended. The text also mentions the need to append elements to a list using the "ref" keyword and provides an example of a recursive function implementation. It further discusses the second part of the task, which involves finding a search path in the binary tree using DFS. It suggests using a recursive function and provides an example of how to implement it. The text also mentions some important points to consider, such as using indices instead of actual values to avoid running out of gas and using the .span() function to remove the last value from an array. Overall, the text highlights the challenges of the task and suggests that a good understanding of algorithms is necessary to complete it successfully.

Reference for those who have not completed the introductory task Installation Guide

Puzzling Pyramids is the second task in the Think Cairo data structures and algorithms series, focusing on binary tree problems. There are two subtasks in total.

Inorder DFS#

pyramids_02_cd51837de0

As shown in the figure, the binary tree needs to be converted into a list from left to right. If you have some understanding of algorithms, you will know that this can be achieved using inorder depth-first search (DFS). There are many explanations available on the internet.

When writing Cairo code, if you encounter issues such as how to define an empty array or how to index, you can refer to https://book.cairo-lang.org/ch03-01-arrays.html.

"lower_chambers" is of type Option, and if you are unsure how to operate on Option types, you can refer to https://book.cairo-lang.org/ch06-02-the-match-control-flow-construct.html?highlight=Option#matching-with-options.

This problem can be solved using both recursive and non-recursive approaches. However, due to the limitations of Cairo's built-in array functions (as you may have experienced in a previous task), writing the code can be more complicated. Therefore, it is recommended to use a recursive approach.

You can first take a look at the official recursive version of the Fibonacci function, as the principles are the same: https://github.com/starkware-libs/cairo/blob/main/examples/fib_array.cairo.

The recursive function should implement the logic of "check and recursively traverse the left leaf -> add node -> check and recursively traverse the right leaf" for each node.

There are a few key points to note:

  • When using recursion, the elements need to be appended to a list, and this list needs to be prefixed with the "ref" keyword, as the same array will be referenced during recursion.
  • The recursive function also needs to implement Clone and Drop, similar to the PyramidIntoArray task. However, the syntax in the newer version of Cairo in the GitHub repository is slightly different.
  • Convert "chambers" to a snapshot first, so that it can be referenced multiple times without ownership issues. Then use "clone" to convert it back to its original type and append it to the list.
  • If the tests fail, you can use use debug::PrintTrait; and [variable].print(); for debugging.

Search Path#

puzzling_pyramids_04_683fbd4b56

The second subtask requires implementing a search path, which is also done using DFS but is much more challenging than the first task.

Here is an example of the test case: to find "k", the expected result is [h, l, j, k].

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

Similarly, this can be solved using recursion. Create a list to store the results, and call the recursive function. The recursive function should implement the following logic for each node:

  1. If the value of the node is the key, return the index.
  2. If the value is not the key, check the left and right nodes recursively and return an array or None.
  3. Obtain the array returned by the recursive call on the child leaf and append the current index to it.

For example, when recursively calling on node "j" in the above test case, you will get Option::None and [k].append(j). When returning to node "l", it will be [k, j].append(l) and Option::None. When returning to node "h", it will be [k, j, l].append(h). (All of these operations need to be changed to index operations, as explained in the following notes)

Since Cairo does not support append_front, you can only append to the end and then use a loop to reverse the resulting path array.

Notes:

  • If you encounter "out of gas" errors, it is recommended to only operate on indices within the recursion. Use the indices in the final loop to retrieve the actual items.
  • When using a loop, the array needs to be .span() before using pop_back to remove the last value. For more details, refer to https://github.com/starkware-libs/cairo/blob/main/corelib/src/array.cairo.

Summary#

ng3_result

If you have a weak foundation in algorithms, these tasks can be quite challenging. Initially, I used a non-recursive method, but encountered a bug related to circular assignment of ref arrays at the language level. Later, when writing the recursive solution, I faced many syntax issues and it took me a long time to complete. However, I gained a lot from it. I hope the above explanations are helpful to you.

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.