This notebook was prepared by Donne Martin. Source and license info is on GitHub.

# Solution Notebook¶

## Constraints¶

• If n == 0, what should the result be?
• Go with 1, but discuss different approaches
• Can we assume the inputs are valid?
• No
• Can we assume this fits memory?
• Yes

## Test Cases¶

• None or negative input -> Exception
• n == 0 -> 1
• n == 1 -> 1
• n == 2 -> 2
• n == 3 -> 4
• n == 4 -> 7
• n == 10 -> 274

## Algorithm¶

To get to step n, we will need to have gone:

• One step from n-1
• Two steps from n-2
• Three steps from n-3

If we go the one step route above, we'll be at n-1 before taking the last step. To get to step n-1, we will need to have gone:

• One step from n-1-1
• Two steps from n-1-2
• Three steps from n-1-2

Continue this process until we reach the start.

Base case:

• If n < 0: return 0
• If n == 0: return 1

Note, if we had chosen n == 0 to return 0 instead, we would need to add additional base cases. Otherwise we'd be adding multiple 0's once we hit the base cases and not get any result > 0.

Recursive case:

We'll memoize the solution to improve performance.

• Use the memo if we've already processed the current step.
• Update the memo by adding the recursive calls to step(n-1), step(n-2), step(n-3)

Complexity:

• Time: O(n), if using memoization
• Space: O(n), where n is the recursion depth

Note: The number of ways will quickly overflow the bounds of an integer.

## Code¶

In [1]:
class Steps(object):

def count_ways(self, num_steps):
if num_steps is None or num_steps < 0:
raise TypeError('num_steps cannot be None or negative')
cache = {}
return self._count_ways(num_steps, cache)

def _count_ways(self, num_steps, cache):
if num_steps < 0:
return 0
if num_steps == 0:
return 1
if num_steps in cache:
return cache[num_steps]
cache[num_steps] = (self._count_ways(num_steps-1, cache) +
self._count_ways(num_steps-2, cache) +
self._count_ways(num_steps-3, cache))
return cache[num_steps]


## Unit Test¶

In [2]:
%%writefile test_steps.py
import unittest

class TestSteps(unittest.TestCase):

def test_steps(self):
steps = Steps()
self.assertRaises(TypeError, steps.count_ways, None)
self.assertRaises(TypeError, steps.count_ways, -1)
self.assertEqual(steps.count_ways(0), 1)
self.assertEqual(steps.count_ways(1), 1)
self.assertEqual(steps.count_ways(2), 2)
self.assertEqual(steps.count_ways(3), 4)
self.assertEqual(steps.count_ways(4), 7)
self.assertEqual(steps.count_ways(10), 274)
print('Success: test_steps')

def main():
test = TestSteps()
test.test_steps()

if __name__ == '__main__':
main()

Overwriting test_steps.py

In [3]:
%run -i test_steps.py

Success: test_steps