Skip to content
Permalink
6490c6a3c8
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

7159CEM-Portfolio/DP.ipynb

Go to file
 
 
Cannot retrieve contributors at this time
385 lines (385 sloc) 10.8 KB
Raw Blame
{
"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_{....},\\ldots,v_{....}$ for P2 to choose from.\n",
"\n",
"$$\n",
"\\underbrace{v_{....}, \\ldots, v_{....}}_\\text{P2}, v_j.\n",
"$$\n",
"\n",
"P2 either chooses $v_{j-1}$, leaving $v_{i},\\ldots,v_{j-2}$, or $v_{i}$ leaving $v_{i+1},\\ldots,v_{j-1}$ 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 $vj + 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\\{vi + min(F(i+2, j), F(i+1, j-1))\n",
" , \n",
" vj + 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) = F(i,j) = max(vi, vj) ,if j==i+1\n",
"$$\n",
" "
]
},
{
"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": 5,
"metadata": {
"ExecuteTime": {
"end_time": "2022-10-25T11:38:11.266563Z",
"start_time": "2022-10-25T11:38:11.256547Z"
}
},
"outputs": [],
"source": [
"# Implementation\n",
"# Using Top-down approach, Find the optimal possible value for a coin \n",
"# game of strategy.\n",
"def optimalCoinGame(set, n):\n",
" store = {}\n",
" \n",
" def V(i, j):\n",
" if i > j or i >= n or j < 0:\n",
" return 0\n",
" \n",
" x = (i, j)\n",
" if x in store:\n",
" return store[x]\n",
"# if the user chooses Vith coin, the opponent can choose from Vi+1th or Vjth coin.\n",
"# if he chooses Vi+1th coin, user is left with V(i+2, j) range.\n",
"# if opp chooses Vjth coin, then user is left with V(i+1,j-1) range to \n",
"#choose from.\n",
"#minimum value left after opponent chooses.\n",
" choice1 = set[i] + min(V(i + 2, j), V(i + 1, j - 1))\n",
" \n",
"# if user chooses Vjth coin, opponent can choose Vith coin or Vj-1th coin.\n",
"# if opp chooses Vith coin,user can choose in range V(i+1,j-1).\n",
"# if opp chooses Vj-1th coin, user can choose in range V(i,j-2).\n",
" choice2 = set[j] + min(V(i + 1, j - 1), V(i, j - 2))\n",
" \n",
" store[x] = max(choice1, choice2)\n",
" return store[x]\n",
" \n",
" return V(0, n-1)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"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",
"31\n",
"40\n"
]
}
],
"source": [
"# Test examples\n",
"# Test formulation using examples and other range of numbers\n",
"set1 = [8, 15, 3, 7]\n",
"n = len(set1)\n",
"print(optimalCoinGame(set1, n))\n",
" \n",
"set2 = [7,7,12,4,1,18]\n",
"n = len(set2)\n",
"print(optimalCoinGame(set2, n))\n",
" \n",
"set3 = [15, 22, 15, 8, 2, 10]\n",
"n = len(set3)\n",
"print(optimalCoinGame(set3, n))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 2) Bottom-up approach"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"ExecuteTime": {
"end_time": "2022-10-25T11:38:11.295714Z",
"start_time": "2022-10-25T11:38:11.286560Z"
}
},
"outputs": [],
"source": [
"# Implementation\n",
"# Using Bottom-up-approach, Find the optimal possible value for a coin \n",
"# game of strategy.\n",
" \n",
"def optimalCoinGame(set, n):\n",
" \n",
" \n",
" table = [[0 for i in range(n)]\n",
" for j in range(n)]\n",
" # where n is an even number \n",
" \n",
" \n",
" for A in range(n):\n",
" for j in range(A, n):\n",
" i = j - A\n",
" \n",
"# x is value of V(i + 2, j), y is V(i + 1, j-1) and z is V(i, j-2) \n",
" # accroding to out recursive formulation.\n",
" x = 0\n",
" if((i + 2) <= j):\n",
" x = table[i + 2][j]\n",
" y = 0\n",
" if((i + 1) <= (j - 1)):\n",
" y = table[i + 1][j - 1]\n",
" z = 0\n",
" if(i <= (j - 2)):\n",
" z = table[i][j - 2]\n",
" table[i][j] = max(set[i] + min(x, y),\n",
" set[j] + min(y, z))\n",
" return table[0][n - 1]"
]
},
{
"cell_type": "code",
"execution_count": 8,
"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",
"31\n",
"40\n"
]
}
],
"source": [
"# Test examples\n",
"# Test formulation using examples and other range of numbers\n",
"set1 = [8, 15, 3, 7]\n",
"n = len(set1)\n",
"print(optimalCoinGame(set1, n))\n",
" \n",
"set2 = [7,7,12,4,1,18]\n",
"n = len(set2)\n",
"print(optimalCoinGame(set2, n))\n",
" \n",
"set3 = [15, 22, 15, 8, 2, 10]\n",
"n = len(set3)\n",
"print(optimalCoinGame(set3, n))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Conclusion\n",
"From the implementation above, it can be seen that the greedy approach doesn't necessary arrive at the optimal solution. using the range of values [8,15,3,7] the greedy approch gives out an output of 15 for the user and 18 for the opponent but using the memoization method shows us that the optimal output is 22.\n",
"\n",
"For the range of values [7,7,12,4,1,18] using the greedy approach gives us an output 29 for the user and 22 for the opponent but using memoizaion method show that the optimal output is 31. \n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# List of references\n",
"1) Sahilshelangia, jit_t, Chandan_Kumar, CheshtaKwatra\n",
"bidibaaz123, divyesh072019, surinderdawra388, danceboyyaya, phasing17, sagartomar9927. (2022). https://www.geeksforgeeks.org/optimal-strategy-for-a-game-dp-31/\n"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3.8.5 ('base')",
"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.5"
},
"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": "ac033f1bfcc03fd7d94ee49e5062e90b7567aa783d10948b9fb2cb16e6935923"
}
}
},
"nbformat": 4,
"nbformat_minor": 2
}