神は細部に宿り給う

　OCamlの練習に、長年の疑問だった

• 切符算で解がある全ての組み合わせ

　を求めようとしている。

　ただ、自分の知っているバージョンはローカルルール（？）があり、四則演算と括弧だけではなく、

• 最初から存在する数字をくっつけて2〜4桁の数字にする

　という操作が可能である。意味があるのは2ケタだけだが。

　まだインチキしているのでコード公開できないけど、とりあえず答えは出たはず。これ合ってる？

0001 0011 0012 0013 0014 0015 0016 0017 0018 0019
0022 0023 0025 0028 0033 0034 0037 0044 0045 0046
0055 0056 0066 0067 0077 0078 0088 0089 0099 0111
0112 0115 0118 0119 0122 0123 0124 0125 0126 0127
0128 0129 0133 0134 0135 0136 0137 0138 0139 0144
0145 0146 0147 0149 0155 0156 0158 0159 0166 0167
0169 0177 0178 0179 0188 0189 0199 0223 0224 0225
0226 0227 0228 0229 0234 0235 0236 0237 0238 0239
0244 0245 0246 0247 0248 0249 0255 0256 0257 0258
0259 0266 0267 0268 0278 0279 0288 0289 0334 0336
0337 0339 0345 0346 0347 0349 0355 0356 0357 0358
0367 0368 0369 0377 0378 0379 0446 0448 0449 0455
0456 0457 0458 0459 0466 0467 0468 0469 0477 0488
0555 0556 0557 0558 0559 0568 0569 0578 0579 0589
0669 0679 0688 0779 0789 0889 0899 0999 1111 1112
1114 1115 1116 1117 1118 1119 1122 1123 1124 1125
1126 1127 1128 1129 1133 1134 1135 1136 1137 1138
1139 1144 1145 1146 1147 1148 1149 1155 1156 1157
1158 1159 1166 1167 1168 1177 1178 1188 1189 1199
1222 1223 1224 1225 1226 1227 1228 1229 1233 1234
1235 1236 1237 1238 1239 1244 1245 1246 1247 1248
1249 1255 1256 1257 1258 1259 1266 1267 1268 1269
1277 1278 1279 1288 1289 1299 1333 1334 1335 1336
1337 1338 1339 1344 1345 1346 1347 1348 1349 1355
1356 1357 1358 1359 1366 1367 1368 1369 1377 1378
1379 1388 1389 1444 1445 1446 1447 1448 1449 1455
1456 1457 1458 1459 1466 1467 1468 1469 1477 1478
1479 1488 1489 1555 1556 1557 1558 1559 1566 1567
1568 1569 1577 1578 1579 1588 1589 1599 1666 1668
1669 1678 1679 1688 1689 1777 1778 1779 1788 1789
1799 1888 1889 1899 1999 2222 2223 2224 2225 2226
2227 2228 2229 2233 2234 2235 2236 2237 2238 2239
2244 2245 2246 2247 2248 2249 2255 2256 2257 2258
2259 2266 2267 2268 2269 2277 2278 2279 2288 2289
2299 2333 2334 2335 2336 2337 2338 2339 2344 2345
2346 2347 2348 2349 2355 2356 2357 2358 2359 2366
2367 2368 2369 2377 2378 2379 2388 2389 2399 2444
2445 2446 2447 2448 2449 2455 2456 2457 2458 2459
2466 2467 2468 2469 2477 2478 2479 2488 2489 2499
2555 2556 2557 2558 2559 2566 2567 2568 2569 2577
2578 2579 2588 2589 2599 2666 2667 2668 2669 2677
2678 2679 2688 2689 2699 2777 2778 2779 2788 2789
2799 2888 2889 2899 2999 3333 3334 3335 3336 3337
3338 3339 3344 3345 3346 3347 3348 3349 3355 3356
3357 3358 3359 3366 3367 3368 3369 3377 3378 3379
3388 3389 3399 3444 3445 3446 3447 3448 3449 3455
3456 3457 3458 3459 3466 3467 3468 3469 3477 3478
3479 3488 3489 3499 3555 3556 3557 3558 3559 3566
3567 3568 3569 3577 3578 3579 3588 3589 3599 3666
3667 3668 3669 3677 3678 3679 3688 3689 3699 3777
3778 3779 3788 3789 3799 3888 3889 3899 4444 4445
4446 4447 4448 4449 4455 4456 4457 4458 4459 4466
4467 4468 4469 4477 4478 4479 4488 4489 4499 4555
4556 4557 4559 4566 4567 4568 4569 4577 4578 4579
4588 4589 4599 4666 4667 4668 4669 4677 4678 4679
4688 4689 4699 4777 4778 4779 4788 4789 4799 4888
4889 5555 5556 5557 5558 5559 5566 5567 5568 5569
5577 5578 5579 5588 5589 5599 5666 5667 5669 5677
5678 5679 5688 5689 5699 5777 5778 5779 5789 5888
5889 5999 6666 6667 6668 6669 6677 6678 6679 6688
6689 6699 6777 6779 6788 6789 6799 6889 7777 7778
7779 7788 7789 7799 7888 7889 7899 8888 8889 8899
8999 9999

