Rubyで論理プログラミングしようよ!

人生は選択の連続だよ。１つの選択が君の未来を変えるよ。そして残念なことに、後からその失敗に気がついても、選択をやり直すことは人生ではできないんだよ..

コンピュータプログラムにも似たようなところがあるよ。プログラムは一度走り出したら止まらないから、途中の分岐で選ばれた選択を後から変えるのは得意じゃないんだ。

問題１

例えば次のような問題を考えてみるよ。

xが1,2,3の何れかで、yが4,5,6の何れかであるとき、 x + y = 7 となる、x, yの組みを求めよ。

x, yには複数の選択肢があってxの決定はyの決定に影響を与えるから、その組み合わせを決めるためには、人間がするのと同様の試行錯誤が必要になりそうだよね。どうやってプログラムしたらいいか、ちょっと戸惑うよね。

こういったはっきりと決まっていない事実に基づいて答えを求めることを、非決定性の問題と言うらしいよ。なるほどそうすると人生は差し詰め、非決定性の連立方程式を解くようなものなんだろうね。

さて、君ならこの問題どうコーディングするのかな。

確かにコンピュータプログラムは人間と似ているけど、大きく違うところが２つあるよ。それはその計算量と記憶力だよ。コンピュータは短時間で膨大な量の計算をこなして、その結果を忘れずにしっかりと記憶することができる。そのパワーを活用すれば未来を決定づけるすべての選択肢を用意して、成功の道だけを選ぶようにすることができる。

ここでもしこの問題の解法に、ループを考えたとしたら君は負け組だよ。

なぜならRubyにはすべての選択肢を生成するArray#productがあるんだから。

xl = [1, 2, 3]
yl = [4, 5, 6]
xl.product(yl).tap{|t| p t}.select { |x, y| x + y == 7 } # => [[1, 6], [2, 5], [3, 4]]
# >> [[1, 4], [1, 5], [1, 6], [2, 4], [2, 5], [2, 6], [3, 4], [3, 5], [3, 6]]

ほらできた!

tapの出力を見れば、Array#productがx yのすべての組み合わせを生成しているのが分かるよね。そしてArray#selectでx + y = 7の条件を満たすものだけを選択してる。

問題２

じゃあ次はピタゴラスをやってみようよ。説明するまでもないけどピタゴラス数は、A^2 + B^2 = C^2を満たす整数A B Cの組のことだよ。A B Cをすべての整数とすると答えは無限にあるだろうから、ここでは辺の総和(A+B+C)がN以下であるものを求めてみるよ。

def pythag(n)
  al, bl, cl = [*1..n], [*1..n], [*1..n]
  al.product(bl, cl).select do |a, b, c|
    a + b + c <= n && a**2 + b**2 == c**2
  end
end
pythag(30) # => [[3, 4, 5], [4, 3, 5], [5, 12, 13], [6, 8, 10], [8, 6, 10], [12, 5, 13]]

あっという間に答えが出た。辺の総和が30以下のピタゴラス数は6組あるんだね。

上の条件で各辺の範囲は1～Nで同じだから、Array#repeated_permutationを使ってもいいよね。

def pythag(n)
  [*1..n].repeated_permutation(3).select { |a,b,c| a + b + c <= n && a**2 + b**2 == c**2 }
end
pythag(30) # => [[3, 4, 5], [4, 3, 5], [5, 12, 13], [6, 8, 10], [8, 6, 10], [12, 5, 13]]

問題３

次はもう少し論理問題っぽいものをやってみるよ。

baker(パン屋)、cooper(桶屋)、fletcher(矢屋)、miller(粉屋)、smith(鍛冶屋)が５階建てのアパートの別々の階に住んでいる。bakerは最上階には住んでない。cooperは地上階には住んでない。fletcherは最上階にも地上階にも住んでない。millerはcooperよりも上の階に住んでいる。smithはfletcherに接する階には住んでない。fletcherはcooperに接する階には住んでない。誰がどこに住んでいるか？ [計算機プログラムの構造と解釈/４章/３より(一部改変しました)]

