2008年9月10日 星期三

Share Screen 備忘

Screen 是一個很古老又好用的工具，雖然自已不是很常用…不過有時在幫別人做一些事情時，我們可以用 screen 的 share 功能，多人同時使用同一個 screen。在 demo，教學上實在蠻方便的。
很久之前有在用，不過一陣子沒用後就忘了，寫下來以免自已又忘掉。

1． sudo chmod u+s /usr/bin/screen
2． sudo chmod 755 /var/run/screen
3． screen
4．在另一個 terminal 上 screen -x

如要多人 share

1. ^a + :multiuser on
2. ^a + :acladd

3. 另一個人就可以 screen -x /[pid] 連上去
張貼者： 於 沒有留言:
標籤：

2008年7月30日 星期三

Using git-svn migrate svn repository server

Suppose we create a project on one SVN repository server say A, however that server is going to close and disappear. And we still want to develop that project. So we found another repository server say B as our new host. However if we cannot use svnadmin commit on server B.(if you can you can use this) How do we migrate?

git-svn gives us a chance to do such thing.

Now we have server A and want to migrate project to server B.

support you are in /tmp
1. git-svn clone svn://server_A/my_project my_project_from_A
2. git clone file:///tmp/my_project_from_A my_project_sent_to_B
3. cd my_project_sent_to_B
4. git-svn init svn+ssh://whoyouare@server_B/my_project
(Here svn://server_B/my_project should be empty, make sure you can commit)
5. git-svn fetch
6. git-svn set-tree [the very first one commit in master]
note:1
7. git-svn dcommit
Done, Happy hacking...

Step 1: clone the svn log from old repository (let it read only)
Step 2: does not clone the svn infomation in server_A, so that we will have a clean space to do the hack
Step 4, 5: get the information from Server_B and get the initial point

Step 6: push the very first one commit in master to server B svn
Step 7: commit the whole tree to server B

Combining these skills actually you can migrate/convert/clone many kinds of SCM.

extension reading:GIT first SVN later
Note 1:If you meet
CONFLICT (delete/modify): XXXX deleted in HEAD and modified in adding License declare. Version adding License declare or XXXX left in tree.

you can
git status
then
git add (those unmerged files/directories)
git rebase --continue
張貼者： 於 沒有留言:
標籤：

2008年7月17日 星期四

Easy Sample to create ipk files

step 1. ceate 2 new temp dirs say "_ipkg_temp" "_ipkg_tar"
step 2. use _ipkg_temp as root directory put your stuff there:
for example:
usr/bin/lala.sh
step 3. pushd _ipkg_temp; tar -czf ../ipkg_tar/data.tar.gz .; rm -rf * ; popd
step 4. create control file in _ipkg_temp
fill the following fields: (CONTROL="control")
        echo "Package: Your_package_name"   >  ${CONTROL}
        echo "Version: 0.1"             >> ${CONTROL}
        echo "Description: your_descriptions">> ${CONTROL}
        echo "Section: base"            >> ${CONTROL}
        echo "Priority: optional"       >> ${CONTROL}
        echo "Maintainer: Noname"      >> ${CONTROL}
        echo "Architecture: all"        >> ${CONTROL}
        echo "Homepage: http://ooo.xxx.vvv/svn/trunk"       >>  ${CONTROL}
        echo "Tags: group::unknown"       >> ${CONTROL}
        echo "Depends: ooxxooxx"    >> ${CONTROL}
        echo "Source: http://ooxxooxx.ooxx.vvvoo/" >>  ${CONTROL}
then tar -czf ../_ipkg_tar/control.tar.gz .
step 5. in _ipkg_tar create debian-binary file contents 2.0
echo "2.0" > debian-binary
step 6. in _ipkg_tar ar the ipkg file
ar -crf ooxx_0.1_arm.ipkg debian-binary data.tar.gz control.tar.gz

Done :-)

reference http://code.google.com/p/comic-reader/source/browse/trunk/packer/pack_eet2ipk.sh
張貼者： 於 沒有留言:
標籤：

2008年7月3日 星期四

Icescream

和大家分享一個好物： ICE SCREAM



它是一個分散式的 compiler 架構…
在Debian 和 Ubuntu 下相當好安裝… 只要
sudo aptitude install icecc icecc-monitor
然後
export PATH=/usr/lib/icecc/bin:$PATH
就好了

在同一個網域下，把一台機器設成 scheduler (一台就好)
cat /etc/default/icecc
# Defaults for icecc initscript
# sourced by /etc/init.d/icecc
START_ICECC="true"
START_ICECC_SCHEDULER="false"

把 false 改成 true
sudo /etc/init.d/icecc restart
一切就搞定了…

今天下午用了 10 台 4 CPU 的機器玩了一下 compile qtopia
make -j 20
本來要一個 CPU 要compile 快兩個小時的東西，十幾分鐘就搞定了。

^_^
張貼者： 於 沒有留言:
標籤：

2008年6月25日 星期三

