制約プログラミング楽しそう
Jリーグの対戦予定作成に制約プログラミングソリューション − ＠ITを読んで、制約プログラミングってこういう分野にもつかえるんだなぁっておもたｔ。
制約プログラミングといわれてすぐ浮かぶのはprologなわけなんですが、やっぱりprologとかいってしまうと人工知能とか夢分野的なイメージだったのですが(そいうえば、RHGの逆襲の懇親会でミラクルリナックスの吉岡さんも大学時代はPrologで研究してたとかおっしゃっていたっけか)、こういう複雑な領域の問題を解くのにぴったりですね。
制約的なプログラミングやれそうなのとしては、curryがあるんですが、Leopardにしてからためせてないなぁ
制約プログラミング - Wikipediaに、問題例として覆面算というのがのっていたので、僕も解きたくなったので、解いてみました。
SEND + MORE = MONEY となるような数字を探すという問題。制約プログラミング - Wikipediaに載っているコードを鈍直にRubyに落とすとこんなかんじ
p (1..9).map{|s| (0..9).map{|e| (0..9).map{|n| (0..9).map{|d| (0..9).map{|m| (1..9).map{|o| (0..9).map{|r| (0..9).map{|y| {:s,s,:e,e,:n,n,:d,d,:m,m,:o,o,:r,r,:y,y}}}}}}}}}.flatten.delete_if{|h| 1000*h[:s] + 100*h[:e] + 10*h[:n] + h[:d] + 1000*h[:m] + 100*h[:o] + 10*h[:r] + h[:e] != 10000*h[:m] + 1000*h[:o] + 100*h[:n] + 10*h[:e] + h[:y] }
誰ですか、Rubyは読みやすいとか、きれいなコード書けるとか言っている人は(違う
で、このコードなんですが、うちのCore 2 Duo 2GHz、メモリ2GのLeopardのruby1.8.6で、8分ぐらいまわしましたが全然終わる気配がしませんでした。それどころか、メモリを使い切っている感じで全然駄目です。まぁ、ものすごく膨大な配列を作っている訳なので、しょうがないのですが。
というわけで、もう少し頭使って、生成されるオブジェクトの数を少なくしてみたのがこちら
p (1..9).map{|s| (0..9).map{|e| (0..9).map{|n| (0..9).map{|d| [1].map{|m| (1..9).map{|o| (0..9).map{|r| (0..9).map{|y| {:s,s,:e,e,:n,n,:d,d,:m,m,:o,o,:r,r,:y,y} }.delete_if{|h| (h[:s]*1000 + h[:e]*100 + h[:n]*10 + h[:d] + h[:m]*1000 + h[:o]*100 + h[:r]*10 + h[:e]) != ( h[:m]*10000 + h[:o]*1000 + h[:n]*100 + h[:n]*10 + h[:y] )}}}}}}}}.flatten.delete_if{|a| a.size == 0 }
で、実行すればこんなかんんじ。
: time ruby fukumen.rb
[{:m=>1, :o=>1, :s=>9, :r=>9, :e=>8, :y=>0, :n=>0, :d=>2}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>8, :y=>1, :n=>0, :d=>3}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>8, :y=>2, :n=>0, :d=>4}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>8, :y=>3, :n=>0, :d=>5}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>8, :y=>4, :n=>0, :d=>6}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>8, :y=>5, :n=>0, :d=>7}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>8, :y=>6, :n=>0, :d=>8}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>8, :y=>7, :n=>0, :d=>9}, {:m=>1, :o=>1, :s=>9, :r=>0, :e=>9, :y=>9, :n=>0, :d=>0}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>9, :y=>0, :n=>1, :d=>1}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>9, :y=>1, :n=>1, :d=>2}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>9, :y=>2, :n=>1, :d=>3}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>9, :y=>3, :n=>1, :d=>4}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>9, :y=>4, :n=>1, :d=>5}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>9, :y=>5, :n=>1, :d=>6}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>9, :y=>6, :n=>1, :d=>7}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>9, :y=>7, :n=>1, :d=>8}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>9, :y=>8, :n=>1, :d=>9}]
real 1m35.881s
user 1m35.618s
sys 0m0.253sもう少しがんばれるきがするんですが、眠いのでやめときます。
ごめんなさい。いろんなことを明日にまわします。
追記:式をみてmが1ってわかってるんだから、sの可能性は9or8というのをわすれたので、書き直し。
p (8..9).map{|s| (0..9).map{|e| (0..9).map{|n| (0..9).map{|d| [1].map{|m| (1..9).map{|o| (0..9).map{|r| (0..9).map{|y| {:s,s,:e,e,:n,n,:d,d,:m,m,:o,o,:r,r,:y,y} }.delete_if{|h| (h[:s]*1000 + h[:e]*100 + h[:n]*10 + h[:d] + h[:m]*1000 + h[:o]*100 + h[:r]*10 + h[:e]) != ( h[:m]*10000 + h[:o]*1000 + h[:n]*100 + h[:n]*10 + h[:y] )}}}}}}}}.flatten.delete_if{|a| a.size == 0 }
[{:m=>1, :o=>1, :s=>9, :r=>9, :e=>8, :y=>0, :n=>0, :d=>2}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>8, :y=>1, :n=>0, :d=>3}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>8, :y=>2, :n=>0, :d=>4}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>8, :y=>3, :n=>0, :d=>5}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>8, :y=>4, :n=>0, :d=>6}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>8, :y=>5, :n=>0, :d=>7}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>8, :y=>6, :n=>0, :d=>8}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>8, :y=>7, :n=>0, :d=>9}, {:m=>1, :o=>1, :s=>9, :r=>0, :e=>9, :y=>9, :n=>0, :d=>0}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>9, :y=>0, :n=>1, :d=>1}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>9, :y=>1, :n=>1, :d=>2}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>9, :y=>2, :n=>1, :d=>3}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>9, :y=>3, :n=>1, :d=>4}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>9, :y=>4, :n=>1, :d=>5}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>9, :y=>5, :n=>1, :d=>6}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>9, :y=>6, :n=>1, :d=>7}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>9, :y=>7, :n=>1, :d=>8}, {:m=>1, :o=>1, :s=>9, :r=>9, :e=>9, :y=>8, :n=>1, :d=>9}]
real 0m18.549s
user 0m18.499s
sys 0m0.046s