有名な問題だから知ってる人もいると思うけど、知らなかったらちょっと考えてみてね。

Array#productを使えば造作無いよね。

baker_, cooper_, fletcher_, miller_, smith_ = [[*1..5]] * 5
ans = baker_.product(cooper_, fletcher_, miller_, smith_).detect do |baker, cooper, fletcher, miller, smith|
  [baker,cooper,fletcher,miller,smith].uniq.size == 5 &&
  baker != 5 &&
  cooper != 1 &&
  fletcher != 1 &&
  fletcher != 5 &&
  miller > cooper &&
  (smith - fletcher).abs != 1 &&
  (fletcher - cooper).abs != 1 
end
"baker => %i, cooper => %i, fletcher => %i, miller => %i, smith => %i" % ans # => "baker => 3, cooper => 2, fletcher => 4, miller => 5, smith => 1"

detect内の条件が増えると見た目が綺麗じゃないよね。補助関数を作ってもう少し良くしてみるよ。

def rule(*rules)
  rules.all?
end
ans = [*1..5].permutation(5).tap{|t| p t}.detect do |baker, cooper, fletcher, miller, smith|
  rule baker != 5,
        cooper != 1,
        fletcher != 1,
        fletcher != 5,
        miller > cooper,
        (smith - fletcher).abs != 1,
        (fletcher - cooper).abs != 1 
end
"baker => %i, cooper => %i, fletcher => %i, miller => %i, smith => %i" % ans # => "baker => 3, cooper => 2, fletcher => 4, miller => 5, smith => 1"
# >> #<Enumerator: [1, 2, 3, 4, 5]:permutation(5)>

rule関数はEnumerable#all?を使って各条件の&&を取るよ。これでいくらかすっきりしたね。ちなみにこういうのもDSLって呼んでいいのかな？

さらにここではArray#permutationを使ったよ。５人の選択範囲が同じだからね¹。productとpermutationは似たメソッドだけど、実はその返り値に大きな違いがあるんだよ。productはそのすべての組み合わせを生成して返すけど、permutationはEnumeratorを返すつまり、この段階では組み合わせを生成しないんだ。そしてselectが呼ばれたときその条件に従って、はじめて内容を評価つまり遅延評価するんだ。これは効率上きっと有利だろうね。

継続

さてArray#productを使った先の解法はコンピュータパワーを使った、富豪的プログラミングと言えるかも知れないね。例えば先のピタゴラスにおけるproductで生成される組の数を見てみよう。

def pythag(n)
  al, bl, cl = [*1..n], [*1..n], [*1..n]
  al.product(bl, cl).tap{ |t| p t.size }.select do |a, b, c|
    a + b + c <= n && a**2 + b**2 == c**2
  end
end
pythag(30) # => [[3, 4, 5], [4, 3, 5], [5, 12, 13], [6, 8, 10], [8, 6, 10], [12, 5, 13]]
pythag(100) # => [[3, 4, 5], [4, 3, 5], [5, 12, 13], [6, 8, 10], [7, 24, 25], [8, 6, 10], [8, 15, 17], [9, 12, 15], [9, 40, 41], [10, 24, 26], [12, 5, 13], [12, 9, 15], [12, 16, 20], [12, 35, 37], [15, 8, 17], [15, 20, 25], [15, 36, 39], [16, 12, 20], [16, 30, 34], [18, 24, 30], [20, 15, 25], [20, 21, 29], [21, 20, 29], [21, 28, 35], [24, 7, 25], [24, 10, 26], [24, 18, 30], [24, 32, 40], [28, 21, 35], [30, 16, 34], [32, 24, 40], [35, 12, 37], [36, 15, 39], [40, 9, 41]]
# >> 27000
# >> 1000000

N=30とした場合、その組み合わせの数は27000組になる。そしてN=100とするとその数は100万組!ちょっと気になる数字だよね。

