玩撲克牌算24點是我小時最著迷的遊戲，小時候玩是絞盡腦汁儘快想出解答，各種招數都立刻試著找出可以實現的可能。現在偶爾也玩玩，現在玩的時候，總是想著各種算法的邏輯，試圖摸索出計算的規律，並想通過編程來讓電腦計算出解答，不僅求出解答，而且還想求出所有的解答。
比如說，下面這個遊戲：
解法之一為：(6 - 2 - 1) x 8 = 3 x 8 = 24。
還有其它的解法嗎？仔細思詢，似乎還找到一個答案：
6 * 8 * 1 / 2 = 48 / 2 = 24
還有別的答案嗎？如何求證能已找到的解答之外再沒有其它的解答？將各種排列組合的可能性都試圖一遍，這可以說是一個非常燒腦的數學計算問題了。
於是，我開始想著通過自己總結出的計算邏輯，利用電腦計算的強大功能，一個月前開始動手寫這麼一個的編程，沒有想到編寫這樣一個算法系統也是一個非常燒腦的過程。不過，我最終還是寫成了這麼一個計算系統，下面是我的大概思路和設計結構。
24點算法的目標
我想設計這樣一個計算系統，要達到如下的目標：
- 將答案用表達式即人能夠理解的字符串列出；
- 在所有可能的表達式中求出能計算出24的答案；
- 將所有的答案盡列為一組唯一的表達式答案；
- 作為bonus，即順便容易得到的結果，列出答案從最初到最後的計算步驟。
如果能夠設計出這樣一個24點算法的程序，這就可以做為算24的電腦engine即主機系統了。
四個數字的排列組合
從四張牌的情況，這樣計算的步驟看起來，最多只需要三個步驟，似乎十分簡單。
這只是一組四個數字的計算，加上加減乘除四種運算符，這個計算過程是測試各種不同排列組合表達式的計算問題，列出所有排列組合的表達式數量對於人腦來說還是相當大的。但是對於電腦來說，這個數量是一個完全可以迅速計算和求出解答的過程。
編寫這樣的電腦程序，我想首先要解決的問題是，列出所有四張牌的組合。這是一個數學問題：4!=4x3x2x1=24 種四個數字的排列組合。
以上面的四張牌為例：
1-2-6-8, 1-2-8-6, 1-6-2-8, ...一共可以列出二十四組。
開始寫四個數字的組合排列的程序就比較燒腦，不過在一位高手朋友指點迷津之下，很快寫了一個列出四個數字排列組合的小程序，非常簡潔。我接著發現，實際上這個算法不僅可以排列出任何n個數字的組合，而且經過改進之後，還可以在n個數字中還可以列出i (i<=n) 個數字的排列組合。不僅如此，我還優化這種排列組合，即可以列出唯一或不重複的排列組合，比如四張牌中有可能兩張以上是相同的，這對我下面的計算過程就可以減少計算的數量，從而提高計算的效率。
計算方法
有了一組四張牌數字的排列組合，如何進行計算的呢？按照上面的思維方式，先取兩張牌，得出一個結果，然後再⋯⋯。等等，這第一步，從四張牌數字中取兩個數的方式也有不同，如果用括號來表示，下面是 1,2,6,8 四個數的所有五種可能取法，或者是表達式的可能：
- ((1,2), 6), 8 解釋：1和2計算（加減乘除之一）得出一中間結果，這一結果再與6計算得出另外一個中間結果，最後與8計算得出最後結果。
- (1, (2,8)), 8 解釋：2和8計算得出一結果，1與這個結果計算得出另一結果，最後與8計算得出最後結果。
- 1, (2, (6, 8)) 解釋：6和8計算得出一結果，2 與這個結果計算得出另一結果，1與這個結果計算得出最後結果。
- 1, ((2, 6,), 8) 解釋：2和6計算得出一結果，這個結果與8計算得出另一結果，1與這個結果計算得出最後結果。
- (1, 2), (6, 8) 解釋：1和2計算得出結果一，6和8計算得出結果二，結果一與結果二計算得出最後結果。
在考慮列出表達式的時候，每一組四位排列組合就要考慮用到上面所有的五種計算步驟。當然，其中步驟之中可能就會出現重複的表達式，這是因為 +, x 運算符的左右兩個數字（數字可能是牌中一張，也可能是中間計算的結果）是可以交換的，但是 -, / 運算符的被運算數是不能完全與運算符左邊的數字交換的（除非是減去零或者除以相同的非零數）。
經過一番燒腦，我得出上面這樣一個比較清晰和完全的計算步驟，這樣可以將各種排列組合表現為眾多的算式表達式。
優化表達式
所有的表達式中，許多表達式實際上是同一種算法，只是不同的順序。以四個數字全加的表達式為例：
1 + 2 + 6 + 8, 1 + 6 + 2 + 8, 1 + 8 + 2 + 6, 1 + 8 + 6 + 2, 2 + 1 + 6 + 8, ...
如果將這些不同順序的表達式進行優化，這些表達式都只能考慮為一種全加的算法。
於是我想到將表達式優化。將表達式優化有各種方式，在我的算法中，優化表達式的規則是：括號在先（即放在表達式的最左面），乘除在先，乘在除先，加在減先，最後是大數在先。比如上面四張牌各種答案的表達式之唯一優化表達式只有下面三種解答：
8 * 6 * 1 / 2
(8 + 1) * 2 + 6
(6 - 2 - 1) * 8
如果表達式兩邊都是括號的情況，大數的括號在先：
(10 - 2) * (2 + 1)
(10 - 6) * (10 - 4)
有了這樣的優化表達式規則，眾多的答案表達式就很容易地清除重複的表達式，解答可以歸納為唯一的各種答案了。
表達式模塊
在我的算法中，為了建立表達式，優化表達式和解析表達式（將表達式分解為計算步驟），我設計了一個表達式模塊，這在編程語言中稱為class 或 struct，或者在寫程序中稱為目標性編程技巧。我設計的這個模塊有自己的內部數據結構，以及幾個對外的交接口，或者稱為API。
我的表達式為 ExpressElement<T: Comparable>，簡稱為EE。這是一個通用性模塊，其中T為一種可比較的數據類型，比如整數或小數。24點的基本算法為整數，24點也可以擴展為小數或分數的計算，這個模塊可以處理整數或小數的計算。
EE內部主要有兩個內部數據，一個是計算符，一個計算元組array。如果組是一個元內容，這個內容即為T數據元；根據加減乘除運算符，array組最多為兩個內容元，即計算符的左元和右元，每一個元可以是T數據元，或者是EE，即表達式元。通過這樣的設計，表達式可以用EE的如下API來建立和展示。
API的主要接口為：
- add(T) ：用一個數元初始化EE，比如數 1；
- add(op, T) ：往EE中以一運算符加一個數元，比如用加法運算符 + 和數字 8 加入 EE（如上面的 1 數字初始的 EE，結果是 1 + 8 的 EE）；
- add(op, EE)： 往 EE 中以一運算符加一個EE元，比如用乘法運算符 x 和表達式 6 - 2 加入 EE（比如上面的 EE，結果是 (1 + 8) x (6 - 2)的 EE）；
- expressString() 將EE轉換為表達式string, 即字符串，比如 (1 + 8) x (6 - 2)
- optimizedString() 將EE裝換為優化的表達式字符串，比如 (8 + 1) x (6 -2)
- steps() 將EE分解為從最初到最後結果的計算步驟，比如：8 + 1, 6 - 2, (8 + 1) x (6 - 2) 三步。
- 其它
小結
在具體編程中，還有許多各種各樣的問題需要處理，比如括號問題（比如往EE中加一計算符或一元時，僅加必要的括號來標識計算的優先順序），被除數為零（中間計算結果為零作為被除數）的情況，被除數為 1 情況（我處理優化這種情況為乘 1），小數出現無限循環或不循環的情況，小數或分數運算中出現精確度損失的情況等。
實際上，推出上面的設計結構也是在處理不同情況下逐步逐漸推演出來的，我曾經遇到過許多次撞到無法進行下去的死角，最後不得不推翻重來。這真是一個非常燒腦的過程，但這也是一個鍛鍊大腦思維能力的一次非常好的嘗試。
最終，我完成了上面的設計結構和模塊，24點的求解計算就有了一個完善的主機或計算系統了。我發現，這個系統可以非常容易地，幾乎無需改變，擴展為小數或分數的求解，整數除法的求解（比如 1 / 2 為 0，3 / 2 為 1）。
當然，我設計的系統目前只能適合於 4 個數字的 24 點計算，運算符只限於加減乘除。這個系統可以擴展為小數和整數除法的情況。這並不是一個完美的系統，只是一個可用的系統。將來也許我會再推倒重來，進一步提高和擴展24點的算法，比如 5 或 6 個數字的計算。
順便提及的是，我寫的這套算法系統是用蘋果的 Swift 編程語言，在蘋果電腦上，有一個功能十分強大的 Xcode 編寫程序軟件，Swift 是蘋果電腦設計軟件的最新編程語言。Swift 還有一個 Playground 平台，而且現在網上有 Swift Playground 的平台。通過編寫這個系統，我對Swift語言，尤其是有關Class和Struct的區別，如何正確和巧妙運用block等，都有了更好和更深的理解。
應該提及的是，Swift 核中有一個 Expression class，這個模塊解決了如何計算數學表達式的結果，為我求解表達式的結果提供了機大的便利。
可以說，經過這次燒腦的磨練，我的編程技巧又有一個大高度的跳躍上升。人的大腦思考技能就是在這種不斷磨練中更為健康、睿智的。
通過寫這個博客文章，用通俗語言來描述我這一段經歷，讓我有一個機會從總體審視、回顧和總結我編寫的這套系統。
也許一個新的或不同特色的app產品，正在孕育之中⋯⋯
參考
- 維基百科：24點
- 博客文章：四則運算顯功力：算24
- 網上遊戲：4數
- 我的組合排列程序：IBM Swift Sandbox在線程序
- 蘋果開發者文庫：NSExpression
No comments:
Post a Comment