Fibonacci Experiments...

fibonacci.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import unittest


def naive_fibonacci(n):
    '''Simplest recursive implementation'''
    if n == 0:
        return 0
    elif n <= 2:
        return 1

    return naive_fibonacci(n-1) + naive_fibonacci(n-2)


def create_fibonacci_with_cache():
    '''Closure for creating a fibonacci instance with its own cache'''
    cache = {}

    def cached_fibonacci(n):
        if n == 0:
            return 0
        elif n <= 2:
            return 1
        else:
            if n not in cache:
                cache[n] = cached_fibonacci(n-1) + cached_fibonacci(n-2)
            return cache[n]
    return cached_fibonacci


def iteractive_fibonacci(n):
    '''Non-recursive implementation for fibonnacci'''
    if n == 0:
        return 0
    elif n <= 2:
        return 1
    else:
        current = previous = 1
        for i in range(2, n):
            previous, current = current, current + previous
        return current


def cacheator(fib):
    '''Decorator that includes a cache in a fibonacci function'''
    cache = {}
    def wrapper(*args):
        if args[0] not in cache:
            cache[args[0]] = fib(*args)
        return cache[args[0]]
    return wrapper


@cacheator
def non_naive_fibonacci(n):
    if n == 0:
        return 0
    elif n <= 2:
        return 1
    else:
        return non_naive_fibonacci(n-1) + non_naive_fibonacci(n-2)


class TestFibonaccis(unittest.TestCase):

    def test_naive_fibonacci_for_simple_inputs(self):
        self.assertEqual(naive_fibonacci(0), 0)
        self.assertEqual(naive_fibonacci(1), 1)

    def test_naive_fibonacci_for_arbitrary_inputs(self):
        self.assertEqual(naive_fibonacci(2), 1)
        self.assertEqual(naive_fibonacci(12), 144)
        self.assertEqual(naive_fibonacci(11), 89)

    def test_fibonacci_with_cache_for_simple_inputs(self):
        cachefib = create_fibonacci_with_cache()
        self.assertEqual(cachefib(0), 0)
        self.assertEqual(cachefib(1), 1)

    def test_fibonacci_with_cache_for_arbitrary_inputs(self):
        cachefib = create_fibonacci_with_cache()
        self.assertEqual(cachefib(2), 1)
        self.assertEqual(cachefib(16), 987)
        self.assertEqual(cachefib(15), 610)

    def test_the_existence_of_a_cache_for_every_instance(self):
        fib1 = create_fibonacci_with_cache()
        fib2 = create_fibonacci_with_cache()

        self.assertEqual(fib1(15), 610)
        self.assertEqual(fib2(16), 987)

        self.assertTrue(16 in fib2.__closure__[0].cell_contents)
        self.assertFalse(16 in fib1.__closure__[0].cell_contents)

    def test_iteractive_fibonacci_for_simple_inputs(self):
        self.assertEqual(iteractive_fibonacci(2), 1)
        self.assertEqual(iteractive_fibonacci(0), 0)
        self.assertEqual(iteractive_fibonacci(1), 1)

    def test_iteractive_fibonacci_for_arbitrary_inputs(self):
        self.assertEqual(iteractive_fibonacci(2), 1)
        self.assertEqual(iteractive_fibonacci(12), 144)
        self.assertEqual(iteractive_fibonacci(11), 89)
        self.assertEqual(iteractive_fibonacci(15), 610)
        self.assertEqual(iteractive_fibonacci(16), 987)

    def test_non_naive_fibonacci_for_simple_inputs(self):
        self.assertEqual(non_naive_fibonacci(0), 0)
        self.assertEqual(non_naive_fibonacci(1), 1)

    def test_non_naive_fibonacci_for_arbitrary_inputs(self):
        self.assertEqual(non_naive_fibonacci(2), 1)
        self.assertEqual(non_naive_fibonacci(12), 144)
        self.assertEqual(non_naive_fibonacci(11), 89)
        self.assertEqual(non_naive_fibonacci(15), 610)
        self.assertEqual(non_naive_fibonacci(16), 987)

    def test_the_existence_of_a_cache_in_non_naive_fibonacci(self):
        self.assertEqual(non_naive_fibonacci(16), 987)

        self.assertTrue(16 in non_naive_fibonacci.__closure__[0].cell_contents)
        self.assertFalse(17 in non_naive_fibonacci.__closure__[0].cell_contents)


if __name__ == '__main__':
    unittest.main()