/tmp/bucket

A place to dump my thoughts

0%

Problem

Given a string s, return a cropped which max length is n.
Also, spaces at prefix and postfix need to be removed.

Example 1:

1
2
Input: "Hello World", 8
Output: "Hello"

Example 2:

1
2
Input: "   Hello World   ", 100
Output: "Hello World"

Example 3:

1
2
Input: "Hello World", 3
Output: ""

Thought

Find the start point l and end point r then return result s[l:r]
Left point is easy to find. If s[l] is space, pointer l move right.
On the other hand, r starts from l + N, if s[r] is NOT space, pointer r move left.

The tricky point is that if the given string’s length equals to given n,
and the string ends with character, the last word would be cropped.

Example:

1
2
3
Input: "Learn Golang", 12
Output: "Learn"
Expected: "Learn Golang"

An easy solution is to append a SPACE to the given string at the beginning.

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
func crop(s string, n int) string {
s = s + " " // append an extra space

// keep moving right until reaching the first character
l := 0
for l < len(s)-1 {
if s[l] == ' ' {
l++
} else {
break
}
}

// start from `l+n` or the last char (extra space)
// keep moving left until reaching the first space
r := min(l+n, len(s)-1)
for r > l {
if s[r] == ' ' {
break
} else {
r--
}
}
return s[l:r]
}

func min(i, j int) int {
if i < j {
return i
}
return j
}

Tutorial

Follow this tutorial

New C++ Project in Xcode

Select command line tool

Edit Header Search Paths & Library Search Paths

I could not find where to edit Header Search Paths and Library Search Paths until I found this Toutube tutorial.

Set additional preferences like below

build shorcut in xCode: command + b

Resource

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);

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

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

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

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: "好" }

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

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.

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
}