参考リンク

• M.Hiroi’s Home Page / お気楽 OCaml プログラミング入門

おまけ

by 木戸孝紀 tags:OCaml パズル プログラミング 数学

• レヴィ=ストロース鎮魂のため数学野郎にお願い（追記アリ – 地下生活者の手遊び
• 数学野郎どもアリガトウ – 地下生活者の手遊び

　一昨日のパズル。もう終わっちゃってるけど、乱数でのゴリ押しだけでは芸がなさ過ぎるでしょう常識的に考えて……ということで、ちょっと改良した。

• dunber2.rb

　互いに行き着けないノードの数をスコア（当然低い方が良い）として、ステップごとに上位1/4だけ残してそれを4倍に複製。二本のエッジをちょん切ってつなぎ替える。

　N=4で15個の解はわりとすんなり見つけられるようになった。

15個のノード。
30本のエッジ。
0のスコア。
0:[9, 12, 5, 8]
1:[3, 9, 11, 6]
2:[5, 11, 13, 12]
3:[1, 5, 10, 13]
4:[7, 5, 14, 6]
5:[2, 4, 3, 0]
6:[14, 12, 1, 4]
7:[4, 11, 9, 10]
8:[10, 14, 11, 0]
9:[13, 0, 7, 1]
10:[8, 12, 7, 3]
11:[2, 7, 1, 8]
12:[6, 10, 0, 2]
13:[9, 14, 2, 3]
14:[6, 13, 8, 4]

　まだやってないけど、パラメータ設定とかける時間次第ではN=5もいけるかもしれん。

11/9追記

　ちょっと時間かかったけどN=5で24個いけた。populationは800に設定。

24個のノード。
60本のエッジ。
0のスコア。
0:[6, 11, 7, 16, 13]
1:[15, 3, 13, 4, 18]
2:[6, 5, 14, 3, 23]
3:[1, 7, 20, 2, 11]
4:[19, 13, 17, 1, 5]
5:[2, 16, 4, 12, 10]
6:[2, 0, 23, 15, 19]
7:[17, 21, 0, 3, 10]
8:[12, 10, 23, 13, 20]
9:[14, 20, 17, 15, 16]
10:[8, 22, 15, 7, 5]
11:[12, 0, 22, 3, 17]
12:[8, 11, 21, 15, 5]
13:[14, 4, 1, 8, 0]
14:[13, 9, 21, 2, 22]
15:[1, 6, 9, 12, 10]
16:[20, 0, 5, 18, 9]
17:[23, 7, 4, 9, 11]
18:[23, 21, 1, 22, 16]
19:[20, 22, 4, 6, 21]
20:[19, 16, 9, 3, 8]
21:[7, 18, 14, 12, 19]
22:[19, 10, 11, 14, 18]
23:[18, 17, 8, 6, 2]

おまけ

　もうすぐCDが出るらしい。

by 木戸孝紀 tags:Ruby パズル プログラミング 数学

• レヴィ=ストロース鎮魂のため数学野郎にお願い – 地下生活者の手遊び

　ううむ、地下猫さんが『科学がきらわれる理由』をおすすめされた背景では、そんなこと考えていたのか。これはちょっと予想外だった。