sudoku solver partII

Sudoku Solver 比賽順利結束了，這個比賽相當看重速度，所以在加速和結構上做了相當大的取捨，也對於 python 這個語言的特性有一些更深入的了解。（這是小弟的第二支 python 程式）
和大家分享一下小弟的加速過程…

1. 第一步當然是先寫 Test Framework
Filename: testcase.py

#!/usr/bin/python

import sys
import tick_solver

if sys.argv.__len__() >= 2 and sys.argv[1] :
    name = sys.argv[1]
else:
    name = "case_01.txt"

bb = tick_solver.Board()
bb.file_read(name)

def TC_Board_group_get(bb):
    if bb.group_get(0, 0) == 0 and \
            bb.group_get(2, 2) == 0 and \
            bb.group_get(2, 3) == 1 and \
            bb.group_get(8, 8) == 8 and \
            bb.group_get(5, 7) == 5 and \
            bb.group_get(6, 7) == 8 and \
            bb.group_get(3, 10) == -1 and \
            bb.group_get(3, 0) == 3:
                print "group_get passed!!"
    else:
        print "group_get failed!!"

def TC_Board_data_print(bb):
    bb.data_print()
    bb.pretty_print()

def TC_Board_group_print(bb):
    for i in range(0,9):
        print "Rows["+str(i)+ "]=" + str(bb.Rows[i].left)
        print "Columns["+str(i)+ "]=" + str(bb.Columns[i].left)
        print "Groups["+str(i)+ "]=" + str(bb.Groups[i].left)

def TC_Board_possible_value_get(bb):
    for x in range(0,9):
        for y in range(0,9):
            print "("+str(x)+","+str(y)+") = "+str(bb.possible_value_get(x,y))
            
def TC_Board_puzzle_solving(bb):
    bb.puzzle_solving()
    bb.pretty_print()

import cProfile
def _TC_Board_profileing():
    BB.run(LALA)

def TC_Board_profileing():
    cProfile.run('BB.run(LALA)')

LALA = bb.data[:]
TC_Board_group_get(bb)
TC_Board_data_print(bb)
TC_Board_group_print(bb)
TC_Board_possible_value_get(bb)
bb.pretty_print()
BB = tick_solver.Board()
TC_Board_profileing()
BB.pretty_print()


再開始實做… （小弟習慣先寫 test case 再來寫實做，testcase 會和程式一同成長）
2. 決定演算法
從google 上找出sudoku 的rule
a. 每個 raw 的九個數字都不同
b. 每個 column 的九個數字都不同
c. 每個 group 的九個數字都不同
依這三條 rule 找出 candidates , 再從candidate 最少的 cell 猜起。
trace 的路徑是走迷宮的方式。

3. 開出 functions 實作每個 function , 先不管速度，先正確了再說

Filename: tick_solver.py


ROWS=9
COLUMNS=9
TOTAL_ELEMENTS=81

class Group:
    def __init__(self):
        self.left = range(1, COLUMNS+1)
    def set(self, x):
        if self.left.__contains__(x):
            self.left.remove(x)
            return True
        return False
    def unset(self, x):
        if not self.left.__contains__(x):
            self.left.append(x)
            return True
        return False
    def candidate(self):
        return self.left

class Cmd_Node:
    def __init__(self, x, y, v, Data):
        self.x = x
        self.y = y
        self.v = v
        self.D = []
        self.tried = []
        for d in Data:
            if d != v:
                self.D.append(d)
        self.tried.append(v)

    def retry(self):
        v=self.D.pop()
        self.tried.append(v)
        self.v = v;
        return v;
    def pretty_print(self):
        print "x="+str(self.x)+"  y="+str(self.y)+"  v="+str(self.v)+"  D="+str(self.D)+ "  Tried="+str(self.tried)

