/tmp/bucket

A place to dump my thoughts

0%

Posted on Edited on In

There is no output window in Mac’s Maya so I can’t print out text by std::out. The only way I know is to use Global::displayInfo. However, Global::displayInfo only accepts MString. I haven’t digged into what MString is yet but just provide some examples here. Hope you can get the basic idea:)

1
2
3
4
5
6
7
8
Global::displayInfo("hello"); // Works

string str = "hello";
Global::displayInfo(str); // This will fail

char str[10];
sprintf(str, "hello"); // Writes content to `str`
Global::displayInfo(str); // Works

In this way, we can also print out numeric types!

1
2
3
4
5
flaot value = 100.0f;
char str[10];

sprintf(str, "value:%f", value);
Global::displayInfo(str);

Posted on Edited on In

Concept

  • MObjects
    • class to handle all kinds of data in Maya
    • a handle object pointing to actual data
    • typeless
  • Function Sets
    • work with mobject
  • Wrappers
    • allocated and deallocated by you
  • Proxies
    • used to create custom maya objects (i.e. MPxNode, MPxDeformerNode)

Resources

Posted on Edited on In

Write a custom Maya command that print “Hello world!” in Maya console.
There are Python API 1.0 and 2.0. The syntax would be different.
We will integrate with API 2.0 in this example.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import sys
import maya.api.OpenMaya as api

# Must include to use Maya API 2.0
def maya_useNewAPI():
    pass

class HelloWorldCmd(api.MPxCommand):
    kCmdName = 'helloWorld'

    def __init__(self):
        api.MPxCommand.__init__(self)

    @staticmethod
    def creator():
        return HelloWorldCmd()

    def doIt(self, arg_list):
        print('Hello world!')

# initialize and uninitialize functions are
# needed to be loaded by Maya Plug-in Manager 
def initializePlugin(mobject):
    fn_plugin = api.MFnPlugin(mobject)
    try:
        fn_plugin.registerCommand(
            HelloWorldCmd.kCmdName,
            HelloWorldCmd.creator
        )
    except:
        sys.stderr.write("Fail to register plugin: " + HelloWorldCmd.kCmdName)

def uninitializePlugin(mobject):
    fn_plugin = api.MFnPlugin(mobject)
    try:
        fn_plugin.deregisterCommand(
            HelloWorldCmd.kCmdName
        )
    except:
        sys.stderr.write("Fail to deregister plugin: " + HelloWorldCmd.kCmdName)

Open Maya Plug-in Manager, and hit “Browse” to load our command.

Then we can run our command

1
helloworld;

We can also call it in Python:

1
2
from maya import cmds
cmds.helloWorld

Posted on Edited on In

Doc:
https://developers.google.com/protocol-buffers/docs/gotutorial

Proto Buffer

Download Proto Buffer:
https://developers.google.com/protocol-buffers/docs/downloads

Check if protoc installed

1
$ protoc --version

Install protoc-gen-go

1
$ go install google.golang.org/protobuf/cmd/protoc-gen-go@latest

Add these text to ~/.bashrc or ~/.zshrc (depends on what shell you use)

1
2
export GOPATH=$HOME/go
export PATH=$PATH:$GOPATH/bin

This step is important to avoid Error "protoc-gen-go: program not found or is not executable"

.proto File

.proto example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
syntax = "proto3";

package proto;

option go_package ="../proto"; // avoid "unable to determine go import path"

message Request {
    int64 a = 1;
    int64 b = 2;
}

message Response {
    int64 result = 1;
}

service AddService {
    rpc Add(Request) returns (Response);
    rpc Multiply(Request) returns (Response);
}

Scaffolding:

1
2
3
4
project/
└── proto/
   └── package.proto

Compile

1
2
$ cd proto
$ protoc --go_out=plugins=grpc:. service.proto

plugins=grpc is needed or the output file will lack some functions

Install grpc

1
$ go get -u google.golang.org/grpc

