Project Euler - Problem 329

f:id:my316g:20170801201758p:plain

python はメモリの限りでかい数を扱ってくれるのでさっそく Atom で環境構築しました．
環境構築が WANIMA の次くらいに嫌いなおれでも簡単にできたのでいい．WANIMA 聴いたことねえけど

というわけでオーバーフロー関係で怒りに包まれて放置していた Problem 329 です．

Prime frog

超意訳:

素数カエルというのが数直線上の自然数点 1, 2, ..., 500 のどこかにいる．
このカエルは一回のジャンプで隣り合う点に等確率で移動する（端にいる場合，自動的に移動可能方向にジャンプ）．

素数である点にいる場合，次の点に跳ぶ直前に，カエルは 2/3 の確率で 'P' (PRIME) と鳴き，1/3 の確率で 'N' (NOT PRIME) と鳴く．
素数でない点にいる場合，次の点に跳ぶ直前に，カエルは 1/3 の確率で 'P' と鳴き，2/3 の確率で 'N' と鳴く．

カエルの初期位置は全ての点に対して等確率でランダムとして，最初の 15 回の鳴き声が "PPPPNNPPPNPPNPN" と聞こえる確率はいくつか？
約分済みの分数 p/q の形で答えよ．

出鱈目なカエルが出てきました．
端点にいる場合を考慮せず多めに見積もっても 500 * 2¹⁵ = 16384000 パターンなので，まあ総当りでいけるでしょう．
というか素数が関わってくる中で総当り以外のきれいな解法を思いつかなかった．

深さ優先探索で解きます．

i が素数のとき True となる配列 p[i] をふるいにかけて生成し，文字列 croak = ‘PPPPNNPPPNPPNPN’ と共にグローバル領域に置く．

鳴き声の種類とジャンプ方向が独立であることに注意して，問題文に忠実に再帰関数を書いておわり．

import math
from fractions import Fraction

SIZE = 500
MAXSTEP = 15

# ふるい
p = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(SIZE + 1)]
p[0] = p[1] = False
p[2] = p[3] = p[5] = True

sqrt = math.sqrt(SIZE)
for i in range(3, SIZE, 2):
    if i >= sqrt:
        break
    for j in range(i ** 2, SIZE, i):
        p[j] = False


croak = 'PPPPNNPPPNPPNPN'   # 鳴き声パターン
ans = 0                     # 答えを保持するグローバル変数


# 深さ優先探索． pos:現在位置, step:移動回数, prob:確率．
def dfs(pos, step, prob):
    global ans

    # 移動回数が 15 回に到達
    if step == MAXSTEP:
        ans += prob
        return

    if pos == 1:    # 現在位置が 1
        if croak[step] == 'P':  # 'P' と鳴くべきなら
            dfs(pos + 1, step + 1, prob / 3)            # 確率 1/3 で右に移動
        else:                   # 'N' と鳴くべきなら
            dfs(pos + 1, step + 1, prob * 2 / 3)        # 確率 2/3 で右に移動

    elif pos == SIZE:   # 現在位置が 500
        if croak[step] == 'P':
            dfs(pos - 1, step + 1, prob / 3)            # 確率 1/3 で左に移動
        else:
            dfs(pos - 1, step + 1, prob * 2 / 3)        # 確率 2/3 で左に移動

    elif p[pos] == True:    # 現在位置が素数
        if(croak[step] == 'P'):
            # 等確率 1/3 で左右に移動
            dfs(pos - 1, step + 1, prob / 3)
            dfs(pos + 1, step + 1, prob / 3)
        else:
            # 等確率 1/6 で左右に移動
            dfs(pos - 1, step + 1, prob / 6)
            dfs(pos + 1, step + 1, prob / 6)

    else:   # 現在位置が素数でない
        if(croak[step] == 'P'):
            # 等確率 1/6 で左右に移動
            dfs(pos - 1, step + 1, prob / 6)
            dfs(pos + 1, step + 1, prob / 6)
        else:
            # 等確率 1/3 で左右に移動
            dfs(pos - 1, step + 1, prob / 3)
            dfs(pos + 1, step + 1, prob / 3)


def PE0329():
    # 1 から 500 まで
    for pos in range(1, SIZE + 1):
        print(pos)
        # 確率 1/500 で位置 pos からスタート
        dfs(pos, 0, Fraction(1, SIZE))

    print(ans)


PE0329()