編程套路

在software craftsmanship運動裏，有一堆用來練功的「Kata」¹，是日本字「形」的意思，中文對應應該是「套路」。練習套路，就是重複同一個動作，將其內化，熟能生巧。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 在此也提供很方便的驗證網。