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

用 30 行 ruby 寫俄羅斯方塊

學一種程式語言，第一步是先跟著 Tutorial 走一遍。
然後，找到參考手冊，因為，這是你的救生圈。像是 Python 的文件就寫得相當清楚。
所以，我無法理解那些在網路上問一些官方文件就有答案的問題的人。如果一個人看不懂文件上那麼清楚的文字，那表示他閱讀能力有問題。那他又怎麼能夠讀懂網友回答的文字？
現在學 ruby，文件風格和 python 有很大不同，但是也非常清楚有用。
當然，光是這樣還不夠，還要真的寫幾個程式才能算數。
至於要寫哪些程式呢？每個人都有自己喜好。就我來說，以前，每學一種 GUI framework 或者語言，我會寫一個 Ansi Terminal Emulator。更早一點，還沒有 GUI 的時候，碰到新的系統，會寫個簡單的畫圖程式和簡單的中文系統 Viewer。
這有點像是一種儀式，如同成年禮一樣，你學程式語言的成年禮。寫完這一個中小型的計畫，就能說自己會一種語言了。
不過我學 Python 的時候，倒是沒有什麼成年禮。因為 Python 實在太好學了，差不多是看到就會了。勉強要說的話，就是之前那個 Alpha-Beta Search 系統。
但這也就是為什麼我 Python 的程式設計能力不太紮實的緣故。後來用 Python 寫了一些短的的俄羅斯方塊，才體會到這點。
所以，現在我學 Ruby 時，也打算把俄羅斯方塊當成是成年禮的一部分。以下就是用 ruby 寫的 29 行俄羅斯方塊。

require "tk"

W,H,Blk=40,40,{0xf=>"red",0x2e=>"#0f0",0x27=>"blue",0x47=>"#ff0",

0x66=>"#0ff",0xC6=>"#38f",0x6C=>"#f0f", 0=>"#000"}

Bkeys=Blk.keys.select{|x| x!=0}

new_piece= proc{ proc{|pc| {:a=>(0..16).select{|i|(pc>>i)&1>0}.map!{|i|

[(i>>2)+1,i&3]},:i=>3,:j=> -2,:c=>pc}}.call Bkeys[rand(Bkeys.length)]}

def collide(na,ni,nj)

na.map {|n| true if @board[nj+n[1]][ni+n[0]]!=0}.include? true

end

def redraw

@canvas.delete "all"

@board.each_with_index{|b,j| b.each_with_index {|c,i|

TkcRectangle.new(@canvas, i*W, j*H, i*W+W,j*H+H,

'fill'=>Blk[@p[:a].include?([i-@p[:i],j-@p[:j]])? @p[:c]: c])}}

end

@score, @bw, @bh, @p = 0, 10, 20, new_piece.call

@board=Array.new(@bh+3){|j| j!=@bh ? [0]*@bw+[15]*3:[15]*(@bw+2)+[0]}

(@canvas=TkCanvas.new :width=>@bw*W,:height=>@bh*H).pack

TkRoot.new.bind("Any-Key") { |e| na,ni,nj=@p[:a],@p[:i],@p[:j]

ni+= e.keysym=="Left" ? -1:(e.keysym=="Right" ? 1:0)

na=na.map{|n| [n[1],3-n[0]]} if e.keysym=="Up"

nj+=1 if e.keysym=="Down"

@p[:a],@p[:i],@p[:j]=na,ni,nj unless collide na,ni,nj

redraw}

TkTimer.new(200,-1){|e| !(collide(@p[:a],@p[:i],@p[:j]+1) or !(@p[:j]+=1)) or

proc{ @p[:a].each{|n| @board[n[1]+@p[:j]][n[0]+@p[:i]]=@p[:c]}

@board=@board.inject([]){|a,l| l.include?(0)? a+[l]:[[0]*@bw+[15]*3]+a}

@p[:j]<0 ? exit : @p=new_piece.call}.call

redraw}.start(0).mainloop

這個比 python 的 tk 版要短，不過可讀性差多了。
原來寫的可讀性比較高，最開始甚至還有定義一組 class，不過行數大約是五十行。
後來不用 class，就變成 40行以內，然後再進一步犧牲一點可讀性，就降到了三十行以內。
ruby 高手可能可以找到不少以上程式碼的可笑錯誤吧！
ruby 和 python 的比較一直是個熱門話題，不過呢，我得先要等我更了解一點 ruby 再說。

Read More