feat: memoized fibonnaci

benmtz · benmtz · commit 012a2436ed6c · 2021-09-21T07:46:29.000+02:00
diff --git a/katas/5-memoized-fibonnaci.py b/katas/5-memoized-fibonnaci.py
@@ -0,0 +1,73 @@
+# 529adbf7533b761c560004e5
+#
+# Problem Context
+# The Fibonacci sequence is traditionally used to explain tree recursion.
+#
+# def fibonacci(n):
+#     if n in [0, 1]:
+#         return n
+#     return fibonacci(n - 1) + fibonacci(n - 2)
+#
+# This algorithm serves welll its educative purpose but it's tremendously
+# inefficient, not only because of recursion, but because we invoke the
+# fibonacci function twice, and the right branch of recursion
+# (i.e. fibonacci(n-2)) recalculates all the Fibonacci numbers already
+# calculated by the left branch (i.e. fibonacci(n-1)).
+#
+# This algorithm is so inefficient that the time to calculate any Fibonacci
+# number over 50 is simply too much. You may go for a cup of coffee or go take
+# a nap while you wait for the answer. But if you try it here in Code Wars you
+# will most likely get a code timeout before any answers.
+#
+# For this particular Kata we want to implement the memoization solution. This
+# will be cool because it will let us keep using the tree recursion algorithm
+# while still keeping it sufficiently optimized to get an answer very rapidly.
+#
+# The trick of the memoized version is that we will keep a cache data structure
+# (most likely an associative array) where we will store the Fibonacci numbers
+# as we calculate them. When a Fibonacci number is calculated, we first look it
+# up in the cache, if it's not there, we calculate it and put it in the cache,
+# otherwise we returned the cached number.
+#
+# Refactor the function into a recursive Fibonacci function that using a
+# memoized data structure avoids the deficiencies of tree recursion Can you
+# make it so the memoization cache is private to this function?
+
+from unittest import TestCase
+
+
+# Used this resource
+# https://www.geeksforgeeks.org/memoization-using-decorators-in-python/
+def cache_result(func):
+    mem = {}
+
+    def inner(n):
+        if n not in mem:
+            mem[n] = func(n)
+        return mem[n]
+
+    return inner
+
+# From the solutions this one was cool, since it didn't write it's own
+# memoization decorator
+#
+# from functools import lru_cache
+#
+# @lru_cache(None)
+# def fibonacci(n):
+#     if n in [0, 1]:
+#         return n
+#     return fibonacci(n - 1) + fibonacci(n - 2)
+
+@cache_result
+def fibonacci(n):
+    if n in [0, 1]:
+        return n
+    return fibonacci(n - 1) + fibonacci(n - 2)
+
+
+class Test5MemoizedFibonnaci(TestCase):
+    def test_1(self):
+        self.assertEqual(fibonacci(70), 190392490709135)
+        self.assertEqual(fibonacci(60), 1548008755920)
+        self.assertEqual(fibonacci(50), 12586269025)
