Liuw's Thinkpad

可以大言不慚地吼著說：“我寫的！”

複用不好，很多冗餘代碼。設計不好，接口不明。寫法丑，不夠Pythonic。

唯一的優點是它確實能解決我的問題。數學建模一個題目“最佳陣容”，要算出所有得分會大于某個特定分數的出場陣容。

其實是一個0-1背包問題，但是約束條件比較多，算法自己又不在行，用回溯剪枝寫不出來。Lingo的規劃又只能做出一個解。

還好，動手算了一下，這個組合數也不過百萬級別，這對於現代的電腦完全是小case。所以用最丑的辦法寫了一個出來，當然，還是有點優化的。

程序我也不打算別人看懂，自己以后估計也不會再看，所以就不多解釋了。放這里做個留念，看看自己寫的程序有多丑。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Author: Liu Wei

def combination(items, n=None):
    if n is None:
        n = len(items)
    for i in xrange(len(items)):
        v = items[i:i+1]
        if n == 1:
            yield v
        else:
            rest = items[i+1:]
            for c in combination(rest, n-1):
                yield v + c

def permutation(items, n=None):
    if n is None:
        n = len(items)
    for i in xrange(len(items)):
        v = items[i:i+1]
        if n == 1:
            yield v
        else:
            rest = items[:i] + items[i+i:]
            for p in permutation(rest, n-1):
                yield v + p

# highest score for each player
scores = [
    [9.4, 9.8, 10, 9.5, 9.4, 9.9, 10, 10, 9.4, 9.7],
    [10, 9.4, 9.5, 9.9, 9.7, 9.9, 10, 10, 9.8, 9.5],
    [9.8, 10, 9.4, 9.7, 9.3, 9.1, 9.3, 9.9, 10, 9.6],
    [9.9, 9.6, 10, 10, 9.9, 9.4, 9.8, 9.8, 9.9, 9.8]
    ]

# final array
array = [
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
    ]

# sparse array for 6 cols
sparse_array = [
    [0, 0, 0, 0, 0, 0], \
    [0, 0, 0, 0, 0, 0], \
    [0, 0, 0, 0, 0, 0], \
    [0, 0, 0, 0, 0, 0], \
    ]

def __sparse_array_check_valid():
    global sparse_array
    # 6 cols
    for i in xrange(6):
        sum = 0
        for j in xrange(4):
            sum += sparse_array[j][i]
        if sum > 3:
            return False
    return True

def __sparse_array_init():
    global sparse_array
    sparse_array =  [[0, 0, 0, 0, 0, 0], \
                    [0, 0, 0, 0, 0, 0], \
                    [0, 0, 0, 0, 0, 0], \
                    [0, 0, 0, 0, 0, 0], \
                    ]

def __sparse_array_set_row(p, r):
    global sparse_array
    a, b = p
    sparse_array[r][a] = 1
    sparse_array[r][b] = 1

def __sparse_array_clear_row(r):
    global sparse_array
    for i in xrange(len(sparse_array[r])):
        sparse_array[r][i] = 0

def sparse_array_output():
    global sparse_array
    print sparse_array

# generator for sparse arrays
def sparse_array_generator():
    global sparse_array
    # 4 rows
    __sparse_array_init()
    for r0 in combination(range(6), 2):
        __sparse_array_clear_row(0)
        __sparse_array_set_row(r0, 0)
        for r1 in combination(range(6), 2):
            __sparse_array_clear_row(1)
            __sparse_array_set_row(r1, 1)
            for r2 in combination(range(6), 2):
                __sparse_array_clear_row(2)
                __sparse_array_set_row(r2, 2)
                for r3 in combination(range(6), 2):
                    __sparse_array_clear_row(3)
                    __sparse_array_set_row(r3, 3)

                    if __sparse_array_check_valid():
                        yield sparse_array
                    #    sparse_array_output()

def __array_set_col(c):
    global array
    for i in xrange(len(array)):
        array[i]1 = 1

