{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given two strings:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = 'ABCBDAB'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "B = 'BDCABA'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "find the longest common subsequence between A and B.\n",
    "\n",
    "There are two:\n",
    "\n",
    "1. B, C, B, A\n",
    "\n",
    "2. B, D, A, B\n",
    "\n",
    "Returning either (or both) is fine.\n",
    "\n",
    "I believe this example comes from a uOttawa course on algorithms (CSI 3105). It illustrates the problem and highlights the fact that subsequences need not be contiguous, but A and B are a meaningless scramble of letters. Here's a friendlier example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "occidental = \"occidental\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "superdelicately = \"superdelicately\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The longest common subsequence of these two words is an English word, can you find it?\n",
    "\n",
    "It's \"deal\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The length of the longest common subsequence\n",
    "\n",
    "The [longest common subsequence problem](https://en.wikipedia.org/wiki/Longest_common_subsequence_problem) can be solved with dynamic programming."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import lru_cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "@lru_cache(maxsize=None)\n",
    "def lcs(A, B):\n",
    "    # Base case A and/or B is empty\n",
    "    if len(A) == 0 or len(B) == 0:\n",
    "        return 0\n",
    "    \n",
    "    last_letter_A = A[-1]\n",
    "    last_letter_B = B[-1]\n",
    "    if last_letter_A == last_letter_B:\n",
    "        # Recursive case 1: the last letter of A matches the last letter of B\n",
    "        return 1 + lcs(A[:-1], B[:-1])\n",
    "    else:\n",
    "        # Recursive case 2: the last letter of A does not match the last letter of B\n",
    "        return max( [lcs(A[:-1], B), lcs(A, B[:-1])] )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lcs(A, B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Which is true, both \"B, C, B, A\" and \"B, D, A, B\" are four characters long."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lcs(occidental, superdelicately)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Yep, \"deal\" is four characters as well."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The longest common subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Alternate version that returns a longest common subsequence as a string:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "@lru_cache(maxsize=None)\n",
    "def lcs2(A, B):\n",
    "    # Base case A and/or B is empty\n",
    "    if len(A) == 0 or len(B) == 0:\n",
    "        return ''\n",
    "    \n",
    "    last_letter_A = A[-1]\n",
    "    last_letter_B = B[-1]\n",
    "    if last_letter_A == last_letter_B:\n",
    "        # Recursive case 1: the last letter of A matches the last letter of B\n",
    "        return lcs2(A[:-1], B[:-1]) + last_letter_A\n",
    "    else:\n",
    "        # Recursive case 2: the last letter of A does not match the last letter of B\n",
    "        option1 = lcs2(A[:-1], B)\n",
    "        option2 = lcs2(A, B[:-1])\n",
    "        if len(option1) > len(option2):\n",
    "            return option1\n",
    "        else:\n",
    "            return option2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'BDAB'"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lcs2(A, B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This particular implementation happened to find the second possible longest common subsequence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'deal'"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lcs2(occidental, superdelicately)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This was somewhat tricky. You can't just drop a print statement somewhere because a single call has no idea whether it will actually make it into the final answer. The algorithm explores a DAG of possibilities (a binary tree?), if you're in the middle of a branch there is no telling whether that branch will become the path to the answer or ultimately culled in favour of another branch that yields a longer subsequence."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Iterative, \"bottom-up\" version"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some people say that algorithms using memoization are not [\"truly dynamic programming\"](http://interactivepython.org/courselib/static/pythonds/Recursion/DynamicProgramming.html?fbclid=IwAR2C-ahvj8LHzESa3wSsewvdiUuC0rz0zpUH0SPqPCYj1c3sRmvUFKP48qo) and demand a \"bottom-up\" approach. \n",
    "\n",
    "In the bottom-up approach the lookup table is constructed manually. Starting from nothing, simple cases are solved and then those results are used to solve progressively more difficult cases. I find this approach less elegant then the top-down memoized approach. However, the bottom-up solution does have one major advantage over the top-down solution for Python: since it has no recursive calls, it will never reach the maximum recursion depth."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lcs3(A, B):\n",
    "    # Create a lookup table. This is a 2D array with the letters of A as columns\n",
    "    # and the letters of B as rows. It includes a buffer row and column filled with zeroes.\n",
    "    columns = len(A) + 1\n",
    "    rows = len(B) + 1\n",
    "    lookup = [[0 for n in range(columns)] for n in range(rows)]\n",
    "    \n",
    "    # Since the lookup table is initialized with 0's, \n",
    "    # the base case (len(A) == 0 or len(B) == 0) is \"baked-in\".\n",
    "    \n",
    "    # What's left is to go row by row, column by column and \n",
    "    # apply the iterative version of the recursive cases in lcs().\n",
    "    for row_id in range(1, rows):\n",
    "        for column_id in range(1, columns):\n",
    "            letter_in_A = A[column_id-1]\n",
    "            letter_in_B = B[row_id-1]\n",
    "            if letter_in_A == letter_in_B:\n",
    "                # Equivalent to \"Recursive case 1\"\n",
    "                lookup[row_id][column_id] = 1 + lookup[row_id - 1][column_id - 1]\n",
    "            else:\n",
    "                # Equivalent to \"Recursive case 2\"\n",
    "                option1 = lookup[row_id][column_id-1]\n",
    "                option2 = lookup[row_id-1][column_id]\n",
    "                if option1 > option2:\n",
    "                    lookup[row_id][column_id] = option1\n",
    "                else:\n",
    "                    lookup[row_id][column_id] = option2\n",
    "    \n",
    "    \n",
    "    [print(r) for r in lookup]\n",
    "    \n",
    "    return lookup[rows-1][columns-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 0, 0, 0, 0, 0, 0]\n",
      "[0, 0, 1, 1, 1, 1, 1, 1]\n",
      "[0, 0, 1, 1, 1, 2, 2, 2]\n",
      "[0, 0, 1, 2, 2, 2, 2, 2]\n",
      "[0, 1, 1, 2, 2, 2, 3, 3]\n",
      "[0, 1, 2, 2, 3, 3, 3, 4]\n",
      "[0, 1, 2, 2, 3, 3, 4, 4]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lcs3(A, B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\n",
      "[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]\n",
      "[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]\n",
      "[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1]\n",
      "[0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 2]\n",
      "[0, 0, 0, 0, 0, 1, 2, 2, 2, 2, 3]\n",
      "[0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 3]\n",
      "[0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3]\n",
      "[0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3]\n",
      "[0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3]\n",
      "[0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3]\n",
      "[0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4]\n",
      "[0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lcs3(occidental, superdelicately)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Iterative version that returns the subsequence:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pretty_print(arr):\n",
    "    '''A hacky function that makes every string in an array equal length, then prints\n",
    "    it row by row.'''\n",
    "    longest_length = len(arr[:-1][:-1])\n",
    "    nicer = []\n",
    "    for i, row in enumerate(arr):\n",
    "        new_row = []\n",
    "        for j, cell in enumerate(row):\n",
    "            cell_length = len(cell)\n",
    "            padding_needed = longest_length - cell_length\n",
    "            new_cell = cell + (' ' * padding_needed)\n",
    "            new_row.append(new_cell)\n",
    "        nicer.append(new_row)\n",
    "    \n",
    "    [print(r) for r in nicer]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def lcs4(A, B, print_table=False):\n",
    "    # Create a lookup table. This is a 2D array with the letters of A as columns\n",
    "    # and the letters of B as rows. It includes a buffer row and column filled with empty strings.\n",
    "    columns = len(A) + 1\n",
    "    rows = len(B) + 1\n",
    "    lookup = [['' for n in range(columns)] for n in range(rows)]\n",
    "    \n",
    "    # Since the lookup table is initialized with '' \n",
    "    # the base case (len(A) == 0 or len(B) == 0) is \"baked-in\".\n",
    "    \n",
    "    # What's left is to go row by row, column by column and \n",
    "    # apply the iterative version of the recursive cases in lcs().\n",
    "    for row_id in range(1, rows):\n",
    "        for column_id in range(1, columns):\n",
    "            letter_in_A = A[column_id-1]\n",
    "            letter_in_B = B[row_id-1]\n",
    "            if letter_in_A == letter_in_B:\n",
    "                # \"Recursive case 1\"\n",
    "                lookup[row_id][column_id] = lookup[row_id - 1][column_id - 1] + letter_in_A\n",
    "            else:\n",
    "                # \"Recursive case 2\"\n",
    "                option1 = lookup[row_id][column_id-1]\n",
    "                option2 = lookup[row_id-1][column_id]\n",
    "                if len(option1) > len(option2):\n",
    "                    lookup[row_id][column_id] = option1\n",
    "                else:\n",
    "                    lookup[row_id][column_id] = option2\n",
    "    \n",
    "    \n",
    "    if print_table:\n",
    "        pretty_print(lookup)\n",
    "    \n",
    "    return lookup[rows-1][columns-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['     ', '     ', '     ', '     ', '     ', '     ', '     ', '     ']\n",
      "['     ', '     ', 'B    ', 'B    ', 'B    ', 'B    ', 'B    ', 'B    ']\n",
      "['     ', '     ', 'B    ', 'B    ', 'B    ', 'BD   ', 'BD   ', 'BD   ']\n",
      "['     ', '     ', 'B    ', 'BC   ', 'BC   ', 'BD   ', 'BD   ', 'BD   ']\n",
      "['     ', 'A    ', 'B    ', 'BC   ', 'BC   ', 'BD   ', 'BDA  ', 'BDA  ']\n",
      "['     ', 'A    ', 'AB   ', 'BC   ', 'BCB  ', 'BCB  ', 'BDA  ', 'BDAB ']\n",
      "['     ', 'A    ', 'AB   ', 'BC   ', 'BCB  ', 'BCB  ', 'BCBA ', 'BDAB ']\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'BDAB'"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lcs4(A, B, print_table=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'deal'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lcs4(occidental, superdelicately)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The occidental, superdelicately example yields a table that is too large to display."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# For part 2\n",
    "\n",
    "This notebook is long enough, so I've split it up into two parts. \n",
    "\n",
    "The second part extends the LCS algorithm implemented above to numbers larger than 9 and explores an interesting connection between the longest common subsequence problem and the longest **increasing** subsequence problem."
   ]
  }
 ],
 "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}