採用クイズで頭の体操

こんな採用クイズがあったのでpython初心者なりにやってみました。

import functools

def main():
    fibo =getFibonacci()
    fibo.reverse()
    count = 0
    for i in range(len(fibo) - 1):
        list = [fibo[i]]
        count = getMillion(fibo, list, fibo[i], i, count)
    print('Number of fibonacci combination is ', count)

def getMillion(fibo, list, now, i, count):
    new = now + fibo[i]
    list += [fibo[i]]
    if new < 1000000:
        return getMillion(fibo, list, new, i, count)
    else:
        if new == 1000000:
            print(list, ' = ', functools.reduce(lambda x, y: x + y, list))
            count += 1
        i += 1
        list = list[:-1]
        if i < len(fibo):
            return getMillion(fibo, list, now, i, count)
        else:
            return count

def getFibonacci():
    return list(filter(lambda x: 2 <= x <= 1000000, functools.reduce(lambda x,y: x+[x[-1]+x[-2],], range(30), [0,1])));

if __name__ == '__main__':
    main()

ザ・再帰。

フィボナッチ数の取得処理は検索して持ってきました。

書いている途中から嫌な予感がしていましたが、実行するとこうなりました。

[832040, 121393, 46368, 144, 55]  =  1000000
[832040, 121393, 46368, 144, 34, 21]  =  1000000
[832040, 121393, 46368, 144, 34, 13, 8]  =  1000000
[832040, 121393, 46368, 144, 34, 13, 5, 3]  =  1000000
[514229, 317811, 121393, 46368, 144, 55]  =  1000000
[514229, 317811, 121393, 46368, 144, 34, 21]  =  1000000
[514229, 317811, 121393, 46368, 144, 34, 13, 8]  =  1000000
[514229, 317811, 121393, 46368, 144, 34, 13, 5, 3]  =  1000000
[317811, 317811, 317811, 46368, 144, 55]  =  1000000
[317811, 317811, 317811, 46368, 144, 34, 21]  =  1000000
[317811, 317811, 317811, 46368, 144, 34, 13, 8]  =  1000000
[317811, 317811, 317811, 46368, 144, 34, 13, 5, 3]  =  1000000
[196418, 196418, 196418, 196418, 196418, 17711, 144, 55]  =  1000000
[196418, 196418, 196418, 196418, 196418, 17711, 144, 34, 21]  =  1000000
[196418, 196418, 196418, 196418, 196418, 17711, 144, 34, 13, 8]  =  1000000
[196418, 196418, 196418, 196418, 196418, 17711, 144, 34, 13, 5, 3]  =  1000000
(中略)
Traceback (most recent call last):
  File "/Users/Tono/Library/Application Support/IntelliJIdea13/python/helpers/pydev/pydevd.py", line 1004, in trace_dispatch
    return additionalInfo.CreateDbFrame((self, filename, additionalInfo, t, frame)).trace_dispatch(frame, event, arg)
RuntimeError: maximum recursion depth exceeded

ですよねー。

というわけでロジック変更。
数が小さくなればなるほど同じ数の組み合わせが増えるため、再帰が限界を超えてしまいます。
ロジックを組み直し、フィボナッチ×数の辞書で値を保持するようにしました。

import functools

def main():
    fibo =getFibonacci()
    fibo.reverse()
    count = 0
    for i in range(len(fibo) - 1):
        map = {fibo[i]:1}
        count = getMillion(fibo, map, fibo[i], i, count)
    print('Number of fibonacci combination is ', count)

def getMillion(fibo, map, now, i, count):
    new = now
    while new < 1000000:
        new += fibo[i]
        map[fibo[i]] = map[fibo[i]] + 1 if fibo[i] in map else 1
    if new == 1000000:
        list = sorted(map.items(), key=lambda x: x[0]);
        list.reverse()
        print(list, ' = ', functools.reduce(lambda x, y: x + (y[0] * y[1]), list, 0))
        count += 1
    if map[fibo[i]] == 1:
        map.pop(fibo[i])
    else:
        map[fibo[i]] = map[fibo[i]] - 1
    new -= fibo[i]
    i += 1
    if i < len(fibo):
        return getMillion(fibo, map, new, i, count)
    else:
        return count