Reference

Posted on Edited on In

Study how to use Borsh Serialize. When we write vanila Solana program, we need to serialize and deserialize accounts’ data by ourselves.

1
2
3
4
5
// Cargo.toml
// ...
[dependencies]
borsh = "0.9.3"
borsh-derive = "0.9.1"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// main.rs
use borsh::{BorshDeserialize, BorshSerialize};

#[derive(BorshSerialize, BorshDeserialize, Debug)]
struct Node {
    num: i32,
    str: String
}

fn main() {
    let uint:i32 = 256; // 2^8 -> 1 byte
    let node = Node{
        num: uint.pow(0) + uint.pow(1)*2 + uint.pow(2)*3 + uint.pow(3)*4, // [1, 2, 3, 4]
        str: String::from("好") // first 4 bytes represents how many bytes of this string
    };

    if let Ok(buf) = node.try_to_vec() {
        println!("serialized: {:?}", buf);

        if let Ok(deserz_node) = Node::try_from_slice(&buf) {
            println!("deserialized: {:?}", deserz_node);
        }
    }
}

Run the code:

1
2
3
$ cargo run
serialized: [1, 2, 3, 4, 3, 0, 0, 0, 229, 165, 189]
deserialized: Node { num: 67305985, str: "好" }

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// rest.js
const row = {
    name: "Amy",
    age: 32,
    email: "amy@gamil.com",
    job: "cook"
};

const { job: a, none: b, ...rest_props } = row;

console.log(a); // maps to property "job"
console.log("---")
console.log(b); // property "none" doesn't exist so b is undefined
console.log("---")
console.log(rest_props); // row but without "job" property

run the code:

1
2
3
4
5
6
$ node rest.js                                                                                           
cook
---
undefined
---
{ name: 'Amy', age: 32, email: 'amy@gamil.com' }

More

Posted on Edited on In

Problem

Problem: Implement strStr()

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. If needle is empty, return 0.

Thoughts

strategies:

  • two pointers to compare each characters of needle and haystack (2 while loops)
  • iterate through haystack to get slices to compare with needle
  • iterate through haystack to get slices. Hash each slice and compare the hashed with the hashed needle
  • use find method

Code

Two While Loops

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        let hay_vec: Vec<char> = haystack.chars().collect();
        let needle_vec: Vec<char> = needle.chars().collect();

        let mut i_hay: usize = 0;
        let mut i_needle: usize = 0;
        while i_hay < hay_vec.len() {
            while i_needle < needle_vec.len() {

                let offset_hay = i_hay + i_needle;
                if offset_hay >= hay_vec.len() {
                    break;
                }

                if hay_vec[offset_hay] != needle_vec[i_needle] {
                    i_needle = 0;
                    break;
                } else if hay_vec[offset_hay] == needle_vec[i_needle] && i_needle == needle_vec.len() - 1 {
                    return i_hay as i32;
                }

                i_needle += 1;
            }

            i_hay += 1;
        }

        return -1;
    }
}

Compare String Slice

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        let (hay_len, needle_len) = (haystack.len(), needle.len());

        if needle_len == 0 { return 0 }
        else if needle_len > hay_len { return -1 } // avoid hay: "aa", needle: "aaaa"

        for i in 0..=hay_len - needle_len {
            if haystack[i..i + needle_len] == needle {
                return i as i32;
            }
        }

        -1
    }
}

Use Manual Hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
const MAGIC_NUM: u64 = 31; // can be any number but should not too big

