DP.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Optimal strategy for a game on a list of numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider a list of $n$ coins of values $v_1,\\ldots,v_n$, where $n$ is even.\n",
    "\n",
    "Two equally smart players P1 and P2 play against each other in alternating turns, with P1 starting first.\n",
    "\n",
    "In each turn, a player removes either the first or last coin from the list and receives the value of that coin as reward.\n",
    "\n",
    "Determine the maximum possible amount of money that P1 can win."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Marking scheme\n",
    "\n",
    "|Item|Mark|\n",
    "|:----|---:|\n",
    "|Part (2) of \"Approach\" (see below)|/4|\n",
    "|Recursive formulation (see below)|/4|\n",
    "|Implementation - Memoization|/6|\n",
    "|Implementation - Bottom-up|/6|\n",
    "|||\n",
    "|**Total**:     |/20|\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example\n",
    "\n",
    "- `5, 3, 7, 10`: P1 wins a maximum value of 15 = 10 + 5.\n",
    "- `8, 15, 3, 7`: P1 wins a maximum value of 22 = 7 + 15.\n",
    "\n",
    "In the second example, here is how the game goes:\n",
    "\n",
    "| State         | P1   | P2  |\n",
    "|---------------|------|-----|\n",
    "| `8, 15, 3, 7` |      |     |\n",
    "| `8, 15, 3`    | 7    |     |\n",
    "| `15, 3`       |      | 8   |\n",
    "| `3`           | 7+15 |     |\n",
    "|               |      | 8+3 |\n",
    "\n",
    "Total value collected by P1 is 7+15 = 22."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Note\n",
    "\n",
    "Note that the greedy approach, where the players pick the highest value, does not guarantee maximum reward.\n",
    "For example, in the second example, this is how the game goes:\n",
    "\n",
    "| State         | P1  | P2   |\n",
    "|---------------|-----|------|\n",
    "| `8, 15, 3, 7` |     |      |\n",
    "| `15, 3, 7`    | 8   |      |\n",
    "| `3, 7`        |     | 15   |\n",
    "| `3`           | 8+7 |      |\n",
    "|               |     | 15+3 |\n",
    "\n",
    "Total value collected by P1 this time is only 8+7=15."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Approach\n",
    "\n",
    "Each of P1 and P2 will try to reduce their opponent's chances of winning.\n",
    "\n",
    "Let $F(i, j)$ represent the maximum value that a player can collect from the list $v_i,\\ldots,v_j$.\n",
    "\n",
    "Starting from the list $v_i,\\ldots,v_j$, there are two possible cases:\n",
    "\n",
    "#### 1) P1 removes $v_i$ leaving $v_{i+1},\\ldots,v_j$ for P2 to choose from.\n",
    "\n",
    "$$\n",
    "v_i, \\underbrace{v_{i+1}, \\ldots, v_j}_\\text{P2}.\n",
    "$$\n",
    "\n",
    "P2 either chooses $v_{i+1}$, leaving $v_{i+2},\\ldots,v_j$, or $v_j$ leaving $v_{i+1},\\ldots,v_{j-1}$ for P1 to choose from.\n",
    "\n",
    "P2 intends to choose the coin which leaves P1 with minimal value.\n",
    "So, P1 can later collect the value $v_i + \\min(F(i+2, j), F(i+1, j-1))$. \n",
    "\n",
    "#### 2) P1 chooses $v_j$ leaving $v_{i},\\ldots,v_{j-1}$ for P2 to choose from.\n",
    "\n",
    "$$\n",
    "\\underbrace{v_{i}, \\ldots, v_{j-1}}_\\text{P2}, v_j.\n",
    "$$\n",
    "\n",
    "P2 either chooses $v_{i}$, leaving $v_{i+1},\\ldots,v_{j-1}$, or $v_{j-1}$ leaving $v_{i},\\ldots,v_{j-2}$ for P1 to choose from.\n",
    "P2 intends to choose the coin which leaves P1 with minimal value.\n",
    "So, P1 can later collect the value $v_j + \\min(F(i+1, j-1), F(i, j-2))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recursive formulation\n",
    "\n",
    "Based on the above two choices, we take a maximum of two choices. \n",
    "\n",
    "$$\n",
    "F(i, j) = \\max\\Big\\{\n",
    "        $v_i + \\min(F(i+2, j), F(i+1, j-1))$ ,\n",
    "        $v_j + \\min(F(i+1, j-1), F(i, j-2))$\n",
    "        \\Big\\}\n",
    "$$\n",
    "\n",
    "P1 wants to maximise the number of coins. \n",
    "\n",
    "Base Cases:\n",
    "\n",
    "$$\n",
    "F(i, j) = i>j\n",
    "$$\n",
    "\n",
    "Note: i==j is impossible as total amount of coins is even."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The recursive top down solution in is shown below"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1) Memoization (Top-down approach)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-10-25T11:38:11.266563Z",
     "start_time": "2022-10-25T11:38:11.256547Z"
    }
   },
   "outputs": [],
   "source": [
    "def game_mem(i, j, v, cache = None):\n",
    "    if i>j:\n",
    "        return 0\n",
    "\n",
    "    if cache is None:\n",
    "        cache = {}\n",
    "\n",
    "    if str(i) + str(j) in cache:\n",
    "        return cache[str(i) + str(j)]\n",
    "\n",
    "    left = v[i] + min(game_mem(i+2, j, v), game_mem(i+1, j-1, v))\n",
    "    right = v[j] + min(game_mem(i+1, j-1, v), game_mem(i, j-2, v))\n",
    "    score =  max(left, right)\n",
    "    cache[str(i) + str(j)] = score\n",
    "    return score\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-10-25T11:38:11.281559Z",
     "start_time": "2022-10-25T11:38:11.271567Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "22\n"
     ]
    }
   ],
   "source": [
    "print(game_mem(0, 3, [8, 15, 3, 7]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2) Bottom-up approach"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-10-25T11:38:11.295714Z",
     "start_time": "2022-10-25T11:38:11.286560Z"
    }
   },
   "outputs": [],
   "source": [
    "def game_bup(v):\n",
    "    Saved = {}\n",
    "\n",
    "    for interval in range(0, len(v), 1):\n",
    "        i=0\n",
    "        for j in range(interval, len(v), 1):\n",
    "            if i+2 <= j:\n",
    "                var1 = Saved[str(i+2)+ str(j)]\n",
    "            else:\n",
    "                var1 = 0\n",
    "\n",
    "            if i+1<=j-1:\n",
    "                var2 = Saved[str(i+1)+str(j-1)]\n",
    "            else:\n",
    "                var2 =0\n",
    "\n",
    "            if i<=j-2:\n",
    "                var3 = Saved[str(i)+str(j-2)]\n",
    "            else:\n",
    "                var3 =0\n",
    "\n",
    "            Saved[str(i)+str(j)] = max(v[i] + min(var1, var2), v[j] + min(var2,var3))\n",
    "            i+=1\n",
    "\n",
    "    return Saved[str(0)+str(len(v)-1)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2022-10-25T11:38:11.311861Z",
     "start_time": "2022-10-25T11:38:11.295714Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "22\n"
     ]
    }
   ],
   "source": [
    "print(game_bup([8, 15, 3, 7]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Conclusion\n",
    "\n",
    "Throughout this exercise, we have successfully identified the approach to solve this 2 player coin game problem using dynamic programming. We have then reasoned the recursive formulation and implemented a python solution using both memoization and bottom-up/tabulation approaches."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# List of references\n"
   ]
  }
 ],
 "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.3"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  },
  "vscode": {
   "interpreter": {
    "hash": "6d1e45cadc3597bb8b6600530fbdf8c3eefe919a24ef54d9d32b318795b772e0"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}