script (⏱,💰)

Reference to the introductory task that has not been completed Installation Guide

Puzzling Pyramids is the second task of Think Cairo for data structures and algorithms in Cairo. It mainly solves binary tree problems and consists of two subtasks.

Inorder DFS#

As shown in the figure, the binary tree needs to be converted from left to right into a list. If you have some understanding of algorithms, you will know that it is an inorder DFS (Depth-First Search), and you can find many explanations on the internet.

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

lower_chambers is of Option type. If you don't know 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 methods. However, due to the limitations of Cairo's built-in array functions (as you may have experienced in a previous task), it may be more complicated to write using non-recursive methods. Therefore, it is recommended to use recursion.

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

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

There are several key points:

• When using recursion, the elements need to be appended to the list, and the list needs to be prefixed with the "ref" keyword, so that the same array can be referenced in the recursion.
• The recursive function also needs to implement Clone and Drop, which is the same as in PyramidIntoArray. However, the syntax in the Cairo library on GitHub is slightly different in the new version.
• chambers should be converted to a snapshot first, so that it can be referenced multiple times without causing ownership issues. Then use clone to convert it back to the original type and append it to the list.
• If the test fails, you can use use debug::PrintTrait; and [variable].print(); for debugging.

Search Path#

The second subtask requires implementing a search path, which is also a DFS but much more difficult to write than the first subtask.

The test case is as follows. 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, use recursion to solve the problem. Create a list to store the results, call the recursive function, and the recursive function needs to implement the following for each node:

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

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

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

Notes:

• If you encounter "out of gas" errors, it is recommended to only operate on indices in the recursion, and use indices to retrieve the actual items in the final loop.
• When looping, 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#

If you don't have a good foundation in algorithms, the tasks can be quite difficult. At first, I used a non-recursive method, but encountered a bug in the language that caused a circular assignment error with ref arrays. Later, when writing the recursive solution, I encountered many syntax issues and it took a long time to complete, but I gained a lot from it. I hope the above explanations are helpful to you.