「笑わない数学者 - 森博嗣 」に出てくる数学パズルをプログラム(Clojure)で解く [吾輩の小説 for iPhone]
自炊系小説ビューワ「我輩の小説」で今日も電車で本を読んでいたら、話の中に数学パズルが出てきました。それもそのはず、読んでいたのは森博嗣 による「笑わない数学者」です。
五つのビリヤードの玉を、真珠のネックレスのように、リングにつなげてみるとしよう。玉には、それぞれナンバが書かれている。さて、この五つの玉のうち、幾つ取っても良いが、隣どうしが連続したものしか取れないとしよう。一つでも、二つでも、五つ全部でも良い。しかし、離れているものは取れない。この条件で取った玉のナンバを足し合わせて、1から21までのすべての数ができるようにしたい。さあ、どのナンバの玉を、どのように並べて、ネックレスを作れば良いかな？
うーん、まず1を作るには「1」の玉が必要。次に2を作るには、0+2、1+1の組み合わせがあって、1の玉を2つは入れられないから、「2」の玉も必要だ。と、ここまで考えたところで気付きました。プログラマにはコンピュータという計算の得意な友達がいる！
ということで計算機にパズルを解いてもらいました。言語は、最近はまっているClojureという関数型言語です。
; 名前空間の設定と使うライブラリのインポート
(ns ball-chain
(:use [clojure.contrib.combinatorics :only (combinations permutations)])
(:use clojure.contrib.test-is))
; 玉を定義
(defn balls [] (range 3 15))
; ネックレスの start 番目から length 個だけ取り出して数を合計する関数
(defn take-sum [chain start length]
(reduce + (for [i (range start (+ start length))]
(nth chain
(mod i (count chain)) 1))))
; ネックレスから玉を取り出して
; 合計が number になるようにできるか? を返す関数
(defn yields?
([chain number]
(not (empty? (take 1 (filter #(yields? chain number %) (range 0 5))))))
([chain number start]
(not (empty? (take 1 (filter #(= number (take-sum chain start %)) (range 1 5)))))))
; ネックレスが条件に合うか? を返す関数
(defn correct? [chain]
(every? identity (map #(yields? chain %) (range 1 20))))
; 玉を組み合わせてネックレスを作る関数
(defn all-chains [] (map permutations (map #(concat % (list 1 2)) (combinations (balls) 3))))
; ネックレスの組み合わせの中から、条件に合うものを抽出する関数
(defn answers []
(for [perms (all-chains) :when (not-empty (filter correct? perms))]
(filter correct? perms)))
; yields? のテスト
(deftest test-yields
(is (yields? (list 1 2 3 4 11) 1))
(is (yields? (list 1 2 3 4 11) 2))
(is (yields? (list 1 2 3 4 11) 3))
(is (yields? (list 1 2 3 4 11) 4))
(is (yields? (list 1 2 3 4 11) 11))
)
; テストを実行
(run-tests)
; 答えを1つ出力
(println (take 1 (answers)))
「1と2の玉が必ずある」という条件を組み込んで、多少の高速化をはかっています。ネックレス状なので右回りも左回りも同等の組み合わせになる、といった条件は考慮できていません。
これを Mac OS X で動かすには、たとえば ball-chain.clj というファイルに保存した上で、以下のように実行します。
$ sudo port install clojure clojure-contrib
$ java -classpath .:/opt/local/share/java/clojure/lib/clojure.jar:/opt/local/share/java/clojure/lib/clojure-contrib.jar clojure.main ball-chain.clj --
※ 本来は
$ clj ball-chain.clj
だけで実行できるはずなんですが、MacPorts のバグのため、それには少し設定が必要です。詳しくはリンク先を参照してください。
答え? 答えはネタバレなのでここには書きません。どうしても見たい方は↓へどうぞ
。。。
スクリプトの出力結果はこちら:
$ clj ball-chain.clj
Testing ball-chain
Ran 1 tests containing 5 assertions.
0 failures, 0 errors.
(((3 10 2 5 1) (3 1 5 2 10) (5 1 3 10 2) (5 2 10 3 1) (10 3 1 5 2) (10 2 5 1 3) (1 3 10 2 5) (1 5 2 10 3) (2 5 1 3 10) (2 10 3 1 5)))
1 つ目の答え (3 10 2 5 1) が本当に合っているか、見てみましょう。
| 1 | 3 10 2 5 **1** |
| 2 | 3 10 **2** 5 1 |
| 3 | **3** 10 2 5 1 |
| 4 | **3** 10 2 5 **1** |
| 5 | 3 10 2 **5** 1 |
| 6 | 3 10 2 **5 1** |
| 7 | 3 10 **2 5** 1 |
| 8 | 3 10 **2 5 1** |
| 9 | **3** 10 2 **5 1** |
| 10 | 3 **10** 2 5 1 |
| 11 | **3** 10 **2 5 1** |
| 12 | 3 **10 2** 5 1 |
| 13 | **3 10** 2 5 1 |
| 14 | **3 10** 2 5 **1** |
| 15 | **3 10 2** 5 1 |
| 16 | **3 10 2** 5 **1** |
| 17 | 3 **10 2 5** 1 |
| 18 | 3 **10 2 5 1** |
| 19 | **3 10** 2 **5 1** |
| 20 | **3 10 2 5** 1 |
| 21 | **3 10 2 5 1** |
その他の答えも、右回り・左回りを逆にしたり、さらに開始点をずらしたりすることで 1 つ目の答えと同じネックレスになっていることがわかります。