Pearls in the box (DropBox) - 白い真珠の確率は？

どんな問題？

Pearls in the box
http://www.checkio.org/mission/box-probability/

箱の中に白と黒の真珠が入っている。交互に真珠を一つ箱から取り出し、取り出したものと反対の色の真珠を箱に入れる。このとき、N回後に白の真珠を取り出すことができる確率を求めよ。

引数は、最初の真珠の並び（黒は'b'、白は'w'）と、ステップ数(N)が渡される。
戻り値は、確率を小数点2桁で返す。

ステップ数は20以下、真珠の数も20以下となる。

例題：

checkio('bbw', 3) == 0.48
checkio('wwb', 3) == 0.52
checkio('www', 3) == 0.56
checkio('bbbb', 1) == 0
checkio('wwbb', 4) == 0.5
checkio('bwbwbwb', 5) == 0.48

どうやって解く？

初期値が 'wbb' であれば、次のステップでは 'bbb'、'wwb'、'wbw' の3パターンとなる。その次のステップでも同様にそれぞれ3パターンずつ変化していく。
Nステップ後に白を取り出す確率を求めるのだから、N-1ステップ後に白が何個あるかを調べればいい。

itertools.product()で、x番目の真珠を選ぶ操作を、N-1回繰り返し、その結果の真珠の並びを文字列で取得する。
すべての文字列から'w'の数を調べて確率を求める。

from itertools import product

def checkio(marbles, step):
    def swap_marbles(choices):
        l = list(marbles)
        for i in choices:
            l[i] = 'b' if l[i] == 'w' else 'w'
        return ''.join(l)

    s = ''.join([swap_marbles(p) for p in product(range(len(marbles)), repeat=step - 1)])
    return round(s.count('w') / len(s), 2)

セルフチェックは無事にクリア。
Run&Checkすると・・・あれ？固まってる？

しばらく待っても反応がない。FAILになるわけでもなく、途中で止まってしまったようだ。
GitHubで公開されているテスト問題を確認してみると、どうやら、

"input": ('wwwwwwwwwwwwwwwwwwww', 20)

で止まっているようだ。

ローカルで試してみると、メモリーエラーになってしまった。
真珠20個で20ステップという問題だから、20^19パターン。ちょっと多すぎたか。

もうちょっと計算回数を減らす方法を考えることにした。
毎回、白と黒のどちらかを選択するわけだから、ステップ毎に2パターンと考えることができる。これなら、2^19パターンで済むので、大丈夫だろう。先ほどと違って、パターンごとに確率が変わってくる。

初期値が 'wbb'（白1＋黒2）であれば、

• 白を選択（確率は1/3）→ 結果は、白0＋黒3
• 黒を選択（確率は2/3）→ 結果は、白2＋黒1

となる。
この白黒のどちらかを選択する操作を、N-1回繰り返す。

まとめ

from itertools import product
 
def checkio(marbles, step):
    def calc_probability(choices):
        white, length = marbles.count('w'), len(marbles)
        ratio = 1
        for c in choices:
            if c == 'w':
                ratio *= white / length
                white -= 1
            else:
                ratio *= 1 - white / length
                white += 1
            if white < 0 or white > length:
                return 0
        return ratio * (white / length)
 
    return round(sum(calc_probability(p) for p in product(['w', 'b'], repeat=step - 1)), 2)

http://www.checkio.org/mission/box-probability/publications/natsuki/python-3/first/

calc_probabilyty()では、ステップ毎の確率をratioとして累積していき、最終的に白が出てくる確率を求めている。すべてのパターンを合計すれば答えが求められる。

他の人の答え

再帰を使っている人が多かった。

数学的に解く人も。

def checkio(seq, n):
    r = len(seq)
    w = seq.count('w')
    return round(1/2 + (1-2/r)**(n-1) * (w/r-1/2), 2)

http://www.checkio.org/mission/box-probability/publications/Juge_Ti/python-3/maths-with-proof/

コメントで詳しい説明があるけど、、、よくわからない。数学つらい orz