class Board:
 def __init__(self, name="case_01.txt"):
            self.num_rest=TOTAL_ELEMENTS
            self.trace = []
            self.DATA = []
            self.data = []
            self.Rows = []
            self.Columns = []
            self.Groups  = []
            self.name = name
            for i in range(0, ROWS):
                self.Rows.append(Group())
                self.Columns.append(Group())
                self.Groups.append(Group())
            for i in range(0, ROWS):
                self.data.append([0, 0, 0, 0, 0, 0, 0, 0, 0])
                self.DATA.append([[], [], [], [], [], [], [], [], []])
            if not self.file_read(self.name):
                print "Warning: Bad sudoku!!"

 
        # index from 0 - 8
 def value_set(self, x, y, v):
            if (v==0):
                return True
            if self.Columns[y].candidate().__contains__(v) and \
                    self.Rows[x].candidate().__contains__(v) and \
                    self.Groups[self.group_get(x,y)].candidate().__contains__(v):
                self.data[x][y]  = v
                self.Columns[y].set(v)
                self.Rows[x].set(v)
                self.Groups[self.group_get(x,y)].set(v)
                self.num_rest = self.num_rest - 1;    
                return True
            return False

        def value_unset(self, x, y):
            v = self.data[x][y]
            self.data[x][y] = 0
            self.Columns[y].unset(v)
            self.Rows[x].unset(v)
            self.Groups[self.group_get(x,y)].unset(v)
            self.num_rest = self.num_rest + 1;
            for x in range(0,9):
                for y in range(0,9):
                    self.DATA[x][y] = self.possible_value_get(x,y)


        def group_get(self, x, y):
            #if (x < 0 or x > 8 or y < 0 or y > 8):
            #    return -1
            return int(x/3)*3 + int(y/3) 

        def data_print(self):
            print self.data

        def pretty_print(self):
            for i in range(0,ROWS):
                print self.data[i]

        def file_read(self, name):
            f = open(name, "r")
            for x in range(0,9):
                for y in range(0,9):
                    if not self.value_set(x,y,int(f.read(2))):
                        print "Bad sudoku!!"
                        return False
            return True

        def possible_value_get(self, x, y):
            if (self.data[x][y] != 0):
                return
            ans = [];
            Group = self.Groups[self.group_get(x, y)].candidate()
            Row   = self.Rows[x].candidate()
            Column= self.Columns[y].candidate()
            for i in Group:
                if i in Row and i in Column:
                    ans.append(i);
            return ans;

        def puzzle_solving_iterate(self):
            min_x = 0
            min_y = 0
            min=10
            for x in range(0,9):
                for y in range(0,9):
                    pos = self.possible_value_get(x,y)
                    self.DATA[x][y] = pos
                    if pos == None:
                        continue
                    if len(pos) == 1:
                        v = pos[0]
                        self.value_set(x,y,v)
                        self.trace.append(Cmd_Node(x,y,v, pos))
                    if pos.__len__() < min:
                        min_x = x
                        min_y = y
                        min = pos.__len__()
            if min == 1:
                return True
            #guess has to be made
            if self.DATA[min_x][min_y].__len__() > 0:
                guess = self.DATA[min_x][min_y][0]
                self.trace.append(Cmd_Node(min_x, min_y, guess, self.DATA[min_x][min_y]))
                return self.value_set(min_x, min_y,guess)
            return False

        def puzzle_solving(self):
            while self.num_rest > 0:
                if self.puzzle_solving_iterate():
                    continue
                continue_flag=True
                while continue_flag:
                    cmd = self.trace.pop()
                    if cmd.D.__len__()==0:
                        self.value_unset(cmd.x, cmd.y)
                        continue
                    self.value_unset(cmd.x, cmd.y)
                    for x in range(0,9):
                        for y in range(0,9):
                            pos = self.possible_value_get(x,y)
                            self.DATA[x][y] = pos
                    while cmd.D.__len__() > 0:
                        v = cmd.retry()
                        if self.DATA[cmd.x][cmd.y].__contains__(v):
                            self.value_set(cmd.x, cmd.y, v)
                            self.trace.append(cmd)
                            continue_flag = False
                            break




4. run a lot of test cases to check out the bottleneck

如 case 

0 7 8 1 0 0 5 0 0
0 0 6 0 0 0 0 0 0
5 0 0 0 4 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 4 8 0 0 0 0 0
0 0 0 0 0 9 2 0 3
0 0 1 0 0 2 0 0 8
9 6 3 0 0 0 0 5 0
0 0 0 4 0 0 3 0 9