pub fn str_str(haystack: String, needle: String) -> i32 {
    let (hay_len, needle_len) = (haystack.len(), needle.len());

    if needle_len == 0 { return 0 }
    else if needle_len > hay_len { return -1 } // avoid hay: "aa", needle: "aaaa"

    let hash_needle = hash(&needle);
    let mut hash_hay:u64 = 0;
    let highest_pow = MAGIC_NUM.pow(needle_len as u32 - 1);

    for i in 0..=hay_len - needle_len {
        if hash_hay == 0 { 
            hash_hay = hash(&haystack[i..i + needle_len]); 
        } else {
            /* rolling hash */ 
            // abc -> _bc
            let first_c = haystack.chars().nth(i-1).unwrap();
            hash_hay -= first_c as u64 * highest_pow;
            // _bc -> bc_
            hash_hay *= MAGIC_NUM;
            // bc_ -> bcd
            hash_hay += haystack.chars().nth(i + needle_len - 1).unwrap() as u64;
        }

        if hash_hay == hash_needle {
            return i as i32;
        }
    }

    -1
}

fn hash(str: &str) -> u64 {
    let mut buf:u64 = 0;

    for c in str.chars() {
        buf *= MAGIC_NUM;
        buf += c as u64;
    }

    buf
}

Use Find

1
2
3
4
5
6
7
8
9
10
impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        if needle.is_empty() { return 0 }

        match &haystack.find(&needle) {
            Some(i) => *i as i32,
            None => -1
        }
    }
}

If An Unicode String Given

1
2
let str = String::from("好");
println!("{}", str.len()); // This will print out 3

Since the len() returns the length of bytes not characters, we need to change our code if unicode strings given.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        // Get length of chars instead of bytes
        let (hay_len, needle_len) = (
            haystack.chars().count(),
            needle.chars().count()
        );

        // Collect string into `Vec<char>`
        let (hay_chars, needle_chars) = (
            haystack.chars().collect::<Vec<char>>(),
            needle.chars().collect::<Vec<char>>()
        );

        // The rest are same
        if needle_len == 0 { return 0 }
        else if needle_len > hay_len { return -1 }

        for i in 0..=hay_len - needle_len {
            if hay_chars[i..i + needle_len] == needle_chars {
                return i as i32;
            }
        }

        -1
    }
}

Conculsion

  • utilize string slice or find looks easier.
  • in some situations, hash may be useful. However, for this case, it may not be the best practise.

Posted on Edited on In

Problem

Given a inorder-traversal result and a preorder-traversal result of a tree, Figure out the tree structure.

For example:

  • inorder: 1,2,3,4,5,6,7
  • preorder: 5,2,1,4,3,6,7

What is the structure of this tree? Can we build a tree based on these two clues?

Thoughts

The first element of preorder-traversal must be the Root of a tree. On the other hand, we can determine left and right from inorder-traversal after we get the root. As the result, we can again get inorder and preorder result of left-sub-tree and right-sub-tree, then both left and right redo above process until they get no or only one element.

Overview the tree for now

So we can expect we can get the whole tree if we repeat the process.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
pub struct Node {
    pub val: i32,
    pub left: Option<Box<Node>>,
    pub right: Option<Box<Node>>
}

impl Node {
    pub fn new(val: i32) -> Self {
        Node { 
            val,
            left: None,
            right: None
        }
    }

    pub fn inorder_traversal(&self) {
        if let Some(left) = &self.left {
            left.inorder_traversal();
        }

        println!("{}", &self.val);

        if let Some(right) = &self.right {
            right.inorder_traversal();
        }
    }

    pub fn preorder_traversal(&self) {

        println!("{}", &self.val);

        if let Some(left) = &self.left {
            left.preorder_traversal();
        }

        if let Some(right) = &self.right {
            right.preorder_traversal();
        }
    }
}

