Euler 計畫和其他

前一陣註冊了 Project Euler，然後玩了一下裡面的題目。
Project Euler 蒐集了一系列的挑戰問題，這些問題的答案都是一個數字或者一組數字。每當你破解一個問題後，你就能與其他同樣破解這個問題的人，討論答案與心得。通常解決這問題需要一點程式設計技巧和數學知識。

網站裡面也會對於不同國家或者程式語言的解題者做統計和排名。比方說這是台灣的統計，而這是 Python 語言的統計。和「點點點」相比，台灣的表現很爛。
一般所謂的 online judge 系統其實很多，ACM 風格的 online judge 是主流。 UVa online judge 是其中的代表。其他還有如ZeroJudge。
和 Project Euler 不同， Project Euler 上傳的是答案，而這類 online judge 要你上傳的是「程式」。所以有限定使用的程式語言。標準的語言是 C,C++,Java。雖然我也寫 C++和C，但我還是比較喜歡能自由選擇工具。這點到不是根本性的問題，像是 Sphere Online Judge 就能讓你使用許多不同的程式語言，包含 perl, ruby, python。
另外一個不同點是時間限制，雖然 Project Euler 也有所謂的「一分鐘法則」，就是程式應該要能在一分鐘跑完，但這不是硬性規定，真正的裁判是你自己。事實上，如果你喜歡（而且可以的話），你甚至可以 用google 找答案。真正的裁判是你自己。我喜歡這種風格。
一般的 online judge，有些題目有時間限制。就比賽而言，這提供競賽公平性的基準。但這個時間限制沒有「理論上的定義」，端看裁判主機端執行的時間而定。這缺乏了一點美感。
另外就是題目取向，Project Euler 的題目有時會需要一點數學知識，而一般程式競賽有時則是要一點演算法上的知識。而 Project Euler 容許的執行時間往往比較長一點。
總之，雖然都是程式挑戰題，但是風格和取向各有不同。
另外一種類型是 Code Golf，著重在用最短短的程式碼達成指定的功能，就像是打高爾夫一樣，你想要用最少的桿數完成比賽。雖然也是程式解題競賽，但又另有一番風格。
當然，寫程式的目的在於寫出「真正有用」的東西，而不是解答這些問題來炫耀自己有多強。但是，不管是哪一種風格的程式解題競賽，在你解題的過程，都能增進自己的程式設計能力。比方 Code Golf 裡面，有些解答是不可思議的短，在你追求這個目標的同時，才發現原來有些語言特性是自己之前忽略的，某種問題原來還有這種寫法。
(對 Project Euler 有興趣的朋友，可能也會對 IBM 的 Ponder This 有興趣。)

Read More

夢

「昨天還夢到妳呢！」我說。才發現，仍然在夢裡。

Read More

突破性思考的小謎題

這個題目是從 PTT 上看到的：

作者  newtonapple (newton and apple)

阿基米德的浴缸－突破性思考的藝術與邏輯
作者：大衛‧伯金斯/著
譯者：林志懋
---------------- 正題開始--------------------------

兩個參賽者輪流挑選桌上寫桌上寫著有數字1到9的便條 紙，每次一人只能拿一張，看誰能搶在對手之前湊出來 任三個總合為15的數字，第一個參賽者先挑二，第二個 參賽者的最佳挑法為何??

還挺有趣的題目。在相信有「突破性思考」能解決的漂亮解答的前提下。花了我十分鐘左右才想到，而且還動手稍微算了一下。不過這類題目，花多久時間解答或是否被考倒，都無所謂，只是有趣而已，就像冷笑話一樣。

提示：(用滑鼠拉反白可看到)

井字棋、魔方陣。要動手確認一下三個數字能組成 15 的只有 (5,x,10-x) 和 (6,8,1) (6,2,7) (4,2,9) (4,8,3)

438
951
276

Read More

Python 算圓週率 這次算到無窮位

python 的 generator 很好用，理論上來說，可以表示無窮小數。而無窮小數的四則運算，可以用前面有限位來計算到一定的位數，所以，如果用 generator 生成的十進位展開，配合 operator +-*/ 等等，我們在 python 上可以弄出一個無窮精確的 real number class。
這樣，其實有點用有限的電腦來存放無窮位的資料的感覺。
這樣，我們可以很優雅的算出圓週率近似值到無窮位。
當然，速度一定很慢。反正太匆忙本來就不太優雅。
之前有看過利用類似概念來算圓周率的 python 程式，實在不錯。不過那個程式太長了，而且年代久遠，沒有用 operator 和 generator。
另一個好像叫做 accurate-math 的東西，也是可以做無窮位計算，不過呢，他的方法比較類似先固定算前一千位，然後等到需要一千零一位時，從頭開始算前兩千位。
像這種沒有實用價值的東西，用這麼醜的方法是不行的。
於是，我嘗試了一下寫一般性的 real number class ，才發現很麻煩（主要是 0.999...這類的問題）。而且， python 有 recursion 的 limit ，雖然可以改大一點，但再怎麼大也不是無窮位，除非用 stackless python。當然，可以避開不用 recursion，但程式結構就沒有那麼漂亮了。
所以就放棄，改成以算圓週率為目標。這樣，只需要簡單的除法、減法以及交錯級數就行。
結果需要三十幾行，跟之前只算固定位的三行比起來，差太遠了，不夠漂亮。
所以算是失敗，不過還是可以看看就是了。雖然超級慢，但是只要記憶體夠，可以一直跑到無窮位的圓週率。(這個程式碼的風格很糟，原本希望能夠用短短幾句話，很清楚的描述四則運算和交錯級數的計算，可惜失敗)

