2011-01-06 21:06 墳墓 (Brian Hsu)
還記得連線猜數字是我在暨大六年來，老俞上 Java 程式設計時一定要教到的東西，在我們那屆甚至是回家作業。如果我沒記錯，老俞在這個例子中，想要強調的是電腦的解題方式和人腦有時會有很大的差別。
雖然那時作業我有寫出來，之後研所當程設助教，好像也有教過學弟妺這題，但有一點我須承認：這個程式對我而言並不簡單。想通之後我可以了解整個解題的邏輯（並不難），但我很難去掌握要如何處理一些細節上的問題，特別是當老俞的標準版本裡甚至出現了四層迴圈時，我就開始頭痛了……
而早上嚐試了用 Scala 以及 Functional Programming 的方式寫比對幾 A 幾 B 後，我就開始想，如果用 Function Programming 的方式來解這題，是不是會比較漂亮，比較簡單呢？！
所以，這篇文章就是試著實作這個作業，不過為了一些原因，我並沒有把他做成連線版的，而是單機跑的 Multi-Thread 版本，一個 Thread 當 Server，一個 Thread 當 Client。
以下是這個作業（？）的規格：
- 一個 Server Thread 來模擬猜數字的伺服器
- 一個 Client Thread 來模擬猜數字的客戶端
- 客戶端要嚐試在最少次數內猜中 Server 端上的數字
- 客戶端可以丟一個類似 Guess("3215") 的訊息給 Server 端
- Server 端則回傳 Status("3215", 2, 1) // 3215 的結果為 2A1B 給 Client 端
- 伺服端和客戶端均在猜中正確答案時中止
在這個範例裡，我們會用 Scala 的 Actor 來模擬伺服器的行為，基本上 Actor 就類似伺服器－－監聽訊息並做出反應。
首先，我們定義一些訊息物件，你可以把他想像成是網路上的封包，並且 import 一些之後需要用到的東西。
import scala.actors.Actor import scala.actors.Actor._ import scala.util.Random /** * 猜數字伺服器回傳的結果 * * @param x 使用者輸入的答案 * @param a 猜數字遊戲裡的A（數字對，位置也對） * @param b 猜數字遊戲裡的B（數字對，但位置錯） */ case class Status(x: String, a: Int, b: Int) /** * 要送給猜數字伺器的猜測 * * @param x 使用者猜的數字 */ case class Guess(x: String) /** * 用這個訊息告訴猜數字 AI 開始猜數字 */ case object StartGuess
接著，定義以下兩個猜數字的輔助函式：
- 產生猜數字裡所有的可能解
- 比對兩個數字是幾 A 幾 B
/**
* 猜數字的輔助函式
*/
trait GuessNumberFunctions
{
// 產生猜數字遊戲裡所有可能答案的組合，共 5040 種
//
// 產生方式：
//
// 1. 先產生 0 到 9999 所有數字
// 2. 將這些數字補零至四位數並轉成字串
// 3. 過濾掉所有出現重覆數字的字串
//
def generateAllPossible = {
// 重覆的定義：
//
// 將字串轉成字元集合後，如果大小不為四，就是有重覆的字元
//
// 例： "1234" -> Set(1, 2, 3, 4) -> 不重覆 (return false)
// "1224" -> Set(1, 2, 4) -> 有重覆 (return true)
def hasRepeatNumber (x: String) = x.toSet.size != 4
def convertToPaddingString(x: Int) = "%04d" format (x)
(0 to 9999). // 先產生 0 到 9999 的所有整數
map(convertToPaddingString). // 將這些整數全轉成補零成四位數的字串
filterNot(hasRepeatNumber) // 濾出所有不含重覆數字的部份
}
/**
* 比對兩個猜數字字串後，回覆幾 A 幾 B
*
* 詳細的說明請參考[前一篇文章][1]的講解。
*
* [1]: http://brianhsu.moe/blog/archives/1787
*
* @param number1 第一個數字
* @param number2 第二個數字
*/
def compare(number1: String, number2: String) = {
def pairIsSame(x: (Char, Char)) = x._1 == x._2
val sumA = (number1 zip number2) filter (pairIsSame)
val (remainNumber1, remainNumber2) =
(number1 zip number2).
filterNot (sumA contains _).
unzip
val sumB = remainNumber1 intersect remainNumber2
(sumA.length, sumB.length)
}
}
伺服器的部份很簡單：不斷監聽封包，如果傳進來的是猜測就進行比對並回傳結果，不然就略過該訊息。
/**
* 猜數字伺服器
*
* 這裡使用 Scala 的 Actor 來模擬老俞的作業裡的猜數字伺服器，
* 而會使用這個方法的原因有兩個：
*
* 1. 練習 Scala 的 Actor 的概念和寫法
* 2. 用這種方式實作比較簡單，不用處理 Socket
*
* 這個伺服器啟動後會做下面的事情：
*
* 1. 亂數產生一個猜數字正確解答
* 2. 持續監聽別人丟過來的訊息
* - 當這個訊息是一個猜數字的猜測訊息時（Guess）物件，
* 伺服器就會將其與正確答案比對，並回傳給猜數字客戶端
*
* - 如果是其他訊息就略過並印出
*
* 這個伺服器會在以下情況結束：
*
* - 客戶端猜中了正確數字
*
*/
class GuessNumberServer extends Actor with GuessNumberFunctions
{
// 亂數選擇正確答案
val answer =
Random.shuffle((0 to 9).toList) // 產生一個 List(0, 1, 2..., 9) 然後打亂之後
.take(4) // 取前四個數字，例：List(3,4,1,5)
.mkString // 再結合成字串，例："3415"
// 印出正確答案
println ("[debug] answer:" + answer)
// 持續 (loop) 地監聽事件 (react)
def act () = loop {
react {
// 當進來的是一個猜數字的訊息（可以把他當做是封包之類的）
case Guess(x) =>
// 將傳進來的猜測與正確答比對
val (statusA, statusB) = compare (answer, x)
// 印出比對後是『幾 A 幾 B』
println ("%s => %dA%dB" format(x, statusA, statusB))
// 回傳給對方此次猜測的結果
// x => 這次他猜的數字
// statusA => 數字對，位置也對的數量
// statusB => 數字對，位置錯的數量
sender ! Status(x, statusA, statusB)
// 當 4A 時遊戲結束
if (statusA == 4) Actor.exit()
// 收到其他我不懂的訊息
case otherwise =>
println ("Server 收到不明訊息：" + otherwise)
}
}
}
接下來是重頭戲的部份，猜數字的 AI，其實概念很簡單：
- 先把所有可能的解列出
- 隨便挑一個來猜
- 如果對方告訴你答案是 2A1B
- 那把你的解答列表中，和你的答案相比是 2A1B 的東西全部找出來，正解一定在裡頭！而且此時可能解的範圍已經縮小了
- 從你在上一步中產生的新的可能解範圍裡，再挑一個出來猜
- 重覆以上的動作，直到猜中 4A 為止
/**
* 猜數字 AI
*
* 猜數字的 AI 其實很簡單，但套句老俞的說法：『不要用人腦的思維來想這
* 個問題！電腦和人腦的優點是不一樣的！』
*
* 記得：
* 1. 電腦的處理速度很快
* 2. 電腦的記憶量非常大
*
* 所以從電腦的角度來想，你可以用消去法來解猜數字的問題：
*
* 1. 把所有可能的解列出（一開始會有 5040 個）
* 2. 當你猜一個數字，對方告訴你是 2A0B 的時候
* 3. 把你所有可能解裡，和你猜的數字比對為 2A0B 的部份列出（假設此時已縮減到 1000 個可能解）
* 4. 因為正解和你的解比對是 2A0B，所以正解一定在這 1000 個可能解裡
* 5. 從這 1000 個可能解中，隨便找一個猜
* 6. 4A 的話結束，不然的話依照 2 ~ 5 的方式繼續進行
*
* 這個 AI Client 做的事情也一模一樣，他可以處理以下的訊息：
*
* - StartGame
* 開始向 Server 丟一個數字
*
* - Status(myGuess, 4, 0)
* 4A，所有數字和位置都對，遊戲結束
*
* - Status(myGuess, a, b)
* 過濾出可能解裡，和 myGuess 比對後為 aAbB 的解答之後繼續猜
*
* @param server 要連線到哪個 Server 猜數字
*/
class GuessNumberClient(server: GuessNumberServer) extends Actor with GuessNumberFunctions
{
// 目前的可能解，一開始是全部的數字
var possibleAnswer = generateAllPossible
// 檢測 number1 和 number2 的結果是不是 nAnB
def isSameStatus (number1: String, number2: String, nA: Int, nB: Int) = {
compare(number1, number2) == (nA, nB)
}
// 持續 (loop) 地監聽 (react) 事件
def act () = loop {
react {
// 如果開始玩猜數字遊戲
case StartGuess =>
// 從第一個數字猜
println ("開始猜數字")
server ! Guess(possibleAnswer.head)
// 如果伺服器告訴我們猜中了，就印出答案並結束
case Status(myGuess, 4, 0) =>
println ("答案是：" + answer)
Actor.exit()
// 如果沒中的話，利用消去法，濾出剩下的所有組合理，
// 同樣也是 nAnB 的部份
case Status(myGuess, a, b) =>
// 濾出剩下的可能答案
possibleAnswer = possibleAnswer.filter(isSameStatus(_, myGuess, a, b))
println ("現在的可能答案數：" + possibleAnswer.length)
// 拿剩下的答案中的第一個繼續猜
server ! Guess(possibleAnswer.head)
// 如果收到不明訊息
case otherwise =>
println ("Client 收到不明訊息：" + otherwise)
}
}
}
最後是主程式的部份，很單純的就是建立 Client / Server 物件，然後開始猜數字。
object Main
{
def main (args: Array[String]) {
val server = new GuessNumberServer
val client = new GuessNumberClient(server)
server.start() // 啟動 Server
client.start() // 啟動 AI Client
client ! StartGuess // 開始玩猜數字！
}
}
最後附上執行結果，從執行結果可以看出來，用這種方式猜測，大概 5 ~ 6 次之內就可以猜出正確的解答。
brianhsu@NBGentoo ~/GuessNumber $ scala Main [debug] answer:0951 開始猜數字 0123 => 1A1B 現在的可能答案數：720 0245 => 1A1B 現在的可能答案數：110 0356 => 2A0B 現在的可能答案數：7 0374 => 1A0B 現在的可能答案數：2 0851 => 3A0B 現在的可能答案數：1 0951 => 4A0B 答案是：0951
brianhsu@NBGentoo ~/GuessNumber $ scala Main [debug] answer:4183 開始猜數字 0123 => 2A0B 現在的可能答案數：180 0145 => 1A1B 現在的可能答案數：48 0426 => 0A1B 現在的可能答案數：5 4173 => 3A0B 現在的可能答案數：2 4183 => 4A0B 答案是：4183
以上，是不是覺得 Scala 和 Functional Programming 很神奇有趣呢？快點一起來玩 Scala 吧～:p
註一：如果你算一下，你會發現註解比程式碼還長，可見 Scala 在短短的幾行裡幫你做了多少事。XDD
註二：老俞的版本在這邊，和這個版本最大的差別在如何處理幾 A 幾 B，以及他是網路程式。
註三：不知道你有沒有發現，這隻程式裡除了監聽事件的 loop 外沒有迴圈。^_^
回響