fibonacci.py

"""Coding challenge cample with tests."""

import unittest

# the naive recursive solution is solution is branching 2 ^ n
# we can make it O(n) with memoizing the sub problems.


memo = {}


def solution(n):
    """Return the nth fibonacci number.

    Ex:  1, 1, 2, 3, 5, 8, 13, 21
    """
    if n in memo:
        return memo[n]
    if n == 1 or n == 2:
        return 1

    memo[n] = solution(n - 1) + solution(n - 2)
    return memo[n]


class Tests(unittest.TestCase):
    """Test runner to prove solution works."""

    def test_base(self):
        """Unit tests."""
        # ignoring the case for n <= 0
        self.assertEqual(solution(1), 1)
        self.assertEqual(solution(2), 1)
        self.assertEqual(solution(3), 2)
        self.assertEqual(solution(4), 3)
        self.assertEqual(solution(5), 5)
        self.assertEqual(solution(6), 8)
        self.assertEqual(solution(7), 13)
        self.assertEqual(solution(8), 21)
        self.assertEqual(solution(9), 34)
        self.assertEqual(solution(10), 55)

    def test_normal(self):
        """Unit tests."""
        # Sorry for lack of pep8.  These numebrs are BIG
        self.assertEqual(solution(100), 354224848179261915075L)
        self.assertEqual(solution(200), 280571172992510140037611932413038677189525L)
        self.assertEqual(solution(300), 222232244629420445529739893461909967206666939096499764990979600L)
        self.assertEqual(solution(400), 176023680645013966468226945392411250770384383304492191886725992896575345044216019675L)
        self.assertEqual(solution(500), 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125L)
        self.assertEqual(solution(600), 110433070572952242346432246767718285942590237357555606380008891875277701705731473925618404421867819924194229142447517901959200L)
        self.assertEqual(solution(700), 87470814955752846203978413017571327342367240967697381074230432592527501911290377655628227150878427331693193369109193672330777527943718169105124275L)
        self.assertEqual(solution(800), 69283081864224717136290077681328518273399124385204820718966040597691435587278383112277161967532530675374170857404743017623467220361778016172106855838975759985190398725L)
        self.assertEqual(solution(900), 54877108839480000051413673948383714443800519309123592724494953427039811201064341234954387521525390615504949092187441218246679104731442473022013980160407007017175697317900483275246652938800L)
        self.assertEqual(solution(1000), 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875L)

        # maximum recursion depth ase.
        self.assertEqual(solution(1972), 5944859168336277078007115399868864968580762691988401357723206114189888898438348078028049347155886140696930187046851587414978304493731374563935702884082757553313865840006252792255845413550507062768712428686569940848011212983022741812742533029325218234779494850728840444439782903600270844780351217279478882156618724299121836048233833626362220971160150558042677009807598738040832563812847336707169805826878801779939L)

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