pub fn rebuild_tree(inord_arr: &Vec<i32>, preord_arr: &Vec<i32>) -> Node {
        
    let root_val = preord_arr[0];
    let mut root = Node::new(root_val);

    // Find the index of root from inorder result
    let inord_arr_root_i = inord_arr
        .iter()
        .position(|&x| x == root_val)
        .unwrap();

    let inord_left_sub_len = inord_arr_root_i;

    if inord_left_sub_len == 1 {
        root.left = Some(Box::new(Node::new(inord_arr[0])));
    } else if inord_left_sub_len > 1 {
        let preord_left_sub_vec = preord_arr[1..inord_left_sub_len+1].to_vec();
        let inord_left_sub_vec = inord_arr[..inord_arr_root_i].to_vec();
        root.left = Some(
            Box::new(rebuild_tree(
                &inord_left_sub_vec,
                &preord_left_sub_vec
            ))
        );
    }

    let inord_right_sub_len = inord_arr.len() - inord_left_sub_len - 1;
    if inord_right_sub_len == 1 {
        root.right = Some(Box::new(Node::new(inord_arr[inord_arr_root_i + 1])));
    } else if inord_right_sub_len > 1 {
        let preord_right_sub_vec = preord_arr[1+inord_left_sub_len..].to_vec();
        let inord_right_sub_vec = inord_arr[inord_arr_root_i+1..].to_vec();
        root.right = Some(
            Box::new(rebuild_tree(
                &inord_right_sub_vec,
                &preord_right_sub_vec
            ))
        );
    }

    root
}

fn main() {
    let inord_vec = vec![1,2,3,4,5,6,7];
    let preord_vec = vec![5,2,1,4,3,6,7];
    let rebuild_tree_n = rebuild_tree(&inord_vec, &preord_vec);

    rebuild_tree_n.inorder_traversal(); // 1,2,3,4,5,6,7
    println!("--------");
    rebuild_tree_n.preorder_traversal(); // 5,2,1,4,3,6,7
}

Posted on Edited on In

Problem

Problem: Koko Eating Bananas

Let’s draw some pictures to understand this quesiton. If there are 4 piles of bananas like below, the given array would be [3, 2, 4, 1].

Then if Koko can eat 3 bananas per hour, it will takes her 5 hours to eat all the bananas like blow.

Now, if the limit hours h is 5 then 3 bananas per hour satisfies. However, if h, for example, is 3, then Koko need to SPEEDS UP to finish all the bananas. On the other hand, if h is 10 which means we still have time right? So Koko should SLOW DOWN to certain speed to make herself chill but still can finish all the bananas in time.

So what is the best eating speed is the question!

Thoughts

  • The maximum of speed should equals to the number of the bananas of the tallest pile
  • The minimun of speed should equals to 1

Which means we are trying to find the best from 1 ~ piles.max(). Searching a value from a sorted array… maybe binary search is a soslution.

Code

Try #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
use std::cmp::Ordering;

impl Solution {
    pub fn min_eating_speed(piles: Vec<i32>, h: i32) -> i32 {
        let mut sorted_piles = piles.clone();
        sorted_piles.sort();
        Solution::min_eating_speed_inner(
            &sorted_piles,
            h,
            1,
            *sorted_piles.last().unwrap()
        )
    }

    fn min_eating_speed_inner(piles: &Vec<i32>, h: i32, min: i32, max: i32) -> i32 {
        // return codition
        if piles.len() == 0 || min > max {
            return -1;
        }

        // speeds arr is [min..max]
        // so the mid speed is (min + max) / 2
        let mid = min + (max - min) / 2;

        // piles divides speed return spend time
        let time = Solution::count_eating_time(&piles, mid);

        // find the matched speed or continue go down to sub tree
        match time.cmp(&h) {
            // spend too much time to eat, speed up
            Ordering::Greater => Solution::min_eating_speed_inner(piles, h, mid + 1, max),
            // match, try to find a better (slower) speed
            _ => {
                let new_speed = Solution::min_eating_speed_inner(piles, h, min, mid - 1);

                if new_speed > 0 {
                    return new_speed;
                }
                mid
            }
        }
    }

    fn count_eating_time(piles: &Vec<i32>, speed: i32) -> i32 {
        // count the time to eat each pile and return sum
        let sum = piles
            .into_iter()
            .map(|pile| {
                if pile % speed > 0 {
                    return pile / speed + 1
                }
                return pile / speed
            })
            .sum();

        sum
    }
}