以下是test case 分析出來的結果

         172502 function calls in 0.651 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.651    0.651 :1()
        1    0.000    0.000    0.651    0.651 testcase.py:45(_TC_Board_profileing)
        1    0.000    0.000    0.002    0.002 tick_solver.py:102(file_read)
    34101    0.318    0.000    0.507    0.000 tick_solver.py:111(possible_value_get)
       98    0.033    0.000    0.188    0.002 tick_solver.py:123(puzzle_solving_iterate)
      909    0.004    0.000    0.005    0.000 tick_solver.py:14(unset)
        1    0.006    0.006    0.649    0.649 tick_solver.py:150(puzzle_solving)
    53544    0.079    0.000    0.079    0.000 tick_solver.py:19(candidate)
      341    0.002    0.000    0.002    0.000 tick_solver.py:23(__init__)
       20    0.000    0.000    0.000    0.000 tick_solver.py:34(retry)
        1    0.000    0.000    0.002    0.002 tick_solver.py:43(__init__)
      442    0.007    0.000    0.017    0.000 tick_solver.py:64(value_set)
       27    0.000    0.000    0.000    0.000 tick_solver.py:7(__init__)
      303    0.064    0.000    0.424    0.001 tick_solver.py:78(value_unset)
     1152    0.004    0.000    0.006    0.000 tick_solver.py:9(set)
    18535    0.044    0.000    0.044    0.000 tick_solver.py:90(group_get)
     4397    0.006    0.000    0.006    0.000 {len}
    52821    0.073    0.000    0.073    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
      323    0.001    0.000    0.001    0.000 {method 'pop' of 'list' objects}
       81    0.000    0.000    0.000    0.000 {method 'read' of 'file' objects}
     1152    0.002    0.000    0.002    0.000 {method 'remove' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {open}
     4249    0.008    0.000    0.008    0.000 {range}


我們會發現
possible_value_get被 call 了 34101 次，花了 0.318 秒
candidate 被 call 了 53544 次…花了 0.079 秒
list 的 append 被 call 了 52821 次 花了 0.073 秒

種種的數據告訴我 possible_value_get 是最大的 bottleneck
array 的 operation 過於 大量且昂貴
而在這，我選擇的方式是…改變 Group 存數字的方式：用 binary operations
所以 Group 就變成了

class Group:
    def __init__(self, value=0x1ff):
        self.left = value
    def set(self, x):
        if self.left & (1 << (x-1)):
            self.left &= (~(1<< (x-1)))
            return True
        return False
    def unset(self, x):
        if not self.left & (1 << (x-1)):
            self.left |= (1 << (x-1))
            return True
        return False
    def contains(self, x):
        return not not self.left & (1 << (x-1))
    def len(self):
        ans = 0
        v = self.left;
        while v:
            v &= v -1
            ans += 1
        return ans

def len(v):
    ans=0
    while v:
        v &= v - 1
        ans += 1
    return ans

def min_value(V):
    v=1
    while not V & 1:
        V = V >> 1
        v+=1
    return v


而 possible_value_get 變成了

        def possible_value_get(self, x, y):
            return self.Groups[(int(x/3)*3 + int(y/3))].left & self.Rows[x].left & self.Columns[y].left


沒錯…就變成了兩個 operations
而時間從 變成 0.651

27546 function calls in 0.126 CPU seconds
   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.126    0.126 :1()
        1    0.000    0.000    0.126    0.126 testcase.py:45(_TC_Board_profileing)
        1    0.001    0.001    0.002    0.002 tick_solver.py:114(file_read)
     7280    0.024    0.000    0.024    0.000 tick_solver.py:127(possible_value_get)
      128    0.042    0.000    0.104    0.001 tick_solver.py:136(puzzle_solving_iterate)
     1161    0.002    0.000    0.002    0.000 tick_solver.py:14(unset)
        1    0.007    0.007    0.124    0.124 tick_solver.py:172(puzzle_solving)
     1404    0.002    0.000    0.002    0.000 tick_solver.py:19(contains)
    12148    0.028    0.000    0.028    0.000 tick_solver.py:29(len)
      415    0.001    0.000    0.001    0.000 tick_solver.py:37(__init__)
       30    0.000    0.000    0.000    0.000 tick_solver.py:44(retry)
        1    0.000    0.000    0.002    0.002 tick_solver.py:56(__init__)
       27    0.000    0.000    0.000    0.000 tick_solver.py:7(__init__)
      526    0.007    0.000    0.013    0.000 tick_solver.py:76(value_set)
     1404    0.003    0.000    0.003    0.000 tick_solver.py:9(set)
      387    0.003    0.000    0.006    0.000 tick_solver.py:90(value_unset)
      490    0.001    0.000    0.001    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
      387    0.001    0.000    0.001    0.000 {method 'pop' of 'list' objects}
      161    0.000    0.000    0.000    0.000 {method 'read' of 'file' objects}
        1    0.000    0.000    0.000    0.000 {open}
     1591    0.003    0.000    0.003    0.000 {range}


從快的我們會發現 bottleneck 變成了
12148 0.028 0.000 0.028 0.000 tick_solver.py:29(len)
7280 0.024 0.000 0.024 0.000 tick_solver.py:127(possible_value_get)
由於我是用 binary operation 算 len 變成一個 cost 相當高的事。而小弟覺得用查表法實在不夠好玩… 就是不肯用，所以就找出 len 的使用點，只做最必要的計算。(其實還可以用其它變數去存…這也會比較快)
而possible_value_get 其實已經很快了…可是因為被 call 的次數很多，所以太花時間 （大多在 type checking 和 stack jump） 所以就直接 inline 到被 call 的地方

如此一直找 bottleneck 的位置，不停的 "反" refactoring
最後變成

         2655 function calls in 0.039 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.039    0.039 :1()
      387    0.002    0.000    0.002    0.000 tick_solver.py:107(value_unset)
        1    0.000    0.000    0.000    0.000 tick_solver.py:137(array_get)
        1    0.031    0.031    0.038    0.038 tick_solver.py:149(puzzle_solving)
      387    0.001    0.000    0.001    0.000 tick_solver.py:29(len)
      415    0.001    0.000    0.001    0.000 tick_solver.py:44(__init__)
       30    0.000    0.000    0.000    0.000 tick_solver.py:51(retry)
        1    0.000    0.000    0.000    0.000 tick_solver.py:68(reinit)
       27    0.000    0.000    0.000    0.000 tick_solver.py:7(__init__)
        1    0.000    0.000    0.039    0.039 tick_solver.py:84(run)
      526    0.003    0.000    0.003    0.000 tick_solver.py:92(value_set)
      490    0.001    0.000    0.001    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
      387    0.001    0.000    0.001    0.000 {method 'pop' of 'list' objects


又快了三倍 ^_^

然而在高興之餘卻發現到有一些 test case 會跑非常的久

tick@tock:~/work/sudoku>./testcase.py case_09.txt 
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 9, 0, 0]
[0, 0, 0, 0, 6, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 9, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 5, 0]
[0, 0, 0, 0, 0, 0, 8, 0, 0]
[0, 9, 0, 0, 0, 0, 0, 3, 0]
[0, 0, 0, 7, 0, 0, 0, 0, 0]
         3838777 function calls in 47.685 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   47.685   47.685 :1()
        1    0.000    0.000   47.685   47.685 testcase.py:47(_TC_Board_profileing)
        1    0.000    0.000    0.001    0.001 tick_solver.py:134(array_get)
        1   36.462   36.462   47.684   47.684 tick_solver.py:181(puzzle_solving)
   639734    1.038    0.000    1.038    0.000 tick_solver.py:29(len)
   568664    1.425    0.000    1.425    0.000 tick_solver.py:37(__init__)
    71141    0.297    0.000    0.297    0.000 tick_solver.py:44(retry)
        1    0.000    0.000    0.000    0.000 tick_solver.py:61(reinit)
       27    0.000    0.000    0.000    0.000 tick_solver.py:7(__init__)
        1    0.000    0.000   47.685   47.685 tick_solver.py:77(run)
   639886    3.827    0.000    3.827    0.000 tick_solver.py:85(value_set)
   639734    2.801    0.000    2.801    0.000 tick_solver.py:99(value_unset)
   639850    0.893    0.000    0.893    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
   639734    0.942    0.000    0.942    0.000 {method 'pop' of 'list' objects}


[7, 6, 9, 1, 2, 8, 3, 4, 5]
[1, 2, 8, 3, 4, 5, 9, 6, 7]
[3, 4, 5, 9, 6, 7, 1, 2, 8]
[6, 5, 7, 2, 1, 3, 4, 8, 9]
[2, 8, 3, 5, 9, 4, 6, 7, 1]
[9, 1, 4, 8, 7, 6, 2, 5, 3]
[5, 7, 2, 4, 3, 1, 8, 9, 6]
[8, 9, 1, 6, 5, 2, 7, 3, 4]
[4, 3, 6, 7, 8, 9, 5, 1, 2]

這是因為我走迷宮時用相當簡單的 guess ，找出最小的 candidate
而很不幸，在一些迷宮中…（尤其是那些只有唯一解的）一但走錯… cost 就會走很遠，再走回來…這是我在演算法上的miss。所以就再加上了一些演算法來做相當複雜的 guess。而演算法的選擇也是很出現機率最高的來選擇… 只為 hard guess 相當的花時間…所以我只有在題目相當困難時 (最少candidate 的cell 依然有超過三個選擇時) (關鍵少數) 才去做。其它的，就交給暴力走迷宮法。

而 hard guess 也很成功的減少了 retry 的次數… ^^;

tick@tock:~/work/sudoku>./testcase.py case_09.txt 
[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 9, 0, 0]
[0, 0, 0, 0, 6, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 9, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 5, 0]
[0, 0, 0, 0, 0, 0, 8, 0, 0]
[0, 9, 0, 0, 0, 0, 0, 3, 0]
[0, 0, 0, 7, 0, 0, 0, 0, 0]
         372 function calls in 0.028 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.028    0.028 :1()
        1    0.000    0.000    0.001    0.001 tick_solver.py:137(array_get)
        1    0.025    0.025    0.027    0.027 tick_solver.py:149(puzzle_solving)
       71    0.000    0.000    0.000    0.000 tick_solver.py:44(__init__)
        1    0.000    0.000    0.000    0.000 tick_solver.py:68(reinit)
       27    0.000    0.000    0.000    0.000 tick_solver.py:7(__init__)
        1    0.000    0.000    0.028    0.028 tick_solver.py:84(run)
      152    0.001    0.000    0.001    0.000 tick_solver.py:92(value_set)
      116    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}