def __array_clean_col(c):
    global array
    for i in xrange(len(array)):
        array[i]1 = 0

def __array_init():
    global array
    array = [
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        ]

def set_allround_player(a):
    for i in a:
        __array_set_col(i)

def set_individual_player(sa, s):
    global array
    for i in range(4):
        for j in range(6):
            array[i][s[j]] = sa[i][j]

def array_generator():
    global array
    for g in combination(range(10), 4):
        # select cols for sparse array in big array
        s = [i for i in range(10) if i not in g]
        __array_init();
        # start to manipulate the array
        # first select all-round player
        set_allround_player(g)
        # then cope with individual event player
        for sa in sparse_array_generator():
            set_individual_player(sa, s)
            yield array

def calc_score(a):
    sum = 0
    for i in range(len(a)):
        for j in range(len(a[0])):
            sum += a[i][j] * scores[i][j]
    return sum

def final_generator():
    for a in array_generator():
        total_score = calc_score(a)
        if total_score >= 236.2:
            yield [a, total_score]

import os
os.chdir("d:/liuw/")
f = file("output", 'a')
for solution, total_score in final_generator():
    f.write(str(solution))
    f.write('\n')
    f.write(str(total_score))
    f.write('\n\n')
f.close()

用到了大量的generator，因為怕會內存不足。但是總yield一個全局數組總覺得有點別扭。話說我們這次的做題目用到了Lingo、Python、Matlab和C，果然是程序員的命，全部學計算機的人組個隊還是有好處的。

最後在電腦上跑了5分鐘左右，結果就出來了。假如想再快點，還可以做雙核並行計算。不過自己這方面沒什麽研究，程序也要得比較急，就沒有多管。

m-x flush-lines
^$

今天第一次去給老闆跑腿，圓滿了。得總結一下。

因為大部份人都是不喜歡跑腿的，所以看到老闆來電話一定要三思而後行，首先想好老闆在此特定時刻找你的所有可能性，並且想好說辭。不過今天我倒無所謂，因為也很久沒有出去運動過了，就當是去運動一下。

出去一定要帶點錢，因為老闆可能要買東西，而她給的錢是不一定夠的（因為她自己也沒什麽概念）。為了避免來來回回的麻煩，最好自己帶上一到兩百。不過這也是有風險的，老闆貴人事忙，萬一哪一天她忘記這回事了，那就是自己給老闆做貢獻了。

出去給老闆花什麽錢了，一定要有收據之類的東西，這樣大家都放心。這可以給老闆辦事認真細緻的印象，這種人才夠可靠。有什麽老闆吩咐外的事情，一定要打電話問清楚老闆的意思，有好的解決方案也得先讓她首肯，不然那就是自作聰明了。

細節決定成敗，不但要會做事，還要做得夠細緻。

再寫點題外的話，今天去到老闆的家，覺得挺亂的。成功人士也不是所有方面都那麼成功的，呵呵。

在某处看到一篇文章，使用grep来找回没有分区表的硬盘中的文本文件内容。基本命令是：

grep "keyword" /dev/DEVICE

有可能需要加上其他的一些选项。

能这样做是因为在Unix中万物皆文件，即使没有Filesystem的信息，也可以通过bypass掉Filesystem的方法去读取block，得到raw data。

这个方法是有局限的。Filesystem处理数据时以block为单位，而多block的文件，block的分布不一定是连续的。也就是说grep也许能找到一部分数据，但是不大可能把所有的数据都找回来。当然，一个block一般是1K或者4K找回来的数据量对于一个文本文件来说也是相当可观的了。

为了证实我的想法，我做了以下的实验。

dd if=/dev/urandom of=hd.img bs=1M count=10

之所以用urandom而不是zero做输入，是为了增加数据，模拟真实的Filesystem。

losetup hd.img /dev/loop0

把这个文件连接到loop0，成为一个设备。

