/tmp/bucket

A place to dump my thoughts

0%

Posted on Edited on In

Strategies

Memoization (Top-down)

  1. make it works first
    1. draw the tree
    2. implement & test if the answer is correct (when small cases)
  2. then make it efficient
    1. add a memo with base case return values
    2. store new values in the memo

Tabulation (Bottom-up)

  1. create a table based on the input
  2. fill it with default & base-case values
  3. iterate through to generate the next value based on the current value

Posted on Edited on In

Purpose of this data structure

can search words by prefix in time complexity, O(n).

Recursion Implement

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
package main

import (
	"fmt"
)

type Node struct {
	Keys  map[string]*Node
	IsEnd bool
}

func newNode() *Node {
	return &Node{make(map[string]*Node), false}
}

type Trie struct {
	Root *Node
}

func newTrie() *Trie {
	return &Trie{newNode()}
}

func (t *Trie) Add(str string) {
	Add(str, t.Root)
}

func Add(str string, node *Node) {
	if len(str) == 0 {
		node.IsEnd = true
		return
	} else if _, ok := node.Keys[str[:1]]; ok {
		Add(str[1:], node.Keys[str[:1]])
	} else {
		// create new node for this string
		node.Keys[str[:1]] = newNode()
		Add(str[1:], node.Keys[str[:1]])
	}
}

func (t *Trie) HasWord(str string) bool {
	return HasWord(str, t.Root)
}

func HasWord(str string, node *Node) bool {
	if node.IsEnd && len(str) == 0 {
		return true
	} else if len(str) == 0 {
		return false
	}
	if _, ok := node.Keys[str[:1]]; ok {
		return HasWord(str[1:], node.Keys[str[:1]])
	} else {
		return false
	}
}

func (t *Trie) Words() []string {
	words := []string{}
	Print("", t.Root, &words)
	return words
}

func Print(curr string, node *Node, words *[]string) {
	if node.IsEnd {
		*words = append(*words, curr)
	}
	for key := range node.Keys {
		Print(curr+key, node.Keys[key], words)
	}
}

func main() {
	t := newTrie()
	t.Add("apple")
	t.Add("cat")
	t.Add("category")
	t.Add("")
	fmt.Println(t.Words())
	fmt.Println(t.HasWord("apple"))
	fmt.Println(t.HasWord("none"))
	fmt.Println(t.HasWord("category"))
	fmt.Println(t.HasWord("cat"))
	fmt.Println(t.HasWord(""))
}

output

1
2
3
4
5
6
[ apple cat category]
true
false
true
true
true

Forloop Implement

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
type TrieNode struct {
	Children [26]*TrieNode
	IsEnd    bool
}

type Trie struct {
	Root *TrieNode
}


func Constructor() Trie {
    return Trie{&TrieNode{}}
}


func (this *Trie) Insert(word string) {
	curr := this.Root
	for i := range word {
		// check if has word[i] as a child
		k := word[i] - 'a'
		if curr.Children[k] == nil {
			curr.Children[k] = &TrieNode{}
		}
		curr = curr.Children[k]
	}
	curr.IsEnd = true
}

func (this *Trie) Search(word string) bool {
	curr := this.Root
	for i := range word {
		// check if has word[i] as a child
		k := word[i] - 'a'
		if curr.Children[k] == nil {
			return false
		}
		curr = curr.Children[k]
	}
	return curr.IsEnd
}

func (this *Trie) StartsWith(word string) bool {
	curr := this.Root
	for i := range word {
		// check if has word[i] as a child
		k := word[i] - 'a'
		if curr.Children[k] == nil {
			return false
		}
		curr = curr.Children[k]
	}
	return true
}

Posted on Edited on In

Quick sorting is a pre-order traversal operation. Every time we dive into a node, we divide it into two portions: small and large. Then recursively apply this logic to these two portions.

Implementation

Let’s compare the two implementations below. The first one is straightforward, and the other one uses struct.
#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
func quicksort(array []int) []int {
	var dfs func(start, end int)
	dfs = func(start, end int) {
		if start >= end || start < 0 || end >= len(array) {
			return
		}
		pivot := (start + end) / 2
		swap(array, pivot, end) // swap value
		pivot = end
		l, r := start, end-1
		for {
			for ; l < r && array[l] <= array[pivot]; l++ {
			}
			for ; l < r && array[r] >= array[pivot]; r-- {
			}
			if l == r {
				break
			}
			swap(array, l, r)
		}
		meet := l
		if array[meet] >= array[pivot] {
			swap(array, meet, pivot)
            pivot = meet
		}
		dfs(start, pivot-1)
		dfs(pivot+1, end)
	}
	dfs(0, len(array)-1)
	return array
}