[8, 2, 5, 1, 7, 9, 3, 4, 6]
[4, 1, 6, 3, 2, 5, 9, 7, 8]
[9, 3, 7, 4, 6, 8, 1, 2, 5]
[7, 5, 9, 2, 1, 6, 4, 8, 3]
[3, 4, 8, 5, 9, 7, 6, 1, 2]
[1, 6, 2, 8, 4, 3, 7, 5, 9]
[5, 7, 1, 9, 3, 2, 8, 6, 4]
[2, 9, 4, 6, 8, 1, 5, 3, 7]
[6, 8, 3, 7, 5, 4, 2, 9, 1]

有些地方被 inline 掉了 :P

以下是目前的 source code, 蠻髒的，不過也蠻好玩的

Filename: tick_solver.py


ROWS=9
COLUMNS=9
TOTAL_ELEMENTS=81

class Group:
    def __init__(self, value=0x1ff):
        self.left = value
    def set(self, x):
        if self.left & (1 << (x-1)):
            self.left &= (~(1<< (x-1)))
            return True
        return False
    def unset(self, x):
        if not self.left & (1 << (x-1)):
            self.left |= (1 << (x-1))
            return True
        return False
    def contains(self, x):
        return not not self.left & (1 << (x-1))
    def len(self):
        ans = 0
        v = self.left;
        while v:
            v &= v -1
            ans += 1
        return ans

