技術をかじる猫

適当に気になった技術や言語、思ったこと考えた事など。

プログラマ脳を鍛える数学パズル 08

前後左右に動けるロボットが存在し、こいつが 12 回移動したとすると、移動経路は何通り考えられるか?
ただし一度移動したルートを踏むことはできないこととする。

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問

ということで、アルゴリズムらしくなってきた?感じですね。

再起であぼん

def count_move(log, max_move):
    if len(log) == max_move + 1:
        return 1

    patterns = 0
    for move_to in [(0,1), (1,0), (0, -1), (-1, 0)]:
        x, y = log[-1]
        x += move_to[0]
        y += move_to[1]
        position = (x, y)
        if position in log:
            continue
        else:
            nlog = log[:]
            nlog.append(position)
            patterns += count_move(nlog, max_move)
    return patterns

print(count_move([(0, 0)], 12))
  1. 初期座標含めて 13 (12 + 初期座標)個座標を格納したら 1 を返す。
  2. その場所から前後左右をとりあえず移動できるなら移動して、次の再起へ進む
  3. 帰ってきた 1 と蓄えて、再起の呼び出し元に通知

を繰り返す。
全幅探索だったっけか深さ優先探索だったか…

python3て末尾再起最適化ないんだっけ…デコレータつかって擬似末尾再起最適化はあったのだけど…
あるなら書き直す。