数学パズルを解いてみる その１

プログラミング Groovy

ちょっと前にtwitter上で数学パズルがいくつか紹介されていて、groovyで解いてみたくなりました。

これ好き。問８．「ＡとＢはそれぞれ、1以上1000以下の整数をひとつ考えて紙に書く。Ａの考えた数がＢのそれよりも大きい確率は？」

「スマリヤンの究極の論理パズル」て本に載ってるそうです。
人間が解く解き方じゃなくて、Aの手とBの手の2重ループでカウントアップしてとかでもなくて、ちょっと賢しげなプログラムで解いてみたい。

要は1~1000の集合A, Bが有って、その直積集合のうちa > bな物の比率を答える訳ですね。

((1..1000) * (1..1000)).findAll{it.a > it.b}.size() / ((1..1000) * (1..1000)).size()

積集合が&で、直積集合なら*かな、と。でも残念ながら*演算なんて出来ません。そこで演算子オーバーライド。

IntRange.metaClass.multiply = {
    delegate.collect{a->it.collect{b->[a:a, b:b]}}.sum()
}

Aの各要素について{(a, b1), (a, b2),…}のリストを作り、そのリストのリストをsum()で{(a1, b1), (a1, b2),…}+{(a2, b1), (a2, b2),…}…とすることで{(a1, b1), (a1, b2),…(a2, b1), (a2, b2),…}と晴れて*演算で直積集合が得られるようになりました。
で、動くコード。

IntRange.metaClass.multiply = {
    delegate.collect{a->it.collect{b->[a:a, b:b]}}.sum()
}
((1..1000) * (1..1000)).findAll{it.a > it.b}.size() / ((1..1000) * (1..1000)).size()

GroovyConsoleで実行すると、

Result: 0.4995

と正しく答えが出ます。ただ…スッゲー重いです。メモリ的にも計算量的にも…GroovyConsoleを素で起動して実行してもOutOfMemoryErrorで落ちるくらいに重いです。
-Xmx512mしてやったらなんとか動きましたが、数十秒返って来ません。
どうもやっぱり1000×1000の総当たりで直積集合を作るのが重いようなので、直積集合を変数に入れて総当たりを1回にしてみます。

IntRange.metaClass.multiply = {
    delegate.collect{a->it.collect{b->[a:a, b:b]}}.sum()
}
def productSet = ((1..1000) * (1..1000))
productSet.findAll{it.a > it.b}.size() / productSet.size()

相変わらず重いですが、だいぶましにはなりました。

せっかくここまでしたので、もうちょっといろんな数列で

例えば1~1000の中から奇数を選んで、とかやってみたくなりました。

IntRange.metaClass.multiply = {
    delegate.collect{a->it.collect{b->[a:a, b:b]}}.sum()
}
def A = (1..1000).findAll{it % 2 == 1}
def B = A
def productSet = (A * B)
productSet.findAll{it.a > it.b}.size() / productSet.size()

おっと、IntRangeじゃなくなってしまったので*ができません。Aがどんなクラスでも良いように、ちょっと入れ替えて…

def A = (1..1000).findAll{it % 2 == 1}
def B = A
A.metaClass.multiply = {
    delegate.collect{a->it.collect{b->[a:a, b:b]}}.sum()
}
def productSet = (A * B)
productSet.findAll{it.a > it.b}.size() / productSet.size()

これで、A, Bの初期化を変えたり最後のfindAllの条件を変えたりすればどんな条件もばっちりです!-)