def len(v):
    ans=0
    while v:
        v &= v - 1
        ans += 1
    return ans

def min_value(V):
    v=1
    while not V & 1:
        V = V >> 1
        v+=1
    return v

class Cmd_Node:
    def __init__(self, x, y, v, Data):
        self.x = x
        self.y = y
        self.v = v
        self.D = Data
        self.D &= ~( 1 << (v-1) )

    def retry(self):
        v=0
        while not self.D & (1 << v):
            v+=1
        self.D &= ~(1 << v);
        v+=1
        self.v = v;
        return v;
    def pretty_print(self):
        print "x="+str(self.x)+"  y="+str(self.y)+"  v="+str(self.v)+"  D="+str(self.D)

from test_module import *

class Board(TestModule):
 def __init__(self):
            self.reinit()

        def reinit(self):
            self.num_rest=TOTAL_ELEMENTS
            self.trace = []
            self.DATA = []
            self.data = []
            self.Rows = []
            self.Columns = []
            self.Groups  = []
            for i in  xrange(0,9):
                self.Rows.append(Group())
                self.Columns.append(Group())
                self.Groups.append(Group())
                self.data.append([0, 0, 0, 0, 0, 0, 0, 0, 0])
                self.DATA.append([ 0, 0, 0, 0, 0, 0, 0, 0, 0])


        def run(self, array):
            self.reinit()
            self.array_get(array)
            self.puzzle_solving()
            return self.data

 
        # index from 0 - 8
 def value_set(self, x, y, v):
            if (v==0):
                return True
            mask = (1<< (v-1))
            if mask & self.Columns[y].left & self.Rows[x].left & self.Groups[(int(x/3)*3 + int(y/3))].left:
                self.data[x][y]  = v
                mask = ~mask
                self.Columns[y].left &= mask
                self.Rows[x].left &= mask
                self.Groups[(int(x/3)*3 + int(y/3))].left &= mask
                self.num_rest = self.num_rest - 1;    
                return True
            print "Set ("+str(x)+", "+str(y)+")="+str(v) +" Failed!!!"
            return False

        def value_unset(self, x, y):
            v = self.data[x][y]
            self.data[x][y] = 0
            mask = (1 << (v-1))
            self.Columns[y].left |= mask
            self.Rows[x].left |= mask
            self.Groups[(int(x/3)*3 + int(y/3))].left |= mask
            self.num_rest = self.num_rest + 1;


        def data_print(self):
            print self.data

        def pretty_print(self):
            for i in xrange(0,9):
                print self.data[i]

        def file_read(self, name):
            f = open(name, "r")
            for x in  xrange(0,9):
                for y in  xrange(0,9):
                    while True:
                        v = f.read(1)
                        if v >= '0' and v <= '9':
                            break;
                    if not self.value_set(x,y,int(v)):
                        print "Bad sudoku!!"
                        return False
            return True

        def array_get(self, array):
            for x in xrange(0,9):
                for y in xrange(0,9):
                    if not self.value_set(x,y,array[x][y]):
                        print "Bad sudoku!!"
                        return False
            return True

        def possible_value_get(self, x, y):
            return self.Groups[(int(x/3)*3 + int(y/3))].left & self.Rows[x].left & self.Columns[y].left


        def puzzle_solving(self):
            while self.num_rest > 0:
                min=10
                for x in  xrange(0,9):
                    for y in  xrange(0,9):
                        if self.data[x][y]:
                            continue
                        pos = self.Groups[(int(x/3)*3 + int(y/3))].left & self.Rows[x].left & self.Columns[y].left
                        self.DATA[x][y] = pos
                        if pos == None:
                            continue
                        lentmp = 0
                        v = pos;
                        while v:
                            v &= v -1
                            lentmp += 1

                        if lentmp == 1:
                            v = 0
                            while not (pos & 1 << v):
                                v += 1
                            v += 1
                            self.value_set(x,y,v)
                            self.trace.append(Cmd_Node(x,y,v, pos))
                        if lentmp < min:
                            min_x = x
                            min_y = y
                            min = lentmp
                if min == 1:
                    continue
                #guess has to be made
                if min > 0:
                    guess = 0
                    if min == 2:
                        while not (self.DATA[min_x][min_y] &  1 << guess):
                            guess += 1
                        guess += 1
                    else: # give a better guess here
                        Row = min_x % 3
                        R_base = min_x/3
                        Column = min_y % 3
                        C_base = min_y/3
                        V = self.DATA[min_x][min_y]
                        # remove hidden 
                        while V:
                            a = V & 1
                            V = V >> 1
                            guess += 1
                            if not a:
                                continue
                            row_single_check = 0
                            column_single_check = 0
                            mask = (1 << (guess-1))
                            for i in [0, 1, 2]:
                                if Row != i and (self.Rows[R_base + i].left & mask):
                                        row_single_check += 1
                                if Column != i and (self.Columns[C_base + i].left & mask):
                                        column_single_check += 1
                            if row_single_check == 2  or column_single_check == 2:  # guess first
                                break
                        #guess = self.hard_guess_find(min_x, min_y, self.DATA[min_x][min_y])
                    self.trace.append(Cmd_Node(min_x, min_y, guess, self.DATA[min_x][min_y]))
                    if self.value_set(min_x, min_y,guess):
                        continue


                continue_flag=True
                while continue_flag:
                    cmd = self.trace.pop()
                    lentmp = len(cmd.D)
                    if lentmp==0:
                        self.value_unset(cmd.x, cmd.y)
                        continue
                    self.value_unset(cmd.x, cmd.y)
                    for x in xrange(0,9):
                        for y in  xrange(0,9):
                            if self.data[x][y]:
                                continue
                            self.DATA[x][y] = self.Groups[(int(x/3)*3 + int(y/3))].left & self.Rows[x].left & self.Columns[y].left
                    while lentmp > 0:
                        if lentmp==1:
                            v = cmd.retry()
                            if self.DATA[cmd.x][cmd.y] & (1<< (v-1)):
                                self.value_set(cmd.x, cmd.y, v)
                                self.trace.append(cmd)
                                continue_flag = False
                                break
                        else:  # when there are more than one candidates, may be we can take long time to find out a better guess
                            v = self.hard_guess_find(cmd.x, cmd.y, cmd.D)
                            if self.DATA[cmd.x][cmd.y] & (1<< (v-1)):
                                cmd.D &= ~ (1<<(v-1))
                                self.value_set(cmd.x, cmd.y, v)
                                self.trace.append(cmd)
                                continue_flag = False
                                break
                        lentmp = len(cmd.D)

        def hard_guess_find(self, x, y, V):
            Row = x % 3
            R_base = x/3
            Column = y % 3
            C_base = y/3
            v = 0
            # remove hidden 
            while V:
                a = V & 1
                V = V >> 1
                v += 1
                if not a:
                    continue
                row_single_check = 0
                column_single_check = 0
                mask = (1 << (v-1))
                for i in xrange(0,3):
                    if Row != i and (self.Rows[R_base + i].left & mask):
                            row_single_check += 1
                    if Column != i and (self.Columns[C_base + i].left & mask):
                            column_single_check += 1
                if row_single_check == 2  or column_single_check == 2:  # guess first
                    return v
            return v


