【Project Euler】Problem 220 Heighway Dragonの感想（その２）

D=20で4秒なのでD=50は136年

前回でD=20のドラゴン曲線を描いてみましたが処理時間はPythonで4秒程度。元の問題は以下のようにD=50なのでまともにO(2ⁿ)で計算すると136年。ということで何らかの高速化が必要になります。

Project Euler; Proglem 220
D50のHeighway Dragon曲線の10¹²番目の点の座標を求めろ

問題要求されているのは上のように最後の座標で途中経過は必要とされないので、高速化の方法としては以下の２つがあるのかなと思います。
１．Cache等のプログラミング・テクニックを使う
２．問題の周期性に注目して座標を求めるアルゴリズムを探す

本来は２をするのが出題者の意図かなと思い色々考えましたが、なかなか上手く行かなかったので今回は前回のドラゴン曲線を描くプログラムをCacheを使って高速化を模索しました。

Pythonの@lru_cacheは使えず

Pythonでお手軽Cacheと言えば@lru_cacheで過去にProject Eulerの問題で何度もお世話になったので、今回もどうかなと色々試してみました。

from functools import lru_cache

@lru_cache(maxsize=100000)

ただ今回は再帰関数からの結果だけを得ればよいという訳ではなくて、ターゲットの10¹²番目の点に到達するのがどの深さで起こるのか分からないので、その時にはCahcheをオフにして実際に計算を行う必要があるということで使えませんでした。

したがって自分でPythonのDICTを使ってCacheを実現しました。要は再帰関数を呼ぶ前に残りStep数、座標、向きを記録しておいて関数から帰ってきたらそれらの差分をDICTに記録するというものです。

Cacheを使うかどうかは以下のロジックで残りStep数を見て判断しました。

if 残りステップ数　> CacheされたStep数:
  Cacheを使って残りStep数、座標、向きを更新
else:
  再帰関数を呼ぶ

この方法でなんとか答えを得ることできましたが、Project Eulerの素晴らしいところはどうな方法でも正解を得ることが出来れば、正解者たちが書き込んでいるThreadにアクセスができるようになることです。このThreadは世界中から集まった素晴らしいアイデアの宝庫で、よくもこんなアルゴリズムを思いつくなといつも感心させられてしまいます。