If you haven't completed the introductory task, refer to the Installation Guide
Racing Riverboats is the third task of Think Cairo, a Cairo data structure and algorithm task. It mainly involves solving the problem of finding duplicate values in an array using dictionary queries. There are two sub-tasks in total.
Index of Duplicate Values in a List#
The first sub-task, "Finding Crocodiles," essentially involves finding duplicate items in an array and marking their indices to be stored in another array.
The sub-elements to be compared in the array are structs composed of u32, u32, and felt252. The initial data is an Array<Obstacle>.
#[derive(Drop)]
struct Obstacle {
length: u32,
width: u32,
description: Array<felt252>
}
The direct approach is to use Felt252Dict. Iterate through the Obstacles and pop them into the Felt252Dict, similar to a mapping(index => struct) in Solidity. If the value exists, record the index; otherwise, insert it.
After writing the initial version of the code, it was discovered that felt252Dict.get(index) -> Obstacle is invalid due to the fact that the sub-element Array<felt252> of Obstacle cannot be copied. Therefore, a different approach is needed.
Without using a dictionary, a nested loop can be used to compare the Obstacles, add the duplicates to a temporary list, and then find the indices. However, during testing, it ran out of gas and actually consumed 3.2 million gas, exceeding the target of 1.8 million. Optimization is needed.
Analyzing the gas limit of the test case, the cost of comparing two Obstacles once is 26,100 gas. The test case contains 13 Obstacles, so calculating 1,800,000 gas can only allow for up to 69 comparisons. However, the above algorithm requires a total of 78 comparisons (1+2+...+12) to iterate through all the Obstacles. Therefore, the number of comparisons needs to be reduced.
Then, the test cases of the core library dict were used as a reference. By using Felt252Dict to store the indices, unnecessary comparisons can be reduced. However, it still exceeded the gas limit. The number of comparisons cannot be further reduced. Therefore, the cost of a single comparison needs to be optimized, specifically the comparison of Obstacle.description.
After being stuck for a while without any ideas, I reached out to the NG mentor for guidance. He provided a solution to hash the Obstacles, which can achieve the goal in O(n) complexity.
So how can the struct be hashed? Initially, I changed #[derive(Drop)] of Obstacle to #[derive(Drop,Serde)] and used the following code to obtain the hash:
let mut raw_data = Default::default();
obs.serialize(ref raw_data);
let hash = poseidon_hash_span(raw_data.span());
Later, it was found that it couldn't pass the online test because Obstacle cannot be modified.
If Obstacle cannot be modified, all the attributes of the struct can be manually packed and then hashed.
After successfully hashing, it is only necessary to insert (index, hash) into the dict and get(index) to obtain the duplicate indices. The code can then pass the tests smoothly.
There are also many conversions between u_size and felt252, which require the use of into and unwarp. You can refer to the documentation to solve them.
Another pitfall here is that if the index is 0 and the value is also 0, both dict.get(0) and dict.get(nonexistent index) will return 0, leading to incorrect judgments and failing the related tests of the second sub-task.
This can be solved by using the library use nullable::{NullableTrait, match_nullable, FromNullableResult};. It is recommended to study the source code of nullable for this part.
To summarize, the key points of the first sub-task are:
- How to hash a struct
- Conversions between u_size and felt252
- Felt252Dict's new, get, and insert methods
- Usage of nullable
Option Return in Conditional Statements in Loops#
This sub-task involves returning the minimum number of steps needed to surpass the array (river) without exceeding a step length of 3. If the first and last cells are crocodiles, return None.
The approach is to use nested loops. Each time a jump is made, check if it can be done with 3, 2, or 1 step. If it can be done, make the jump and increment the step count. If none of the jumps can be made, return Option::None. Repeat the jumps multiple times until the goal is achieved.
The implementation of this sub-task is relatively simple. After obtaining the index array from the first sub-task, it can be solved using two loops. The main challenge is encountering out of gas issues during testing, which means that checking for an empty river and checking if the starting and ending points are crocodiles should be done in advance to save gas.
It is recommended to compare the test cases and make use of print statements to see where each jump takes place.
Some pitfalls have already been mentioned in the first sub-task, so if they are addressed in advance, there is no need to make further changes.
After submitting the verification, there was a small bug that prevented passing the tests. It is important to note whether the condition for ending the loop is river.len or river.len-1.
This sub-task involves many return values within loops, and since Cairo does not have a return statement, it is easy to make mistakes and requires multiple modifications.
It also provides practice with various operations related to Option.
Summary#
Since the memory in Cairo is immutable and does not allow slot overriding, some techniques are needed to achieve the effect of a dictionary. Familiarity with these operations will be helpful for future development.