以下是跑 1000 個 test case 的分析圖 (用 octave 畫的)


可以看得出來其實大多數的 test case 都在 0.01 秒做完，而比較久的也在 0.02 秒內做完. 中位數在 0.003 秒
其實還有相當多地方可以改進… 如查表，pattern map等等…
不過…我個人覺得以一個小比賽來說…可以了… ^_^;
張貼者： 於 沒有留言:

2008年6月19日 星期四

Sudoku solver

在公司內辦了一場 Python Sudoku solver 比賽
下星期二才會正式跑 benchmark ^^
今早寫了一下，加上一些 turning
就看著 code 是如何的一步一步的加速…
從開始到現在，竟然已經加速了 1000 多倍了…
可是 code 也越來越噁心…簡直就是 反refactoring
為了讓比賽更好玩… 先把 code post 出來了 ^_^


反正… just for fun :)

Filename: tick_solver.py


ROWS=9
COLUMNS=9
TOTAL_ELEMENTS=81

class Group:
   def __init__(self, value=0x1ff):
       self.left = value
   def set(self, x):
       if self.left & (1 << (x-1)):
           self.left &= (~(1<< (x-1)))
           return True
       return False
   def unset(self, x):
       if not self.left & (1 << (x-1)):
           self.left |= (1 << (x-1))
           return True
       return False
   def contains(self, x):
       return not not self.left & (1 << (x-1))
   def len(self):
       ans = 0
       v = self.left;
       while v:
           v &= v -1
           ans += 1
       return ans

def len(v):
   ans=0
   while v:
       v &= v - 1
       ans += 1
   return ans

class Cmd_Node:
   def __init__(self, x, y, v, Data):
       self.x = x
       self.y = y
       self.v = v
       self.D = Data
       self.D &= ~( 1 << (v-1) )

   def retry(self):
       v=0
       while not self.D & (1 << v):
           v+=1
       self.D &= ~(1 << v);
       v+=1
       self.v = v;
       return v;
   def pretty_print(self):
       print "x="+str(self.x)+"  y="+str(self.y)+"  v="+str(self.v)+"  D="+str(self.D)


