CODEWITHSUNDEEP
pythonpython-3.x
PeanutTest
PeanutTest

Reputation: 1

Python: Codewars, Tribonacci Sequence (Timing Out)

I am trying to solve this kata. I pass all the tests, but at the very end, I time out. It mentions below that my code isn't running efficiently enough, but I don't know how or where to optimize it. I don't need this solved for me, but a nudge in the right direction would be greatly appreciated.

This is what I've come up with so far:

def tribonacci(signature, n):
    for x in range(n):
        for y in range(len(signature)):
            tri  = sum(signature[::-1][0:3])
        signature.append(tri)
    return signature[0:n] if n > 0 else []

Upvotes: 0

Views: 284

Answers (1)

Rodrigo Rodrigues
Rodrigo Rodrigues

Reputation: 8556

@Sash's answer is good and addresses the specific issue in your code.

But I'd like to invite you to explore recursive solutions for this challenge. Fibonacci's sequence is one of the classical examples of the application of recursion.

Moreover, by doing so you might have the opportunity to meet one crucial coding technique: memoization, the basis of the so called dynamic programming.

Let's start with a straightforward recursive implementation of Tribonacci:

def trib(sig, n):
  return sig[n] if n < len(sig) else sum(trib(sig, n-i-1) for i in range(len(sig)))

print([trib([1, 1, 1], n) for n in range(10)])
#> [1, 1, 1, 3, 5, 9, 17, 31, 57, 105]

(This implementation is interesting because it generalizes the length of the signature parameter. In fact, if you do trib([0, 1], n), you will get just the Fibonacci sequence.)

It is all good and works fine, but if you try to enumerate the sequence for successive values of n, you will not be able to even reach n=50 without having to wait several hours to get a result.

for n in range(50):
  print(f"n={n}: {trib(n)}")
  # grab a seat...

This is inefficient because it recurs on previously computed values multiple times, and calculates them again and again.

Python has a decorator to automatically memoize the result of the function when called again with the same arguments, @cache from the functools module.

@cache
def trib(sig, n):
  return sig[n] if n < len(sig) else sum(trib(sig, n-i-1) for i in range(len(sig)))

print(trib((1,1,1), 1000))
# blazing fast!
#> 1943335101817423037603257437918638255032052728012636576169065490082178633662775470389183266653136647509149636552913234635998078993186804699028479634780879223078384506020833416748095549560738200450581610234174332966917848084977685046687323269576208049024348154816217

[Note 1]: I had to change the type of the signature argument from a list [1, 1, 1] to a tuple (1, 1, 1), because @cache does not work with mutable data types.

[Note 2]: If you try higher values of n, you will quickly stumble into the "RecursionError: maximum recursion depth exceeded while calling a Python object", because Python does not have tail call optimization (and will never have).

[Note 3]: Why even bother?? You have a "loopy" solution that works fine and don't have all those additional quirks! Why would anyone get into the recursive madness at all?
Well, with the cached solution, I am able to quickly calculate the element for n=100000 (I had to trick the maximum recursion depth mentioned above).

print(str(tribonacci((1,1,1), 100000))) 
# the result has just 26,465 digits

I tried the same with your iterative implementation and... it froze my PC and after a few minutes, and then it just shut down. Don't try that.

EDIT

To be fair, it is easy to improve your iterative answer so it will not burn out all the computer memory for huge values of n. You can just use a Python's generator, and keep in memory only the last 3 calculated values.

def tribonacci(signature, n):
  yield from signature[:n]
  for x in range(len(signature), n):
    signature = [*signature[1:], sum(signature)]
    yield signature[-1]


# now you must enumerate your sequence explicitly
for t in tribonacci([1,1,1], 100000):
  continue
print(len(str(t))) # 26,465 digits

Upvotes: 1

Related Questions