Posted on Edited on In

Thoughts

The core concept is to find the target from a sorted array which is quite suitable to use binary serach I think.

Here are my instructions:

  1. Get the middle element, mid
  2. Compare the mid with the target. there will be 3 branches:
    a. target < mid: continue to find the target from the LEFT side of the mid
    b. target > mid: continue to find the target from the RIGHT side of the mid
    c. target = mid: In this case, [index_of_mid, index_of_mid] will be our base answer so keep it. Then based on this answer, we need to go further to the both left and right to seek if there is other elements match to the search target.

For example, if the given array is [1, 2, 3, 4, 4, 4, 4, 6, 9], and the search target is 4.

Then we are trying to get this green range.

When we go through the instructions, we will get the middle element, and hit the c case.

Then base on this position, we seek towar left and right to get the final range.

So the answer should be [3, 6]

Code

Try #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
impl Solution {
    pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
        if nums.len() == 0 {return vec![-1,-1]}
        bst_search_index_rec(&nums, target, 0, (nums.len()-1) as i32)
    }  
}

fn bst_search_index_rec(arr: &Vec<i32>, val: i32, start_i: i32, end_i: i32) -> Vec<i32> {
    if start_i > end_i {
        return vec![-1, -1];
    }

    let mut result: Vec<i32> = vec![-1, -1];

    let mid_i = (start_i + end_i)/2;

    if val == arr[mid_i as usize] {
        result[0] = mid_i as i32;
        result[1] = mid_i as i32;
        
        let tmp_left_result = bst_search_index_rec(&arr, val, start_i, (mid_i-1) as i32);
        if tmp_left_result[0] != -1 {
            result[0] = tmp_left_result[0];
        }

        let tmp_right_result = bst_search_index_rec(&arr, val, (mid_i+1) as i32, end_i);
        if tmp_right_result[1] != -1 {
            result[1] = tmp_right_result[1];
        }

    } else if val < arr[mid_i as usize] {
        result = bst_search_index_rec(&arr, val, start_i, (mid_i - 1) as i32);
    } else if val > arr[mid_i as usize] {
        result = bst_search_index_rec(&arr, val, (mid_i + 1) as i32, end_i);
    }

    return result;
}

Try #2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
use std::cmp::Ordering; // Don't forget to import this

impl Solution {
    pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {

        Solution::bst_search_index_inner(&nums, target, 0, nums.len() as i32 - 1)
    }
    
    fn bst_search_index_inner(arr: &Vec<i32>, val: i32, start_i: i32, end_i: i32) -> Vec<i32> {
        // return condition
        if start_i > end_i || arr.len() == 0 {
            return vec![-1, -1];
        }

        // avoid overflows rather than simply (start_i + end_i) / 2
        let mid_i = start_i + (end_i - start_i) / 2;

        match val.cmp(&arr[mid_i as usize]) {
            Ordering::Less => Solution::bst_search_index_inner(&arr, val, start_i, mid_i - 1),
            Ordering::Greater => Solution::bst_search_index_inner(&arr, val, mid_i + 1, end_i),
            Ordering::Equal => {
                let l = Solution::bst_search_index_inner(arr, val, start_i, mid_i - 1);
                let r = Solution::bst_search_index_inner(arr, val, mid_i + 1, end_i);

                match (l[0], r[1]) {
                    (-1, -1) => vec![mid_i, mid_i],
                    (-1, new_r) => vec![mid_i, new_r],
                    (new_l, -1) => vec![new_l, mid_i],
                    (new_l, new_r) => vec![new_l, new_r]
                }
            }
        }
    }
    
}

Conclusions

Improvements

  • avoid overflows in some edge cases
  • move the recursion function into Solution struct
  • more rusty coding style

Learned

  • Combo of cmp & match
  • How to use the function itself in a implementation
    -> Solution::bst_search_index_inner