DP_Practice.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fib"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "832040\n",
      "Wall time: 383 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def fib(n):\n",
    "    if n <= 2: return 1\n",
    "    return fib(n - 1) + fib(n - 2)\n",
    "\n",
    "print(fib(30))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "832040\n",
      "Wall time: 342 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def fib_memo(n, memo = {}):\n",
    "    if n in memo: return memo[n]\n",
    "    if n <= 2: return 1\n",
    "    memo[n] = fib(n - 1) + fib(n - 2)\n",
    "    return memo[n]\n",
    "\n",
    "print(fib_memo(30))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "832040\n",
      "Wall time: 0 ns\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def fib_table(n):\n",
    "    table = [0] * (n + 1)\n",
    "    table[1] = 1\n",
    "    for i in range(1, n):\n",
    "        table[i+1] += table[i]\n",
    "        if i < n -1:\n",
    "            table[i+2] += table[i]\n",
    "    return table[n]\n",
    "\n",
    "print(fib_table(30))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Grid Traveller"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3432\n",
      "Wall time: 4.49 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def grid_traveller(m ,n):\n",
    "    if m == 1 and n == 1:\n",
    "        return 1\n",
    "    if m ==0 or n == 0:\n",
    "        return 0\n",
    "    return grid_traveller(m-1, n) + grid_traveller(m, n-1)\n",
    "\n",
    "print(grid_traveller(8, 8))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3432\n",
      "Wall time: 0 ns\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def grid_traveller_memo(m ,n, memo = {}):\n",
    "    key = f'{m},{n}'\n",
    "    if key in memo: return memo[key]\n",
    "        \n",
    "    if m == 1 and n == 1:\n",
    "        return 1\n",
    "    if m == 0 or n == 0:\n",
    "        return 0\n",
    "    memo[key] = grid_traveller_memo(m-1, n, memo) + grid_traveller_memo(m, n-1, memo)\n",
    "    \n",
    "    return memo[key]\n",
    "\n",
    "print(grid_traveller_memo(8, 8))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "3\n",
      "3\n",
      "6\n",
      "2333606220\n",
      "Wall time: 0 ns\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def grid_travller_table(m, n):\n",
    "    table = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "    table[1][1] = 1\n",
    "    for i in range(0, m + 1):\n",
    "        for j in range(0, n + 1):\n",
    "            current = table[i][j]\n",
    "            if j+1 <= n:\n",
    "                table[i][j + 1] += current\n",
    "            if i+1 <= m:\n",
    "                table[i + 1][j] += current\n",
    "    return table[m][n]\n",
    "            \n",
    "print(grid_travller_table(1,1))\n",
    "print(grid_travller_table(2,3))\n",
    "print(grid_travller_table(3,2))\n",
    "print(grid_travller_table(3,3))\n",
    "print(grid_travller_table(18,18))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Can_Sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "def can_sum(target, number_list):\n",
    "    if target == 0: return True\n",
    "    if target < 0: return False\n",
    "    \n",
    "    for i in number_list:\n",
    "        balance = target - i\n",
    "        if can_sum(balance, number_list):\n",
    "            return True\n",
    "        \n",
    "    return False\n",
    "\n",
    "print(can_sum(300, [7, 14]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "Wall time: 7.87 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def can_sum_memo(target, number_list, memo = {}):\n",
    "    if target in memo: return memo[target]\n",
    "    if target == 0: return True\n",
    "    if target < 0: return False\n",
    "    \n",
    "    for i in number_list:\n",
    "        balance = target - i\n",
    "        if can_sum_memo(balance, number_list, memo):\n",
    "            memo[target] = True\n",
    "            return memo[target]\n",
    "    memo[target] = False\n",
    "    return memo[target]\n",
    "\n",
    "print(can_sum_memo(300, [7, 14]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "False\n",
      "True\n",
      "False\n",
      "Wall time: 0 ns\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def can_sum_table(target, number_list):\n",
    "    table = [False] * (target + 1)\n",
    "    table[0] = True\n",
    "    \n",
    "    for i in range(0, target + 1):\n",
    "        if table[i] == True:\n",
    "            for j in number_list:\n",
    "                index_in_table = i + j\n",
    "                if index_in_table <= target:\n",
    "                    table[index_in_table] = True\n",
    "#             if table[target] == True:\n",
    "#                 break\n",
    "    return table[target]\n",
    "\n",
    "print(can_sum_table(7, [3, 4, 5]))\n",
    "print(can_sum_table(7, [2, 3]))\n",
    "print(can_sum_table(7, [2, 4]))\n",
    "print(can_sum_table(8, [2, 3, 5]))\n",
    "print(can_sum_table(300, [7, 14]))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# how_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 2, 2]\n",
      "[2, 2, 2, 2]\n",
      "None\n",
      "Wall time: 0 ns\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def how_sum(target, number_list):\n",
    "    if target == 0: return []\n",
    "    if target < 0: return None\n",
    "    \n",
    "    for i in number_list:\n",
    "        balance = target - i\n",
    "        result = how_sum(balance, number_list)\n",
    "        if result is not None:\n",
    "            result += [i]\n",
    "            return result\n",
    "    \n",
    "    return None\n",
    "\n",
    "print(how_sum(7, [2, 3]))\n",
    "print(how_sum(8, [2, 3, 5]))\n",
    "print(how_sum(7, [2, 4]))\n",
    "# print(how_sum(300, [7, 14]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n",
      "Wall time: 0 ns\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def how_sum_memo(target, number_list, memo = {}):\n",
    "    if target in memo: return memo[target]\n",
    "    if target == 0: return []\n",
    "    if target < 0: return None\n",
    "    \n",
    "    for i in number_list:\n",
    "        balance = target - i\n",
    "        result = how_sum_memo(balance, number_list, memo)\n",
    "        if result is not None:\n",
    "            memo[target] = result + [i]\n",
    "            return memo[target]\n",
    "        \n",
    "    memo[target] = None\n",
    "    return memo[target]\n",
    "\n",
    "# print(how_sum_memo(7, [2, 3]))\n",
    "# print(how_sum_memo(8, [2, 3, 5]))\n",
    "# print(how_sum_memo(7, [2, 4]))\n",
    "print(how_sum_memo(300, [7, 14]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[4, 3]\n",
      "[3, 2, 2]\n",
      "None\n",
      "[2, 2, 2, 2]\n",
      "None\n",
      "Wall time: 0 ns\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def how_sum_table(target, number_list):\n",
    "    table = [None] * (target + 1)\n",
    "    table[0] = []\n",
    "    \n",
    "    for i in range(0, target):\n",
    "        if table[i] is not None:\n",
    "            for j in number_list:\n",
    "                index_in_table = i + j\n",
    "                if index_in_table <= target:\n",
    "                    table[index_in_table] = table[i] + [j]\n",
    "    return table[target]\n",
    "\n",
    "\n",
    "print(how_sum_table(7, [3, 4, 5]))\n",
    "print(how_sum_table(7, [2, 3]))\n",
    "print(how_sum_table(7, [2, 4]))\n",
    "print(how_sum_table(8, [2, 3, 5]))\n",
    "print(how_sum_table(300, [7, 14]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# best_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[7]\n",
      "[5, 3]\n",
      "None\n",
      "Wall time: 7.97 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def best_sum(target, number_list):\n",
    "    if target == 0: return []\n",
    "    if target < 0: return None\n",
    "    \n",
    "    shortest_combination = None\n",
    "    \n",
    "    for i in number_list:\n",
    "        balance = target - i\n",
    "        result = best_sum(balance, number_list)\n",
    "        if result is not None:\n",
    "            combination = result + [i]\n",
    "            if (shortest_combination is None) or (len(combination) < len(shortest_combination)):\n",
    "                shortest_combination = combination\n",
    "                \n",
    "    return shortest_combination\n",
    "    \n",
    "print(best_sum(7, [2, 3, 7]))\n",
    "print(best_sum(8, [2, 3, 5]))\n",
    "print(best_sum(7, [2, 4]))\n",
    "# print(best_sum(100, [1, 2, 5, 25]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[25, 25, 25, 25]\n",
      "Wall time: 0 ns\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def best_sum_memo(target, number_list, memo = {}):\n",
    "    if target in memo: return memo[target]\n",
    "    if target == 0: return []\n",
    "    if target < 0: return None\n",
    "    \n",
    "    shortest_combination = None\n",
    "    \n",
    "    for i in number_list:\n",
    "        balance = target - i\n",
    "        result = best_sum_memo(balance, number_list, memo)\n",
    "        if result is not None:\n",
    "            combination = result + [i]\n",
    "            if (shortest_combination is None) or (len(combination) < len(shortest_combination)):\n",
    "                shortest_combination = combination\n",
    "    \n",
    "    memo[target] = shortest_combination\n",
    "    return memo[target]\n",
    "    \n",
    "# print(best_sum_memo(7, [2, 3, 7]))\n",
    "# print(best_sum_memo(8, [2, 3, 5]))\n",
    "# print(best_sum_memo(7, [2, 4]))\n",
    "print(best_sum_memo(100, [1, 2, 5, 25]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[3, 4]\n",
      "[2, 2, 3]\n",
      "None\n",
      "[3, 5]\n",
      "[5, 5, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29]\n",
      "Wall time: 8 ms\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def best_sum_table(target, number_list):\n",
    "    table = [None] * (target + 1)\n",
    "    table[0] = []\n",
    "    for i in range(0, target):\n",
    "        if table[i] is not None:\n",
    "            for j in number_list:\n",
    "                index_in_table = i + j\n",
    "                if index_in_table <= target:\n",
    "                    target_combi = table[i] + [j]\n",
    "                    if table[index_in_table] is None or (len(target_combi) < len(table[index_in_table])):\n",
    "                        table[index_in_table] = target_combi\n",
    "    return table[target]  \n",
    "                    \n",
    "print(best_sum_table(7, [3, 4, 5]))\n",
    "print(best_sum_table(7, [2, 3]))\n",
    "print(best_sum_table(7, [2, 4]))\n",
    "print(best_sum_table(8, [2, 3, 5]))\n",
    "print(best_sum_table(300, [8, 5, 29, 28]))    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# can_construct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "True\n",
      "Wall time: 0 ns\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def can_construct(target, word_bank):\n",
    "    if target == '': return True\n",
    "    for i in word_bank:\n",
    "        if i in target and target.index(i) == 0:        \n",
    "            suffix = target[len(i):]\n",
    "            if can_construct(suffix, word_bank):\n",
    "                return True\n",
    "        else:\n",
    "            continue\n",
    "    return False\n",
    "\n",
    "print(can_construct(\"abcdef\", [\"ab\", \"abc\", \"cd\", \"def\", \"abcd\"]))\n",
    "print(can_construct(\"skateboard\", [\"bo\", \"rd\", \"ate\", \"t\", \"ska\", \"sk\", \"boar\"]))\n",
    "print(can_construct(\"enterapotentpot\", [\"a\", \"p\", \"ent\", \"enter\", \"ot\", \"o\", \"t\"]))\n",
    "# print(can_construct(\"eeeeeeeeeeeeeeeeeeeeeeeeef\", [\"e\", \"ee\", \"eee\", \"eeee\", \"eeeee\", \"eeeeee\", \"eeeeeee\"]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "Wall time: 31.6 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def can_construct_memo(target, word_bank, memo = {}):\n",
    "    if target in memo: return memo[target]\n",
    "    if target == '': return True\n",
    "    for i in word_bank:\n",
    "        if i in target and target.index(i) == 0:        \n",
    "            suffix = target[len(i):]\n",
    "            if can_construct_memo(suffix, word_bank, memo):\n",
    "                memo[target] = True\n",
    "                return memo[target]\n",
    "            \n",
    "        else:\n",
    "            continue\n",
    "    memo[target] = False\n",
    "    return memo[target]\n",
    "\n",
    "# print(can_construct(\"abcdef\", [\"ab\", \"abc\", \"cd\", \"def\", \"abcd\"]))\n",
    "# print(can_construct(\"skateboard\", [\"bo\", \"rd\", \"ate\", \"t\", \"ska\", \"sk\", \"boar\"]))\n",
    "# print(can_construct(\"enterapotentpot\", [\"a\", \"p\", \"ent\", \"enter\", \"ot\", \"o\", \"t\"]))\n",
    "print(can_construct(\"eeeeeeeeeeeeeeeeeeeeeeeeef\", [\"e\", \"ee\", \"eee\", \"eeee\", \"eeeee\", \"eeeeee\", \"eeeeeee\"]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "False\n",
      "True\n",
      "False\n",
      "Wall time: 0 ns\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def can_construct_table(target, word_bank):\n",
    "    table = [False] * (len(target) + 1)\n",
    "    table[0] = True\n",
    "    \n",
    "    for i in range(0, len(target)):\n",
    "        if table[i] == True:\n",
    "            for j in word_bank:\n",
    "                if target[i: i+len(j)] == j:\n",
    "                    table[i+len(j)] = True\n",
    "                    \n",
    "    return table[len(target)]\n",
    "\n",
    "print(can_construct_table(\"abcdef\", [\"ab\", \"abc\", \"cd\", \"def\", \"abcd\"]))\n",
    "print(can_construct_table(\"skateboard\", [\"bo\", \"rd\", \"ate\", \"t\", \"ska\", \"sk\", \"boar\"]))\n",
    "print(can_construct_table(\"enterapotentpot\", [\"a\", \"p\", \"ent\", \"enter\", \"ot\", \"o\", \"t\"]))\n",
    "print(can_construct_table(\"eeeeeeeeeeeeeeeeeeeeeeeeef\", [\"e\", \"ee\", \"eee\", \"eeee\", \"eeeee\", \"eeeeee\", \"eeeeeee\"]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# count construct"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "0\n",
      "4\n",
      "0\n",
      "Wall time: 33.9 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def count_construct(target, word_bank):\n",
    "    if target == '': return 1\n",
    "    \n",
    "    total_count = 0\n",
    "    for i in word_bank:\n",
    "        if i in target and target.index(i) == 0:  \n",
    "            suffix = target[len(i):]\n",
    "            suffix_ways = count_construct(suffix, word_bank)\n",
    "            total_count += suffix_ways\n",
    "    \n",
    "    return total_count\n",
    "\n",
    "print(count_construct(\"abcdef\", [\"ab\", \"abc\", \"cd\", \"def\", \"abcd\"]))\n",
    "print(count_construct(\"skateboard\", [\"bo\", \"rd\", \"ate\", \"t\", \"ska\", \"sk\", \"boar\"]))\n",
    "print(count_construct(\"enterapotentpot\", [\"a\", \"p\", \"ent\", \"enter\", \"ot\", \"o\", \"t\"]))\n",
    "print(count_construct(\"eeeeeeeeeeeeeeeeeeeeeeeeef\", [\"e\", \"ee\", \"eee\", \"eeee\", \"eeeee\", \"eeeeee\", \"eeeeeee\"]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "Wall time: 32.9 s\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def count_construct_memo(target, word_bank, memo = {}):\n",
    "    if target in memo: return memo[target]\n",
    "    if target == '': return 1\n",
    "    \n",
    "    total_count = 0\n",
    "    for i in word_bank:\n",
    "        if i in target and target.index(i) == 0:  \n",
    "            suffix = target[len(i):]\n",
    "            suffix_ways = count_construct_memo(suffix, word_bank, memo)\n",
    "            total_count += suffix_ways\n",
    "            memo[target] = total_count\n",
    "            \n",
    "    memo[target] = total_count\n",
    "    return memo[target]\n",
    "\n",
    "# print(count_construct(\"abcdef\", [\"ab\", \"abc\", \"cd\", \"def\", \"abcd\"]))\n",
    "# print(count_construct(\"skateboard\", [\"bo\", \"rd\", \"ate\", \"t\", \"ska\", \"sk\", \"boar\"]))\n",
    "# print(count_construct(\"enterapotentpot\", [\"a\", \"p\", \"ent\", \"enter\", \"ot\", \"o\", \"t\"]))\n",
    "print(count_construct(\"eeeeeeeeeeeeeeeeeeeeeeeeef\", [\"e\", \"ee\", \"eee\", \"eeee\", \"eeeee\", \"eeeeee\", \"eeeeeee\"]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "1\n",
      "0\n",
      "4\n",
      "0\n",
      "Wall time: 0 ns\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def count_construct_table(target, word_bank):\n",
    "    table = [0] * (len(target) + 1)\n",
    "    table[0] = 1\n",
    "    \n",
    "    for i in range(0, len(target)):\n",
    "        for j in word_bank:\n",
    "            if target[i: i + len(j)] == j:\n",
    "                table[i + len(j)] += table[i]\n",
    "    \n",
    "    return table[len(target)]\n",
    "                \n",
    "print(count_construct_table(\"purple\", [\"purp\", \"p\", \"ur\", \"le\", \"purpl\"]))\n",
    "print(count_construct_table(\"abcdef\", [\"ab\", \"abc\", \"cd\", \"def\", \"abcd\"]))\n",
    "print(count_construct_table(\"skateboard\", [\"bo\", \"rd\", \"ate\", \"t\", \"ska\", \"sk\", \"boar\"]))\n",
    "print(count_construct_table(\"enterapotentpot\", [\"a\", \"p\", \"ent\", \"enter\", \"ot\", \"o\", \"t\"]))\n",
    "print(count_construct_table(\"eeeeeeeeeeeeeeeeeeeeeeeeef\", [\"e\", \"ee\", \"eee\", \"eeee\", \"eeeee\", \"eeeeee\", \"eeeeeee\"]))   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# All_constructs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['le', 'purp'], ['le', 'p', 'ur', 'p']]\n",
      "[['ef', 'cd', 'ab'], ['def', 'c', 'ab'], ['def', 'abc'], ['ef', 'abcd']]\n",
      "[]\n",
      "Wall time: 0 ns\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def all_constructs(target, word_bank):\n",
    "    if target == '': return [[]]\n",
    "    \n",
    "    result = []\n",
    "    \n",
    "    for i in word_bank:\n",
    "        if i in target and target.index(i) == 0:\n",
    "            suffix = target[len(i):]\n",
    "            suffix_ways = all_constructs(suffix, word_bank)\n",
    "            target_ways = [j + [i] for j in suffix_ways]\n",
    "            result.extend(target_ways)\n",
    "    \n",
    "    return result\n",
    "\n",
    "\n",
    "print(all_constructs(\"purple\", [\"purp\", \"p\", \"ur\", \"le\", \"purpl\"]))\n",
    "print(all_constructs(\"abcdef\", [\"ab\", \"abc\", \"cd\", \"def\", \"abcd\", 'ef', 'c']))\n",
    "print(all_constructs(\"aaaaaz\", [\"a\", \"aa\", \"aaa\", \"aaaa\", \"aaaaa\"]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['le', 'purp'], ['le', 'p', 'ur', 'p']]\n",
      "[['ef', 'cd', 'ab'], ['def', 'c', 'ab'], ['def', 'abc'], ['ef', 'abcd']]\n",
      "[]\n",
      "Wall time: 0 ns\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def all_constructs_memo(target, word_bank, memo = {}):\n",
    "    if target in memo: return memo[target]\n",
    "    if target == '': return [[]]\n",
    "    \n",
    "    result = []\n",
    "    \n",
    "    for i in word_bank:\n",
    "        if i in target and target.index(i) == 0:\n",
    "            suffix = target[len(i):]\n",
    "            suffix_ways = all_constructs_memo(suffix, word_bank, memo)\n",
    "            target_ways = [j + [i] for j in suffix_ways]\n",
    "            result.extend(target_ways)\n",
    "    \n",
    "    memo[target] = result\n",
    "    return result\n",
    "\n",
    "\n",
    "print(all_constructs_memo(\"purple\", [\"purp\", \"p\", \"ur\", \"le\", \"purpl\"]))\n",
    "print(all_constructs_memo(\"abcdef\", [\"ab\", \"abc\", \"cd\", \"def\", \"abcd\", 'ef', 'c']))\n",
    "print(all_constructs_memo(\"aaaaaz\", [\"a\", \"aa\", \"aaa\", \"aaaa\", \"aaaaa\"]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[['purp', 'le'], ['p', 'ur', 'p', 'le']]\n",
      "[['abc', 'def']]\n",
      "[]\n",
      "[['enter', 'a', 'p', 'ot', 'ent', 'p', 'ot'], ['enter', 'a', 'p', 'o', 't', 'ent', 'p', 'ot'], ['enter', 'a', 'p', 'ot', 'ent', 'p', 'o', 't'], ['enter', 'a', 'p', 'o', 't', 'ent', 'p', 'o', 't']]\n",
      "[]\n",
      "Wall time: 0 ns\n"
     ]
    }
   ],
   "source": [
    "%%time\n",
    "def all_construct_table(target, word_bank):\n",
    "    table = [[] for _ in range(0, len(target) + 1)]\n",
    "    table[0] = [[]]\n",
    "    \n",
    "    for i in range(0, len(target)):\n",
    "        for j in word_bank:\n",
    "            if target[i: i + len(j)] == j:\n",
    "                new_combi = [k + [j] for k in table[i]]\n",
    "                table[i + len(j)].extend(new_combi)\n",
    "    \n",
    "    return table[len(target)]\n",
    "\n",
    "print(all_construct_table(\"purple\", [\"purp\", \"p\", \"ur\", \"le\", \"purpl\"]))\n",
    "print(all_construct_table(\"abcdef\", [\"ab\", \"abc\", \"cd\", \"def\", \"abcd\"]))\n",
    "print(all_construct_table(\"skateboard\", [\"bo\", \"rd\", \"ate\", \"t\", \"ska\", \"sk\", \"boar\"]))\n",
    "print(all_construct_table(\"enterapotentpot\", [\"a\", \"p\", \"ent\", \"enter\", \"ot\", \"o\", \"t\"]))\n",
    "print(all_construct_table(\"eeeeeeef\", [\"e\", \"ee\", \"eee\", \"eeee\", \"eeeee\", \"eeeeee\"])) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}