Ghosts age (O'Reilly) - フィボナッチ数

どんな問題？

Ghosts age
http://www.checkio.org/mission/ghosts-age/

お化けは、生まれたときは不透明度(opacity)が10000である。（＝完全に不透明）
誕生日を迎えると、不透明度が増減する。

年齢がフィボナッチ数なら、年齢の数だけ減少

それ以外の年は、1 増加

また、お化けは5000歳を超えることはない。（消えてしまう）
このとき、不透明度から年齢を求めよ。

注意：これはハロウィーンの問題なので、普通の解答ではなく、魔法みたいな解答、びっくりするような解答を書くこと！

引数は、お化けの不透明度(opacity)が整数値で渡される。0＜opacity≦10000
戻り値は、お化けの年齢を整数値で返す。age＜5000

例題：

checkio(10000) == 0
checkio(9999) == 1
checkio(9997) == 2
checkio(9994) == 3
checkio(9995) == 4
checkio(9990) == 5

どうやって解く？

魔法みたいな解答って言われても・・・とりあえず、普通に解いてみる。

フィボナッチ数

フィボナッチ数といえば、よく再帰呼び出しの例で出てくるが、1つ前の数字と2つ前の数字の和からなる数列。n番目のフィボナッチ数を取得する関数を書くとこうなる。

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

再帰が2重だと遅いので、1重にしてみる。

def fib(n, a1=1, a2=0):
    if n == 0:
        return a2
    elif n == 1:
        return a1
    else:
        return fib(n - 1, a1 + a2, a1)

再帰を使わずにループでも書ける。

def fib(n):
    a1, a2 = 1, 0
    while n > 0:
        a1, a2 = a1 + a2, a1
        n -= 1
    return a2

まあ、今回は数字がフィボナッチ数かどうかを判定すればいいので、あらかじめ10000までのフィボナッチ数をリスト化しておけばいい。

def fibonacci_numbers(max_value=10000):
    a1, a2 = 0, 1
    yield a1
    while a2 < max_value:
        yield a2
        a2, a1 = a2 + a1, a2

FIBONACCI = list(fibonacci_numbers())  # 10000未満のフィボナッチ数のリスト

あとは、年齢をループさせて、透明度が一致すればループ終了する。

まとめ

def fibonacci_numbers(max_value=10000):
    a1, a2 = 0, 1
    yield a1
    while a2 < max_value:
        yield a2
        a2, a1 = a2 + a1, a2

FIBONACCI = list(fibonacci_numbers())

def checkio(opacity):
    value = 10000
    for year in range(5000):
        value += -year if year in FIBONACCI else 1
        if value == opacity:
            return year

    return None

http://www.checkio.org/mission/ghosts-age/publications/natsuki/python-3/first/

普通の答えだけど、いちおう公開しておく。
面白い解き方っていうのもどんなんだろう？思いつかないなぁ。コメントでお化けのAA描くとか？
今はハロウィーンの季節じゃないから、普通でいいや。（なげやり）

他の人の答え

面白いのがいっぱいあった！みんなすごいなぁ。

すべての答えを辞書に埋め込み

checkio={3219:4181,3220:4182,（中略）,10000:0}.get

http://www.checkio.org/mission/ghosts-age/publications/veky/python-3/first/

ラムダ式ですらない。

年齢と不透明度の規則性を利用

def checkio(opacity):
    x = \
    [[9999, 9999, 1],
     [9997, 9997, 2],
　　（中略）
     [5804, 7400, 2584],
     [3219, 5802, 4181]
    ]
    for i in x:
        if i[0] <= opacity <= i[1]:
            return i[2] + opacity -i[0]