この例では各辺の選択範囲は同じだから、Array#permutationを使えば問題は解決するけど、選択範囲が異なる場合はpermutationが使えない。それにコンピュータはもっと人間の思考をシミュレートしたものであるべきだって意見もあるだろうね。つまり一つ試しては戻り一つ試しては戻るという動作を繰り返しながら一つづつ答えを見つける、そんな試行錯誤型の解法があってもいいよね。

Rubyでは継続(Continuation)を使ったプログラミングにより、それが実現できるんだ。Rubyにおける継続はKernel#callccの呼び出しで「今」を持ち運び可能なオブジェクトにして、未来のどこかでそれを再度呼び出す(callする)、つまり「過去」に戻ることを実現可能にする。

ちょっと例を示すよ。

require "continuation"
time_machine = nil
my_vocabularies = 
  [:be_my_wife?, :i_love_you, :i_need_you, :present_for_you, :i_always_love_you]
print "I met her...\n\n"
sleep 1
propose = callcc { |t| time_machine = t; my_vocabularies.shift }
print "I said.. #{propose}.\n"
sleep 1
print "and she said..\n"
sleep 2
puts answer =
    case propose
    when :i_always_love_you
      "yes!"
    when :i_love_you, :i_need_you
      "hmm..."
    else
      "goodbye"
    end
sleep 2
puts
unless answer == "yes!"
  print "Back to the past\n\n"
  time_machine.call(my_vocabularies.shift)
else
  print "Y.E.S!\n"
  exit
end
# >> I met her...
# >> 
# >> I said.. be_my_wife?.
# >> and she said..
# >> goodbye
# >> 
# >> Back to the past
# >> 
# >> I said.. i_love_you.
# >> and she said..
# >> hmm...
# >> 
# >> Back to the past
# >> 
# >> I said.. i_need_you.
# >> and she said..
# >> hmm...
# >> 
# >> Back to the past
# >> 
# >> I said.. present_for_you.
# >> and she said..
# >> goodbye
# >> 
# >> Back to the past
# >> 
# >> I said.. i_always_love_you.
# >> and she said..
# >> yes!
# >> 
# >> Y.E.S!

暇なら手元にコピーして実行してみてくれる？

さて自分でRubyの継続を使って先の問題を解きたいところなんだけど、どうにも僕の頭がついていかなくて、継続を使いこなすにはまだ時間が掛かりそうなんだよ。

そこで継続を使ったRubyの拡張ライブラリAmbの助けを借りることにするよ。Ambを使うとより宣言的に論理問題の条件を記述できるんだ。

gem install ambでインストールして次のように使うよ²。まずはピタゴラスから。

require 'amb'
def pythag(n)
  q = []
  amb = Class.new{include Amb}.new
  a = amb.choose *(1..n)
  b = amb.choose *(1..n)
  c = amb.choose *(1..n)
  
  amb.assert a + b + c <= n
  amb.assert a**2 + b**2 == c**2
  q << [a, b, c]
  amb.failure
rescue
  q
end
pythag(30) # => [[3, 4, 5], [4, 3, 5], [5, 12, 13], [6, 8, 10], [8, 6, 10], [12, 5, 13]]

Ambはモジュールだからクラスにincludeして使うよ。Amb#chooseで選択肢をセットするんだけど、このとき裏ではcalccが呼ばれているよ。Amb#assertで条件を定義して、a b cを呼び出せば答えが得られる。Amb#failureはすべての答えが得られるまで、継続をcallして答えがなくなるとエラーを送出するんだ。failureを呼ばなければ最初の答えだけが得られる。

同じことはAMB.solve_allクラスメソッドでも実現できるよ。

n = 30
AMB = Class.new{include Amb}
AMB.solve_all do |amb|
  a = amb.choose *(1..n)
  b = amb.choose *(1..n)
  c = amb.choose *(1..n)
  amb.assert a + b + c <= n
  amb.assert a**2 + b**2 == c**2
  p [a, b, c]
end
# >> [3, 4, 5]
# >> [4, 3, 5]
# >> [5, 12, 13]
# >> [6, 8, 10]
# >> [8, 6, 10]
# >> [12, 5, 13]
# >> No More Solutions

