Plover Temp: 2013

2013年12月31日星期二

[FWD] Getting start with Python for data science

https://www.kaggle.com/wiki/GettingStartedWithPythonForDataScience

Python 選用 32-bit Python 3.2

Train or test data 採用 open('Data/train.csv','Ub') Ub 模式開檔

TODO: Do some study on random forests.

2013年12月30日星期一

[FWD] Automation Tools

http://www.autoitscript.com/site/autoit/

http://www.seleniumhq.org/
http://www.sikuli.org/

2013年12月16日星期一

[ROSALIND] Alignment

基礎題：
Global Alignment with Scoring Matrix

基礎變化題：
Local Alignment with Scoring Matrix
Counting Optimal Alignments

搞人題：
Semiglobal Alignment

Overlap Alignment
Fitting Alignment

非常搞人題：
Global Alignment with Constant Gap Penalty
Maximizing the Gap Symbols of an Optimal Alignment

2013年12月11日星期三

Given a dictionary of English words (one word per input line in lower case letters), we must find all anagram classes.

不禁令人想到一個 hash function h:

h(A) = 2, h(B) = 3, h(C) = 5, h(D) = 7, h(E) = 11, ..., h(k-th alphabet) = k-th prime number.

h is multiplicative on each alphabet. For example, h(WORD) = h(W) h(O) h(R) h(D). Observe that x and y are in the same anagram class if and only if h(x) = h(y).

Or you can define h to be h(letter[]) = sort(letter[]).

2013年12月10日星期二

[LINK] 台北市鐘錶眼鏡業職業工會

http://www.cwotp.org.tw/front/bin/home.phtml

2013年12月9日星期一

[ROSALINE] Suffix Tree

Problem: http://rosalind.info/problems/lrep/

Introduction to suffix tree: https://cs.uwaterloo.ca/~binma/cs482/06_suffix-tree-array.pdf

Suffix trees can do many string operations you might think are very hard, in linear time.

Application: Any substring of S is a prefix of a suffix.

Now we can solve this Rosalind's problem.

PS. Implement suffix tree for better representations.

2013年11月29日星期五

Some notes

1. Vienna regulator style pendulum wall clock
Antique Tall Case / Grandfather Clock Disassembly tutorial: https://www.youtube.com/watch?v=DpZWsx7qDFc

2. http://rosalind.info 有幾題相當困難，還在思考怎麼做。

2013年11月28日星期四

[ROSALIND] Shortest Common Supersequence

相當有梗的詞。

想了許久，greedy algorithm 不太行，後來想到要短就要盡量共用 subsequence，

所以問題搖身一變，就變成了 LCS。

[ROSALIND] Longest Common Subsequence

原本 CLR 的 Print-LCS(b, X, i, j) 用 recursive function 寫的，有點蠢。

改用 stack 的概念重寫。

def longest_common_subsequence(s, t):
    c, b = longest_common_subsequence_table(s, t)
    return longest_common_subsequence_printable(b, s, len(s), len(t))

def longest_common_subsequence_table(s, t):
    m, n = len(s), len(t)
    b = [[0 for _ in range(n)] for _ in range(m)] 
    c = [[0 for _ in range(n+1)] for _ in range(m+1)] 
    for i in range(m):
        for j in range(n):
            if s[i] == t[j]:
                c[i+1][j+1] = c[i][j] + 1
                b[i][j] = 'Diagonal'
            elif c[i][j+1] > c[i+1][j]:
                c[i+1][j+1] = c[i][j+1]
                b[i][j] = 'Up'
            else:
                c[i+1][j+1] = c[i+1][j]
                b[i][j] = 'Left'
    return c, b

def longest_common_subsequence_printable(b, s, i, j):
    reversed_lcs = ''
    while True:
        if i == 0 or j == 0:
            break
        direction = b[i-1][j-1]
        if direction == 'Diagonal':
            lcs += s[i-1]
            i, j = i-1, j-1
        elif direction == 'Up':
            i, j = i-1, j
        else:
            i, j = i, j-1
    return reversed_lcs[::-1]

