/tmp/bucket

A place to dump my thoughts

0%

Posted on Edited on In

除草，單純想在這裡 dump 一些想法。

#1

安排班夫行程。火車臥鋪肖貴。還在觀望機票和行程，希望不要售罄

#2

這週處理 3 個任務

Batch convert studiolib data

  • 寫了測試棒棒，之後改動更安心
  • 之後思考有沒有更好的方法，能跟 Maya 解耦
  • integrate with G-drive or other storages

Convert global translation to other controller

  • replace root-hip with global-main
    做功能時，之前寫的測試有幫助到找到忘記一起改的錯誤

Fixed 2 bugs

  • file format reading
  • API response updated
    覺得之前設計的架構讓我很好 debug，修改起來很快

#3

思緒上有點喘不過氣，聽說是職業倦怠的徵兆…
なんか、頭をリセットする方法ないかな。

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

What is a tier?

both logical and physical separation of components

Single-tier App

All components are located in the same machine. e.g. Maya, Photoshop…

Pros

  • no network latency
  • privacy data safe since no need to upload users’ data

Cons

  • efficiency bounds on the machine where the app lives on
  • app publisher has no control over the app (users decide whether update the app or not)
  • be vulnerable to being tweaked and reversed engineered

Two-tier App

client-server architecture

Three-tier App

client-backend-database. e.g. blog

N-tier App

What are these components?

  • cache
  • load balancer
  • database
  • queue (for asynchronous behavior)
  • search engine
  • customized business logic services

It is an implementation of the single-responsibility principle

decoupled. it’s easier to maintain. so, for example, we should not store business logic in the database. Also, it is easier to be scaled.

Layer & Tier

layers represent the conceptual/logical organization of the code (code level)

tiers represent the physical separation of components.

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

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

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

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