class Board():
 def __init__(self):
           self.num_rest=TOTAL_ELEMENTS
           self.trace = []
           self.DATA = []
           self.data = []
           self.Rows = []
           self.Columns = []
           self.Groups  = []
           for i in range(0, ROWS):
               self.Rows.append(Group())
               self.Columns.append(Group())
               self.Groups.append(Group())
               self.data.append([0, 0, 0, 0, 0, 0, 0, 0, 0])
               self.DATA.append([ 0, 0, 0, 0, 0, 0, 0, 0, 0])

       def run(self, array):
           self.array_get(array)
           self.puzzle_solving()


       # index from 0 - 8
 def value_set(self, x, y, v):
           if (v==0):
               return True
           if self.Columns[y].contains(v) and \
                   self.Rows[x].contains(v) and \
                   self.Groups[(int(x/3)*3 + int(y/3))].contains(v):
               self.data[x][y]  = v
               self.Columns[y].set(v)
               self.Rows[x].set(v)
               self.Groups[(int(x/3)*3 + int(y/3))].set(v)
               self.num_rest = self.num_rest - 1;   
               return True
           return False

       def value_unset(self, x, y):
           v = self.data[x][y]
           self.data[x][y] = 0
           self.Columns[y].unset(v)
           self.Rows[x].unset(v)
           self.Groups[(int(x/3)*3 + int(y/3))].unset(v)
           self.num_rest = self.num_rest + 1;


       def group_get(self, x, y):
           if (x < 0 or x > 8 or y < 0 or y > 8):
               return -1
           return int(x/3)*3 + int(y/3)

       def data_print(self):
           print self.data

       def pretty_print(self):
           for i in range(0,ROWS):
               print self.data[i]

       def file_read(self, name):
           f = open(name, "r")
           for x in range(0,9):
               for y in range(0,9):
                   while True:
                       v = f.read(1)
                       if v >= '0' and v <= '9':
                           break;
                   if not self.value_set(x,y,int(v)):
                       print "Bad sudoku!!"
                       return False
           return True

       def array_get(self, array):
           for x in [0, 1, 2, 3, 4, 5, 6, 7, 8]:
               for y in [0, 1, 2, 3, 4, 5, 6, 7, 8]:
                   if not self.value_set(x,y,array[x][y]):
                       print "Bad sudoku!!"
                       return False
           return True

       def possible_value_get(self, x, y):
           return self.Groups[(int(x/3)*3 + int(y/3))].left & self.Rows[x].left & self.Columns[y].left

       def puzzle_solving_iterate(self):
           min_x = 0
           min_y = 0
           min=10
           for x in range(0,9):
               for y in range(0,9):
                   if self.data[x][y]:
                       continue
                   pos = self.Groups[(int(x/3)*3 + int(y/3))].left & self.Rows[x].left & self.Columns[y].left
                   self.DATA[x][y] = pos
                   if pos == None:
                       continue
                   lentmp = len(pos)
                   if lentmp == 1:
                       v = 0
                       while not (pos & 1 << v):
                           v += 1
                       v += 1
                       self.value_set(x,y,v)
                       self.trace.append(Cmd_Node(x,y,v, pos))
                   if lentmp < min:
                       min_x = x
                       min_y = y
                       min = lentmp
           if min == 1:
               return True
           #guess has to be made
           if min > 0:
               guess = 0
               while not (self.DATA[min_x][min_y] &  1 << guess):
                   guess += 1
               guess += 1
               self.trace.append(Cmd_Node(min_x, min_y, guess, self.DATA[min_x][min_y]))
               return self.value_set(min_x, min_y,guess)
           return False

       def puzzle_solving(self):
           while self.num_rest > 0:
               if self.puzzle_solving_iterate():
                   continue
               continue_flag=True
               while continue_flag:
                   cmd = self.trace.pop()
                   lentmp = len(cmd.D)
                   if lentmp==0:
                       self.value_unset(cmd.x, cmd.y)
                       continue
                   self.value_unset(cmd.x, cmd.y)
                   for x in range(0,9):
                       for y in range(0,9):
                           if self.data[x][y]:
                               continue
                           self.DATA[x][y] = self.Groups[(int(x/3)*3 + int(y/3))].left & self.Rows[x].left & self.Columns[y].left
                   while lentmp > 0:
                       v = cmd.retry()
                       if self.DATA[cmd.x][cmd.y] & (1<< (v-1)):
                           self.value_set(cmd.x, cmd.y, v)
                           self.trace.append(cmd)
                           continue_flag = False
                           break
張貼者： 於 沒有留言:

2008年6月14日 星期六

邪惡的小案子

提升大家宅度的邪惡計畫：
http://code.google.com/p/comic-reader/
張貼者： 於 1 則留言:
訂閱： 文章 (Atom)