{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"[Home](Home.ipynb)\n",
"\n",
"[nbviewer view](https://nbviewer.org/github/4dsolutions/elite_school/blob/master/Exercises.ipynb#USA-Computing-Olympiad)\n",
"\n",
"\n",
"# Example Exercises and Games\n",
"\n",
"If you forked this project, consider adding your own example exercises to this Notebook. Whether you include solutions or not is up to you. Are you a teacher? Perhaps you have hidden the answers in another place.\n",
"\n",
"Jump to (internal links, may not work on Github):\n",
"\n",
"* [ACSL](#American-Computer-Science-League)\n",
"* [USACO](#USA-Computing-Olympiad)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Idea: Scissors Paper Rock\n",
"\n",
"Write a scissors-paper-rock game that uses input( ) for a player. The computer plays the other player and doesn't cheat; it uses random.\n",
"\n",
"Keep score such that after a certain number of rounds, a winner is declared."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from puzzles import spr"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdin",
"output_type": "stream",
"text": [
"s, p, r or q: r\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"player picks rock\n",
"computer picks scissors\n",
"rock versus scissors\n",
"player wins\n"
]
},
{
"name": "stdin",
"output_type": "stream",
"text": [
"s, p, r or q: r\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"player picks rock\n",
"computer picks paper\n",
"rock versus paper\n",
"computer wins\n"
]
},
{
"name": "stdin",
"output_type": "stream",
"text": [
"s, p, r or q: q\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Thanks for playing\n"
]
}
],
"source": [
"spr()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Before taking a look at [one possible implementation](puzzles.py), why not come up with a solution yourself? Take your time. Don't feel you have to follow the example interface exactly."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Idea: Indigs\n",
"Write a function that takes any positive integer or zero and returns its \"indig\", meaning you keep adding the integers together until you're down to one between 0 and 9.\n",
"\n",
"Below, the comments next to the function call show the steps to the final answer.\n",
"\n",
"\n",
">>> indig(12345) # -> 15 -> 6\n",
"6\n",
">>> indig(7822) # -> 19 -> 10 -> 1\n",
"1\n",
""
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [],
"source": [
"from puzzles import indig"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"indig(12345)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"indig(7822)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Idea: Explore a Ramanujan Identity\n",
"\n",
"Find a Ramanujan Identity and validate it (not a proof) using an extended precision library, either Python's native Decimal, or something 3rd party such as [gmpy2](https://pypi.org/project/gmpy2/).\n",
"\n",
"$$\n",
"\\frac{1}{\\pi} = \\frac{\\sqrt{8}}{9801}\\sum_{n=0}^{\\infty}\\frac{(4n)!}{(n!)^4}\\times\\frac{26390n + 1103}{396^{4n}}\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [],
"source": [
"from math import factorial"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"3628800"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"factorial(10) # 10 * 9 * 8 ..... * 2 * 1"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"factorial(0)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Validating the above identity from Ramanujan requires a multiple-precision number type. The Anaconda ecosystem supplies one, mpmath. Or we can pip install it.\n",
"\n",
"Lets install it:"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Requirement already satisfied: mpmath in /Users/mac/opt/anaconda3/envs/new_world/lib/python3.9/site-packages (1.2.1)\n"
]
}
],
"source": [
"! pip install mpmath # ! means Operating Sys shell"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [],
"source": [
"import mpmath\n",
"from mpmath import mp, mpf"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Instead of going straight to Ramanujan's formula, lets practice with the number e, a convergence based on a single input, n, as n increases towards infinity.\n",
"\n",
"$$\n",
"e = \\mathop {\\lim }\\limits_{n \\to \\infty } \\left( {1 + \\frac{1}{n}} \\right)^n\n",
"$$"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [],
"source": [
"mp.prec = 1000"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [],
"source": [
"n = mpf('1'+'0'*100) # that's 1 followed by 100 zeroes"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"mpf('10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.0')"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"n"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"mpf('2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642729155230050905079815380304002899591868503797961026261688238975094242411197308585410131164426899269765211310564282704549680989698996537618283902467719057129820836416823535319224585963641777525861808095801')"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"(1 + 1/n)**n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"From [a published source](https://www.boxentriq.com/code-breaking/euler-number):\n",
"\n",
"2.7182818284 5904523536 0287471352 6624977572 4709369995 9574966967"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Idea: Quiz Me on the Keywords\n",
"\n",
"In the first version, the goal is to remember as many of the 33-35 keywords as you can. Then q to quit and see which ones you missed. \n",
"\n",
"Entering any correct guess another time will trigger a listing of all the keywords guessed so far."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"36 keywords left to guess\n"
]
},
{
"name": "stdin",
"output_type": "stream",
"text": [
"What is your guess? (q to quit): hint\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"hint is not a keyword in Python.\n",
"36 keywords left to guess\n"
]
},
{
"name": "stdin",
"output_type": "stream",
"text": [
"What is your guess? (q to quit): q\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"You gave up!\n",
"Unguessed: ['False', 'None', 'True', '__peg_parser__', 'and', 'as', 'assert', 'async', 'await', 'break', 'class', 'continue', 'def', 'del', 'elif', 'else', 'except', 'finally', 'for', 'from', 'global', 'if', 'import', 'in', 'is', 'lambda', 'nonlocal', 'not', 'or', 'pass', 'raise', 'return', 'try', 'while', 'with', 'yield']\n",
"Guessed: []\n"
]
}
],
"source": [
"import kw_quiz"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In this next version, the computer picks a keyword at random, and you have only a few chances to guess it. Thanks to hints, however, guessing correctly is pretty easy."
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Welcome to Spooky Castle. To Escape, guess the secret keyword\n",
"So what is the secret keyword then? Guess so far: 0\n"
]
},
{
"name": "stdin",
"output_type": "stream",
"text": [
"You may answer (or type 'hint'): hint\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"The keyword begins with a\n",
"So what is the secret keyword then? Guess so far: 0\n"
]
},
{
"name": "stdin",
"output_type": "stream",
"text": [
"You may answer (or type 'hint'): as\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"No, that's not it.\n",
"So what is the secret keyword then? Guess so far: 1\n"
]
},
{
"name": "stdin",
"output_type": "stream",
"text": [
"You may answer (or type 'hint'): assert\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"No, that's not it.\n",
"So what is the secret keyword then? Guess so far: 2\n"
]
},
{
"name": "stdin",
"output_type": "stream",
"text": [
"You may answer (or type 'hint'): and\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"No, that's not it.\n",
"So what is the secret keyword then? Guess so far: 3\n"
]
},
{
"name": "stdin",
"output_type": "stream",
"text": [
"You may answer (or type 'hint'): async\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"No, that's not it.\n",
"So what is the secret keyword then? Guess so far: 4\n"
]
},
{
"name": "stdin",
"output_type": "stream",
"text": [
"You may answer (or type 'hint'): hint\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"The keyword is 5 letters long.\n",
"So what is the secret keyword then? Guess so far: 4\n"
]
},
{
"name": "stdin",
"output_type": "stream",
"text": [
"You may answer (or type 'hint'): await\n"
]
},
{
"name": "stdout",
"output_type": "stream",
"text": [
"Excellent, we're done here\n",
"You have won the Copper Key\n",
"Congratulations!\n",
"Here is your Copper Key\n",
"Always always run this...\n"
]
}
],
"source": [
"%run castle_game.py"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Playing these games may be fun and challenging, but don't forget to read the source code to see exactly how each works\n",
"\n",
"* [kw_quiz.py](kw_quiz.py)\n",
"* [castle_game.py](castle_game.py)\n",
"\n",
"Check them out!"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# American Computer Science League\n",
"\n",
"* [ACSL Ball](#ACLS-Ball)\n",
"* [ACSL Letters](#ACLS-Letters)\n",
"* [Pattern Finder](#Pattern-Finder)\n",
"* [Hexgrid Walk](#HexaGrid-Walk)\n",
"* [15 Puzzle](#15-Puzzle)\n",
"* [Look and Say](#Look-and-Say)\n",
"* [Subpattern Coverage](#Subpattern-Coverage)\n",
"* [Gridimeter](#Gridimeter)\n",
"* [Compressed Trees](#Compressed-Trees)\n",
"* [Hexgrid Path Generation](#Hexgrid-Path-Generation)"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [],
"source": [
"import os\n",
"os.chdir(\"./acsl\")"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"/Users/mac/Documents/elite_school/acsl\n"
]
}
],
"source": [
"! pwd"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### ACSL Ball\n",
"\n",
"* [PDF Instructions](acsl/as_1_aball.pdf)\n",
"* [Solution](acsl/as_1_aball.py)\n",
"* [Test Data 1](acsl/as_1_aball_sample1.txt)\n",
"* [Test Data 2](acsl/as_1_aball_sample2.txt)"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [],
"source": [
"import as_1_aball"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"6\n",
"Chico\n",
"Shemp\n",
"50\n",
"Groucho\n"
]
}
],
"source": [
"as_1_aball.main(\"as_1_aball_sample1.txt\")"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"19\n",
"Beth\n",
"Dick\n",
"57\n",
"Ellen\n"
]
}
],
"source": [
"as_1_aball.main(\"as_1_aball_sample2.txt\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### ACSL Letters\n",
"\n",
"* [PDF Instruction](./acsl/as_5_letters.pdf)\n",
"* [Solution](./acsl/as_5_letters.py)\n",
"* [Test Data 1](./acsl/as_5_letters_sample1.py)\n",
"* [Test Data 2](./acsl/as_5_letters_sample2.py)"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {},
"outputs": [],
"source": [
"import as_5_letters"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"L 7\n",
"L 5\n",
"WTSRONLIHFEDCBA\n",
"LOT\n",
"LAEOTDINRHS\n",
"E 5\n",
"E 5\n",
"YWTSRONLIGFEDA\n",
"G\n",
"EWINORADGT\n"
]
}
],
"source": [
"as_5_letters.main(\"as_5_letters_sample1.txt\")"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"R 6\n",
"R 5\n",
"ZYWVUTSRPONLIHGFEDA\n",
"IRST\n",
"RTAIODESHLNUW\n",
"E 11\n",
"E 8\n",
"WVTSRPONLIHGFEDCBA\n",
"CE\n",
"EWATCHIDNORV\n"
]
}
],
"source": [
"as_5_letters.main(\"as_5_letters_sample2.txt\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Pattern Finder\n",
"\n",
"* [PDF Instructions](acsl/as_1_pattern.pdf)\n",
"* [Solution](acsl/as1.py)\n",
"* [Test Data 1](acsl/as1_pattern_sample1.txt)\n",
"* [Test Data 2](acsl/as1_pattern_sample2.txt)"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import as1\n",
"from imp import reload\n",
"reload(as1)"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 1. 2\n",
" 2. 1\n",
" 3. 0\n",
" 4. 15\n",
" 5. 1\n",
" 6. 1\n",
" 7. 5\n",
" 8. 2\n",
" 9. 3\n",
"10. 3\n"
]
}
],
"source": [
"as1.main(\"as1_pattern_sample1.txt\")"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 1. 4\n",
" 2. 2\n",
" 3. 6\n",
" 4. 32\n",
" 5. 1\n",
" 6. 11\n",
" 7. 0\n",
" 8. 13\n",
" 9. 7\n",
"10. 3\n"
]
}
],
"source": [
"as1.main(\"as1_pattern_sample2.txt\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### HexGrid Walk\n",
"\n",
"* [PDF Instructions](acsl/as_3_hexgrid_walk.pdf)\n",
"* [Solution](acsl/as3.py)\n",
"* [Test Data 1](acsl/as3_hexwalk1.txt)\n",
"* [Test Data 2](acsl/as3_hexwalk2.txt)"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import as3\n",
"reload(as3)"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 1. D4\n",
" 2. E3\n",
" 3. I8\n",
" 4. B1\n",
" 5. B1\n",
" 6. A8\n",
" 7. Z3\n",
" 8. N12\n",
" 9. N36\n",
"10. J118\n"
]
}
],
"source": [
"as3.main(\"as3_hexwalk1.txt\")"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" 1. D1\n",
" 2. E3\n",
" 3. C7\n",
" 4. E5\n",
" 5. E5\n",
" 6. U9\n",
" 7. H9\n",
" 8. G10\n",
" 9. B3\n",
"10. A2\n"
]
}
],
"source": [
"as3.main(\"as3_hexwalk2.txt\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### 15 Puzzle\n",
"\n",
"* [PDF Instructions](acsl/as_4_fifteen_puzzle.pdf)\n",
"* [Solution](acsl/as3.py)\n",
"* [Test Data 1](acsl/as4_fifteen_sample1.txt)\n",
"* [Test Data 2](acsl/as4_fifteen_sample2.txt)"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import as4\n",
"reload(as4)"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1. 10\n",
"2. 7\n",
"3. 5\n",
"4. 10\n",
"5. 3\n",
"6. 10\n",
"7. 1\n",
"8. 6\n",
"9. 16\n",
"10. 4\n"
]
}
],
"source": [
"as4.main(\"as4_fifteen_sample1.txt\")"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1. 6\n",
"2. 13\n",
"3. 4\n",
"4. 16\n",
"5. 10\n",
"6. 1\n",
"7. 9\n",
"8. 16\n",
"9. 15\n",
"10. 12\n"
]
}
],
"source": [
"as4.main(\"as4_fifteen_sample2.txt\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Look and Say\n",
"\n",
"* [PDF Instructions](acsl/as_5_look_and_say.pdf)\n",
"* [Solution](acsl/as5_looksay.py)\n",
"* [Test Data 1](acsl/as5_sample1.txt)\n",
"* [Test Data 2](acsl/as5_sample2.txt)"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {},
"outputs": [],
"source": [
"from as5_looksay import substr, looksay"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'1113'"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"s = \"21131211131221\"\n",
"substr(s,7,3) # Term 9: 21131211131221"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'21131211131221'"
]
},
"execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"s"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'12211311123113112211'"
]
},
"execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"looksay(s)"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {},
"outputs": [],
"source": [
"assert looksay('312211') == '13112221'\n",
"assert looksay('13112221') == '1113213211'"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'11'"
]
},
"execution_count": 39,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"looksay('1')"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {},
"outputs": [],
"source": [
"sequence = ['1']\n",
"for i in range(25):\n",
" sequence.append(looksay(sequence[-1]))"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['1',\n",
" '11',\n",
" '21',\n",
" '1211',\n",
" '111221',\n",
" '312211',\n",
" '13112221',\n",
" '1113213211',\n",
" '31131211131221',\n",
" '13211311123113112211']"
]
},
"execution_count": 41,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sequence[:10]"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"2 2 0 --> 1 [ 1. 1 ]\n",
"3 1 1 --> 21 [ 2. 21 ]\n",
"4 2 2 --> 211 [ 3. 211 ]\n",
"5 4 2 --> 221 [ 4. 221 ]\n",
"6 1 2 --> 312 [ 5. 312 ]\n",
"7 2 4 --> 31122 [ 6. 31122 ]\n",
"8 4 4 --> 32132 [ 7. 32132 ]\n",
"9 7 3 --> 1113 [ 8. 1113 ]\n",
"10 10 5 --> 231131 [ 9. 231131 ]\n",
"11 15 6 --> 1321132 [ 10. 1321132 ]\n"
]
}
],
"source": [
"test = open(\"as5_sample1.txt\")\n",
"ans = open(\"as5_looksay1.txt\")\n",
"for line, answer in zip(test, ans):\n",
" print(line[:-1], end=\"\")\n",
" args = [int(arg) for arg in line[:-1].split()]\n",
" print(\" -->\", substr(sequence[args[0]-1], args[1], args[2]), end=\"\")\n",
" print(\" [\", answer[:-1], \"]\")"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"12 10 2 --> 123 [ 1. 123 ]\n",
"13 15 4 --> 13122 [ 2. 13122 ]\n",
"14 20 5 --> 112111 [ 3. 112111 ]\n",
"16 25 6 --> 3112111 [ 4. 3112111 ]\n",
"18 40 7 --> 12211121 [ 5. 12211121 ]\n",
"20 100 10 --> 12221131112 [ 6. 12221131112 ]\n",
"21 200 5 --> 321133 [ 7. 321133 ]\n",
"22 300 8 --> 112311332 [ 8. 112311332 ]\n",
"23 400 10 --> 21321231231 [ 9. 21321231231 ]\n",
"24 500 10 --> 21113122113 [ 10. 21113122113 ]\n"
]
}
],
"source": [
"test = open(\"as5_sample2.txt\")\n",
"ans = open(\"as5_looksay2.txt\")\n",
"for line, answer in zip(test, ans):\n",
" print(line[:-1], end=\"\")\n",
" args = [int(arg) for arg in line[:-1].split()]\n",
" print(\" -->\", substr(sequence[args[0]-1], args[1], args[2]), end=\"\")\n",
" print(\" [\", answer[:-1], \"]\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Subpattern Coverage\n",
"\n",
"* [PDF Instructions](acsl/as_6_subpattern_coverage.pdf)\n",
"* [Solution](as6.py)\n",
"* [Test Data 1](acsl/as6_sample1.txt)\n",
"* [Test Data 2](acsl/as6_sample2.txt)"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"8 8 FF AA 55 00 FF AA 55 00\n",
"4 4 F F F F\n",
"4 4 1 1 1 1\n",
"3 4 A A A\n",
"4 8 CC AA CC AA\n",
"4 6 22 B1 22 B1\n",
"6 4 3 A F 3 A F\n",
"6 6 B1 D2 21 B1 D2 21\n",
"6 8 AA AA AA AA AA AA\n",
"5 5 00 00 00 00 00\n"
]
}
],
"source": [
"with open(\"as6_sample1.txt\") as f:\n",
" for line in f:\n",
" print(line, end=\"\")"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['1', '0', '1', '0', '1', '0', '1', '0']"
]
},
"execution_count": 45,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"list(\"{:08b}\".format((int(\"AA\", 16))))"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {},
"outputs": [],
"source": [
"def make_panel(rows, cols, data):\n",
" rows = []\n",
" template = \"{:0\" + str(cols) + \"b}\"\n",
" for hexcode in data.split():\n",
" row = list(template.format((int(hexcode, 16))))\n",
" rows.append(row)\n",
" return rows"
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[['1', '1', '1', '1', '1', '1', '1', '1'],\n",
" ['1', '0', '1', '0', '1', '0', '1', '0'],\n",
" ['0', '1', '0', '1', '0', '1', '0', '1'],\n",
" ['0', '0', '0', '0', '0', '0', '0', '0'],\n",
" ['1', '1', '1', '1', '1', '1', '1', '1'],\n",
" ['1', '0', '1', '0', '1', '0', '1', '0'],\n",
" ['0', '1', '0', '1', '0', '1', '0', '1'],\n",
" ['0', '0', '0', '0', '0', '0', '0', '0']]"
]
},
"execution_count": 47,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"target = make_panel(8,8,\"FF AA 55 00 FF AA 55 00\")\n",
"target"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[['1', '1', '1', '1'],\n",
" ['1', '1', '1', '1'],\n",
" ['1', '1', '1', '1'],\n",
" ['1', '1', '1', '1']]"
]
},
"execution_count": 48,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"target = make_panel(4, 4, \"F F F F\")\n",
"target"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [],
"source": [
"target = make_panel(8,8,\"FF AA 55 00 FF AA 55 00\")"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {},
"outputs": [],
"source": [
"from as6 import *"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"What tile sizes evenly divide the target panel? In order of total tile size? We will start with smallest and go bigger, each time generating the whole from the part, to see if we have a match."
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(1, 1),\n",
" (1, 2),\n",
" (2, 1),\n",
" (1, 4),\n",
" (2, 2),\n",
" (4, 1),\n",
" (1, 8),\n",
" (2, 4),\n",
" (4, 2),\n",
" (8, 1),\n",
" (2, 8),\n",
" (4, 4),\n",
" (8, 2),\n",
" (4, 8),\n",
" (8, 4),\n",
" (8, 8)]"
]
},
"execution_count": 51,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"make_sizes(8,8)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's get the subpanel of a specific size."
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[['1', '1'], ['1', '0'], ['0', '1'], ['0', '0']]"
]
},
"execution_count": 52,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"subp = get_subpanel(target, 4, 2)\n",
"subp"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now lets generate the target using the candidate tile. We need so many across and so many down."
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {},
"outputs": [],
"source": [
"generated = mult_subpanel(subp, across=8//2, down=8//4)"
]
},
{
"cell_type": "code",
"execution_count": 54,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 54,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"generated == target"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The solve method brings it all together:\n",
"\n",
"* generate the target panel from hexcodes\n",
"* generate possible subpanel sizes in size order\n",
"* multiply subpanels to make candidate\n",
"* if candidate == target, we have found the smallest size."
]
},
{
"cell_type": "code",
"execution_count": 55,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(4, 2)"
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"solve(8, 8, \"FF AA 55 00 FF AA 55 00\")"
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(1, 1)"
]
},
"execution_count": 56,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"solve(4, 4, \"F F F F\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Gridimeter\n",
"\n",
"* [PDF Instructions](acsl/as_7_gridimeter.pdf)\n",
"* [Solution](acsl/as7_Gridimeter.py)\n",
"* [Test Data 1](acsl/as7_sample1.txt)\n",
"* [Test Data 2](acsl/as7_sample2.txt)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The code cell below reviews the \"scatter and gather\" operator. The star in front of a parameter makes it collect positional arguments. The star in front of an argument breaks it up into separate elements.\n",
"\n",
"The actual solution provided is translated from Java and involves figuring out the \"gray area\" i.e. the internal versus external cells, using a 2nd grid to develop such a picture. Only 1s and 2s get used in the 2nd grid eventually. "
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"r: 4; c: 4; rows: ('6E', '4C5', '4C5', '6E')\n"
]
},
{
"data": {
"text/plain": [
"0"
]
},
"execution_count": 57,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"data = \"4 4 6E 4C5 4C5 6E\"\n",
"\n",
"def make_grid(r, c, *rows): # gather into 3 params\n",
" \"\"\"\n",
" r - number of rows\n",
" c - number of columns\n",
" rows - data for each row, convert to decimal\n",
" \"\"\"\n",
" print(f\"r: {r}; c: {c}; rows: {rows}\")\n",
" # more code\n",
" gridmeter = 0\n",
" return gridmeter\n",
" \n",
"make_grid(*data.split()) # explode into 6 args"
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'0110'"
]
},
"execution_count": 58,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"\"{:04d}\".format(int('6E', 16))"
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'1221'"
]
},
"execution_count": 59,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"\"{:04d}\".format(int('4C5', 16))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Compressed Trees\n",
"\n",
"* [PDF Instructions](acsl/as_8_compressed_trees.pdf)\n",
"* [Solution](acsl/as8.py)\n",
"* [Test Data 1](acsl/as8_sample1.txt)\n",
"* [Test Data 2](acsl/as8_sample2.txt)"
]
},
{
"cell_type": "code",
"execution_count": 60,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(1, 'A'),\n",
" (1, 'D'),\n",
" (1, 'E'),\n",
" (1, 'H'),\n",
" (1, 'R'),\n",
" (1, 'W'),\n",
" (2, 'O'),\n",
" (3, 'L')]"
]
},
"execution_count": 60,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"data = \"HELLOAWORLD\"\n",
"freq = \"1A 1D 1E 1H 1R 1W 2O 3L\"\n",
"\n",
"from collections import Counter\n",
"\n",
"def make_freq(s):\n",
" ordered = sorted(Counter(s).items(), \n",
" key=lambda t: (t[1],t[0]))\n",
" return [(num, let) for let, num in ordered]\n",
" \n",
"data = make_freq(data)\n",
"data"
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'1A 1D 1E 1H 1R 1W 2O 3L'"
]
},
"execution_count": 61,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def pretty(the_row):\n",
" s = \"\"\n",
" return \" \".join([str(i)+j for i,j in the_row])\n",
"\n",
"pretty(data)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Fixed this after class (May 9th):"
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {},
"outputs": [],
"source": [
"tree = {}\n",
"\n",
"def combine(t0, t1):\n",
" number = t0[0] + t1[0]\n",
" # alphabetize the concatenated letters\n",
" letters = \"\".join(sorted(list(t0[1] + t1[1])))\n",
" newterm = (number, # numeric\n",
" letters) # lexical\n",
" return newterm\n",
"\n",
"def add2tree(the_tree, new_key, left, right):\n",
" the_tree[new_key] = (left, right)\n",
" return the_tree\n",
"\n",
"def insert(the_data, term):\n",
" the_data.append(term)\n",
" newdata = sorted(the_data, # by number, letters \n",
" key=lambda t: (t[0],t[1]))\n",
" return newdata"
]
},
{
"cell_type": "code",
"execution_count": 63,
"metadata": {},
"outputs": [],
"source": [
"def compress(the_data = \"HELLOAWORLD\", tree={}):\n",
" the_data = make_freq(the_data)\n",
" print(pretty(the_data))\n",
" while len(the_data) > 1:\n",
" result = combine(*the_data[:2])\n",
" add2tree(tree, result, the_data[0], the_data[1])\n",
" the_data = the_data[2:]\n",
" the_data = insert(the_data, result)\n",
" print(pretty(the_data))\n",
" return tree"
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1A 1D 1E 1H 1R 1W 2O 3L\n",
"1E 1H 1R 1W 2AD 2O 3L\n",
"1R 1W 2AD 2EH 2O 3L\n",
"2AD 2EH 2O 2RW 3L\n",
"2O 2RW 3L 4ADEH\n",
"3L 4ADEH 4ORW\n",
"4ORW 7ADEHL\n",
"11ADEHLORW\n"
]
},
{
"data": {
"text/plain": [
"{(2, 'AD'): ((1, 'A'), (1, 'D')),\n",
" (2, 'EH'): ((1, 'E'), (1, 'H')),\n",
" (2, 'RW'): ((1, 'R'), (1, 'W')),\n",
" (4, 'ADEH'): ((2, 'AD'), (2, 'EH')),\n",
" (4, 'ORW'): ((2, 'O'), (2, 'RW')),\n",
" (7, 'ADEHL'): ((3, 'L'), (4, 'ADEH')),\n",
" (11, 'ADEHLORW'): ((4, 'ORW'), (7, 'ADEHL'))}"
]
},
"execution_count": 64,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"t = compress()\n",
"t"
]
},
{
"cell_type": "code",
"execution_count": 65,
"metadata": {},
"outputs": [],
"source": [
"def findit(c, the_tree):\n",
" the_key, (left, right) = list(the_tree.items())[-1] # root\n",
" searching = True\n",
" srchstr = \"\"\n",
" if c not in the_key[1]:\n",
" return None\n",
" \n",
" while searching:\n",
" print(the_key, left, right)\n",
" if c in left[1]:\n",
" the_key = left\n",
" srchstr += \"0\"\n",
" if len(left[1])==1:\n",
" searching = False\n",
" continue\n",
" \n",
" else:\n",
" the_key = right\n",
" srchstr += \"1\"\n",
" if len(right[1])==1:\n",
" searching = False\n",
" continue\n",
" \n",
" left, right = the_tree[the_key]\n",
" \n",
" return srchstr"
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1A 1B 1C 1D 1E 1F 3H 3L 3N\n",
"1C 1D 1E 1F 2AB 3H 3L 3N\n",
"1E 1F 2AB 2CD 3H 3L 3N\n",
"2AB 2CD 2EF 3H 3L 3N\n",
"2EF 3H 3L 3N 4ABCD\n",
"3L 3N 4ABCD 5EFH\n",
"4ABCD 5EFH 6LN\n",
"6LN 9ABCDEFH\n",
"15ABCDEFHLN\n"
]
},
{
"data": {
"text/plain": [
"{(2, 'AD'): ((1, 'A'), (1, 'D')),\n",
" (2, 'EH'): ((1, 'E'), (1, 'H')),\n",
" (2, 'RW'): ((1, 'R'), (1, 'W')),\n",
" (4, 'ADEH'): ((2, 'AD'), (2, 'EH')),\n",
" (4, 'ORW'): ((2, 'O'), (2, 'RW')),\n",
" (7, 'ADEHL'): ((3, 'L'), (4, 'ADEH')),\n",
" (11, 'ADEHLORW'): ((4, 'ORW'), (7, 'ADEHL')),\n",
" (2, 'AB'): ((1, 'A'), (1, 'B')),\n",
" (2, 'CD'): ((1, 'C'), (1, 'D')),\n",
" (2, 'EF'): ((1, 'E'), (1, 'F')),\n",
" (4, 'ABCD'): ((2, 'AB'), (2, 'CD')),\n",
" (5, 'EFH'): ((2, 'EF'), (3, 'H')),\n",
" (6, 'LN'): ((3, 'L'), (3, 'N')),\n",
" (9, 'ABCDEFH'): ((4, 'ABCD'), (5, 'EFH')),\n",
" (15, 'ABCDEFHLN'): ((6, 'LN'), (9, 'ABCDEFH'))}"
]
},
"execution_count": 66,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"t = compress(\"ABCDEFHHHLLLNNN\")\n",
"t"
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(15, 'ABCDEFHLN') (6, 'LN') (9, 'ABCDEFH')\n",
"(9, 'ABCDEFH') (4, 'ABCD') (5, 'EFH')\n",
"(4, 'ABCD') (2, 'AB') (2, 'CD')\n",
"(2, 'CD') (1, 'C') (1, 'D')\n"
]
},
{
"data": {
"text/plain": [
"'1011'"
]
},
"execution_count": 67,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"findit(\"D\", t)"
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1A 1B 1C 1D 3G 5K\n",
"1C 1D 2AB 3G 5K\n",
"2AB 2CD 3G 5K\n",
"3G 4ABCD 5K\n",
"5K 7ABCDG\n",
"12ABCDGK\n"
]
},
{
"data": {
"text/plain": [
"{(2, 'AD'): ((1, 'A'), (1, 'D')),\n",
" (2, 'EH'): ((1, 'E'), (1, 'H')),\n",
" (2, 'RW'): ((1, 'R'), (1, 'W')),\n",
" (4, 'ADEH'): ((2, 'AD'), (2, 'EH')),\n",
" (4, 'ORW'): ((2, 'O'), (2, 'RW')),\n",
" (7, 'ADEHL'): ((3, 'L'), (4, 'ADEH')),\n",
" (11, 'ADEHLORW'): ((4, 'ORW'), (7, 'ADEHL')),\n",
" (2, 'AB'): ((1, 'A'), (1, 'B')),\n",
" (2, 'CD'): ((1, 'C'), (1, 'D')),\n",
" (2, 'EF'): ((1, 'E'), (1, 'F')),\n",
" (4, 'ABCD'): ((2, 'AB'), (2, 'CD')),\n",
" (5, 'EFH'): ((2, 'EF'), (3, 'H')),\n",
" (6, 'LN'): ((3, 'L'), (3, 'N')),\n",
" (9, 'ABCDEFH'): ((4, 'ABCD'), (5, 'EFH')),\n",
" (15, 'ABCDEFHLN'): ((6, 'LN'), (9, 'ABCDEFH')),\n",
" (7, 'ABCDG'): ((3, 'G'), (4, 'ABCD')),\n",
" (12, 'ABCDGK'): ((5, 'K'), (7, 'ABCDG'))}"
]
},
"execution_count": 68,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"t = compress(\"ABCDGGGKKKKK\")\n",
"t"
]
},
{
"cell_type": "code",
"execution_count": 69,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"(12, 'ABCDGK') (5, 'K') (7, 'ABCDG')\n",
"(7, 'ABCDG') (3, 'G') (4, 'ABCD')\n"
]
},
{
"data": {
"text/plain": [
"'10'"
]
},
"execution_count": 69,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"code = findit(\"G\", t)\n",
"code"
]
},
{
"cell_type": "code",
"execution_count": 70,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1L 1Y 2A 2E 2G 3P\n",
"2A 2E 2G 2LY 3P\n",
"2G 2LY 3P 4AE\n",
"3P 4AE 4GLY\n",
"4GLY 7AEP\n",
"11AEGLPY\n",
"(11, 'AEGLPY') (4, 'GLY') (7, 'AEP')\n",
"(4, 'GLY') (2, 'G') (2, 'LY')\n",
"(2, 'LY') (1, 'L') (1, 'Y')\n"
]
},
{
"data": {
"text/plain": [
"'010'"
]
},
"execution_count": 70,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"t = compress(\"LYAAEEGGPPP\")\n",
"code = findit(\"L\", t)\n",
"code"
]
},
{
"cell_type": "code",
"execution_count": 71,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1A 1B 1C 1D 1E 1F 2H 3L\n",
"1C 1D 1E 1F 2AB 2H 3L\n",
"1E 1F 2AB 2CD 2H 3L\n",
"2AB 2CD 2EF 2H 3L\n",
"2EF 2H 3L 4ABCD\n",
"3L 4ABCD 4EFH\n",
"4EFH 7ABCDL\n",
"11ABCDEFHL\n",
"(11, 'ABCDEFHL') (4, 'EFH') (7, 'ABCDL')\n",
"(7, 'ABCDL') (3, 'L') (4, 'ABCD')\n",
"(4, 'ABCD') (2, 'AB') (2, 'CD')\n",
"(2, 'AB') (1, 'A') (1, 'B')\n"
]
},
{
"data": {
"text/plain": [
"'1100'"
]
},
"execution_count": 71,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"t = compress(\"ABCDEFHHLLL\")\n",
"code = findit(\"A\", t)\n",
"code"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Hexgrid Path Generation\n",
"\n",
"* [PDF Instructions](acsl/as_9_hexgrid_path_generation.pdf)\n",
"* [Solution](acsl/as9_hexgrid.py)\n",
"* [Test Data 1](acsl/as9_sample1.txt)\n",
"* [Test Data 2](acsl/as9_sample2.txt)\n",
"\n",
"Given a valid path of the required length, what transformation rules might give an alternative path? Do we have a way to cover all the paths of a given length by means of these transformations, and count only the unique ones?\n",
"\n",
"In point of fact, the provided solution employs a recursive strategy. Every path from a starting tile is explored out to a given length, counting only those that happen to end up exactly on the target tile."
]
},
{
"cell_type": "code",
"execution_count": 72,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"/Users/mac/Documents/elite_school\n"
]
}
],
"source": [
"# matches code at the start of the ACSL section to drop down\n",
"# into a subfolder. So now lets pop back up as the next \n",
"# section should run from elite_school (parent):\n",
"os.chdir(\"..\")\n",
"\n",
"! pwd # this code "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# USA Computing Olympiad\n",
"\n",
"The USA Computing Olympiad is a national programming competition that occurs four times a year, with December, January, February, and US Open (March) contests. The regular contests are four hours long, and the US Open is five hours long. Each contest contains three problems. Solutions are evaluated and scored against a set of predetermined test cases that are not visible to the student. Scoring is out of 1000 points, with each problem being weighted equally (~333 points). There are four divisions of contests: Bronze, Silver, Gold, and Platinum. After each contest, students who meet the contest-dependent cutoff for promotion will compete in the next division for future contests.\n",
"\n",
"Sign up for an account in [the USACO training area](https://train.usaco.org/). \n",
"\n",
"Here's another great find: [USACO Guide](https://usaco.guide/).\n",
"\n",
"You'll find a lot of interesting challenges such as...\n",
"\n",
"* [Broken Necklace](https://train.usaco.org/usacoprob2?a=gTpkbBkxTzg&S=beads) | [replit solution](https://replit.com/@kurner/BrokenNecklace#main.py)\n",
"* [Friday 13](https://train.usaco.org/usacoprob2?a=gTpkbBkxTzg&S=friday) | [replit solution](https://replit.com/@kurner/friday13#main.py)\n",
"\n",
"From past competitions:\n",
"\n",
"January 2021, Bronze level:\n",
"\n",
"* [Uddered But Not Heard](http://usaco.org/index.php?page=viewproblem2&cpid=1083) | [replit in progress](https://replit.com/@kurner/notherd#main.py)\n",
"* [Even More Odd Photos](http://usaco.org/index.php?page=viewproblem2&cpid=1084) | [replit solution](https://replit.com/@kurner/evenoddcows#main.py)\n",
"* [Just Stalling](http://usaco.org/index.php?page=viewproblem2&cpid=1085) | [replit solution](https://replit.com/@kurner/JustStalling#main.py) ($N <= 8$ only)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Your Olympiad Sandbox\n",
"\n",
"Drawing from examples above, one may conclude that any attempt to solve a USACO problem should focus on the following elements:\n",
"\n",
"* a statement of the problem (or at least a link)\n",
"* the provided test data (it needs to be unzipped)\n",
"* template code, modified to suit each problem, to and make reading the test files routine\n",
"* a placeholder function where a solution would go\n",
"* a solution (however it's a complete sandbox even without one)\n",
"\n",
"Whether you set up these sandboxes in Replit, per the homework, or choose something on your local device, the point is to maximize the value of what's already given. \n",
"\n",
"The test data (e.g. `1.in` comes with the comes with the correct answers e.g. in `1.out`. Find out if your solution gets the same answers.\n",
"\n",
"In this way, you can check a solution in the Replit itself without submitting code to USACO. Learn in more detail where and how it fails, to continue with debugging.\n",
"\n",
"Another question is when to consult the published solution. \n",
"\n",
"Training exercises often feature a correct answer. A serious USACO training need be no exception.\n",
"\n",
"Given the number of past problems on file, a few may be selected to provide complete demos, which may also involve converting the suggested solution (e.g. Java) into working code in another language (e.g. Python).\n",
"\n",
"To review...\n",
"\n",
"## Typical Homework Assignment\n",
"\n",
"* Choose a USACO problem\n",
"* start a Replit (replit.com) in a language of your choice\n",
"* download and unzip the test data \n",
"* migrate the test data to a final subfolder\n",
"* start with a URL in the comments or docstring pointing to the USACO problem\n",
"* include \"boilerplate code\" for reading all or any test data files (examples given)\n",
"* modify the file-reading code to give informative variable names to Solution()\n",
"* pass some or all of these variables to a Solution(), which is where you will focus on developing your efficient algorithm"
]
},
{
"cell_type": "markdown",
"metadata": {
"tags": []
},
"source": [
"## Eureka Moments\n",
"\n",
"#### Kadane's Algorithm\n",
"\n",
"Find the maximum sum of any subarray in an array."
]
},
{
"cell_type": "code",
"execution_count": 89,
"metadata": {},
"outputs": [],
"source": [
"def kadane(the_array):\n",
" max_sum = the_array[0]\n",
" last_sum = the_array[0]\n",
" for i in range(len(the_array[1:])):\n",
" # add to growing subarray or start fresh?\n",
" best = max(the_array[i], the_array[i] + the_array[i-1])\n",
" # does the winner beat the best so far?\n",
" max_sum = max(max_sum, best)\n",
" return max_sum"
]
},
{
"cell_type": "code",
"execution_count": 90,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"12"
]
},
"execution_count": 90,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"kadane([-2, 2, 5, -11, 6, 4, 8, -10, -1, 9, 0, -3])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Links:\n",
"\n",
"* [Maximum subarray problem on Wikipedia](https://en.wikipedia.org/wiki/Maximum_subarray_problem)\n",
"* [K-Concatenation Maximum Sum](https://leetcode.com/problems/k-concatenation-maximum-sum/discuss?currentPage=1&orderBy=hot&query=) -- discussion section contains a Rust solution\n",
"* [Kadane’s Algorithm Explained with Examples](https://hackernoon.com/kadanes-algorithm-explained-50316f4fd8a6)\n",
"* [The Algorithms: Dynamic Programming](https://the-algorithms.com/category/dynamicprogramming)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Longest Increasing Sequence Length\n",
"\n",
"A sequence, unlike a subarray, is not necessarily continuous. How many numbers in a row might you excerpt, left to right, that increase? Their sum is not important.\n",
"\n",
"A clever algorithm using \"dynamic programming\" keeps enlarging a sequence one more to the right, planting the flag one step further, then reviewing the array up to that point.\n",
"\n",
"Any of the `A[(0...j)]` elements, j < i, such that `array[j] < array[i]` is at the end of a sequence we might continue, and we keep a counter for the length of each. We continue the longest of the eligible so far, and so on.\n",
"\n",
"With clever bookkeeping, we keep the indexes of elements playing a role, such that we not only know the number of terms, but the terms themselves."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"\"\"\" \n",
"Based on: https://youtu.be/E6us4nmXTHs\n",
"\"\"\"\n",
"\n",
"class Solution:\n",
" \n",
" def __init__(self, data):\n",
" self.the_array = data\n",
" self.dp = [1]*len(data)\n",
" self.subseq = [None]*len(data)\n",
"\n",
" def subprob(self, i):\n",
" curr = self.the_array[i]\n",
" max_dp = 0\n",
" for j, prev in enumerate(self.the_array[:i]):\n",
" if curr > prev:\n",
" if self.dp[j] + 1 >= self.dp[i]:\n",
" self.dp[i] = self.dp[j] + 1\n",
" self.subseq[i] = j\n",
"\n",
" def solve(self):\n",
" for i in range(len(self.the_array))[1:]:\n",
" self.subprob(i)\n",
" return max(self.dp)\n",
" \n",
" def sequence(self):\n",
" final_seq = []\n",
" idx = self.dp.index(max(self.dp))\n",
" while True:\n",
" final_seq.append(self.the_array[idx])\n",
" idx = self.subseq[idx]\n",
" if idx == None:\n",
" break\n",
" return list(reversed(final_seq))"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"testing = Solution([10, 5, 8, 3, 9, 4, 12, 11])\n",
"testing.solve()"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[5, 8, 9, 12]"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"testing.sequence()"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[None, None, 1, None, 2, 3, 4, 4]"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"testing.subseq"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"testing.subprob(7)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1, 1, 2, 1, 3, 2, 4, 4]"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"testing.dp"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"testing = Solution([3, 4, -1, 0, 6, 2, 3])\n",
"testing.solve()"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1, 2, 1, 2, 3, 3, 4]"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"testing.dp"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[-1, 0, 2, 3]"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"testing.sequence()"
]
},
{
"cell_type": "code",
"execution_count": 161,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"3"
]
},
"execution_count": 161,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"testing = Solution([2, 5, 1, 8, 3])\n",
"testing.solve()"
]
},
{
"cell_type": "code",
"execution_count": 162,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[2, 5, 8]"
]
},
"execution_count": 162,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"testing.sequence()"
]
},
{
"cell_type": "code",
"execution_count": 163,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"6"
]
},
"execution_count": 163,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"the_data = [0, 4, 12, 2, 10, 6, 9, 13, 3, 11, 7, 15]\n",
"testing = Solution(the_data)\n",
"testing.solve()"
]
},
{
"cell_type": "code",
"execution_count": 164,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[0, 2, 6, 9, 11, 15]"
]
},
"execution_count": 164,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"testing.sequence()"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"4"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"the_data = [-1, 5, 7, 3, 12, 4, 9]\n",
"testing = Solution(the_data)\n",
"testing.solve()"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[-1, 5, 7, 12]"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"testing.sequence()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Longest Increasing Path in a Matrix\n",
"\n",
"Our [guest Youtuber](https://youtu.be/bI27Vnwakxc) suggests the solution does not use dynamic programming exactly, because we don't have a specific starting position. It does use both recursion and memoization however.\n",
"\n",
"From the [Leetcode site](https://leetcode.com/problems/longest-increasing-path-in-a-matrix/):\n",
"\n",
"Constraints:\n",
"\n",
"```python:\n",
" m == matrix.length\n",
" n == matrix[i].length\n",
" 1 <= m, n <= 200\n",
" 0 <= matrix[i][j] <= 2**31 - 1\n",
"```\n",
" \n",
"Implementation Hint:\n",
"\n",
"Python can make good use of @lru_cache instead of having to manually create a memoization data structure. Or try @cache in Python 3.9 and above."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [],
"source": [
"from functools import lru_cache\n",
"\n",
"@lru_cache(maxsize=None)\n",
"def fib(n):\n",
" if n < 2:\n",
" return n\n",
" return fib(n-1) + fib(n-2)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"[fib(n) for n in range(16)]"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"CacheInfo(hits=28, misses=16, maxsize=None, currsize=16)"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"fib.cache_info()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For practice with numpy, lets make use of the numpy ndarray type object for our matrix. \n",
"\n",
"Is the code below a valid max path finder? It's based on some of the [Leetcode discussion](https://leetcode.com/problems/longest-increasing-path-in-a-matrix/discuss/1948313/python-solution-oror-depth-first-search-oror-faster-than-97-oror-time%3A-O(mn)-oror-space%3A-O(mn)).\n",
"\n",
"Idea: feed it some simple test data from pre-existing problems. The challenge is to use numpy."
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[ 8, 2, 2, 0, 13],\n",
" [ 8, 15, 5, 2, 15],\n",
" [15, 1, 7, 18, 1],\n",
" [12, 13, 11, 7, 10],\n",
" [14, 17, 12, 13, 15]])"
]
},
"execution_count": 42,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import numpy as np\n",
"matrix = np.random.randint(0, 20, 25).reshape(5,5)\n",
"matrix"
]
},
{
"cell_type": "code",
"execution_count": 81,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0"
]
},
"execution_count": 81,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"matrix[(0, 3)]"
]
},
{
"cell_type": "code",
"execution_count": 109,
"metadata": {},
"outputs": [],
"source": [
"path_length = np.zeros(matrix.size, dtype=int).reshape(matrix.shape)\n",
"\n",
"def around_me(matrix, path_length_matrix, loc):\n",
" if path_length[loc] != 0:\n",
" return path_length[loc]\n",
" length = 1\n",
" value = matrix[loc]\n",
" i,j = loc\n",
" for offset in (i, j+1), (i, j-1), (i+1, j), (i-1, j):\n",
" try:\n",
" if value < matrix[offset]:\n",
" path = 1 + around_me(matrix, path_length_matrix, offset)\n",
" if path > length:\n",
" length = path\n",
" except IndexError: # out of bounds, index error\n",
" pass\n",
" path_length_matrix[loc] = length \n",
" return length"
]
},
{
"cell_type": "code",
"execution_count": 112,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[0, 0, 7, 8, 2],\n",
" [0, 1, 6, 7, 1],\n",
" [0, 0, 5, 1, 0],\n",
" [0, 2, 4, 0, 0],\n",
" [0, 1, 3, 2, 1]])"
]
},
"execution_count": 112,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"path_length"
]
},
{
"cell_type": "code",
"execution_count": 111,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"8"
]
},
"execution_count": 111,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"around_me(matrix, path_length, (0,3))"
]
},
{
"cell_type": "code",
"execution_count": 80,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[ 8, 2, 2, 0, 13],\n",
" [ 8, 15, 5, 2, 15],\n",
" [15, 1, 7, 18, 1],\n",
" [12, 13, 11, 7, 10],\n",
" [14, 17, 12, 13, 15]])"
]
},
"execution_count": 80,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"matrix"
]
},
{
"cell_type": "code",
"execution_count": 114,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"8"
]
},
"execution_count": 114,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def driver():\n",
" path_length = np.zeros(matrix.size, dtype=int).reshape(matrix.shape)\n",
" record = 0\n",
" for i in range(matrix.shape[0]):\n",
" for j in range(matrix.shape[1]):\n",
" path = around_me(matrix, path_length, (i, j))\n",
" if path > record:\n",
" record = path\n",
" return record\n",
" \n",
"driver()"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {},
"outputs": [],
"source": [
"class Solution:\n",
" def longestIncreasingPath(self, matrix):\n",
" max_len = 0\n",
" return max_len"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Triangular Numbers\n",
"\n",
"At this juncture, it's useful to share a story about the young Johann Carl Friedrich Gauss (1777-1855) , later a famous mathematician. The class was misbehaving and the teacher assigned everyone to find the sum of all the numbers from 1 to 100 as busy work.\n",
"\n",
"The young Gauss, already brilliant, wrote two lines and added them, like this (notice we skip actually writing and adding most of the numbers -- so did he):\n",
"\n",
" 1 + 2 + 3 + ... + 100\n",
" 100 + 99 + 98 + ... + 1 <-- same 100 terms in reverse \n",
" --------------------------- \n",
" 101 + 101 + 101 + ... + 101 \n",
"\n",
"Clearly, he reasoned, I'm getting this number 101 in the bottom row 100 times. But that's from adding all the numbers I need twice (I added the series to itself). So the number I really want is 1/2 of 100 x 101 = 10100/2 = 5050.\n",
"\n",
"So a more general way of writing the solution is:\n",
"\n",
" 1 + 2 + 3 + ... + N \n",
" N + N-1 + N-2 + ... + 1 <-- same N terms in reverse \n",
" --------------------------- \n",
" N+1 + N+1 + N+1 + ... + N+1 \n",
"\n",
"where we're adding all consecutive integers from 1 up to N. In other words, we have N+1 added to itself N times, for a total of $N(N+1)$ . But again, that's from adding the series twice (adding it to itself). So the answer we're really looking for is:\n",
"\n",
"Sum of N consecutive integers = $N (N+1) / 2$\n",
"\n",
"Also note that when we're talking about \"consecutive integers\" what's important is one of them be one larger than the other. $N(N+1)/2$ is a perfectly fine way of writing it, but then so is $N(N-1)/2$.\n",
"\n",
"Think of asking yourself this question: with N people in a room, how many ways may two people shake hands? \n",
"\n",
"Consider yourself to be one of these N people. You will not shake your own hand, so you have N - 1 hands to shake. And so for everybody. \n",
"\n",
"It would seem that for N people, we have (N-1) handshakes, so $N (N - 1)$ would be the answer. However, lets stop to remember that me shaking George's hand is the same as George shaking my hand. We will count every handshake twice if we go with $N (N - 1)$, and so $N (N - 1)/2$ must be our answer.\n",
"\n",
"Source: [Getting Serious about Series](http://4dsolutions.net/ocn/numeracy0.html)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Counting Edges from Faces\n",
"\n",
"A similar divide-by-two step applies when we want the number of edges in some Platonic polyhedron, i.e. a shape with all faces bordered by the same number of edges, such as the tetrahedron, cube, octahedron, pentagonal dodecahedron and icosahedron.\n",
"\n",
"Think of polyhedrons in terms of Graph Theory: nodes connected by edges, defining circuits, such as faces.\n",
"\n",
"Multiply the number of edges defining each face, by the number of faces. You will have counted every edge twice, since each is a fence between two fields, we could say.\n",
"\n",
"Four faces times three edges is twelve edges, divided by two, gives us six edges in a tetrahedron.\n",
"\n",
"Six faces times the four edges of the cube, divided by two, gives the twelve edges of the cube.\n",
"\n",
"Eight faces times three edges is twenty-four, divided by two, gives the twelve edges in an octahedron.\n",
"\n",
"Twenty faces times three edges is sixty, divided by two, gives the thirty edges of the icosahedron.\n",
"\n",
"Twelve faces times five edges is sixty, divided by two, gives the thirty edges of the pentagonal dodecahedron.\n",
"\n",
"#### Counting Edges from Vertexes\n",
"\n",
"A Platonic polyhedron has the property that every vertex is the same i.e. the same number of edges branch from it. If we know how many spokes per vertex, such as five, and the number of vertexes, such as twelve, then these two number multiplied (five times twelve) gives twice the number of edges again, in this case thirty.\n",
"\n",
"For additional discussion of Polyhedra, see use [Sandbox](ADS_sandbox.ipynb) on building a data structure / nested hierarchy."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"#### Outer Product or Cartesian Product\n",
"\n",
"Suppose you want to evaluate \"everything times everything\" except you might not want \"times\" to be the operator. You want all possible pairs (i, j) where i is a row and j is a column, in some rectangle. If the indexing row and column are the same, then the rectangle will be a square."
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"
\n",
" \n",
" \n",
" | \n",
" 0 | \n",
" 1 | \n",
" 2 | \n",
" 3 | \n",
" 4 | \n",
"
\n",
" \n",
" \n",
" \n",
" | 10 | \n",
" 0 | \n",
" 10 | \n",
" 20 | \n",
" 30 | \n",
" 40 | \n",
"
\n",
" \n",
" | 20 | \n",
" 0 | \n",
" 20 | \n",
" 40 | \n",
" 60 | \n",
" 80 | \n",
"
\n",
" \n",
" | 30 | \n",
" 0 | \n",
" 30 | \n",
" 60 | \n",
" 90 | \n",
" 120 | \n",
"
\n",
" \n",
"
\n",
"
\n",
"\n",
"
\n",
" \n",
" \n",
" | \n",
" 2 | \n",
" 4 | \n",
" 3 | \n",
" 4 | \n",
"
\n",
" \n",
" \n",
" \n",
" | 1 | \n",
" True | \n",
" True | \n",
" True | \n",
" True | \n",
"
\n",
" \n",
" | 2 | \n",
" True | \n",
" True | \n",
" True | \n",
" True | \n",
"
\n",
" \n",
" | 3 | \n",
" False | \n",
" True | \n",
" True | \n",
" True | \n",
"
\n",
" \n",
" | 4 | \n",
" False | \n",
" True | \n",
" False | \n",
" True | \n",
"
\n",
" \n",
"
\n",
"