Home
About
Resume
Projects
Links
Blog
Download notebook
{ "cells": [ { "cell_type": "markdown", "id": "ceb90590-0c76-443d-bad7-a9cbbf6800a6", "metadata": {}, "source": [ "### Q15\n", "How many such routes are there through a \\(20 \\times 20\\) grid?" ] }, { "cell_type": "code", "execution_count": 1, "id": "cd671323-0a34-4916-ba97-0d4f3e6990f9", "metadata": {}, "outputs": [], "source": [ "def num_routes_of_m_n_grid(m,n):\n", " if n > m:\n", " m, n = n, m\n", " routes_of_edge = [[0 for j in range(n+1)] for i in range(m+1)]\n", " for i in range(m+1):\n", " routes_of_edge[i][0] = 1\n", " for j in range(n+1):\n", " routes_of_edge[0][j] = 1 \n", " for i in range(1,m+1):\n", " for j in range(1,min([i+1,n+1])):\n", " routes_of_edge[i][j] = routes_of_edge[i-1][j] + routes_of_edge[i][j-1]\n", " if i <= n:\n", " routes_of_edge[j][i] = routes_of_edge[i][j]\n", " return routes_of_edge[m][n]" ] }, { "cell_type": "code", "execution_count": 2, "id": "58ebb691-fd2f-43cf-b4c5-b04c71649a4c", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 48 µs, sys: 0 µs, total: 48 µs\n", "Wall time: 49.1 µs\n" ] }, { "data": { "text/plain": [ "137846528820" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%time\n", "num_routes_of_m_n_grid(20,20)" ] }, { "cell_type": "code", "execution_count": 3, "id": "69e94a95-4e1e-44e8-9bcb-6c72c0d48636", "metadata": {}, "outputs": [], "source": [ "def factorial(n):\n", " return n*factorial(n-1) if n > 1 else 1\n", "\n", "def nCr(n,r):\n", " return factorial(n)//factorial(n-r)//factorial(r)" ] }, { "cell_type": "code", "execution_count": 4, "id": "76c88946-14bd-4a20-8de6-0f6ab69b96a0", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 13 µs, sys: 0 ns, total: 13 µs\n", "Wall time: 13.6 µs\n" ] }, { "data": { "text/plain": [ "137846528820" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "%%time\n", "nCr(40,20)" ] }, { "cell_type": "code", "execution_count": null, "id": "83aed11b-72a6-4f86-a4f4-536647079846", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.8.10" } }, "nbformat": 4, "nbformat_minor": 5 }
Previous Notebook:
Project Euler Q14
Next Notebook:
Project Euler Q16
Loading