How is Rust in leetcode ?

#How is Rust in Leetcode?

#Motivation
To be familiar with Rust, doing practices is necessary. By resolving algorithm questions, I'm hoping to know more about how data structure is like in Rust. This is why leetcode comes to picture

Note: This article was to share feeling/feedback and it could be personal and offensive. Please bear with me

Leetcode - Coding with online judge

Currently there are over 1200+ questions with label as easy, mediam and hard

The interface
https://leetcode.com/problemset/algorithms/

As we saw, multiple languages were supported from javascript to c and of course RUST is one of them

Rust info

1. 1.31.0 (cannot config) Note: leetcode didn't say it and this was found from other forums
2. Edition=2018 (cannot config)
3. Stable(cannot config)
4. No external crate
5. debug ? release ? TBC

Summary: Though the version is a little bit old, it's quite enough to solve questions

#Sharing
Note: In the following examples, I'm gonna take C++ as control group because this is the only language I knew before Rust

##Pros
###Iterator
Iterator trait of Rust is more straight-forward than c++ to iterate data with combinator. What's more, use fold/try_fold to get a result with grace

// c++ ugly code,
const vector<int> v{1,2,3,4,5};
auto ret = -1;
for( auto i = 0; i < v.size(); i++){
    if (v[i] == 3){
        ret = i;
        break;
    }
    // do some complicated logic
}

return ret; // return 2

// c++ using std find, still a little bit redundant
auto it = std::find(v.begin(), v.end(), [](int cur){
    if (cur == 3)
        return true;
    ... // do some complicated logic
    return false;
})
return it == v.end() ? it-v.begin() : -1; // return 2

// c++ using c++17 fold expression
// No, that's too evil to read, not gonna happened here

// rust equivalent code with nicer readability
vec![1,2,3,4,5].into_iter().enumerate().try_fold(-1, |acc, (i, inner)| {
    if inner == 3 {
        Err(i as i32)
    }else {
        // do some complicated logic
        Ok(acc)
    }
}).unwrap_or_else(|e|e) // return 2

Derive hashmap in Rust

Since hashmap is widely used in leetcode questions, there are some cases we have to map our own struct (Ex. pair/tuple/vector) to record some info.
In C++, it's unordered_map. If we wanna use self-defined struct as key of unordered_map, we have to impl our own hasher as well. It's not cool and time-consuming to invent our own untested-hasher
Though there are some tricks that we could skipping inventing hash function ourselves, that's another story which will not be covered here

