Some Rust notes II

  1. A simple example of the syntax of specifying generic type parameters, trait bounds, and lifetimes:
    use std::fmt::Display;
    fn longest_with_an_announcement<'a, T>(x: &'a str, y: &'a str, ann: T) -> &'a str
     where T: Display
    {
     println!("Announcement! {}", ann);
     if x.len() > y.len() {
         x
     } else {
         y
     }
    }
    
  2. We can put expected panic information in the expected parameter of #[should_panic]:
    #[should_panic(expected = "Guess value must be less than or equal to 100")]
    
  3. FnOnce consumes the variables it captures from the closure’s environment. To consume the captured variables, the closure must take ownership of these variables and move them into the closure when it is defined. The Once part of the name represents the fact that the closure can’t take ownership of the same variables more than once, so it can be called only once. FnMut can change the environment because it mutably borrows values. Fn borrows values from the environment immutably.
  4. An example of using a closure function as a element in a struct:
    struct Cacher<T>
     where T: Fn(u32) -> u32 
    {
     calculation: T,
     value: HashMap<u32, u32>,
    }
    impl<T> Cacher<T>
     where T: Fn(u32) -> u32 
    {
     fn new(calculation: T) -> Cacher<T> {
         Cacher {
             calculation,
             value: HashMap::new(),
         }
     }
     fn value(&mut self, arg: u32) -> u32 {
         match self.value.get(&arg) {
             Some(v)     => *v,
             None        => {
                 let v = (self.calculation)(arg);
                 self.value.insert(arg, v);
                 v
             }
         }
     }
    }
    
  5. Using sum method for iterator will take ownership so that if this statement is called:
    let v1 = vec![1, 2, 3];
    let v1_iter = v1.iter();
    let total: i32 = v1_iter.sum();
    

    we cannot use v1_iter after the call because of the reason stated above.

  6. The default value for the opt-level setting for the dev profile is 0 and the one for the release profile is 3. Add these two lines in Cargo.toml will override the default optimization level for dev profile:
    [profile.dev]
    opt-level = 1
    
  7. A cons list example written using Box<T>:
    enum List {
     Cons(i32, Box<List>),
     Nil,
    }
    use self::List::{Cons, Nil};
    fn main() {
     let test = Cons(1, 
                     Box::new(Cons(2,
                     Box::new(Cons(3, 
                     Box::new(Nil))))));
    }
    
  8. An example of creating a simple smart pointer implementing Deref and Drop traits:
    struct MyBox<T>(T);
    impl<T> MyBox<T> {
     fn new(x: T) -> MyBox<T> {
         MyBox(x)
     }
    }
    impl<T> Deref for MyBox<T> {
     type Target = T;
     fn deref(&self) -> &T {
         &self.0
     }
    }
    impl<T> Drop for MyBox<T> {
     fn drop(&mut self) {
         println!("Dropping MyBox!");
     }
    }
    
  9. Comparing with regular reference, with Rc we can create things with shared ownership and do not need to specify lifetime parameters.
  10. An example of combination of Rc and RefCell:
    use std::rc::Rc;
    use std::cell::RefCell;
    #[derive(Debug)]
    enum List {
    Cons(Rc<RefCell<i32>>, Rc<List>),
    Nil,
    }
    use crate::List::{Cons, Nil};
    fn main() {
    let value = Rc::new(RefCell::new(5));
    let a = Rc::new(Cons(Rc::clone(&value), Rc::new(Nil)));
    let b = Cons(Rc::new(RefCell::new(6)), Rc::clone(&a));
    let c = Cons(Rc::new(RefCell::new(12)), Rc::clone(&a));
    *value.borrow_mut() += 10;
    println!("{:?}\n{:?}\n{:?}\n", a, b, c);
    }
    
  11. By using Rc<T> and RefCell<T>, it’s possible to create reference cycles which creates memory leaks because the reference count of each item in the cycle will never reach 0, and the values will never be dropped.
  12. An example of using Weak<T> to avoid reference cycle and create a simple node structure: ```rust struct Node { value: i32, parent: RefCell<Weak>, children: RefCell<Vec<Rc>>, } fn main() { let root = Rc::new(Node { value: 0, parent: RefCell::new(Weak::new()), children: RefCell::new(vec![]), });

Comment system is added now

Just added a comment system using Utterances. Welcome to leave your thoughts about my blogs!

Some Rust notes

  1. io::stdin().read_line(&xx) appends new value on the target which is “xx” in this case.
  2. A tuple can have values with different types in it while an array must have the same type.
  3. A tuple with explictly type annotations example:
    let x: (i32, f64, u8) = (500, 6.4, 1);
    
  4. An array in Rust have a fixed length while a Vector can grow or shrink its size.
  5. An array with explictly type and elements’ number annotations example:
    let a: [i32; 5] = [1, 2, 3, 4, 5];
    
  6. If [6, 6, 6, 6, 6] is the desirable array, we can declare it in this way:
    let a = [6; 5];
    
  7. A good way to create a new instance of a struct that uses most of an old instance’s values but changes some is using update syntax:
    let user2 = User {
     email: String::from("user2@example.com"),
     username: String::from("user2name"),
     ..user1
    };
    
  8. An example of using derived traits of custom structs:
    #[derive(Debug)]
    println!("{:?}",user1);
    println!("{:#?}",user1);
    
  9. If a struct tuple is defined, when a function want to call an instance of this struct, other struct tuple (even with the same form) cannot be used:
    struct Color (u32,u32,u32);
    struct Point (u32,u32,u32);
    

    In this case, if a function want to call an instance of “Color”, we cannot put an instance of “Point” in it even they have the same form.

  10. An example of a struct and its method implementation: ```rust struct Rectangle { width: u32, height: u32, } impl Rectangle { fn area(&self) -> u32 { self.width * self.height }

Semantic versioning note

Given a version number MAJOR.MINOR.PATCH, increment the:

  1. MAJOR version when you make incompatible API changes,
  2. MINOR version when you add functionality in a backwards-compatible manner, and
  3. PATCH version when you make backwards-compatible bug fixes.

Additional labels for pre-release and build metadata are available as extensions to the MAJOR.MINOR.PATCH format.

Add two numbers in two reversed singly linked list

Given two non-empty linked lists representing two non-negative integers in reverse order. Also, each node contains a single digit. The question is to add the two numbers and return the result in reverse order in another linked list. For instance, as the example given by LeetCode, here’s the input: (2 -> 4 -> 3) + (5 -> 6 -> 4) and the output should be 7 -> 0 -> 8 because 342 + 465 = 807.

Here’s the definition for singly-linked list:

public class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
 }

