一昨日のパズル。もう終わっちゃってるけど、乱数でのゴリ押しだけでは芸がなさ過ぎるでしょう常識的に考えて……ということで、ちょっと改良した。
互いに行き着けないノードの数をスコア（当然低い方が良い）として、ステップごとに上位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なんてとてもとても。
かと言って、一応数学野郎・プログラム野郎の端くれのつもりなのに手も足も出ずに終わるのは悔しいので、小さい数ぐらいでなら遊べるように、ゴリ押しで解を探すスクリプトを書いた。
見つからないと延々と探し続けるので、諦めるときは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]
もちろん完全ランダムなので、見つからなくてもない証明にはならないが、見つかった解は正しい（はず）。
追記
やっとまともにグラフ理論っぽい説明が来てくれた。面白い。
N=4は15まであるのかよ。やはりN=4で早くもゴリ押しは通用しなくなるみたいだな。まあ今回はN=3の10を見つけるスクリプトがさっと書けたのと、一般には未解決だろうと一目で当たりがつけられたということで個人的には満足しておこう。
おまけ
プログラミングつながり。これは楽しい。
by 木戸孝紀
tags:Ruby パズル プログラミング 数学
ふと思い立って作ったら、かかった時間の割に意外と効用があったので公開。
#!/usr/local/bin/ruby
#-*- coding: Windows-31J -*-
SOURCE = 'training.txt'
puts "トレーニングを開始します。\n\n"
File.open(SOURCE){|file|
file.each do |line|
line.chomp!
next if line.size == 0
print line
gets
puts "...Done\n\n"
end
}
puts "おつかれさまでした！！"
スクワット足を閉じて 10
スクワット足を普通に開いて 10
スクワット足を大きく開いて 10
アレイ交互前上げ 10
アレイ上持ちあげ 10
アレイ背筋上げ 10
アレイ内上げ 10
アレイ前持ちあげ 10
アレイ横持ちあげ 10
アレイ後ろ持ちあげ 10
手を押しあう前で 10秒
手を引き合う前で 10秒
首を前から押す 10秒
首を後から押す 10秒
首を左から押す 10秒
首を右から押す 10秒
腹筋 10
背筋 10
腕立て 10
もも上げ 10
尻蹴り 10
足を横開き左 10
足を横開き右 10
こんなメニューを作っておけば一行ずつ表示してくれる。それだけのプログラム。
ちょっとしたことなのだけど、単に表を見ながらやるより能率上がるのよね。
おまけ
トレーニング→スポーツ
by 木戸孝紀
tags:Ruby プログラミング 健康 日記
最近Ruby1.9.1が出たので、乗り換えついでに久しぶりにプログラミングっぽい話題でもと思い、ピクロスのソルバを書いてみました。
ファイル
使い方
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 パズル ピクロス プログラミング
別に初めてではないのだが買ってしまった。著者のYuguiさんにも興味があった（これとかこれとかかなり共感するところがある）からなのだが。
美しい、としか表現しようがない。足すべきものも引くべきものも一つもないという完璧さに恍惚となる。こんな感覚を言語の解説書から受けるというのは夢想だにしなかった。
弾さんの書評はいつ頃からか売らんかなの傾向を強く感じるようになって今はまったく信用してないのだけど、今回のベタ褒めはそのまま信じてよい。
おまけ
ルビーつながり……だけでなく極限を突き詰める美しさつながりも。ゲーム的にもニコ動技術的にも完璧。
by 木戸孝紀
tags:Ruby Yugui プログラミング 書評
ブログを書く時にわずかとはいえHTML（もしくはXHTML）の記述するのは面倒である。せっかくブログなんだから、わずかのHTMLも書かずに済ませたいではないか。
我ながら面倒くさがりもいいところだと思うが、プログラマの三大美徳は怠惰・短気・傲慢だそうだから、そう悪いことではないかも知れない。
省略記法はすでに上記のようにいろいろと存在するが、どれも一長一短があって満足できない。
はてな記法は一番使いやすいが、すでにHTMLで書かれている部分を混ぜて書けないのが困る。本の紹介に使っているamazletやおまけに使っているニコニコ動画など、他のツールやサービスで作成された部品を追加しづらい。
MarkdownはHTMLも混ぜて書くことができるが、英文のメールで使われる表現がベースになっているらしく、どうも日本語で書こうとすると不便がある。
Pukiwikiの記法も良くできていると思うが、もちろんwiki前提に考えられているので微妙に違和感が残る。
というわけで不満たらたらでその場その場の対応をしていたのだが、先週末ついに自分が好きな記法を作ってしまえばいいじゃないかと気がついたので、
で取り上げられているwikiパーサを参考にrubyで自分専用の記法を作った。まだ完全ではないが一応実用に耐える。これもそれで書いて変換したもの。
自分が好きなようにルールを決めただけあって素晴らしく快適！ 更新意欲が増しそう。
おまけ
なぜかflash全盛期のノリを感じる……。もはや精神的ブラクラの域に達しているので閲覧注意。
by 木戸孝紀
tags:Ruby ブログ プログラミング ライフハック 記法
清涼飲料水のキャップのオマケとして、10 種類の清涼飲料水マンのキャップがついてくるキャンペーンがありました。そこで、豪気な凛さんは 24 本の箱買いを実行しました。24 本も買えば、10 種類そろっていそうな感じですが、実際には（以下省略）そこで、そろわない場合の確率はどのくらいになるのか？ 果たして凛さんは、全部の種類の清涼飲料水マンのキャップを持っているのだろうか？
（サンプル: "多倍長計算のサンプル(ペプシ算)"）
ペプシ算ファイナル – 永字八法で知って、久々にパズル欲を触発されたのでやってみた。我ながらなかなかエレガント。大元ページの再帰的な計算法では手も足も出ない数になっても瞬殺。rubyのBignumが許す限り。
pepsi.rb
class Integer
def factorial
(1..self).inject(1){|r, i| r * i}
end
def combination(n)
self.factorial / (n.factorial * (self - n).factorial)
end
end
def pepsi(m, n)
result = (0..m).inject(0){|r, i| r + (-1)**i * m.combination(i) * (m - i)**n}
(result * 10000000000000000 / m**n).to_f / 10000000000000000
end
puts pepsi(ARGV[0].to_i, ARGV[1].to_i)
下のように実行するとm種類のおまけ付きのペプシn本入りを箱買いしたときにコンプできている確率を返してくれます。
ruby pepsi.rb m n
たとえば例題の通りなら、
ruby pepsi.rb 10 24
ね。それだけ。
11/27追記
combinationも整数のメソッドにしてみたりちょっと表現を整理。ロジックはまったく一緒。それと、30 300程度で計算できなくなるのは、よく見たらBignumに入りきらないって言ってるんじゃなくてFloatで表現できないと言ってるだけだった。道理で少なすぎると思った。整数だけで最後の割り算をするようにしたらもっとでかい数でもいけるようになった。
ruby pepsi.rb 365 2287
0.500370783936947
つまり誕生日が均等に分布していると仮定して2月29日を無視した場合、人口2287人以上の街では「毎日誰かしらは誕生日を迎えている」確率5割以上。へー。
おまけ
by 木戸孝紀
tags:Ruby パズル プログラミング 数学
|
|
|
木戸孝紀
