Skip to content
Permalink
98df406b54
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?

assignments/7159CEM-Portfolio-main/DP.ipynb

Go to file
 
 
Cannot retrieve contributors at this time
422 lines (422 sloc) 12.2 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_{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_{vj-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, \n",
"\n",
"#### P1 can later collect the value v_j+ (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",
" (Vi + min(F(i+2, j), F(i+1, j-1) ), \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) = Vi, \\space\\space\\space If j == i\n",
"$$\n",
"\n",
"$$\n",
"\n",
"F(i, j) = max(Vi, Vj), \\space\\space\\space If j == i + 1\n",
" \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": null,
"metadata": {
"ExecuteTime": {
"end_time": "2022-10-25T11:38:11.266563Z",
"start_time": "2022-10-25T11:38:11.256547Z"
}
},
"outputs": [
{
"ename": "",
"evalue": "",
"output_type": "error",
"traceback": [
"\u001b[1;31mRunning cells with 'Python 3.11.0 ('venv': venv)' requires ipykernel package.\n",
"\u001b[1;31mRun the following command to install 'ipykernel' into the Python environment. \n",
"\u001b[1;31mCommand: '\"c:/Users/Ali Ibrahim/Downloads/7159CEM-Portfolio-main/venv/Scripts/python.exe\" -m pip install ipykernel -U --force-reinstall'"
]
}
],
"source": [
"# Implementation\n",
"def top_down(arr, n):\n",
"\tmemo = {}\n",
"\n",
"\t# recursive top down memoized solution\n",
"\tdef solve(i, j):\n",
"\t\tif i > j or i >= n or j < 0:\n",
"\t\t\treturn 0\n",
"\n",
"\t\tk = (i, j)\n",
"\t\tif k in memo:\n",
"\t\t\treturn memo[k]\n",
"\n",
"\t\t\n",
"\t\toption1 = arr[i] + min(solve(i+2, j), solve(i+1, j-1))\n",
"\n",
"\t\t# if user chooses jth number, opponent can choose ith number or j-1th number.\n",
"\t\t# if opp chooses ith number,user can choose in range [i+1,j-1].\n",
"\t\t# if opp chooses j-1th number, user can choose in range [i,j-2].\n",
"\t\toption2 = arr[j] + min(solve(i+1, j-1), solve(i, j-2))\n",
"\n",
"\t\t# since the user wants to get maximum number\n",
"\t\tmemo[k] = max(option1, option2)\n",
"\t\treturn memo[k]\n",
"\n",
"\treturn solve(0, n-1)\n",
" "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"ExecuteTime": {
"end_time": "2022-10-25T11:38:11.281559Z",
"start_time": "2022-10-25T11:38:11.271567Z"
}
},
"outputs": [
{
"ename": "",
"evalue": "",
"output_type": "error",
"traceback": [
"\u001b[1;31mRunning cells with 'Python 3.11.0 ('venv': venv)' requires ipykernel package.\n",
"\u001b[1;31mRun the following command to install 'ipykernel' into the Python environment. \n",
"\u001b[1;31mCommand: '\"c:/Users/Ali Ibrahim/Downloads/7159CEM-Portfolio-main/venv/Scripts/python.exe\" -m pip install ipykernel -U --force-reinstall'"
]
}
],
"source": [
"# Test examples\n",
"# Test Code\n",
"list1 = [5, 3, 7, 10]\n",
"n1 = len(list1)\n",
"list2 = [8, 15, 3, 7]\n",
"n2 = len(list2)\n",
"list3 = [2, 13, 2, 5, 7, 11]\n",
"n3 = len(list3)\n",
"\n",
"\n",
"#Top Down results\n",
"print('Maximum Profit of P1 using Top Down approach = ', top_down(list1, n1))\n",
"print('Maximum Profit of P1 using Top Down approach = ',top_down(list2, n2))\n",
"print( 'Maximum Profit of P1 using Top Down approach = ',top_down(list3, n3))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#Output\n",
"Maximum Profit of P1 using Top Down approach = 15\n",
"Maximum Profit of P1 using Top Down approach = 22\n",
"Maximum Profit of P1 using Top Down approach = 29"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### 2) Bottom-up approach"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"ExecuteTime": {
"end_time": "2022-10-25T11:38:11.295714Z",
"start_time": "2022-10-25T11:38:11.286560Z"
}
},
"outputs": [
{
"ename": "",
"evalue": "",
"output_type": "error",
"traceback": [
"\u001b[1;31mRunning cells with 'Python 3.11.0 ('venv': venv)' requires ipykernel package.\n",
"\u001b[1;31mRun the following command to install 'ipykernel' into the Python environment. \n",
"\u001b[1;31mCommand: '\"c:/Users/Ali Ibrahim/Downloads/7159CEM-Portfolio-main/venv/Scripts/python.exe\" -m pip install ipykernel -U --force-reinstall'"
]
}
],
"source": [
"# Implementation\n",
"for gap in range(n):\n",
" for j in range(gap, n):\n",
" i = j - gap\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(arr[i] + min(x, y),\n",
" arr[j] + min(y, z))\n",
" return table[0][n - 1]\n",
" "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"ExecuteTime": {
"end_time": "2022-10-25T11:38:11.311861Z",
"start_time": "2022-10-25T11:38:11.295714Z"
}
},
"outputs": [
{
"ename": "",
"evalue": "",
"output_type": "error",
"traceback": [
"\u001b[1;31mRunning cells with 'Python 3.11.0 ('venv': venv)' requires ipykernel package.\n",
"\u001b[1;31mRun the following command to install 'ipykernel' into the Python environment. \n",
"\u001b[1;31mCommand: '\"c:/Users/Ali Ibrahim/Downloads/7159CEM-Portfolio-main/venv/Scripts/python.exe\" -m pip install ipykernel -U --force-reinstall'"
]
}
],
"source": [
"# Test examples\n",
"\n",
"# Test Code\n",
"list1 = [5, 3, 7, 10]\n",
"n1 = len(list1)\n",
"list2 = [8, 15, 3, 7]\n",
"n2 = len(list2)\n",
"list3 = [2, 13, 2, 5, 7, 11]\n",
"n3 = len(list3)\n",
"\n",
"#Bottom Up results\n",
"print('Maximum Profit of P1 using Bottom Up approach = ', bot_up(list1, n1))\n",
"print('Maximum Profit of P1 using Bottom Up approach = ', bot_up(list2, n2))\n",
"print('Maximum Profit of P1 using Bottom Up approach = ', bot_up(list3, n3))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#Output\n",
"Maximum Profit of P1 using Bottom Up approach = 15\n",
"Maximum Profit of P1 using Bottom Up approach = 22\n",
"Maximum Profit of P1 using Bottom Up approach = 29"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Conclusion\n",
"Topdown and bottom up approaches where both successful as the results for this approach is identical. \n",
"\n",
"Please refer to DP.py for python code\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# List of references\n",
"Ghadage, O. P. (2021, November 22). What is Dynamic Programming? Top-down vs Bottom-up Approach. Simplilearn.com. https://www.simplilearn.com/tutorials/data-structure-tutorial/what-is-dynamic-programming\n"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3.11.0 ('venv': venv)",
"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.11.0"
},
"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": "9646fcfabfca22912ce5fe7fa2239f453c97b6dafcc6a8d175371d4d5afbb8ca"
}
}
},
"nbformat": 4,
"nbformat_minor": 2
}