My very beginning thought when I saw the question was that we can read the two linked lists and reversely store them in two String variables, then read those strings as integers and add them. After that, we can store the result in a new linked list. However, this approach will cause high time complexity and is not easy to implement. So we can simply simulate how numbers add. And due to the reverse order of digits, it’s easier to add numbers from the last digits of intended numbers which are safe for carrying. The code below is my solution:

class Solution {
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);            // this line is to simplify the head
        ListNode ans = head;                        // this line is creating pointer instead of normal assignment
        int tempVal = l1.val + l2.val;
        boolean isGTTen = false;
        if (tempVal >= 10) {
            isGTTen = true;
            tempVal -= 10;
        }
        ans.next = new ListNode(tempVal);
        ans = ans.next;
        while (l1.next != null || l2.next != null) {
            l1 = (l1.next != null) ? l1.next : new ListNode(0);
            l2 = (l2.next != null) ? l2.next : new ListNode(0);
            if (isGTTen) {
                l1.val += 1;
                isGTTen = false;
                if (l1.val ==10) {
                    l1.val = 0;
                    isGTTen = true;
                }
            }
            tempVal = l1.val + l2.val;
            if (tempVal >= 10) {
                isGTTen = true;
                tempVal -= 10;
            }
            ans.next = new ListNode(tempVal);
            ans = ans.next;
        }
        if (isGTTen) {
            ans.next = new ListNode(1);
        }
        return head.next;
    }
}