func swap(arr []int, a, b int) {
	arr[a], arr[b] = arr[b], arr[a]
}

#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
36
37
38
39
40
41
42
type Partition struct {
	Pivot int
	Left  []int
	Right []int
}

func doPartition(array []int) Partition {
	start, end, pivot := 0, len(array)-1, (len(array)-1)/2
	swap(array, pivot, end) // swap value
	pivot = end
	l, r := start, end-1
	for {
		for ; l != r && array[l] <= array[pivot]; l++ {
		}
		for ; l != r && array[r] >= array[pivot]; r-- {
		}
		if l == r {
			break
		}
		swap(array, l, r)
	}
	meet := l
	if array[meet] >= array[pivot] {
		swap(array, pivot, meet)
		pivot = meet
	}
	return Partition{pivot, array[:pivot], array[pivot+1:]}
}

func swap(array []int, a, b int) {
	array[a], array[b] = array[b], array[a]
}

func quicksort(array []int) []int {
	if len(array) <= 1 {
		return array
	}
	p := doPartition(array)
	quicksort(p.Left)
	quicksort(p.Right)
	return array
}

Posted on Edited on In

Slice or Array?

In Go, array can only be created by constant int

1
2
3
4
arr := [4]int // works

size := 4
arr := [size]int // Not work!

Thus use slice, if we want to implement a function that create a N size matrix

Implement

straight forward

  • bad memory using, not contiguous matrix
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func newMatrix(s int) [][]int {
    
    m := make([][]int, s)
    
    // Wrong!
    //
    // for _, row := range m {
    //     row = make([]int, s)
    // }
    //
    
    for i, _ := range m {
        m[i] = make([]int, s)
    }
    
    return m
}

method 2

  • ensure to get a contiguous matrix
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func newMatrix(s int) [][]int {
	// allocate the whole space of the matrix
	spaces := make([]int, s*s)

	// create an empty matrix: [[] [] []...]
	m := make([][]int, s)

	// assign spaces to the matrix
	i, j := 0, 0
	for i < s {
		m[i] = spaces[j : j+s]
		i++
		j += s
	}

	return m
}

Generic

more flexiable!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func newMatrix[T any](s int) [][]T {
	// allocate the whole space of the matrix
	spaces := make([]T, s*s)

	// create an empty matrix: [[] [] []...]
	m := make([][]T, s)

	// assign spaces to the matrix
	i, j := 0, 0
	for i < s {
		m[i] = spaces[j : j+s]
		i++
		j += s
	}

	return m
}

Usage

1
m := newMatrix[unit](3) // [[0 0 0] [0 0 0] [0 0 0]]

Resources

Posted on Edited on In

Problem

Given a slice a. There are 2 sub slices. One’s length is k, the other’s is p.
These 2 sub slices are not overlaid. Find the max sum of the 2 sub slices.

Return -1 if can’t find one.

Example 1:

1
2
Input: [1,3,4,7,5,8,2,9], 3, 2
Output: 35

Example 2:

1
2
Input: [1,3,4,7,5,8], 100, 2
Output: -1

Thought

Move slice K through A, at the left and right side of K place the slice P.
To improve the efficiency, store sums of K and P in hash tables.


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
func maxSum(a []int, k, p int) int {
	if k+p > len(a) {
		return -1
	}
	kt := hashTable(a, k)
	pt := hashTable(a, p)
	ki := 0
	for ki < len(kt) {
		left := maxVal(pt[:max(0, ki-p+1)]...)
		right := maxVal(pt[min(ki+k, len(pt)):]...)

		if left == -1 && right == -1 {
			kt[ki] = -1
		} else {
			kt[ki] = kt[ki] + max(right, left)
		}
		ki++
	}

	return maxVal(kt...)
}

func hashTable(a []int, length int) []int {
  if length > len(a) {
		return []int{}
	}
	tlen := len(a) - length + 1
	t := make([]int, tlen)
	i := 0
	for i < tlen {
		t[i] = sum(a[i : i+length]...)
		i++
	}
	return t
}

func maxVal(nums ...int) int {
	m := -1
	for _, v := range nums {
		if m < v {
			m = v
		}
	}
	return m
}

func sum(nums ...int) int {
	res := 0
	for _, n := range nums {
		res += n
	}
	return res
}

func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}

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

Posted on Edited on In

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
}

Posted on Edited on

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

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