文章

編程套路

software craftsmanship運動裏,有一堆用來練功的「Kata」1,是日本字「形」的意思,中文對應應該是「套路」。練習套路,就是重複同一個動作,將其內化,熟能生巧。Code Kata 就是一堆短練習題,不太花時間,但可練某些解決問題之法。最近遇上一個 Potter Kata,卻花了一點時間。

題目:某小說系列共五本,買1本8元,2本95折,3本9折,4本8折,5本75折,寫一個程式去計算買任何組合的最平價。interface 如:

var amount = Potter.buy([0,0,1,2,3,4,4]);

Array 裏的數字是 zero-based 的圖書編號,上述例子,程式應排列取 [0,1,2,3,4][0,4] 組合,即 (5*0.75+2*0.95)*8 = 44.4

這題的最直觀解法,是取最多本組合來計折扣。不過細看題目其實有一個梗,例如以下組合:

[0, 0, 1, 1, 2, 2, 3, 4]
I)  [0, 1, 2, 3, 4][0, 1 2] --> 51.6
II) [0, 1, 2, 3][0, 1, 2, 5] --> 51.2

用括號標記組合的話,第一個是 (5,3),是以最多本組合優先,但比起第二個 (4,4) 來得貴。原因是3本與4本的折相差 10%,但4本與5本只差5%,所以在這特定情形下,買 (4,4)(5,3) 抵。但是否組成最多4本組合為皆呢?不是:

[0, 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 4]
I)  [0, 1, 2, 3, 4][0, 1, 2, 3][0, 2][2] --> 78.8
II) [0, 1, 2, 4][0, 1, 2, 3][0, 2, 3][2] --> 80.8

這裏,組 (5,4,2,1)(4,4,3,1) 更省錢,所以不是盡量多排4本就好。

本來要一個通用解法的話,就必需暴力窮盡所有可買組合,比較計算最低者,但可能會很慢,所以我就用此特寫情景,只將 (5,3) 換成 (4,4),似乎也足夠應用。我寫的解法在此

在這裏,你會發覺用 TDD 是不能給你「摸」出算法的,到一些 test case 就會停步。通常當你悶不出 implementation 時,應當反思 test case 是否走太遠,但似乎在這題也無用。雖然如此,但 TDD 在此也提供很方便的驗證網。


  1. 外國 dev 似乎都對一些異國文化很感冒,常常會見到他們用這些字眼命名:Zen, Tao, Fu, Ninja, Guru, Monk, Jujitsu, Dojo… via twitter 

回應

*