mirror of
https://github.com/donnemartin/interactive-coding-challenges.git
synced 2024-03-22 13:11:13 +08:00
223 lines
5.7 KiB
Python
223 lines
5.7 KiB
Python
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"This notebook was prepared by [Donne Martin](https://github.com/donnemartin). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges)."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"# Solution Notebook"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Problem: You are running up n steps. If you can take a single, double, or triple step, how many possible ways are there to run up to the nth step?\n",
|
|
"\n",
|
|
"* [Constraints](#Constraints)\n",
|
|
"* [Test Cases](#Test-Cases)\n",
|
|
"* [Algorithm](#Algorithm)\n",
|
|
"* [Code](#Code)\n",
|
|
"* [Unit Test](#Unit-Test)"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Constraints\n",
|
|
"\n",
|
|
"* If n == 0, what should the result be?\n",
|
|
" * Go with 1, but discuss different approaches\n",
|
|
"* Can we assume the inputs are valid?\n",
|
|
" * No\n",
|
|
"* Can we assume this fits memory?\n",
|
|
" * Yes"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Test Cases\n",
|
|
"\n",
|
|
"* None or negative input -> Exception\n",
|
|
"* n == 0 -> 1\n",
|
|
"* n == 1 -> 1\n",
|
|
"* n == 2 -> 2\n",
|
|
"* n == 3 -> 4\n",
|
|
"* n == 4 -> 7\n",
|
|
"* n == 10 -> 274"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Algorithm\n",
|
|
"\n",
|
|
"To get to step n, we will need to have gone:\n",
|
|
"\n",
|
|
"* One step from n-1\n",
|
|
"* Two steps from n-2\n",
|
|
"* Three steps from n-3\n",
|
|
"\n",
|
|
"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:\n",
|
|
"\n",
|
|
"* One step from n-1-1\n",
|
|
"* Two steps from n-1-2\n",
|
|
"* Three steps from n-1-2\n",
|
|
"\n",
|
|
"Continue this process until we reach the start.\n",
|
|
"\n",
|
|
"Base case:\n",
|
|
"\n",
|
|
"* If n < 0: return 0\n",
|
|
"* If n == 0: return 1\n",
|
|
"\n",
|
|
"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.\n",
|
|
"\n",
|
|
"Recursive case:\n",
|
|
"\n",
|
|
"We'll memoize the solution to improve performance.\n",
|
|
"\n",
|
|
"* Use the memo if we've already processed the current step.\n",
|
|
"* Update the memo by adding the recursive calls to step(n-1), step(n-2), step(n-3)\n",
|
|
"\n",
|
|
"Complexity:\n",
|
|
"* Time: O(n), if using memoization\n",
|
|
"* Space: O(n), where n is the recursion depth\n",
|
|
"\n",
|
|
"Note: The number of ways will quickly overflow the bounds of an integer."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Code"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 1,
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"class Steps(object):\n",
|
|
"\n",
|
|
" def count_ways(self, num_steps):\n",
|
|
" if num_steps is None or num_steps < 0:\n",
|
|
" raise TypeError('num_steps cannot be None or negative')\n",
|
|
" cache = {}\n",
|
|
" return self._count_ways(num_steps, cache)\n",
|
|
"\n",
|
|
" def _count_ways(self, num_steps, cache):\n",
|
|
" if num_steps < 0:\n",
|
|
" return 0\n",
|
|
" if num_steps == 0:\n",
|
|
" return 1\n",
|
|
" if num_steps in cache:\n",
|
|
" return cache[num_steps]\n",
|
|
" cache[num_steps] = (self._count_ways(num_steps-1, cache) +\n",
|
|
" self._count_ways(num_steps-2, cache) +\n",
|
|
" self._count_ways(num_steps-3, cache))\n",
|
|
" return cache[num_steps]"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"metadata": {},
|
|
"source": [
|
|
"## Unit Test"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 2,
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"name": "stdout",
|
|
"output_type": "stream",
|
|
"text": [
|
|
"Overwriting test_steps.py\n"
|
|
]
|
|
}
|
|
],
|
|
"source": [
|
|
"%%writefile test_steps.py\n",
|
|
"import unittest\n",
|
|
"\n",
|
|
"\n",
|
|
"class TestSteps(unittest.TestCase):\n",
|
|
"\n",
|
|
" def test_steps(self):\n",
|
|
" steps = Steps()\n",
|
|
" self.assertRaises(TypeError, steps.count_ways, None)\n",
|
|
" self.assertRaises(TypeError, steps.count_ways, -1)\n",
|
|
" self.assertEqual(steps.count_ways(0), 1)\n",
|
|
" self.assertEqual(steps.count_ways(1), 1)\n",
|
|
" self.assertEqual(steps.count_ways(2), 2)\n",
|
|
" self.assertEqual(steps.count_ways(3), 4)\n",
|
|
" self.assertEqual(steps.count_ways(4), 7)\n",
|
|
" self.assertEqual(steps.count_ways(10), 274)\n",
|
|
" print('Success: test_steps')\n",
|
|
"\n",
|
|
"\n",
|
|
"def main():\n",
|
|
" test = TestSteps()\n",
|
|
" test.test_steps()\n",
|
|
"\n",
|
|
"\n",
|
|
"if __name__ == '__main__':\n",
|
|
" main()"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": 3,
|
|
"metadata": {},
|
|
"outputs": [
|
|
{
|
|
"name": "stdout",
|
|
"output_type": "stream",
|
|
"text": [
|
|
"Success: test_steps\n"
|
|
]
|
|
}
|
|
],
|
|
"source": [
|
|
"%run -i test_steps.py"
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"kernelspec": {
|
|
"display_name": "Python 3",
|
|
"language": "python",
|
|
"name": "python3"
|
|
},
|
|
"language_info": {
|
|
"codemirror_mode": {
|
|
"name": "ipython",
|
|
"version": 3
|
|
},
|
|
"file_extension": ".py",
|
|
"mimetype": "text/x-python",
|
|
"name": "python",
|
|
"nbconvert_exporter": "python",
|
|
"pygments_lexer": "ipython3",
|
|
"version": "3.7.2"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 1
|
|
}
|