Permalink
Cannot retrieve contributors at this time
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 fileThis commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
279 lines (279 sloc)
6.79 KB
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{ | |
"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_{........}$, leaving $v_{....},\\ldots,v_{....}$, or $v_{....}$ leaving $v_{....},\\ldots,v_{....}$ 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 $.....................$." | |
] | |
}, | |
{ | |
"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", | |
" ................................. , \n", | |
" .................................\n", | |
" \\Big\\}\n", | |
"$$\n", | |
"\n", | |
"P1 wants to maximise the number of coins. \n", | |
"\n", | |
"Base Cases:\n", | |
"\n", | |
"$$\n", | |
"F(i, j) = .................................\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": 1, | |
"metadata": { | |
"ExecuteTime": { | |
"end_time": "2022-10-25T11:38:11.266563Z", | |
"start_time": "2022-10-25T11:38:11.256547Z" | |
} | |
}, | |
"outputs": [], | |
"source": [ | |
"# Implementation" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 2, | |
"metadata": { | |
"ExecuteTime": { | |
"end_time": "2022-10-25T11:38:11.281559Z", | |
"start_time": "2022-10-25T11:38:11.271567Z" | |
} | |
}, | |
"outputs": [], | |
"source": [ | |
"# Test examples" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"### 2) Bottom-up approach" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 3, | |
"metadata": { | |
"ExecuteTime": { | |
"end_time": "2022-10-25T11:38:11.295714Z", | |
"start_time": "2022-10-25T11:38:11.286560Z" | |
} | |
}, | |
"outputs": [], | |
"source": [ | |
"# Implementation" | |
] | |
}, | |
{ | |
"cell_type": "code", | |
"execution_count": 4, | |
"metadata": { | |
"ExecuteTime": { | |
"end_time": "2022-10-25T11:38:11.311861Z", | |
"start_time": "2022-10-25T11:38:11.295714Z" | |
} | |
}, | |
"outputs": [], | |
"source": [ | |
"# Test examples" | |
] | |
}, | |
{ | |
"cell_type": "markdown", | |
"metadata": {}, | |
"source": [ | |
"# Conclusion\n", | |
"\n" | |
] | |
}, | |
{ | |
"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 | |
} |