　確かに『科学がきらわれる理由』は素晴らしい本だが、ダンバー数自体は「まあそりゃ限度のある要素の集まりには何かしらの限界はあるだろうねえ」ぐらいの受け取り方をしておけばいいものだろう。

　少なくとも現時点で、具体的にその数に何かがある・その数から何かが言えると考えるのは、百匹目の猿現象みたいな純然たるオカルトとは異なるものの、六次の隔たりレベルの通俗科学でしかないと思うなあ。

　まあそれはそれとして、

平面上にいくつかの点がある。点と点が線で結ばれている。１本任意の１点から出ている線の数はＮ。任意の２点を取り出すと、その２点は直接、あるいは、別の１点を経由してつながっている。このような状況が可能な点の個数の最大値は？

　という問題そのものには久々にパズル欲が刺激された……と言いたいところだけど、こりゃパズルってレベルじゃねーぞ！

　直感で根拠はないが、M、Nが一般の場合の解を求めるのは、数学上の未解決問題ではないかと思う。具体的な数にしたってN = 150なんてとてもとても。

　かと言って、一応数学野郎・プログラム野郎の端くれのつもりなのに手も足も出ずに終わるのは悔しいので、小さい数ぐらいでなら遊べるように、ゴリ押しで解を探すスクリプトを書いた。

• dunber.rb

　見つからないと延々と探し続けるので、諦めるときはCtrl+Cで止めて下さい。（実行できる人なら止め方も知ってると思うけど。）

　N = 3の時の最大個数は10のようだ。理論上 N^2+1 を上回ることはありえないのでN = 3については解決。

10個のノード。
15本のエッジ。
[0, 1, 2, 7]
[1, 0, 9, 6]
[2, 0, 5, 3]
[3, 2, 8, 6]
[4, 6, 5, 7]
[5, 2, 4, 9]
[6, 1, 3, 4]
[7, 0, 4, 8]
[8, 3, 7, 9]
[9, 1, 5, 8]

　N = 4の時は13まで、

13個のノード。
26本のエッジ。
[0, 6, 11, 9, 4]
[1, 6, 11, 12, 10]
[2, 8, 11, 6, 4]
[3, 5, 4, 7, 12]
[4, 0, 2, 3, 12]
[5, 3, 8, 6, 7]
[6, 0, 1, 2, 5]
[7, 3, 5, 11, 9]
[8, 2, 5, 10, 9]
[9, 0, 7, 8, 10]
[10, 1, 8, 9, 12]
[11, 0, 1, 2, 7]
[12, 1, 3, 4, 10]

　N = 5の時は16まで、

16個のノード。
40本のエッジ。
[0, 5, 10, 8, 9, 1]
[1, 3, 15, 11, 0, 14]
[2, 10, 12, 11, 4, 3]
[3, 10, 6, 1, 4, 2]
[4, 8, 3, 15, 9, 2]
[5, 15, 0, 7, 10, 14]
[6, 10, 3, 13, 7, 8]
[7, 15, 13, 5, 6, 12]
[8, 4, 0, 6, 14, 11]
[9, 15, 12, 4, 13, 0]
[10, 3, 6, 2, 0, 5]
[11, 2, 13, 14, 1, 8]
[12, 9, 2, 13, 14, 7]
[13, 6, 7, 9, 12, 11]
[14, 5, 12, 11, 8, 1]
[15, 9, 5, 1, 7, 4]

　N = 6の時は20個まで発見。（まだあるかも。）（追記：N=4で14はあるみたい。（2009-11-04 – imo758の日記）

20個のノード。
59本のエッジ。
[0, 18, 1, 5, 8, 17, 13]
[1, 7, 0, 10, 4, 16, 14]
[2, 19, 16, 10, 5, 13, 6]
[3, 7, 9, 11, 19, 16, 13]
[4, 12, 18, 16, 19, 1, 11]
[5, 7, 8, 9, 18, 2, 0]
[6, 15, 10, 17, 2, 12, 9]
[7, 9, 3, 5, 1, 15, 17]
[8, 5, 12, 0, 11]
[9, 18, 7, 3, 5, 12, 6]
[10, 12, 15, 2, 6, 13, 1]
[11, 3, 19, 15, 4, 16, 8]
[12, 10, 4, 8, 6, 9, 14]
[13, 19, 10, 2, 18, 0, 3]
[14, 15, 18, 1, 12, 19, 17]
[15, 14, 17, 6, 7, 10, 11]
[16, 17, 2, 4, 1, 11, 3]
[17, 15, 16, 7, 6, 14, 0]
[18, 9, 0, 4, 5, 14, 13]
[19, 2, 4, 13, 11, 3, 14]

