zeck_mvallebr.py

# for any natural number return the ZECK - 
# Given N - return non consecutive list of fibonacci numbers that sum up to N



# 0 1 1 2 3 5 8 13 21 34 55 89
# 10 -> [8 2]
# 62 -> [2, 5, 55], 
# 31 -> [21, 8, 2]
# 30 -> [21, 8, 1]
# 32 -> [21, 8, 3]
# 33 -> [21, 8, 3, 1]

def fib(top_limit):
    yield 0
    if top_limit > 0:
        before_last = 0
        i = 1
        last = i
        while i <= top_limit:
            yield i
            i = last + before_last
            before_last = last
            last = i


def zeck(n):
    fs = list(fib(n))
    result = []
    target = n    
    i = len(fs) - 1
    while i >= 0:
        # print(f" {i} {fs[i]} {target}")
        if fs[i] <= target:
            result.append(fs[i])
            target -= fs[i]
            i -= 1
        if target == 0:
            return result
        i -= 1

    assert False, "this line should be unreachable"


# print(list(fib(31)))
assert list(fib(31)) == [0, 1, 1, 2, 3, 5, 8, 13, 21]
assert list(fib(0)) == [0]
assert list(fib(1)) == [0,1,1]
assert list(fib(2)) == [0,1,1,2]
assert list(fib(4)) == [0,1,1,2,3]
assert list(fib(1000)) == [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]


assert list(zeck(31)) == [21, 8, 2]
# print(f"{list(zeck(55))}")
assert list(zeck(55)) == [55]
assert list(zeck(59)) == [55, 3, 1]
assert list(zeck(1)) == [1]
assert list(zeck(0)) == [0]
assert list(zeck(2)) == [2]