from itertools import *
import sys
# a/b 的無窮位小數展開
def ldiv(a,b,p=0):
 f=lambda x:x.append((x[0]%b)*10) or x.pop(0)/b
 return iter(f.__get__([a*10**p]), -1)
# 比較上界ub 下界lb，然後將相同的位數傳回(p 是用來補前面的 0)
def digits(lb,ub,p):
 u,l="%d"%ub, "%d"%lb
 n,m=len(l),len(u)
 common=takewhile(lambda i:l[i]==u[i], range(n))
 return [] if m-n else chain(repeat(0, p-n), (int(l[i]) for i in common))
# 交錯級數計算（只算一個位數，要代入後面的模版）
def altseries(ub,lb, num, prec, a):
 if num:
   s, d=sum(a(i).next() for i in range(num-1)), a(num-1).next()
   ub, lb= ub+s+max(d,0), lb+s+min(d,0)
 for i in count(num):
  d=a(i, prec).next()
  if not d:
  return ub, lb, i
  ub,lb = (lb+d, lb) if d>0 else (ub, ub+d)
# 減法（只算一個位數，要代入後面的模版）
def subop(ub, lb, num, prec, a,b):
 ub=lb+a.next()
 return ub, ub-b.next(),1
# 減法以及交錯級數計算的模版
# 真正的上下界是 ub+num 和 lb-num
def opgen(ub,lb, num, precs, op, *a):
 for prec in count():
  ub,lb,num=op(ub*10,lb*10,num, prec, *a)
  for x in digits(lb-num/2-1, ub+num/2+1, prec-precs):
  yield x
  precs+=1
  ub,lb=[x%(10**(prec-precs)) for x in (ub,lb)]
# Pi 的交錯級數（其實是 pi(n) 是數列的第 n 項）
s=lambda k,p:opgen(0,0,0,-1,subop, ldiv(16, k*5**k, p), ldiv(4, k*239**k, p))
def pi(n, p=0,  d={}):
 return d.setdefault(n,imap(lambda x:-x, s(2*n+1,p)) if n%2 else s(2*n+1,p))
# 開始利用 generator 展開小數
for n in opgen(0,0,0,-1,altseries, pi):
 sys.stdout.write("%d"%n)
 sys.stdout.flush()

(原始碼)稍微修改，也能夠計算其他的交錯級數。

Read More

python shell-like pipe

像是 python generator tricks 一樣，其實不少人希望能在 python 裡面做 shell-like pipe。很明顯的，用 | operator 可以辦到這件事情，像是 ASPN Recipe: Shell-like data processing 就是一個例子。但缺點是要用一個 terminator 放在最後。此外，每個指令也都必須要加括號。所以，即使是簡單的 ls，也要變成 ls()|printlines 。而且，你要自己幫每個指令自己加上 __ror__。

PipeCmd

所以，我用三個方式來解決這些問題。最後的 __ror__，現在可以用 decorator 來處理了。terminator，我改用 __repr__ 來取代，這樣，在 python interactive shell 下，可以直接看到想要的回應。也因為如此，所有的資料都會被轉成 PipeOuput class (其實只是 iterator 加上 | 和 repr)。至於第一個問題，我用類似 partial function 的 class PiprCmd 來處理，有一個特別的 argument 稱為 stdin，用來代表 pipe input。

這樣，我們就可以

from pipeutils import *
ls|wc
ls|tail(n=5)|sort
cat/"*.py"|grep("def")
grep("pipe")/"*.py"/"/usr/include/*.h"
grep("^a","aaa\nbbb\nccc\nabc".splitlines(), open("text","rb"))

裡面的 / 是吃檔案名稱的，cat("text") 等於是 cat/"text"，但是 cat/"text*" 等於 cat("text1", "text_something", ...)
更好的是，也可以和一般吃 iterator 的函數互相作用，也可以用一般 iterator 作用 (pmap 是把普通的的函數變成吃 iterator 的函數)

ls|(lambda g: (l.upper() for l in g))
"abcdefg"|pmap(mul,range(7))
import math
range(0,90,15)|pmap(lambda x:x*math.pi/180)|pmap(math.sin)

