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/
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/533536/3dc214d7-b813-8a50-fabd-f359bfa20db5.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/533536/8b65a7d8-2bb1-0b40-23cb-750497b008a8.png)

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++
// 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
// 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++
// 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
// 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++
// 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
// 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++
// 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
// 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++
// 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
// 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
// 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++
// c++
auto s = "abc"s;
auto c = s[0]; // okay
```
```rust
// 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++
// c++
const auto a = x>0 ? 1 : 2; // as usual
```
```rust
// 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++
// c++
for(auto i = 0 ; i < v.size(); i++)
    x++, y--, z+=1; // save lines
```

```rust
// 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++
// c++, 
if ( auto a = ++i; --a > 0 )
    // do something
```
```rust
// 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

```c++
// concept
temp = a; // reserve the old value
a = b;    // update value
c = temp; // assign old value to other var
```
```c++
// c++ equivalent code
c = std::exchange(a, b);
```
```rust
// 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++
c = std::exchange(a, a + 5); // Okay
```
```rust
// 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