It’s a really interesting question and definitely help me to understand more about pointer in Java.

Maximum sum of non-consecutive subsequence

Today I saw a question which required us to calculate the maximum sum of the non-consecutive subsequence of a list. An important restriction of this question is that the subsequence must be non-consecutive in the original list. For example, here’s a list [3,5,6,10], all non-consecutive subsequences in this case are [3,6], [5,10] and [3,10]. Therefore the maximum sum of non-consecutive subsequence in this case is 5 + 10 = 15.

In order to solve this problem, we can use brutal method to calculate sums of all non-consecutive subsequences which is neither easy to implement nor efficient. An interesting fact of this problem is that if we go through the original list from the first element, every position has a maximum sum from the first element to this position. And let’s say the position is i which is greater than or equal to 2, so that the maximum sum here is either max(maxSum(list[i-1]), list[i]) or maxSum(list[i-2]) + list[i]. As we can see here, it’s quite easy to solve using the dynamic programming technique.

Here’s the code for this question:

class Solution {
  public static int maxNonConsecSum(int[] inputArray) {
    int[] sumList = inputArray.clone();
    sumList[1] = Math.max(sumList[0], sumList[1]); //base case
    for (int i = 2; i < sumList.length; i++){
      sumList[i] = Math.max(Math.max(sumList[i], sumList[i-1]), sumList[i] + sumList[i - 2]);
    }
    return sumList[sumList.length-1];
  }
}

Some flutter notes

Recently I found that Flutter is interesting so I decide to start learn it and put some of my notes about Flutter and Dart here.

  1. Use arrow notation for one-line functions or methods. For example:
    void main() => runApp(MyApp());
    
  2. A widget’s main job is to provide a build() method that describes how to display the widget in terms of other, lower level widgets.

Fix gems/plugins version issue in GitPage

I got a security alert of my GitPage (this one) today. It was because the dependencies of my site were out of date which might cause some security issues.

I’m not sure if my workaround is the best practice, but it worked so I just put it here.

First I installed Bundler in my computer, then I cd into the directory of my gitpage and run bundle update. I encountered some issues of lacking header files when updating dependencies so that make sure you have ruby-dev (or ruby-devel, depend on your OS) installed.

Running bundle exec jekyll serve to test your website before pushing it to GitHub is highly recommended. I encountered some issues which nested in bundle directory where I installed ruby plugins. Those “issues” are usually date format in example project or symbolic links issues of plugins themselves which don’t affect my project so we can simply add exclude: [vendor] (vendor here can be changed, depends on your directory which contains the bundle and plugins files) in _config.yml.

Jewels and stones problem

This post is about the “jewels and stones” problem and my attempt to it.

The purpose is to find elements of string “J” in string “S”, it’s like finding some type of jewels in a pile of stones.

For example, here’s the input: J=”aA”, S=”aAAAbB”, so the output should be 4 in this case.

This is a pretty easy one, so I just put my code below. Although the speed of my program is not the fastest, I can’t check the official answer because I don’t have a premium subscription.

class Solution {
    public int numJewelsInStones(String J, String S) {
        int num=0;
        for (int i=0, l=S.length(); i<l; i++){
            char c = S.charAt(i);
            for (int j=0, k=J.length(); j<k; j++){
                if(c==J.charAt(j)){
                    num++;
                    break;
                }
            }
        }
        return num;
    }
}

openSUSE Tumbleweed Tips

  1. Check mail-lists frequently.

  2. Use
    zypper dup
    

    instead of

    zypper up
    
  3. Use snapper to manage snapshots for recovery