def getFibonacci():
    return list(filter(lambda x: 2 <= x <= 1000000, functools.reduce(lambda x,y: x+[x[-1]+x[-2],], range(30), [0,1])));

if __name__ == '__main__':
    main()

[(832040, 1), (121393, 1), (46368, 1), (144, 1), (55, 1)]  =  1000000
[(832040, 1), (121393, 1), (46368, 1), (144, 1), (34, 1), (21, 1)]  =  1000000
[(832040, 1), (121393, 1), (46368, 1), (144, 1), (34, 1), (13, 1), (8, 1)]  =  1000000
[(832040, 1), (121393, 1), (46368, 1), (144, 1), (34, 1), (13, 1), (5, 1), (3, 1)]  =  1000000
[(514229, 1), (317811, 1), (121393, 1), (46368, 1), (144, 1), (55, 1)]  =  1000000
[(514229, 1), (317811, 1), (121393, 1), (46368, 1), (144, 1), (34, 1), (21, 1)]  =  1000000
[(514229, 1), (317811, 1), (121393, 1), (46368, 1), (144, 1), (34, 1), (13, 1), (8, 1)]  =  1000000
[(514229, 1), (317811, 1), (121393, 1), (46368, 1), (144, 1), (34, 1), (13, 1), (5, 1), (3, 1)]  =  1000000
[(317811, 3), (46368, 1), (144, 1), (55, 1)]  =  1000000
[(317811, 3), (46368, 1), (144, 1), (34, 1), (21, 1)]  =  1000000
[(317811, 3), (46368, 1), (144, 1), (34, 1), (13, 1), (8, 1)]  =  1000000
[(317811, 3), (46368, 1), (144, 1), (34, 1), (13, 1), (5, 1), (3, 1)]  =  1000000
[(196418, 5), (17711, 1), (144, 1), (55, 1)]  =  1000000
[(196418, 5), (17711, 1), (144, 1), (34, 1), (21, 1)]  =  1000000
[(196418, 5), (17711, 1), (144, 1), (34, 1), (13, 1), (8, 1)]  =  1000000
[(196418, 5), (17711, 1), (144, 1), (34, 1), (13, 1), (5, 1), (3, 1)]  =  1000000
[(121393, 8), (28657, 1), (144, 1), (55, 1)]  =  1000000
[(121393, 8), (28657, 1), (144, 1), (34, 1), (21, 1)]  =  1000000
[(121393, 8), (28657, 1), (144, 1), (34, 1), (13, 1), (8, 1)]  =  1000000
[(121393, 8), (28657, 1), (144, 1), (34, 1), (13, 1), (5, 1), (3, 1)]  =  1000000
[(75025, 13), (17711, 1), (6765, 1), (144, 1), (55, 1)]  =  1000000
[(75025, 13), (17711, 1), (6765, 1), (144, 1), (34, 1), (21, 1)]  =  1000000
[(75025, 13), (17711, 1), (6765, 1), (144, 1), (34, 1), (13, 1), (8, 1)]  =  1000000
[(75025, 13), (17711, 1), (6765, 1), (144, 1), (34, 1), (13, 1), (5, 1), (3, 1)]  =  1000000
[(46368, 21), (17711, 1), (6765, 1), (1597, 1), (144, 1), (55, 1)]  =  1000000
[(46368, 21), (17711, 1), (6765, 1), (1597, 1), (144, 1), (34, 1), (21, 1)]  =  1000000
[(46368, 21), (17711, 1), (6765, 1), (1597, 1), (144, 1), (34, 1), (13, 1), (8, 1)]  =  1000000
[(46368, 21), (17711, 1), (6765, 1), (1597, 1), (144, 1), (34, 1), (13, 1), (5, 1), (3, 1)]  =  1000000
[(28657, 34), (17711, 1), (6765, 1), (987, 1), (144, 1), (55, 1)]  =  1000000
[(28657, 34), (17711, 1), (6765, 1), (987, 1), (144, 1), (34, 1), (21, 1)]  =  1000000
[(28657, 34), (17711, 1), (6765, 1), (987, 1), (144, 1), (34, 1), (13, 1), (8, 1)]  =  1000000
[(28657, 34), (17711, 1), (6765, 1), (987, 1), (144, 1), (34, 1), (13, 1), (5, 1), (3, 1)]  =  1000000
[(17711, 56), (6765, 1), (987, 1), (377, 1), (55, 1)]  =  1000000
[(17711, 56), (6765, 1), (987, 1), (377, 1), (34, 1), (21, 1)]  =  1000000
[(17711, 56), (6765, 1), (987, 1), (377, 1), (34, 1), (13, 1), (8, 1)]  =  1000000
[(17711, 56), (6765, 1), (987, 1), (377, 1), (34, 1), (13, 1), (5, 1), (3, 1)]  =  1000000
[(10946, 91), (2584, 1), (987, 1), (233, 1), (89, 1), (21, 1)]  =  1000000
[(10946, 91), (2584, 1), (987, 1), (233, 1), (89, 1), (13, 1), (8, 1)]  =  1000000
[(10946, 91), (2584, 1), (987, 1), (233, 1), (89, 1), (13, 1), (5, 1), (3, 1)]  =  1000000
[(6765, 147), (4181, 1), (987, 1), (377, 1)]  =  1000000
[(6765, 147), (4181, 1), (987, 1), (233, 1), (144, 1)]  =  1000000
[(6765, 147), (4181, 1), (987, 1), (233, 1), (89, 1), (55, 1)]  =  1000000
[(6765, 147), (4181, 1), (987, 1), (233, 1), (89, 1), (34, 1), (21, 1)]  =  1000000
[(6765, 147), (4181, 1), (987, 1), (233, 1), (89, 1), (34, 1), (13, 1), (8, 1)]  =  1000000
[(6765, 147), (4181, 1), (987, 1), (233, 1), (89, 1), (34, 1), (13, 1), (5, 1), (3, 1)]  =  1000000
[(4181, 239), (610, 1), (89, 1), (34, 1), (8, 1)]  =  1000000
[(4181, 239), (610, 1), (89, 1), (34, 1), (5, 1), (3, 1)]  =  1000000
[(2584, 386), (1597, 1), (610, 1), (233, 1), (89, 1), (34, 1), (13, 1)]  =  1000000
[(2584, 386), (1597, 1), (610, 1), (233, 1), (89, 1), (34, 1), (8, 1), (5, 1)]  =  1000000
[(2584, 386), (1597, 1), (610, 1), (233, 1), (89, 1), (34, 1), (8, 1), (3, 1), (2, 1)]  =  1000000
[(1597, 626), (233, 1), (34, 1), (8, 1), (3, 1)]  =  1000000
[(610, 1639), (144, 1), (55, 1), (8, 1), (3, 1)]  =  1000000
[(377, 2652), (144, 1), (34, 1), (13, 1), (5, 1)]  =  1000000
[(377, 2652), (144, 1), (34, 1), (13, 1), (3, 1), (2, 1)]  =  1000000
[(55, 18181), (34, 1), (8, 1), (3, 1)]  =  1000000
[(34, 29411), (21, 1), (5, 1)]  =  1000000
[(34, 29411), (21, 1), (3, 1), (2, 1)]  =  1000000
[(8, 125000)]  =  1000000
[(8, 124999), (5, 1), (3, 1)]  =  1000000
[(5, 200000)]  =  1000000
[(5, 199999), (3, 1), (2, 1)]  =  1000000
Number of fibonacci combination is  61

わーいできたー、と思ったら全然違うことに気づいた。

これ1000000になる組み合わせが見つかったときに一番小さい数だけ分解してるけど、
他の数も分解してかないといけないんだ。

最後の

[(5, 200000)] = 1000000
を
[(5, 199999), (3, 1), (2, 1)] = 1000000
にするのなんか、
[(5, 199998), (3, 2), (2, 2)] = 1000000
[(5, 199997), (3, 3), (2, 3)] = 1000000
とえんえん分割していけるじゃない。

こりゃロジック考え直しだー、といったところで眠いので切り上げ。
続きやるかどうかはやる気次第。