最近Codilityというサイトでプログラミングの再履修(?!)してたりします。
Lessonsには、項目毎によく知られるアルゴリズムの説明のPDFが置いてあったり、１０いくらかのタイムトライアル問題に挑戦させてくれます。アルゴリズムの正確性と、スケーラブルな速度かどうかでスコアをつけてくれます。タイムトライアルといっても何度でも繰り返しチャレンジさせてくれます。
最初にアルゴリズム戦略を間違えてしまうとなかなかスコア100には到達できない問題とかあります。
Fibonacci数のFibFrogに挑戦したときに、戦略誤りしたときの大きな落差を感じたことを書きます。
この問題は、N個の0/1の数列が与えられ、一度にフィボナッチ数の距離かつ移動先が1の数字であれば移動することができる、その条件下で端から端まで移動するときの最小ホップ数を求めてね、というものです。(FibFrogというのは問題の説明上フィボナッチ数距離なら飛べるカエルが川の向こう岸まで跳躍していくその最短数を見つけてねって感じだったから、だと思う)
最初にとった方針は、ジャンプできるところを再帰で探索していこう、一度通ったところはなんらかの判定で再処理を避けて効率を図ろう、というものにしました。正確性をクリアしたあとなかなかスコアが上がらず、フィボナッチ数の特性でなんとかとか考えて最後から1HOP前の位置をキャッシュしておくとか、一つパスを見つけたらそのパスの長さ以上探索しないとか、ない頭でひねり出してたのですけどもスコア91まできたときlarge_cyclicという項目でなにをしてもTIMEOUT ERROR, Killed. Hard limit reached: 6.000 sec.の壁を越えられなくなりました。ツリー探索ぽい感じでHOPが長くなると探索パスがべき乗的に増えてしまい、でもなかなか適当に探索を省略すると、そのパスに最短が隠れていたりで、笑っちゃうような変な処理とか入れても全然変わらない*1
ヒントは最短HOPが分かればいい問題だったことで、HOP毎の水平探索（？）なるような方法に切り替えました。1HOP目からHOPを増やしていきHOP毎にとりえる次HOPでの位置を全サーチして最初にゴールポイントを見つけたらそのときのHOPがすなわち最小のものです。これだと正解パスを残すのが難しいと思ったのですが、問題はそれを求めてないので、これに切り替えたらスコア100いけました。（ふう）
HOP毎全探索のほうを残しておきます。最初の再帰探索のはこれの倍くらいの行数ありました。
def solution(A):
# some explicit answers
if len(A)<3:
return 1
# the numbers sorted and unique
FIBS = [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025]
last_ni = len(A)
processed_ni = {}
nextjmplst = dict.fromkeys([j-1 for j in reversed(FIBS) if j-1<len(A) and A[j-1]==1 or j==len(A)+1], True)
found = False
hop = 1
while True:
jmplst = list(nextjmplst.keys())
# no position movable
if len(jmplst)==0:
hop = -1
break
nextjmplst = {}
for ni in jmplst:
# reach the goal
if ni == last_ni:
found = True
break
# skip the position passed once
if processed_ni.get(ni):
continue
processed_ni[ni] = True
nextjmplst.update(dict.fromkeys([ni+j for j in reversed(FIBS) if ni+j<len(A) and A[ni+j]==1 or ni+j==len(A)], True))
if found:
break
hop += 1
return hop==0 and -1 or hop*1:あるいは全然だめになるとか
