読者です 読者をやめる 読者になる 読者になる

Problem 287

Project Euler

最新のProject Eulerの問題を解いてみました。
非常に難しかったです。
問題の答えを求めるのが難しいのではなく、
Python 2.5で「計算時間1分以内に」解くのが難しい問題です。
結局1分以内に解くことはできませんでしたが。。。


問題が公開された直後に解こうと思っていたのですが、
朝起きたら今まで経験したことのない頭痛があったため
昼の予定をキャンセルして夕方まで眠り、
結局問題が公開されてから1時間後くらいに
問題にチャレンジしました。


問題は以下のようなものです。
長いのでリンクを掲載するだけに留めます。


Problem 287
Problem 287(原文)


とりあえずPython 2.5で 1626 [sec] もかかる
駄作プログラムを掲載しておきます。
しばらく数学的なことと離れていたせいか、
頭がなまっているような気がします。

def calc():
    N = 24
    
    N1 = 1 << (N - 1)
    N2 = N1 ** 2
    
    def is_black(x, y):
        return (x - N1) ** 2 + (y - N1) ** 2 <= N2
    
    f_lt = lambda (bx, by, ex, ey): ((ex - 1, ey - 1), (bx, by))
    f_rt = lambda (bx, by, ex, ey): ((bx, ey - 1), (ex - 1, by))
    f_lb = lambda (bx, by, ex, ey): ((ex - 1, by), (bx, ey - 1))
    f_rb = lambda (bx, by, ex, ey): ((bx, by), (ex - 1, ey - 1))
    
    def recursive_calc(pos, f):
        pw, pb = f(pos)
        if not is_black(pw[0], pw[1]):
            return 2 # all white
        if is_black(pb[0], pb[1]):
            return 2 # all black
        
        bx, by, ex, ey = pos
        if bx + 2 == ex:
            return 9
        
        ret = 1
        mx = (bx + ex) >> 1
        my = (by + ey) >> 1
        ret += recursive_calc((bx, by, mx, my), f)
        ret += recursive_calc((mx, by, ex, my), f)
        ret += recursive_calc((bx, my, mx, ey), f)
        ret += recursive_calc((mx, my, ex, ey), f)
        return ret
    
    ret = 1
    bx = by = 0
    mx = my = 1 << (N - 1)
    ex = ey = 1 << N
    
    ret += recursive_calc((bx, by, mx, my), f_lt)
    ret += recursive_calc((mx, by, ex, my), f_rt)
    ret += recursive_calc((bx, my, my, ey), f_lb)
    ret += recursive_calc((mx, my, ex, ey), f_rb)
    return ret

print calc()


C++に安直に移植したら 23 [sec] で計算できました。
この問題を解いた人達はC/C++Javaであれば
数秒で計算できているようなので、
暇があればC/C++で最適化も試みたいと思います。
シングルコアのマシンでは厳しいかもしれませんが。