2013年11月27日星期三

[FWD] ROLEX國內AD貨盒單全價格參考

品牌名稱：ROLEX、OMEGA、TUDOR
出廠年份：--
購買年份：2013
手錶型號與欲售金額：
116680(新式序號)510000
116622藍面(新式序號)312000
116610LN(新式序號)售225000
116710LN(新式序號)售223000
216570黑面((新式序號)售216000
216570白面((新式序號)售216000
116400GV(新式序號)售214000
114060(新式序號)售204000
特價錶款如下:
16570黑面(V字序號)售183000(自取價175000)
16570白面(V字序號)售183000(自取價173000)
OMEGA
Planet Ocean 8500陶瓷黑框橘字(45.5mm) 售150000(自取價143000)
TUDOR
Black Bay 鍊帶款售94000(自取價88000)

2013年11月26日星期二

新的計畫也就是把 ROSALIND 一百多題寫完

如標題。

多多鍛鍊自己。

[ROSALIND] Longest Increasing Subsequence

相當經典的題目。

一般的 dynamic programming 的時間複雜度是 O(n^2)

def LIS(sequence):
    # Time complexity is O(n^2)    
    lis_len = [1] * len(sequence)
    for i in range(len(sequence)):
        for j in range(i+1, len(sequence)):
            if sequence[i] < sequence[j]:
                lis_len[j] = max(lis_len[j], lis_len[i] + 1)
    rv = []
    curr_len = max(lis_len)
    for i in range(len(sequence) - 1, -1, -1):
        if curr_len == lis_len[i]:
            rv.append(sequence[i])
            curr_len -= 1
    return rv[::-1]

如果我們使用 Robinson-Schensted-Knuth Algorithm 改良的版本：

def LIS(sequence):
    # Robinson-Schensted-Knuth Algorithm
    # Time complexity is O(n log(n))
    if not sequence:
        return []
    aux_len = [1]
    aux_rv = [sequence[0]] 
    for i in range(1, len(sequence)):
        x = sequence[i]
        if x > aux_rv[-1]:
            aux_rv.append(x)
            aux_len.append(len(aux_rv))
        else:
            j = bisect.bisect_right(aux_rv, x)
            aux_rv[j] = x
            aux_len.append(j + 1)        
    rv = []
    curr_len = len(aux_rv)
    for i in range(len(sequence) - 1, -1, -1):
        if curr_len == aux_len[i]:
            rv.append(sequence[i])
            curr_len -= 1
    return rv[::-1]

這個時間複雜度是 O(n log(n))，關鍵就是用 binary search 把時間複雜度從 n 降成 log(n)。

2013年11月25日星期一

[ROSALIND] DNA

Problem: http://rosalind.info/problems/dna/

Solved by Perl

use strict;
use warnings;

while (my $dna = <>) {
    chomp $dna;
    my @symbols = split //, $dna;
    my %count = (
        'A' => 0,
        'C' => 0,
        'G' => 0,
        'T' => 0,
    );
    for my $symbol (@symbols) {
        $count{$symbol}++;
    }
    print $count{'A'} . ' ' , 
          $count{'C'} . ' ' , 
          $count{'G'} . ' ' ,
          $count{'T'} . "\n";
}

實際寫頗土炮。

Solved by Python

import sys

dna = sys.stdin.read().strip()
print(' '.join([str(dna.count(i)) for i in 'ACGT']))

不得不說演化過的 Python 習得各家語言的優點，才能淬鍊精幹短小的程式碼。

沒有分號倒是很有意思，強迫 programmers 一行不能寫兩個以上的 statements。

Solved by Ruby:

dna = STDIN.read.chomp
puts [dna.count('A'), dna.count('C'), dna.count('G'), dna.count('T')].join ' '

短短的蠻可愛的

2013年11月24日星期日

Ruby Books

Ruby Best Practice: http://majesticseacreature.com/rbp-book/pdfs/rbp_1-0.pdf

Little Book of Ruby: http://www.sapphiresteel.com/IMG/pdf/LittleBookOfRuby.pdf

2013年11月19日星期二

到年底的新目標

一。早睡早起。

就這麼簡簡單單困困難難。

二。持續資助。

NT$1,000 財團法人綠色和平基金會。

現在台灣綠色和平組織仍舊依賴國外資助，

聽起來就很丟臉，台灣什麼都可以輸，但愛心不能輸。

綠色和平有許多議題可以討論與追蹤，除了幫助人我們也可以幫助大自然，

看見台灣說得很好，我們用「為了下一代」作為掠奪大自然的藉口，

其實我們要的太多了，沒必要。

2013年11月13日星期三

Milgauss

http://www.rolex.com/zh-hant/watches/milgauss/m116400-0002.html

貼圖自爽一下。

看到橘色的針感覺很開心。

2013年11月6日星期三

還是雜事

《一》

Mua interpreter 卡在怎麼 interpret function call，

包括 user-defined 以及 library functions。

這方面還在研究當中。

《二》

收到勞力士雜誌第一期。整本都在介紹 Daytona。

《三》

每次想起一些人，都會不自主的暗淡。

2013年10月30日星期三

雜事

2013.10.30

錶耳卡住新買的外套毛線，拿到 RSC 請師傅把毛線清一清，順便註冊。

服務小姐手上掛著迷你版的黑水鬼，頗有意思。

Mini-Lua 繼續卡在 symbol table，不知道怎麼實作比較好，

特別是 array 的部分，可以想想。

2013年10月21日星期一

The Pragmatic Programmer

To be read...

2013年10月20日星期日

La Guitarra - Los Autenticos Decadentes

Tuve un problema de difícil solución,
en una época difícil de mi vida.
Estaba entre la espada y la pared,
y aguantando la opinión de mi familia.

Yo no quería una vida normal,
no me gustaban los horarios de oficina.
Mi espíritu rebelde se reía
del dinero, del lujo y el comfort.

Y tuve una revelación,
ya se que quiero en esta vida.
Voy a seguir mi vocación
será la música mi techo y mi comida.

Porque yo
no quiero trabajar,
no quiero ir a estudiar,
no me quiero casar.

Quiero tocar la guitarra todo el día,
y que la gente se enamore de mi voz.

Porque yo
no quiero trabajar,
no quiero ir a estudiar,
no me quiero casar.

Y en la cabeza tenia
la voz de mi viejo,
que me sonaba como
un rulo de tambor.

Vos, mejor que te afeites,
mejor que madures, mejor que labores.
Ya me cansé de que me tomes la cerveza,
te voy a dar con la guitarra en la cabeza.

Vos, mejor que te afeites,
mejor que madures, mejor que labores.
Ya me cansé de ser tu fuente de dinero,
voy a ponerte esa guitarra de sombrero.

Y tuve una revelación,
ya se que quiero en esta vida.
Voy a seguir mi vocación
será la música mi techo y mi comida.

Porque yo
no quiero trabajar,
no quiero ir a estudiar,
no me quiero casar.

Quiero tocar la guitarra todo el día,
y que la gente se enamore de mi voz.

Porque yo
no quiero trabajar,
no quiero ir a estudiar,
no me quiero casar.

Y en la cabeza tenia
la voz de mi viejo,
que me sonaba como
un rulo de tambor.

Vos, mejor que te afeites,
mejor que madures, mejor que labores.
Ya me cansé de que me tomes la cerveza,
te voy a dar con la guitarra en la cabeza.

Vos, mejor que te afeites,
mejor que madures, mejor que labores.
Ya me cansé de ser tu fuente de dinero,
voy a ponerte esa guitarra de sombrero.

2013年10月15日星期二

Communicate your intentions through your code

Book: Implementation Patterns: Kent Beck

很棒的書，特別是寫了幾年的爛東西後，看這個特別有感覺。

Programs are read more often than they are written.
There is no such thing as “done”. Much more investment will be spent modifying programs than developing them initially.
They are structured using a basic set of state and control flow concepts.
Readers need to understand programs in detail and in concept. Sometimes they move from detail to concept, sometimes from concept to detail.

Using patterns helps programmers write reasonable solutions to common problems, leaving more time, energy, and creativity to apply to the truly unique problems.

Three values that are consistent with excellence in programming are

Communication
Simplicity
Flexibility

The implementation patterns aren’t the way they are “just because”. Each one expresses one or more of the values of communication, simplicity, and flexibility. Principles are another level of general ideas, more specific to programming than the values, that also form the foundation of the patterns.

Several principles:

Local Consequences
Minimize Repetition
Logic and Data Together
Symmetry
Declarative Expression
Rate of Change

2013年10月14日星期一

SQLite Compiler

The Architecture Of SQLite [http://www.sqlite.org/arch.html]

SQL Command Processor 可以往 source code 裡面看：

CAPI3REF: Compiling An SQL Statement
KEYWORDS: {SQL statement compiler}

The sqlite3_prepare function compiles an SQL statement, and produces an equivalent internal object. This object is commonly referred to as a prepared statement in database literature, and is implemented as a bytecode program in SQLite. A bytecode program is an abstract representation of an SQL statement that is run on a virtual machine or an interpreter. For more information, see the later section, Bytecode Programming Language. I use the terms bytecode program and prepared statement interchangeably in this book.

看圖片 SQL compiler 可以再分成三段：

Tokenizer
Parser
Code generator

接下來就往 source code 裡面看進去了。繼續努力！

SQLITE_API int sqlite3_prepare(
sqlite3 *db, /* Database handle */
const char *zSql, /* SQL statement, UTF-8 encoded */
int nByte, /* Maximum length of zSql in bytes. */
sqlite3_stmt **ppStmt, /* OUT: Statement handle */
const char **pzTail /* OUT: Pointer to unused portion of zSql */
);

註解寫的蠻詳細的

((應該使用 sqlite3_prepare_v2，不過因為相容性，所以舊的 API 也會留下來))

現在追到 sqlite3LockAndPrepare，看字面有 lock ((mutex))。

Lock 的 methods 有一對，sqlite3_mutex_enter() 以及 sqlite3_mutex_leave()。

sqlite3BtreeEnterAll() 及 sqlite3BtreeLeaveAll() 就是 backend，裡面有三個主要 modules，B+ tree，Pager，以及 OS Interface ((可以想像 B+ tree 是最頂層的抽象資料結構，每個 file fragments 以 pagers 抽象化，最後 implementor 當然就是 OS 的 file system，這個就看是 Windows 或者是 Unix 或者是你想的到的))。

((這是我的猜測與想像，B+ tree 應該是這樣子的吧？！))

鬼扯一堆，最重要的還是 sqlite3Prepare()，這個得仔細看下去了！

Initialize.
Try to get a read lock on all database schemas.
sqlite3RunParser()
sqlite3VdbeSetSql()

然後這個應該是關鍵：LEMON-generated LALR(1) parser

The Lemon Parser Generator [http://www.sqlite.org/src/doc/trunk/doc/lemon.html]

The main parser program: sqlite3Parser()

[FWD] TimeUnit

http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/TimeUnit.html

A TimeUnit represents time durations at a given unit of granularity and provides utility methods to convert across units, and to perform timing and delay operations in these units.

這是很不錯的設計。

有時候寫程式常常忘記用 second 為單位，或者是用 millisecond 為單位。

何不讓 code 變成 oral language？

2013年10月11日星期五

[FWD] Bloom filters

WIKI: http://en.wikipedia.org/wiki/Bloom_filter

Tutorial: http://billmill.org/bloomfilter-tutorial/

實作細節不外乎 bloom filter 變形以及 hash functions 的選擇。

為什麼會講到 bloom filters？

因為雲端病毒碼就是利用這個技術減少 signatures 的大小。

如果能夠穿過許多道 bloom filters 引擎才上網把完整的 signatures 抓下來。

2013年10月10日星期四

解釋過後好像也沒有比較好

回頭看傻事好有感覺。

那是歷史痕跡不容扭曲。

早已經雲淡風輕。

骨頭裂掉再黏回去就會凸出一塊，轉轉骨頭喀喀啦啦響，那就是痕跡。

以前機車代步，現在公車、捷運、計程車是我的三寶，

每星期騎機車只是為了讓車可以發動。

我也不好意思說有的沒的，倒不是念舊，而是不想讓自己那麼仇恨。

《半生緣》兩人歷盡千帆後再相遇，卻惟有感慨萬千：「世鈞，我們回不過去了。」

這結局才是最美麗的！

至於最近發生的事，暫且不提，反正也是回不過去了。

至於現在發生的事，偷偷告訴大家，完全是個沒進展。

2013年10月9日星期三

ProjectEuler 185 -- TLE on backtracking

Backtracking 只是比較聰明的暴力法，

所以 time complexity 大約還是 10^16。

import sys

DIGIT_COUNT = 5

#DIGIT_COUNT = 15

ANSWER = [0] * DIGIT_COUNT

GUESSES = { 
    "90342" : 2, 
    "70794" : 0, 
    "39458" : 2, 
    "34109" : 1, 
    "51545" : 2, 
    "12531" : 1,
}

#GUESSES = {
#    "5616185650518293" : 2,
#    "3847439647293047" : 1,
#    "5855462940810587" : 3,
#    "9742855507068353" : 3,
#    "4296849643607543" : 3,
#    "3174248439465858" : 1,
#    "4513559094146117" : 2,
#    "7890971548908067" : 3,
#    "8157356344118483" : 1,
#    "2615250744386899" : 2,
#    "8690095851526254" : 3,
#    "6375711915077050" : 1,
#    "6913859173121360" : 1,
#    "6442889055042768" : 2,
#    "2321386104303845" : 0,
#    "2326509471271448" : 2,
#    "5251583379644322" : 2,
#    "1748270476758276" : 3,
#    "4895722652190306" : 1,
#    "3041631117224635" : 3,
#    "1841236454324589" : 3,
#    "2659862637316867" : 2,
#}

def is_unique(digit, position):
    has_more = False

def check_guessing(dimension):
    for guess in GUESSES:
        correct_count = 0
        for i in range(dimension):
            if ANSWER[i] == int(guess[i]):
                correct_count += 1
            if correct_count > GUESSES[guess]:
                return False
        if correct_count + DIGIT_COUNT - dimension < GUESSES[guess]:
            return False
    return True

def backtracking(dimension):
    if not check_guessing(dimension):
        return
    if dimension == DIGIT_COUNT:
        print('Found =>', ANSWER[0:dimension])
        return
    for i in range(10):
        ANSWER[dimension] = i
        backtracking(dimension + 1)    
    
def solve():
    for i in range(10):
        ANSWER[0] = i
        backtracking(1)
    
def main():
    solve()
    
if __name__ == '__main__':
    sys.exit(main())

2013年10月8日星期二

Books about programming contest

Books about programming

Programming Challenges [http://acm.cs.buap.mx/downloads/Programming_Challenges.pdf]
Art of Programming Contest [http://www.acmsolver.org/books/Art_of_Programming_Contest_SE_for_uva.pdf]

2013年10月6日星期日

[Java] insertion sort & merge sort

要熟悉某個語言，最簡單的方式就是寫一次基本的演算法。

此外，將來要面試科技公司，基本演算法更要知道怎麼寫，

怎麼用原子筆寫，這很重要。

以某科技公司為例，主管當然知道考古題的存在，

主管會認為題目已經外洩沒理由考不好，但偏偏就是有面試者考不好，

而且這間公司好的標準異常寬鬆，100分拿35分就可以了。

有時候誠意真的很重要。

~~如果我是主管的話，正妹直接錄取 ((逃))((當作在選後宮))~~

正題：

Insertion sort，對於小的 array 可以用這個實做

merge sort，divide and conquer 基本應用

public class Sorting {
public static void insertionSort(int[] array) {
for (int j = 1; j < array.length; j++) {
int key = array[j];
int i = j - 1;
while (i >= 0 && array[i] > key) {
array[i+1] = array[i];
i--;
}
array[i + 1] = key;
}
}

public static void mergeSort(int[] array) {
mergeSort(array, 0, array.length - 1);
}

private static void mergeSort(int[] array, int p, int r) {
if (p >= r) {
return;
}
int q = (p + r)/2;
mergeSort(array, p, q);
mergeSort(array, q + 1, r);
merge(array, p, q, r);
}

private static void merge(int[] array, int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;

int[] left = new int[n1 + 1];
int[] right = new int[n2 + 1];

for (int k = 0; k < n1; k++) {
left[k] = array[p + k];
}
for (int k = 0; k < n2; k++) {
right[k] = array[q + 1 + k];
}
left[n1] = Integer.MAX_VALUE;
right[n2] = Integer.MAX_VALUE;

int i = 0;
int j = 0;
for (int k = p; k <= r; k++) {
if (left[i] <= right[j]) {
array[k] = left[i];
i++;
}
else {
array[k] = right[j];
j++;
}
}
}
}

2013年10月1日星期二

[Programming] TIPS TO BE COMPETITIVE

Question 1

There are n webpages (1 ≤ n ≤ 10M). Each webpage i has different page rank r_i. You want to pick top 10 pages with highest page ranks. Which method is more feasible?
(a) Load all n webpages’ page rank to memory, sort, and pick top 10.
(b) Use priority queue data structure (heap).

Question 2

Given a list L of up to 10K integers, you want to frequently ask the value of sum(i, j), i.e. the sum of L[i] + L[i+1] + ... + L[j]. Which data structure should you use?
(a) Simple Array.
(b) Balanced Binary Search Tree.
(c) Hash Table.
(d) Segment Tree.
(e) Suffix Tree.
(f) Simple Array that is pre-processed with Dynamic Programming.

Question 3

You have to compute the ‘shortest path’ between two vertices on a weighted Directed Acyclic Graph (DAG) with |V |, |E| ≤ 100K. Which algorithm(s) can be used?
(a) Dynamic Programming + Topological Sort.
(b) Breadth First Search.
(c) Dijkstra’s.
(d) Bellman Ford’s.
(e) Floyd Warshall’s.

Question 4

Which algorithm is faster (based on its time complexity) for producing a list of the first 10K prime numbers?
(a) Sieve of Eratosthenes.
(b) For each number i ∈ [1 − 10K], test if i is a prime with prime testing function.

2013年9月30日星期一

[ProjectEuler] 逆水行舟

之前被超車名次掉到十名之外，剛好卡在200題大關前頭。

為了一口氣只好不斷地往前追。

Country: Taiwan

Found 296 members

1 2 3 Go to Page:

Showing 1 to 100 out of 296

Username

Country

Solved

Level

Language

utomaya

400+

C/C++

chsu

385

Matlab

janshigola

298

Mathematica

xmk

269

progheal

261

Mathematica

jchaoisaac

237

2013年12月31日 星期二

2013年12月30日 星期一

2013年12月16日 星期一

2013年12月11日 星期三

2013年12月10日 星期二

2013年12月9日 星期一

2013年11月29日 星期五

2013年11月28日 星期四

2013年11月27日 星期三

2013年11月26日 星期二

2013年11月25日 星期一

2013年11月24日 星期日

2013年11月19日 星期二

2013年11月13日 星期三

2013年11月6日 星期三

2013年10月30日 星期三

2013年10月21日 星期一

2013年10月20日 星期日

2013年10月15日 星期二

2013年10月14日 星期一

2013年10月11日 星期五

2013年10月10日 星期四

2013年10月9日 星期三

2013年10月8日 星期二

2013年10月6日 星期日

2013年10月1日 星期二