我的方法不算是最好的，應該只要用一個 class 就行。不過，這樣的解法很直覺。
其實用 ruby 會比 python 更像 shell，因為 ruby 函數呼叫可以不用括號。
另外把所有物件變成 file stream like 可能會更像 shell pipe的行為。
其實還挺多人想要把 python, ruby, perl 的強大功能跟 bash 這類　shell 混和。有一個 perl 的 project 就是把 unix 工具用 pure perl 實現。 python 也有很多，比方　shython 等等，python 本身也有 shutil, diff, 而 ipython 也有 shell-like 功能。
**Update: 20080426
改成只用一個 class pipecmd， 邏輯上比較簡潔一點。同時也做了一些處理，讓 cat(range(10))|sum 也可以跑。
**Update: 20080427
基本上一樣原理的 minipipe.py 只有 60行

Read More

Python 的 Generator Tricks

我們都知道 python 的 iterator很有趣，比方下面這個generator 能生成所有質數(根本就只是把質數的定義講一遍而已):

(n for n in itertools.count() if n>1 and not any(n%k==0 for k in range(2,n)))

比較複雜一點的費波納契數列 callable iterator

iter((lambda x:x.append(sum(x)) or x.pop(0)).__get__([1,1]),None)

我們也知道新的 send/yield 能夠玩出不少把戲，不過這篇簡報簡直把 generator 玩得爐火純青 Generator Tricks for System Programming 。

generator 根本就能夠當成 pipeline 來玩。

比方你有一組 log，最後一個欄位不是數字就是 ' -'(當成 0)，你想算這些欄位的總和，原來你可能會寫成

wwwlog = open("access-log")
total = 0
for line in wwwlog:
    bytestr = line.rsplit(None,1)[1]
    if bytestr != '-':
        total += int(bytestr)
print "Total",total

但用 generaotr 來思考

wwwlog = open("access-log")
bytecolumn = (line.rsplit(None,1)[1] for line in wwwlog)
bytes = (int(x) for x in bytecolumn if x != '-')
print "Total", sum(bytes)

優雅多了，而且從 pipeline 來看，反而更容易理解。

配合另外一個也很神的 generator_tools ，就能玩出更多把戲。

Read More

鹿男與美麗的奈良

這部片是Mr. Monkey推薦, 因為劇中主角玉木宏與綾瀨遙分別因此片獲得當季日劇的最佳男主角及最佳女配角獎。玉木宏飾演的小川孝信一位常在重要關頭失敗的倒楣人士, 例如小學時的武術比賽偏偏在比賽前受傷、考大學因為湊熱鬧掉到水池而沒法準時到考、出社會到公司報到那天公司宣佈倒閉, 最後只好回到原來的大學研究室, 但卻因與實驗室同儕相處不融洽被老師建議去奈良女子學院擔任臨時代課老師、臨走之前才發覺自己女朋友要跟實驗室的死對頭結婚了, 原因是覺得玉木宏太神經敏感了。儘管如此, 在抵達奈良的路途中還是發生大大小小的災難, 最後終於到達學校幫忙準備的宿舍, 與劇中其他兩位學校歷史老師藤原道子(綾瀨遙)、美術老師福原重久(佐佐木藏之介)開始新生活。

奈良是個具歷史意義的古城, 我也曾於1991年第一次的日本旅遊曾造訪過奈良東大寺, 對於寺中的漫走鹿群還有印象, 此劇即以鹿作為主題, 引伸出拯救日本免於富士山噴發災難神話故事。劇中的奈良女子學院有兩所姊妹校分別位於大阪、京都, 三所女子學院皆設在當地古城旁邊, 因此分別以該古城的守護動物鹿(奈良)、老鼠(大阪)、狐狸(京都)作為校徽,鹿、老鼠、狐狸為神話中大明神的手下, 傳說中大明神腳下踩著一隻大鯰魚, 大鯰魚每隔六十年就會蠢蠢欲動, 造成火山噴發及地震, 因此鹿、老鼠、狐狸輪流傳遞一個名為”三角”或”目”的神器來封印鯰魚的活動, 劇中設計的背景即為接近六十年轉換週期的日本, 時常發生地震, 富士山也被偵測到有再度噴發的危險, 為狐狸要將封印轉移給鹿的一年, 小川為鹿所選出來的人類, 有著要從狐狸手上拿回”三角”封印的傳遞手使命。

劇中會講話的鹿、被鹿做記號會從鏡中看到自己鹿臉 "憔悴並神經衰弱”的小川老師, 為此劇特別的地方。此外, 為接待新老師小川的歷史老師藤原, 於出遊時不斷介紹各古蹟名勝的歷史, 除了突顯藤原對歷史事務的熱愛外, 亦使此劇別富歷史教育意義。

Read More