mkfs.ext3 -b 1024 /dev/loop0
mount /dev/loop0 /mnt
echo -e "This is a small file for testing.\nsecond line\nthird line" > /mnt/f1
umount /mnt

建立block大小为1024的ext3分区，然后挂载，向里面写入少量数据（少于1个block）。

grep --binary-files=text -z "file" /dev/loop0

不用-z的话，只会grep一行。

这样确实可以看到原来文件的内容。假如文件修改过有几个版本的话，可能还可以看到几个版本的内容。也许这是一个提高Filesystem效率的措施。

再测试大于1 block的文件。

perl -e 'print "string1 " x 128; print "string2 " x 128' > /mnt/f2
perl -e 'print "string3 " x 128; print "string4 " x 128' > /mnt/f3
for i in `seq 4 9`; do echo "$i" > "f$i" ; done
perl -e 'print "paddin" x 128' >> /mnt/f2
perl -e 'print " ssssss " x 128' >> /mnt/f2
...

上面其实进行了很多操作，这里就不一一列出了。block大小为1K，用stat可以看到它们的I/O block。之所以做多个文件，是为了防止ext3 bitmap在再次分配block的时候分配连续block，模拟真实环境。写完文件之后记得sync或者umount，把cache都flush到硬盘上。

再grep一次，可以发现各种数据是夹杂在一起的。

所以，最好还是注意保护自己的Filesystem吧。这些技巧只能解决小问题。

無任何實用價值，無聊的時候寫的，做ASCII Art動畫。

(defun cinema (file fps)
  (interactive "sFile: \nnFPS: ")
  (let ((int-time (/ 1.0 fps)))
    (find-file file)
    (while t
      (scroll-up 25)
      (sit-for int-time))))

具體效果見 ASCII Art Bad Apple Emacs 。

近來比較少寫blog，實在是比較忙。用繁體寫是因為看簡體的字多了眼花，得換換口味了。

72pines的頁面很奇怪，假如我不用搜狗的全網加速功能去開，出來的頁面就沒有樣式了。可能它有一部份的伺服器被教育網墻掉了（？）。

在王亮先生的Emacs定制和擴展中，找到一個“能獲取root權限的輔助腳本”，解決了我一直頭痛的一個問題。原理挺簡單，使用TRAMP來完全的。以前一直以為TRAMP主要是用于遠程編輯文件的，沒有發現這個功能，沒仔細看Manual的後果。

(defun wl-sudo-find-file (file dir)
  (find-file (concat "/sudo:localhost:" (expand-file-name file dir))))

當然，其他的內容也很精彩。

第二個，是從Wowubuntu得來的三手信息。爲什麽說是三手呢，因為它也只是轉載的。主要是講Bash shell的一些奇技淫巧。

最牛B的 Linux Shell 命令 系列连载，有點標題黨了，呵呵。

比較有趣的是活用history功能的條目，比如說sudo執行前一條命令是：

$ sudo !!

兩個嘆號“!!”等價于“!-1”，數字換成其他也是可以的，不過誰記得了那麼多啊。

另外一個有趣的功能就是Bash的替換（原來它也有啊，呵呵）：

$ !!:s/foo/bar/

很熟悉的語法，只是從來沒有想到過還有這個功能，sigh。

文章提到上面兩個技巧都是出自The Definitive Guide to Bash Command Line History。

還有一些其他的技巧，不僅僅限於Bash本身，不一而足。由於有的要么知道了，要么對我自己用處不大，這里就不多記了。

1. 凡单笔画与字根相连或带点结构都视为杂全型，如“天”、“千”、“丸”、“太”。

2. 区分汉字结构时，按“能散不连”的原则来进行，如“矢”、“卡”、“严”、“走”都视为上下型。

3. 含两字根且相交者属杂合型，如“乐”、“串”、“电”、“本”。

4. 下含“走之”字为杂合型，如“进”、“过”、“这”、“边”。

5. 属于“连”和“交”的汉字一律视为杂合型。