じゃあアパート住人の問題もAmbで解いてみるよ。

AMB = Class.new{include Amb}
AMB.solve do |amb|
  baker = amb.choose(1, 2, 3, 4, 5)
  cooper = amb.choose(1, 2, 3, 4, 5)
  fletcher = amb.choose(1, 2, 3, 4, 5)
  miller = amb.choose(1, 2, 3, 4, 5)
  smith = amb.choose(1, 2, 3, 4, 5)
  amb.assert [baker, cooper, fletcher, miller, smith].uniq.size == 5
  amb.assert baker != 5
  amb.assert cooper != 1
  amb.assert fletcher != 1 && fletcher != 5
  amb.assert miller > cooper
  amb.assert (smith - fletcher).abs != 1
  amb.assert (fletcher - cooper).abs != 1
  puts "baker => %i, cooper => %i, fletcher => %i, miller => %i, smith => %i" % [baker, cooper, fletcher, miller, smith]
end
# >> baker => 3, cooper => 2, fletcher => 4, miller => 5, smith => 1

なんか宣言的でいいよね!

最後にベンチマークを取ってみるよ。N=100でビタゴラスを求めたときの結果だよ。

require "benchmark"
require "amb"
def pythag(n)
  al, bl, cl = [*1..n], [*1..n], [*1..n]
  al.product(bl, cl).select do |a, b, c|
    a + b + c <= n && a**2 + b**2 == c**2
  end
end
def pythag_with_permutation(n)
  [*1..n].repeated_permutation(3).select { |a,b,c| a + b + c <= n && a**2 + b**2 == c**2 }
end
def pythag_with_amb(n)
  q = []
  amb = Class.new{include Amb}.new
  a = amb.choose *(1..n)
  b = amb.choose *(1..n)
  c = amb.choose *(1..n)
  
  amb.assert a + b + c <= n
  amb.assert a**2 + b**2 == c**2
  q << [a, b, c]
  amb.failure
rescue
  q
end
Benchmark.bmbm do |bm|
  n = 100
  bm.report { pythag(n) }
  bm.report { pythag_with_permutation(n) }
  bm.report { pythag_with_amb(n) }
end
# >> Rehearsal ------------------------------------
# >>    0.510000   0.050000   0.560000 (  0.594200)
# >>    0.360000   0.000000   0.360000 (  0.361962)
# >>   12.240000   0.600000  12.840000 ( 12.879879)
# >> -------------------------- total: 13.760000sec
# >> 
# >>        user     system      total        real
# >>    0.540000   0.010000   0.550000 (  0.549009)
# >>    0.340000   0.000000   0.340000 (  0.349040)
# >>   12.210000   0.530000  12.740000 ( 12.763450)

うわっAmb遅っ!

参考サイト: 計算機プログラムの構造と解釈/４章/３

お気楽 Ruby プログラミング入門

日本Rubyの会公式Wiki - KansaiWorkshop16

関西オープンソース2005発表 , 非決定性計算 , KOF宴会 - Journal InTime(2005-10-29)

Rubyの「継続(Continuation)」(1) - バリケンのRuby日記 - Rubyist

継続でバックトラックを Ruby で - Tociyuki::Diary

なんでも継続

(追記:2011-9-1) 参考サイトのリンクを追記しました。一部コードを修正しました。

(追記:2011-11-27) 一部Array#permutationをArray#repeated_permutationに変更しました。

(comment) >ans = [1..5].permutation(5)tap{|t| p t}.select do |baker, cooper, fletcher, miller, smith|

tapの前の.が抜け落ちている。

ans = [1..5].permutation(5).tap{|t| p t}.select do |baker, cooper, fletcher, miller, smith| »kumonopanyaさん
ありがとう！訂正しました

各値が異なることが保証されるので、最初の条件も不要になる ↩
loaderroが出た場合lib/amb.rb内のパスを修正してください ↩

blog comments powered by Disqus

100円〜で好評発売中！
M'ELBORNE BOOKS