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 有幾題相當困難，還在思考怎麼做。

[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]

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

新的計畫也就是把 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)。

[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 ' ' 

短短的蠻可愛的

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

到年底的新目標

一。早睡早起。

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



二。持續資助。

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

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

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

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

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

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

Milgauss

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

貼圖自爽一下。

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

還是雜事

《一》

Mua interpreter 卡在怎麼 interpret function call，

包括 user-defined 以及 library functions。

這方面還在研究當中。



《二》

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



《三》

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