　もちろん完全ランダムなので、見つからなくてもない証明にはならないが、見つかった解は正しい（はず）。

追記

• グラフ理論的言い換え – 186::Diary

　やっとまともにグラフ理論っぽい説明が来てくれた。面白い。

　N=4は15まであるのかよ。やはりN=4で早くもゴリ押しは通用しなくなるみたいだな。まあ今回はN=3の10を見つけるスクリプトがさっと書けたのと、一般には未解決だろうと一目で当たりがつけられたということで個人的には満足しておこう。

おまけ

　プログラミングつながり。これは楽しい。

by 木戸孝紀 tags:Ruby パズル プログラミング 数学

• パズル・ロワイアル

　全員で生還する確率を上げたければ、皆が何かしらの意味で協調した行動を取らなければならない。それなのに、挑戦中にも挑戦後に一切情報をやりとりできない。この一見取り付く島もなさそうなルールの裏をかくにはどうしたらいいか。

　情報をやりとりすることはできなくても、新しく全員が得ることができる情報がひとつだけある。というか、ひとつしかない。名前の書かれた紙である。突破口があるとしたらこれしかない。

　考えやすくするためにまず用語の準備をしよう。

　生徒には出席番号がついているものとして以後数字で考える。ついていなければどんな基準でもジャンケンでもくじ引きでもいいので適当に決める。以後生徒1〜42と呼ぶ。生徒nの名前の書かれた紙を紙nと呼ぶ。

　ロッカーにも番号を振る。たとえばロッカーに番号や記号がついていたら辞書順あるいは小さい順に、仮に番号がついてなかったとしても、左上が1でその右が2など事前に決めておいた何らかの規則性に基づいて、やはり1〜42と番号を振る。以後ロッカー1〜42と呼ぶ。

　さらに便宜的に同じ状態の42部屋で全員が同時に挑戦しているとして考え、生徒1が案内される部屋を教室1と呼ぶことにする。同様にして仮想の別々の教室をそれぞれ教室1〜42と呼ぶことにする。

　このゲームでは、生き残るために必要なのは自分の名前の紙だけである。仮に他人の名前の紙が入っていると分かっているロッカーがあるとしたら、そこを開けるのは避けるべきである。これが基本方針である。

　それを知る手段がないから困ってるんだろーが！　と思ってしまいそうだが、もう少し待て。

　まず最初に開けるロッカーは全員別々にすると決めよう。あえて違う選択をする理由はないのでわかりやすさのため、生徒nはロッカーnを開けることにする。

　仮に自分が生徒13だとして、ロッカー13を開ける。もし幸運にも紙13が出てきたら、それでクリアだ。あとは他人の幸運を祈るのみである。しかし、そんなことは1/42の確率でしか起きないので、大抵は外れる。

　出てきたのが紙4だったとする。生徒13は「ああ外れた」と嘆き悲しむ。しかし、死にたくないので嘆いてばかりいないで2個目のロッカーを選ばなければならない。2個目はもう当てずっぽうで選ぶしかないだろうか？　そんなことはない。

　実はこのとき、生徒13は、絶対に手に入らないと思われた他の部屋の情報を、知ることができている。

• 教室4で生徒4が、紙4以外の紙を引き「ああ外れた」と嘆き悲しんでいるということ

　がわかるのだ。なぜなら、紙4はロッカー13に入っているのだから。ロッカー4を開けることになっている生徒4が紙4を引いたということは、ありえない。

　ということは、生徒13が次に選ぶべきは？　ロッカー4である。なぜか？　この時点で生徒13が何らかの情報を持っているのは教室4に関してのみである。たとえば教室7でロッカー7を開けた生徒7が紙7を引いている可能性は、僅かながらある。

　もちろん、生徒13が自分の生き残りだけ考えた場合、ロッカー4もロッカー7も「紙13が入っているかもしれない」ことにおいては何も変わることはない。