In Rust, fear not. We just simply derive hash/Eq/`PartialEq. This is really convenient and awesome

// c++, terrible experience to have customized key of unordered_map
struct Key
{
  std::string first;
  std::string second;
  int         third;
    
  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }    
};

struct KeyHasher
{
  std::size_t operator()(const Key& k) const
  {
    using std::size_t;
    using std::hash;
    using std::string;

    return ((hash<string>()(k.first)
             ^ (hash<string>()(k.second) << 1)) >> 1)
             ^ (hash<int>()(k.third) << 1);
  }
};

std::unordered_map<Key,std::string,KeyHasher> m6 = {
  { {"John", "Doe", 12}, "example"},
  { {"Mary", "Sue", 21}, "another"}
};

// rust
#[derive(Hash, Eq, PartialEq)]
struct A(String, String, i64);
let mut m = std::collections::HashMap::new(); // easy declaration
m.insert(A("a".to_string(), "b".to_string(), 3), 4);

##Cons
Result and Option could be a double-edged sword, sometimes it's a little bit annoying

####Example 1 - hashmap
The hashmap data structure is widely used in leetcode questions. However, c++ hashmap is more straightforward than rust

// c++
std::unordered_map<int, int> m;
// insert data
m[1]=2;
// get data
const auto r = m[1];
// do something if exist or else
if(m.count(1))
    m[1]=3;
else
    m[1]=4;

// rust
std::collections::hashmap<int, int> m; // long declaration
// insert data
m.insert(1, 2);
// get data
let val = m.get(1).unwrap_or(...);
// do something if exist or else
m.entry(1).and_modify(|inner|*inner=3).or_insert(4); // Not cool
m.get_mut(&1).and_then(|inner| *inner=3); // Not cool

Note: We don't wanna deal with Result/Option when time is of the essence

Example 2 - linked-list

Linkedlist-like questions are about 15% number among questions. Accessing linked-list in Rust is quite frustrated. I think Rust doesn't encourage people using self recursion ? Because most of the time people eventually recur to limbo and get lost

Considering a classic question to find the maximum depth of binary tree,

// c++, neat and straight-forward
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int maxDepth(TreeNode *root)
{
    return root == NULL ? 0 : max(maxDepth(root -> left), maxDepth(root -> right)) + 1; // quite straight-forward
}

// rust
pub struct TreeNode {
   pub val: i32,
   pub left: Option<Rc<RefCell<TreeNode>>>,
   pub right: Option<Rc<RefCell<TreeNode>>>,
}
pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
    root.map_or(0, |n| {
        1 + Self::max_depth(n.borrow().left.clone())
            .max(Self::max_depth(n.borrow().right.clone()))    // um....at first glance, why borrow() ? 
    })
}

Note: In Rust, it's painful to deal with borrow(), whether clone or not, Rc and RefCell just because to fight mysterious borrow checker (exhausted)
Note: IMO, I'd suggest to skip all binary-tree-like problems in Rust. It would take us much much more time fixing the compiler error than the algorithm itself

####Example 3 - customized priority_queue
priority_queue is widely used in leetcode since it could sort automatically as it pushed value
In Rust, it's binary_heap. We have to impl Trait Ord to support customized sort which is not quite handy while C++ has lambda function to support as declaration of priority_queue

// c++
auto cmp = [](int a, int b) { return a > b; }; 
std::priority_queue<int, std::vector<int>, decltype(cmp)> q(cmp); // min-heap with lambda style

// rust
// built-in binary heap doesn't support. But there is an external crate, `binary-heap-plus`, would do the trick
// custom-sort heap
let heap = BinaryHeap::from_vec_cmp(vec![1,5,3], FnComparator(|a: &i32, b: &i32| b.cmp(a)));

Since leetcode can not load external crate for now, there is nothing we can do but to sort every time explicitly after pushing data

// rust, workaround to sort by closure
let mut v = vec![];
v.push(2);
v.push(1);
v.push(3);
v.sort_by(|a, b| a.partial_cmp(b).unwrap());

####Example 4 - Rust String
I'm terrified when I failed to access String in Rust by []. The indexing in String is much more important in leetcode than IRL since String are many questions' inputs. If we cannot visit String like vector, chances are we have to deal with Iterator trait or some specific API which took more time typing and fixing compiler error :(

// c++
auto s = "abc"s;
auto c = s[0]; // okay

// rust
let s = "abc".to_string();
let c = s[0]; // compiler error, wait what ?

Example 5 - one liner

• Ternary operator(:?), ternary operator is far more useful in leetcode questions than IRL. IRL, ternary operator sometimes was forbidden in C++, In Rust, they just banned it from syntax. Instead, we have to explicitly use traditional if else. It's not a good news for one-liner because they just simply hate things written in more than one line

// c++
const auto a = x>0 ? 1 : 2; // as usual

// rust
let a = if x>0 {1} else {2}; // barely acceptable

• statements compression, in C++, statements could be compressed in same line. It'd save our time for some cases, but in Rust, we simply cannot. Because we could put statements in one line, we don't have to write extra {}, that would make our code look cooler

// c++
for(auto i = 0 ; i < v.size(); i++)
    x++, y--, z+=1; // save lines

// rust, extra lines, extra typing
for i in 0..v.size() {
    x++; 
    y--; 
    z++;
}

• Operator increment, increment is another love-hated tool which is not for everyone. But with proper use, it could save our valuable time
  In C++, operator++ was supported but not in Rust, so is operator--. In such case, some nasty things cannot be done in Rust

// c++, 
if ( auto a = ++i; --a > 0 )
    // do something

// rust, always explicit
i += 1;
let a = i;
a -= 1;
if (a > 0) {
    // do something
}

• C++ std::exchange V.S Rust std::mem::replace. It's common we would update value and return old value for further use. That's why these 2 apis come to picture. They're also quite useful for functional programming

// concept
temp = a; // reserve the old value
a = b;    // update value
c = temp; // assign old value to other var

// c++ equivalent code
c = std::exchange(a, b);

// rust equivalent code
c = std::mem::replace(&mut a, b);

However, std::mem::replace has some limitation that it works not as the way we're thinking because of borrow checker (again) in which case we would feel not so comfortable. But that's totally okay in C++

// c++
c = std::exchange(a, a + 5); // Okay

// rust
c = std::mem::replace(&mut a, a+5); // compiler error, wait what ?

Example 6 - not all questions support Rust

Since Rust is recently added into leetcode languages list, there are some questions which don't support Rust,
In my experience, I'd say it's about 10-15% questions. The older the question is, the higher possibility it didn't support Rust

#Conclusion

In leetcode, I've learned a lot and become more familiar with Rust

Most of time the solutions in leetcode are short and more like 10-20 lines. It would be a challenge not only to resolve algo itself but to make solutions as short as possible while keeping the quality of readability. Hence, there are many weird tricks or black magic to get it done

However, these tricks/techniques are not as significant as they used to be in Rust even some of them were impossible since Rust instead uses more direct/explicit/secure ways to achieve the same behavior with just little extra cost

IMO, for Rust, we have to be more familiar with Rust api/trait because they are probably the only ways to resolve the issue but in C++, I believe we don't have to know too much std C++ to get it work

Both Rust and C++ are made for everyone. The difference is that Rust is for everyone to communicate well eventually while C++ is for everyone to fight with each other, literally, they would fight to the death