　しかし、全員で生き残りたいと考えている場合には、すでに他の生徒の正解と決定している（かもしれない）ロッカーを避けることには意味がある。

　よって生徒13は2個目にロッカー4を開ける。出てきたのが仮に紙9だったとする。このとき、生徒13には新たに2つのことがわかる。

• 少し前、教室4で生徒4が1個目に開けたロッカー4から出たのは紙9だったこと
• 現在、教室4で生徒4がロッカー9を開けて紙x(4,9以外の何か）を見ていること
• 現在、教室9で生徒9はロッカーxを開けて紙yを見ているがyは9ではないこと

　最初の2つは当然として、紙yが紙9ではないというのはなぜわかるのか？

　紙yが紙9だとすると、紙9はロッカー4に入っているのだから、生徒9は2回目にロッカー4を開けたことになり、ひいては1回目に紙4の入ったロッカー13を開けたことになる。作戦上1回目にロッカー13を開けるのは生徒13である自分なのだから、生徒9が作戦に逆らったことになる。作戦に逆らう生徒はいないことになっているので矛盾である。よってyは9ではない。

　こうして2個目のロッカーを開けた時点で、生徒13は部屋を一歩も出ずして、生徒4と生徒9がいまだクリアしていないことがわかる。

　生徒13が3個目に開けるべきロッカーは？　先と同様の論理で9だ。なぜなら紙13が入っているかもしれない点では他と変わらず、かつ、すでに他の生徒の正解として確定してしまっている可能性がないロッカーだからだ。

　ここで、なんと！　ロッカー9から紙13が出てきたとしよう。生徒13はもちろんクリアの喜びで雀躍する。だが、同時に生徒4と生徒9もクリアの喜びで雀躍していることがわかる。

　というのは、少し前、生徒4が開けたロッカー9に入っていた紙xが紙13だったというのなら、今現在、生徒4はロッカー13を開けて紙4を発見したところだからだ。生徒9に関しても同様。

　では、肝心のその作戦で全員生き残れる確率はいくらかぐらいになるのか？　とりあえず10万回試行させてみたところ、なんと約32%もある。こんな怖ろしいゲームに巻き込まれて笑い話で済む可能性が1/3近くもあるなんて、約4兆4千億分の1とか言ってたのに比べると夢のような話ではないか。

　ただし、いくら同様に続けても紙13が発見できず、今だクリアしていないと分かっている生徒が増えていくだけの可能性もある。21個目のロッカーを開けても紙13が発見できなかった場合。生徒13は死ぬ。

　そして同時に、これまで紙の上に名前を見てきた4,9をはじめとする他の21人も同時に死ぬということがわかってしまう。なぜなら、すでに自分とその21人のクリアはかならず同時になることがわかっているからだ。自分が助かっていない以上みんな死ぬ。

　要するに、例の場合4,9,13の3つのロッカーが13→4→9→13というループを形成していたことになる。すべての番号は必ず1以上42以下の長さのループに所属することになる。ルール上そうならないことは不可能である。

　22以上の長さのループが存在しさえしなければ、全員が、確実にクリアできる。逆に22以上の長さのループが存在してしまうと、そのループにつかまった生徒は一人残らず死ぬ。

　ループの長さがいくつになるパターンがいくつあるかをちゃんと計算すれば厳密な確率も求まるはず……だが、その方法は自分も思い出せない*1ので発展課題にしておく。

試行に使ったRubyスクリプト

#!/usr/local/bin/ruby
#-*- coding: Windows-31J -*-

TIMES = 10000
NUM = 42
max = NUM / 2

all = 0
win = 0

live_sum = 0
dead_sum = 0

TIMES.times do
  all += 1

  arr = (0...NUM).to_a
  arr = arr.sort_by{|i| rand}

  live = 0
  dead = 0

  (0...NUM).to_a.each do |i|
    cnt = 0
    box = i
    loop do
      cnt += 1
      if cnt > max
        dead += 1
        break
      end
      if arr[box] == i
        live += 1
        break
      else
        box = arr[box]
      end
    end
  end

  live_sum += live
  dead_sum += dead

  win += 1 if live == NUM
  puts "#{win}/#{all}回目の試行：#{live}人生存・#{dead}人死亡"
end

puts "個人が助かる確率：#{live_sum.to_f / (live_sum + dead_sum).to_f}"
puts "全員助かる確率：#{win.to_f / all.to_f}"

追記 8/5

　HandDrumさんのコメントを元に、厳密解の求め方をコードにしたもの。これでよさそう。

#!/usr/local/bin/ruby
#-*- coding: Windows-31J -*-

class Integer
  def factorial
    (1..self).inject(1){|r, i| r * i}
  end
  def permutation(n)
    self.factorial / (self - n).factorial
  end
end

NUM = 42
puts 1 - (0...(NUM/2)).inject(0) {|r, n| r + NUM.permutation(NUM - n) / (NUM - n) * n.factorial}.to_f / NUM.factorial

おまけ

　死にゲーつながり。選曲と天丼が秀逸。（釣り・微ビックリ注意）

by 木戸孝紀 tags:クイズ ネタ パズル 解答 数学

　極東の全体主義国家大東亜共和国では、学力向上のため、全国の中学3年生のクラスから無差別に数十クラスを抽出して、命を賭けたパズルをさせるという怖ろしいプログラムが実行されています。

　あなたの3年B組（生徒数42名）は運悪くこのプログラムに選ばれてしまいました。そして、今年のパズルのルールは以下のようなものです。

　今からクラスの生徒は一人づつ別々に、42個のロッカーがある教室に案内されます。それぞれのロッカーの中には紙が一枚入っていて、それぞれの紙には3年B組の誰か一人の名前が記されています。

　教室に案内された各生徒は、21個のロッカーを開けて調べるチャンスを与えられます。自分の名前が記された紙を発見できれば、勝利。生きて帰れます。21個開けても自分の名前が記された紙を発見できなければ、失敗。監視している軍隊に射殺されてしまいます。

　生還した生徒も隔離されるので、まだ挑戦していない生徒に情報を伝えることはできません。また、ある生徒が教室で何をしても、次の生徒が挑戦する前に内部は完全に整頓され、最初の生徒が来たときと全く同じ状態に戻されてしまい、教室の中に情報を残すこともできません。*1

　ただし、プログラムがスタートする前に、全員でゆっくり時間をかけて相談をすることが可能です。

　あなたは主人公属性の思考法の持ち主なので、どうしても全員生きて帰りたいです。全員が助かる作戦を考えて下さい。その作戦を使った場合、全員が助かる確率はいくらぐらいになるでしょうか。*2

おまけ

　射殺つながり。TECH Winって懐かしい。（バイオレンス注意）

by 木戸孝紀 tags:クイズ ネタ パズル 数学

　最近Ruby1.9.1が出たので、乗り換えついでに久しぶりにプログラミングっぽい話題でもと思い、ピクロスのソルバを書いてみました。

ファイル

• picross.rb
• sample.txt

使い方

ruby picross.rb sample.txt

　と問題ファイルを与えると、

　　｜　　 2 1 1 2　　｜
　　｜　　 1 1 1 1 3 2｜
　　｜ 4 6 2 1 1 2 2 1｜
----＋----------------＋
　 4｜　　　　　　　　｜
 2 2｜　　　　　　　　｜
 2 2｜　　　　　　　　｜
　 8｜　　　　　　　　｜
　 2｜　　　　　　　　｜
 2 2｜　　　　　　　　｜
 2 2｜　　　　　　　　｜
　 4｜　　　　　　　　｜
----＋----------------＋
　　｜　　 2 1 1 2　　｜
　　｜　　 1 1 1 1 3 2｜
　　｜ 4 6 2 1 1 2 2 1｜
----＋----------------＋
　 4｜××■■■■××｜
 2 2｜×■■××■■×｜
 2 2｜■■××××■■｜
　 8｜■■■■■■■■｜
　 2｜■■××××××｜
 2 2｜■■××××■■｜
 2 2｜×■■××■■×｜
　 4｜××■■■■××｜
----＋----------------＋

　のような結果を表示します。解なしなら解なしと判定します。解が一つ以上あれば最初に見つかった解を表示します。複数解になっているかどうかまでは気にしません。

　問題ファイルの形式は、

• 最初の一行が盤面の高さと幅
• 次の行からは、一行ごとに
  • 横のヒントを左から順に並べたものを、上から下に
  • 縦のヒントを上から順に並べたものを、左から右に
• 区切り文字に使えるのは半角のスペースかカンマ

　です。詳しくはサンプル問題のファイルを見て下さい。

ruby picross.rb sample.txt -v

　とオプションをつけると途中経過も表示します。この場合よほど単純な問題でなければ長くなりすぎるので、

ruby picross.rb sample.txt -v > result.txt

　などとして、後で結果を書き出したファイルを見るようにした方がいいでしょう。大きな問題でも時間とRubyの許す限り解けるはずですが、ヒントの数字が3桁に達するような場合は、表示されるのは下2桁の値だけになります。

　ちなみに単純な計算を山ほど行うので、1.9.1では1.8系より目に見えて早くなりました。うちの環境では30×30の広さでも数秒、さらにスカスカの難しそうな問題でもせいぜい30秒程度です。

　あまり巨大なのは問題が見つからなかったので試していませんが、人間が解くことを想定しているような問題なら大体リーズナブルな時間で解けるのではないかと思います。

　また、一番面倒くさかったのは解かせてみる問題を打ち込むことでした。入力した問題があったらメールフォームからでも送っていただけるとありがたいです。もちろん著作権のあるものは公開できませんが。

追記　2/20

　横に細長い問題の扱いでバグがあったので修正しました。

追記　2/24

　途中経過の表示時に「★」マークを出力するようにしました。結果ファイルで「★」を次々に検索するようにすれば簡易アニメーションのように見ることができるようになるはず。

おまけ

　誰が得すんだこのTAS。

by 木戸孝紀 tags:Ruby パズル ピクロス プログラミング

1. まず誰か1人でいいので、自分と志を同じくするか、自分の言いなりになる人間を連れてくる。*1
2. その2人を含む3人で、多数決で全てを決する1つ目の秘密結社を作る。
3. その3人を含む5人で、多数決で全てを決する2つ目の秘密結社を作る。
4. その5人を含む9人で、多数決で全てを決する3つ目の秘密結社を作る。
5. n番目の秘密結社は2^n+1人を支配できる。

　世界の総人口はいまちょっとググったところでは約67億人。

2^10 = 1024 ≒ 10^3
2^33 ≒ 8*10^9 > 67*10^8

　だから、33段階の秘密結社を通じて全人類を支配することができる。めでたしめでたし……という話が何の役に立つだろうか？

　世界で最も大きな組織には何段階の階級が存在するでしょうか？

　というフェルミ推定の問題が出されたときに役に立つかも知れない。実際には全人類は1つの組織に統一されていないし、各階層が単純多数決というもっとも効率が悪い*2と思われる意志決定方法であってこの数なので、現実の組織に必要な階層数はこの推計よりかなり少ないと思ってよいだろう。

　たとえばアメリカ合衆国大統領からイラクのどこかで哨戒中の二等兵に何か命令を伝える必要が生じたとする*3。途中で何回命令を受け渡す必要があるだろうか？　直接つまり1ということはなさそうだというのは常識でわかるが、上限について何か推定できることがあるだろうか。ここで33より多くなることは絶対にありえないと断言してよさそうである。

• DSI 米軍階級

　答え合わせにちょっとググってみる。概ね妥当と言ってよさそうである。

おまけ

by 木戸孝紀 tags:パズル フェルミ推定 社会 数学

• ルービックキューブは25手で完成可能、米研究者が新解法の証明に成功 – Technobahn

　上のニュースを見てルービックキューブで検索していたら、昔持っていたこれが復刻されているのを発見した。

　もっとも、様々な点でルービックキューブに比べると遥かに劣る。一番の問題は繋ぎの部分がテグスのせいで耐久性がなくて、ちょっと力の入れ方を間違えたり古くなったりするとすぐ壊れるところで、昔もかなり短い時間で壊れたような記憶がある。

　今考えるとそこまで面白いとも思えないのだが、かなり懐かしい。買ってみようかな。

おまけ

　これと同じ作者とか。多芸だなあ。

by 木戸孝紀 tags:おもちゃ パズル 買い物