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.
Jump to (internal links, may not work on Github):
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.
Keep score such that after a certain number of rounds, a winner is declared.
from puzzles import spr
spr()
player picks rock computer picks scissors rock versus scissors player wins
player picks rock computer picks paper rock versus paper computer wins
Thanks for playing
Before taking a look at one possible implementation, why not come up with a solution yourself? Take your time. Don't feel you have to follow the example interface exactly.
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.
Below, the comments next to the function call show the steps to the final answer.
>>> indig(12345) # -> 15 -> 6 6 >>> indig(7822) # -> 19 -> 10 -> 1 1
from puzzles import indig
indig(12345)
6
indig(7822)
1
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.
$$ \frac{1}{\pi} = \frac{\sqrt{8}}{9801}\sum_{n=0}^{\infty}\frac{(4n)!}{(n!)^4}\times\frac{26390n + 1103}{396^{4n}} $$from math import factorial
factorial(10) # 10 * 9 * 8 ..... * 2 * 1
3628800
factorial(0)
1
Validating the above identity from Ramanujan requires a multiple-precision number type. The Anaconda ecosystem supplies one, mpmath. Or we can pip install it.
Lets install it:
! pip install mpmath # ! means Operating Sys shell
Requirement already satisfied: mpmath in /Users/mac/opt/anaconda3/envs/new_world/lib/python3.9/site-packages (1.2.1)
import mpmath
from mpmath import mp, mpf
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.
$$ e = \mathop {\lim }\limits_{n \to \infty } \left( {1 + \frac{1}{n}} \right)^n $$mp.prec = 1000
n = mpf('1'+'0'*100) # that's 1 followed by 100 zeroes
n
mpf('10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000.0')
(1 + 1/n)**n
mpf('2.71828182845904523536028747135266249775724709369995957496696762772407663035354759457138217852516642729155230050905079815380304002899591868503797961026261688238975094242411197308585410131164426899269765211310564282704549680989698996537618283902467719057129820836416823535319224585963641777525861808095801')
From a published source:
2.7182818284 5904523536 0287471352 6624977572 4709369995 9574966967
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.
Entering any correct guess another time will trigger a listing of all the keywords guessed so far.
import kw_quiz
36 keywords left to guess
hint is not a keyword in Python. 36 keywords left to guess
You gave up! 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'] Guessed: []
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.
%run castle_game.py
Welcome to Spooky Castle. To Escape, guess the secret keyword So what is the secret keyword then? Guess so far: 0
The keyword begins with a So what is the secret keyword then? Guess so far: 0
No, that's not it. So what is the secret keyword then? Guess so far: 1
No, that's not it. So what is the secret keyword then? Guess so far: 2
No, that's not it. So what is the secret keyword then? Guess so far: 3
No, that's not it. So what is the secret keyword then? Guess so far: 4
The keyword is 5 letters long. So what is the secret keyword then? Guess so far: 4
Excellent, we're done here You have won the Copper Key Congratulations! Here is your Copper Key Always always run this...
Playing these games may be fun and challenging, but don't forget to read the source code to see exactly how each works
Check them out!
import os
os.chdir("./acsl")
! pwd
/Users/mac/Documents/elite_school/acsl
import as_1_aball
as_1_aball.main("as_1_aball_sample1.txt")
6 Chico Shemp 50 Groucho
as_1_aball.main("as_1_aball_sample2.txt")
19 Beth Dick 57 Ellen
import as_5_letters
as_5_letters.main("as_5_letters_sample1.txt")
L 7 L 5 WTSRONLIHFEDCBA LOT LAEOTDINRHS E 5 E 5 YWTSRONLIGFEDA G EWINORADGT
as_5_letters.main("as_5_letters_sample2.txt")
R 6 R 5 ZYWVUTSRPONLIHGFEDA IRST RTAIODESHLNUW E 11 E 8 WVTSRPONLIHGFEDCBA CE EWATCHIDNORV
import as1
from imp import reload
reload(as1)
<module 'as1' from '/Users/mac/Documents/elite_school/acsl/as1.py'>
as1.main("as1_pattern_sample1.txt")
1. 2 2. 1 3. 0 4. 15 5. 1 6. 1 7. 5 8. 2 9. 3 10. 3
as1.main("as1_pattern_sample2.txt")
1. 4 2. 2 3. 6 4. 32 5. 1 6. 11 7. 0 8. 13 9. 7 10. 3
import as3
reload(as3)
<module 'as3' from '/Users/mac/Documents/elite_school/acsl/as3.py'>
as3.main("as3_hexwalk1.txt")
1. D4 2. E3 3. I8 4. B1 5. B1 6. A8 7. Z3 8. N12 9. N36 10. J118
as3.main("as3_hexwalk2.txt")
1. D1 2. E3 3. C7 4. E5 5. E5 6. U9 7. H9 8. G10 9. B3 10. A2
import as4
reload(as4)
<module 'as4' from '/Users/mac/Documents/elite_school/acsl/as4.py'>
as4.main("as4_fifteen_sample1.txt")
1. 10 2. 7 3. 5 4. 10 5. 3 6. 10 7. 1 8. 6 9. 16 10. 4
as4.main("as4_fifteen_sample2.txt")
1. 6 2. 13 3. 4 4. 16 5. 10 6. 1 7. 9 8. 16 9. 15 10. 12
from as5_looksay import substr, looksay
s = "21131211131221"
substr(s,7,3) # Term 9: 21131211131221
'1113'
s
'21131211131221'
looksay(s)
'12211311123113112211'
assert looksay('312211') == '13112221'
assert looksay('13112221') == '1113213211'
looksay('1')
'11'
sequence = ['1']
for i in range(25):
sequence.append(looksay(sequence[-1]))
sequence[:10]
['1', '11', '21', '1211', '111221', '312211', '13112221', '1113213211', '31131211131221', '13211311123113112211']
test = open("as5_sample1.txt")
ans = open("as5_looksay1.txt")
for line, answer in zip(test, ans):
print(line[:-1], end="")
args = [int(arg) for arg in line[:-1].split()]
print(" -->", substr(sequence[args[0]-1], args[1], args[2]), end="")
print(" [", answer[:-1], "]")
2 2 0 --> 1 [ 1. 1 ] 3 1 1 --> 21 [ 2. 21 ] 4 2 2 --> 211 [ 3. 211 ] 5 4 2 --> 221 [ 4. 221 ] 6 1 2 --> 312 [ 5. 312 ] 7 2 4 --> 31122 [ 6. 31122 ] 8 4 4 --> 32132 [ 7. 32132 ] 9 7 3 --> 1113 [ 8. 1113 ] 10 10 5 --> 231131 [ 9. 231131 ] 11 15 6 --> 1321132 [ 10. 1321132 ]
test = open("as5_sample2.txt")
ans = open("as5_looksay2.txt")
for line, answer in zip(test, ans):
print(line[:-1], end="")
args = [int(arg) for arg in line[:-1].split()]
print(" -->", substr(sequence[args[0]-1], args[1], args[2]), end="")
print(" [", answer[:-1], "]")
12 10 2 --> 123 [ 1. 123 ] 13 15 4 --> 13122 [ 2. 13122 ] 14 20 5 --> 112111 [ 3. 112111 ] 16 25 6 --> 3112111 [ 4. 3112111 ] 18 40 7 --> 12211121 [ 5. 12211121 ] 20 100 10 --> 12221131112 [ 6. 12221131112 ] 21 200 5 --> 321133 [ 7. 321133 ] 22 300 8 --> 112311332 [ 8. 112311332 ] 23 400 10 --> 21321231231 [ 9. 21321231231 ] 24 500 10 --> 21113122113 [ 10. 21113122113 ]
with open("as6_sample1.txt") as f:
for line in f:
print(line, end="")
8 8 FF AA 55 00 FF AA 55 00 4 4 F F F F 4 4 1 1 1 1 3 4 A A A 4 8 CC AA CC AA 4 6 22 B1 22 B1 6 4 3 A F 3 A F 6 6 B1 D2 21 B1 D2 21 6 8 AA AA AA AA AA AA 5 5 00 00 00 00 00
list("{:08b}".format((int("AA", 16))))
['1', '0', '1', '0', '1', '0', '1', '0']
def make_panel(rows, cols, data):
rows = []
template = "{:0" + str(cols) + "b}"
for hexcode in data.split():
row = list(template.format((int(hexcode, 16))))
rows.append(row)
return rows
target = make_panel(8,8,"FF AA 55 00 FF AA 55 00")
target
[['1', '1', '1', '1', '1', '1', '1', '1'], ['1', '0', '1', '0', '1', '0', '1', '0'], ['0', '1', '0', '1', '0', '1', '0', '1'], ['0', '0', '0', '0', '0', '0', '0', '0'], ['1', '1', '1', '1', '1', '1', '1', '1'], ['1', '0', '1', '0', '1', '0', '1', '0'], ['0', '1', '0', '1', '0', '1', '0', '1'], ['0', '0', '0', '0', '0', '0', '0', '0']]
target = make_panel(4, 4, "F F F F")
target
[['1', '1', '1', '1'], ['1', '1', '1', '1'], ['1', '1', '1', '1'], ['1', '1', '1', '1']]
target = make_panel(8,8,"FF AA 55 00 FF AA 55 00")
from as6 import *
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.
make_sizes(8,8)
[(1, 1), (1, 2), (2, 1), (1, 4), (2, 2), (4, 1), (1, 8), (2, 4), (4, 2), (8, 1), (2, 8), (4, 4), (8, 2), (4, 8), (8, 4), (8, 8)]
Let's get the subpanel of a specific size.
subp = get_subpanel(target, 4, 2)
subp
[['1', '1'], ['1', '0'], ['0', '1'], ['0', '0']]
Now lets generate the target using the candidate tile. We need so many across and so many down.
generated = mult_subpanel(subp, across=8//2, down=8//4)
generated == target
True
The solve method brings it all together:
solve(8, 8, "FF AA 55 00 FF AA 55 00")
(4, 2)
solve(4, 4, "F F F F")
(1, 1)
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.
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.
data = "4 4 6E 4C5 4C5 6E"
def make_grid(r, c, *rows): # gather into 3 params
"""
r - number of rows
c - number of columns
rows - data for each row, convert to decimal
"""
print(f"r: {r}; c: {c}; rows: {rows}")
# more code
gridmeter = 0
return gridmeter
make_grid(*data.split()) # explode into 6 args
r: 4; c: 4; rows: ('6E', '4C5', '4C5', '6E')
0
"{:04d}".format(int('6E', 16))
'0110'
"{:04d}".format(int('4C5', 16))
'1221'
data = "HELLOAWORLD"
freq = "1A 1D 1E 1H 1R 1W 2O 3L"
from collections import Counter
def make_freq(s):
ordered = sorted(Counter(s).items(),
key=lambda t: (t[1],t[0]))
return [(num, let) for let, num in ordered]
data = make_freq(data)
data
[(1, 'A'), (1, 'D'), (1, 'E'), (1, 'H'), (1, 'R'), (1, 'W'), (2, 'O'), (3, 'L')]
def pretty(the_row):
s = ""
return " ".join([str(i)+j for i,j in the_row])
pretty(data)
'1A 1D 1E 1H 1R 1W 2O 3L'
Fixed this after class (May 9th):
tree = {}
def combine(t0, t1):
number = t0[0] + t1[0]
# alphabetize the concatenated letters
letters = "".join(sorted(list(t0[1] + t1[1])))
newterm = (number, # numeric
letters) # lexical
return newterm
def add2tree(the_tree, new_key, left, right):
the_tree[new_key] = (left, right)
return the_tree
def insert(the_data, term):
the_data.append(term)
newdata = sorted(the_data, # by number, letters
key=lambda t: (t[0],t[1]))
return newdata
def compress(the_data = "HELLOAWORLD", tree={}):
the_data = make_freq(the_data)
print(pretty(the_data))
while len(the_data) > 1:
result = combine(*the_data[:2])
add2tree(tree, result, the_data[0], the_data[1])
the_data = the_data[2:]
the_data = insert(the_data, result)
print(pretty(the_data))
return tree
t = compress()
t
1A 1D 1E 1H 1R 1W 2O 3L 1E 1H 1R 1W 2AD 2O 3L 1R 1W 2AD 2EH 2O 3L 2AD 2EH 2O 2RW 3L 2O 2RW 3L 4ADEH 3L 4ADEH 4ORW 4ORW 7ADEHL 11ADEHLORW
{(2, 'AD'): ((1, 'A'), (1, 'D')), (2, 'EH'): ((1, 'E'), (1, 'H')), (2, 'RW'): ((1, 'R'), (1, 'W')), (4, 'ADEH'): ((2, 'AD'), (2, 'EH')), (4, 'ORW'): ((2, 'O'), (2, 'RW')), (7, 'ADEHL'): ((3, 'L'), (4, 'ADEH')), (11, 'ADEHLORW'): ((4, 'ORW'), (7, 'ADEHL'))}
def findit(c, the_tree):
the_key, (left, right) = list(the_tree.items())[-1] # root
searching = True
srchstr = ""
if c not in the_key[1]:
return None
while searching:
print(the_key, left, right)
if c in left[1]:
the_key = left
srchstr += "0"
if len(left[1])==1:
searching = False
continue
else:
the_key = right
srchstr += "1"
if len(right[1])==1:
searching = False
continue
left, right = the_tree[the_key]
return srchstr
t = compress("ABCDEFHHHLLLNNN")
t
1A 1B 1C 1D 1E 1F 3H 3L 3N 1C 1D 1E 1F 2AB 3H 3L 3N 1E 1F 2AB 2CD 3H 3L 3N 2AB 2CD 2EF 3H 3L 3N 2EF 3H 3L 3N 4ABCD 3L 3N 4ABCD 5EFH 4ABCD 5EFH 6LN 6LN 9ABCDEFH 15ABCDEFHLN
{(2, 'AD'): ((1, 'A'), (1, 'D')), (2, 'EH'): ((1, 'E'), (1, 'H')), (2, 'RW'): ((1, 'R'), (1, 'W')), (4, 'ADEH'): ((2, 'AD'), (2, 'EH')), (4, 'ORW'): ((2, 'O'), (2, 'RW')), (7, 'ADEHL'): ((3, 'L'), (4, 'ADEH')), (11, 'ADEHLORW'): ((4, 'ORW'), (7, 'ADEHL')), (2, 'AB'): ((1, 'A'), (1, 'B')), (2, 'CD'): ((1, 'C'), (1, 'D')), (2, 'EF'): ((1, 'E'), (1, 'F')), (4, 'ABCD'): ((2, 'AB'), (2, 'CD')), (5, 'EFH'): ((2, 'EF'), (3, 'H')), (6, 'LN'): ((3, 'L'), (3, 'N')), (9, 'ABCDEFH'): ((4, 'ABCD'), (5, 'EFH')), (15, 'ABCDEFHLN'): ((6, 'LN'), (9, 'ABCDEFH'))}
findit("D", t)
(15, 'ABCDEFHLN') (6, 'LN') (9, 'ABCDEFH') (9, 'ABCDEFH') (4, 'ABCD') (5, 'EFH') (4, 'ABCD') (2, 'AB') (2, 'CD') (2, 'CD') (1, 'C') (1, 'D')
'1011'
t = compress("ABCDGGGKKKKK")
t
1A 1B 1C 1D 3G 5K 1C 1D 2AB 3G 5K 2AB 2CD 3G 5K 3G 4ABCD 5K 5K 7ABCDG 12ABCDGK
{(2, 'AD'): ((1, 'A'), (1, 'D')), (2, 'EH'): ((1, 'E'), (1, 'H')), (2, 'RW'): ((1, 'R'), (1, 'W')), (4, 'ADEH'): ((2, 'AD'), (2, 'EH')), (4, 'ORW'): ((2, 'O'), (2, 'RW')), (7, 'ADEHL'): ((3, 'L'), (4, 'ADEH')), (11, 'ADEHLORW'): ((4, 'ORW'), (7, 'ADEHL')), (2, 'AB'): ((1, 'A'), (1, 'B')), (2, 'CD'): ((1, 'C'), (1, 'D')), (2, 'EF'): ((1, 'E'), (1, 'F')), (4, 'ABCD'): ((2, 'AB'), (2, 'CD')), (5, 'EFH'): ((2, 'EF'), (3, 'H')), (6, 'LN'): ((3, 'L'), (3, 'N')), (9, 'ABCDEFH'): ((4, 'ABCD'), (5, 'EFH')), (15, 'ABCDEFHLN'): ((6, 'LN'), (9, 'ABCDEFH')), (7, 'ABCDG'): ((3, 'G'), (4, 'ABCD')), (12, 'ABCDGK'): ((5, 'K'), (7, 'ABCDG'))}
code = findit("G", t)
code
(12, 'ABCDGK') (5, 'K') (7, 'ABCDG') (7, 'ABCDG') (3, 'G') (4, 'ABCD')
'10'
t = compress("LYAAEEGGPPP")
code = findit("L", t)
code
1L 1Y 2A 2E 2G 3P 2A 2E 2G 2LY 3P 2G 2LY 3P 4AE 3P 4AE 4GLY 4GLY 7AEP 11AEGLPY (11, 'AEGLPY') (4, 'GLY') (7, 'AEP') (4, 'GLY') (2, 'G') (2, 'LY') (2, 'LY') (1, 'L') (1, 'Y')
'010'
t = compress("ABCDEFHHLLL")
code = findit("A", t)
code
1A 1B 1C 1D 1E 1F 2H 3L 1C 1D 1E 1F 2AB 2H 3L 1E 1F 2AB 2CD 2H 3L 2AB 2CD 2EF 2H 3L 2EF 2H 3L 4ABCD 3L 4ABCD 4EFH 4EFH 7ABCDL 11ABCDEFHL (11, 'ABCDEFHL') (4, 'EFH') (7, 'ABCDL') (7, 'ABCDL') (3, 'L') (4, 'ABCD') (4, 'ABCD') (2, 'AB') (2, 'CD') (2, 'AB') (1, 'A') (1, 'B')
'1100'
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?
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.
# matches code at the start of the ACSL section to drop down
# into a subfolder. So now lets pop back up as the next
# section should run from elite_school (parent):
os.chdir("..")
! pwd # this code
/Users/mac/Documents/elite_school
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.
Sign up for an account in the USACO training area.
Here's another great find: USACO Guide.
You'll find a lot of interesting challenges such as...
From past competitions:
January 2021, Bronze level:
Drawing from examples above, one may conclude that any attempt to solve a USACO problem should focus on the following elements:
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.
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.
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.
Another question is when to consult the published solution.
Training exercises often feature a correct answer. A serious USACO training need be no exception.
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).
To review...
def kadane(the_array):
max_sum = the_array[0]
last_sum = the_array[0]
for i in range(len(the_array[1:])):
# add to growing subarray or start fresh?
best = max(the_array[i], the_array[i] + the_array[i-1])
# does the winner beat the best so far?
max_sum = max(max_sum, best)
return max_sum
kadane([-2, 2, 5, -11, 6, 4, 8, -10, -1, 9, 0, -3])
12
Links:
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.
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.
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.
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.
"""
Based on: https://youtu.be/E6us4nmXTHs
"""
class Solution:
def __init__(self, data):
self.the_array = data
self.dp = [1]*len(data)
self.subseq = [None]*len(data)
def subprob(self, i):
curr = self.the_array[i]
max_dp = 0
for j, prev in enumerate(self.the_array[:i]):
if curr > prev:
if self.dp[j] + 1 >= self.dp[i]:
self.dp[i] = self.dp[j] + 1
self.subseq[i] = j
def solve(self):
for i in range(len(self.the_array))[1:]:
self.subprob(i)
return max(self.dp)
def sequence(self):
final_seq = []
idx = self.dp.index(max(self.dp))
while True:
final_seq.append(self.the_array[idx])
idx = self.subseq[idx]
if idx == None:
break
return list(reversed(final_seq))
testing = Solution([10, 5, 8, 3, 9, 4, 12, 11])
testing.solve()
4
testing.sequence()
[5, 8, 9, 12]
testing.subseq
[None, None, 1, None, 2, 3, 4, 4]
testing.subprob(7)
testing.dp
[1, 1, 2, 1, 3, 2, 4, 4]
testing = Solution([3, 4, -1, 0, 6, 2, 3])
testing.solve()
4
testing.dp
[1, 2, 1, 2, 3, 3, 4]
testing.sequence()
[-1, 0, 2, 3]
testing = Solution([2, 5, 1, 8, 3])
testing.solve()
3
testing.sequence()
[2, 5, 8]
the_data = [0, 4, 12, 2, 10, 6, 9, 13, 3, 11, 7, 15]
testing = Solution(the_data)
testing.solve()
6
testing.sequence()
[0, 2, 6, 9, 11, 15]
the_data = [-1, 5, 7, 3, 12, 4, 9]
testing = Solution(the_data)
testing.solve()
4
testing.sequence()
[-1, 5, 7, 12]
Our guest Youtuber 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.
From the Leetcode site:
Constraints:
python:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 2**31 - 1
Implementation Hint:
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.
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
[fib(n) for n in range(16)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]
fib.cache_info()
CacheInfo(hits=28, misses=16, maxsize=None, currsize=16)
For practice with numpy, lets make use of the numpy ndarray type object for our matrix.
Is the code below a valid max path finder? It's based on some of the Leetcode discussion.
Idea: feed it some simple test data from pre-existing problems. The challenge is to use numpy.
import numpy as np
matrix = np.random.randint(0, 20, 25).reshape(5,5)
matrix
array([[ 8, 2, 2, 0, 13], [ 8, 15, 5, 2, 15], [15, 1, 7, 18, 1], [12, 13, 11, 7, 10], [14, 17, 12, 13, 15]])
matrix[(0, 3)]
0
path_length = np.zeros(matrix.size, dtype=int).reshape(matrix.shape)
def around_me(matrix, path_length_matrix, loc):
if path_length[loc] != 0:
return path_length[loc]
length = 1
value = matrix[loc]
i,j = loc
for offset in (i, j+1), (i, j-1), (i+1, j), (i-1, j):
try:
if value < matrix[offset]:
path = 1 + around_me(matrix, path_length_matrix, offset)
if path > length:
length = path
except IndexError: # out of bounds, index error
pass
path_length_matrix[loc] = length
return length
path_length
array([[0, 0, 7, 8, 2], [0, 1, 6, 7, 1], [0, 0, 5, 1, 0], [0, 2, 4, 0, 0], [0, 1, 3, 2, 1]])
around_me(matrix, path_length, (0,3))
8
matrix
array([[ 8, 2, 2, 0, 13], [ 8, 15, 5, 2, 15], [15, 1, 7, 18, 1], [12, 13, 11, 7, 10], [14, 17, 12, 13, 15]])
def driver():
path_length = np.zeros(matrix.size, dtype=int).reshape(matrix.shape)
record = 0
for i in range(matrix.shape[0]):
for j in range(matrix.shape[1]):
path = around_me(matrix, path_length, (i, j))
if path > record:
record = path
return record
driver()
8
class Solution:
def longestIncreasingPath(self, matrix):
max_len = 0
return max_len
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.
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):
1 + 2 + 3 + ... + 100
100 + 99 + 98 + ... + 1 <-- same 100 terms in reverse
---------------------------
101 + 101 + 101 + ... + 101
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.
So a more general way of writing the solution is:
1 + 2 + 3 + ... + N
N + N-1 + N-2 + ... + 1 <-- same N terms in reverse
N+1 + N+1 + N+1 + ... + N+1
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:
Sum of N consecutive integers = $N (N+1) / 2$
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$.
Think of asking yourself this question: with N people in a room, how many ways may two people shake hands?
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.
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.
Source: Getting Serious about Series
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.
Think of polyhedrons in terms of Graph Theory: nodes connected by edges, defining circuits, such as faces.
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.
Four faces times three edges is twelve edges, divided by two, gives us six edges in a tetrahedron.
Six faces times the four edges of the cube, divided by two, gives the twelve edges of the cube.
Eight faces times three edges is twenty-four, divided by two, gives the twelve edges in an octahedron.
Twenty faces times three edges is sixty, divided by two, gives the thirty edges of the icosahedron.
Twelve faces times five edges is sixty, divided by two, gives the thirty edges of the pentagonal dodecahedron.
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.
For additional discussion of Polyhedra, see use Sandbox on building a data structure / nested hierarchy.
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.
import numpy as np
import pandas as pd
cols = np.array(range(5))
rows = np.array((10, 20, 30))
pd.DataFrame(np.multiply.outer(rows, cols), index = rows, columns = cols)
0 | 1 | 2 | 3 | 4 | |
---|---|---|---|---|---|
10 | 0 | 10 | 20 | 30 | 40 |
20 | 0 | 20 | 40 | 60 | 80 |
30 | 0 | 30 | 60 | 90 | 120 |
num_cows = 4
cows = "1 2 3 4"
barns = "2 4 3 4"
ans = 8
import numpy as np
from itertools import permutations
the_cows = np.array(cows.split(), dtype=int)
the_barns = np.array(barns.split(), dtype=int)
table = np.less_equal.outer(the_cows, the_barns)
print(table)
total = 0
rows = range(num_cows)
for perm in permutations(range(num_cows), num_cows):
total += sum(table[rows,perm]) == num_cows
print(total)
[[ True True True True] [ True True True True] [False True True True] [False True False True]] 8
pd.DataFrame(np.less_equal.outer(the_cows, the_barns), index = the_cows, columns = the_barns)
2 | 4 | 3 | 4 | |
---|---|---|---|---|
1 | True | True | True | True |
2 | True | True | True | True |
3 | False | True | True | True |
4 | False | True | False | True |
num_cows = 4
cows = "1 2 3 4"
barns = "2 4 3 4"
ans = 8
def get_data(file_name):
with open("./usaco/bronze_jan_2021/prob3/"+file_name) as testfile:
num_cows = int(testfile.readline()[:-1])
cows = testfile.readline()[:-1]
barns = testfile.readline()[:-1]
return num_cows, cows, barns
def get_out(file_name):
with open("./usaco/bronze_jan_2021/prob3/"+file_name) as testfile:
answer = testfile.read()
return int(answer)
def make_combo(a, b):
if type(a) == list:
return a + [b]
return [a, b]
def solve(rows):
combos = [make_combo(i, j) for i in rows[0] for j in rows[1]]
combos = [c for c in combos if len(c) == len(set(c))]
for row in rows[2:]:
combos = [make_combo(c, j) for c in combos for j in row]
combos = [c for c in combos if len(c) == len(set(c))]
print(len(combos))
return len(combos)
def get_tally(cows, barns):
cows = [int(x) for x in cows.split()]
barns = [int(x) for x in barns.split()]
numcows = len(cows)
rows = []
for cow in cows:
rows.append([rnum for rnum in range(numcows)
if cow <= barns[rnum]])
rows = sorted(rows, key=lambda r: len(r))
answer = solve(rows)
return answer
def check_all():
for x in range(1, 12):
check_one(x)
def check_one(x):
if x >= 6:
raise ValueError("code will stall at this level")
print(f'Testing file {x}')
infile = str(x)+".in"
outfile = str(x)+".out"
num_cows, cows, barns = get_data(infile)
the_tally = get_tally(cows, barns)
print("Number:", the_tally)
print("Answer:", get_out(outfile))
check_one(1)
Testing file 1 8 8 Number: 8 Answer: 8
! pwd
/Users/mac/Documents/elite_school
check_one(2)
Testing file 2 18 72 288 864 1728 1728 Number: 1728 Answer: 1728
check_one(3)
Testing file 3 12 12 24 24 24 24 Number: 24 Answer: 24
check_one(4)
Testing file 4 80 400 1600 4800 9600 9600 Number: 9600 Answer: 9600
"""
http://usaco.org/index.php?page=viewproblem2&cpid=1083
abcdefghijklmnopqrstuvwxyz
mood
3
"""
from usaco.prob3 import get_passes
def get_data(file_name):
with open("./usaco/bronze_jan_2021/prob1/"+file_name) as testfile:
cowphabet = testfile.readline()[:-1]
overhears = testfile.readline()[:-1]
return cowphabet, overhears
def get_out(file_name):
with open("./usaco/bronze_jan_2021/prob1/"+file_name) as testfile:
answer = testfile.read()
return int(answer)
def check_all():
for x in range(1, 10):
check_one(x)
def check_one(x):
print(f'Testing file {x}')
infile = str(x)+".in"
outfile = str(x)+".out"
calpha, hears = get_data(infile)
the_tally = get_passes(calpha, hears)
print("Number:", the_tally)
print("Answer:", get_out(outfile))
check_all()
Testing file 1 Number: 3 Answer: 3 Testing file 2 Number: 496 Answer: 496 Testing file 3 Number: 530 Answer: 530 Testing file 4 Number: 514 Answer: 514 Testing file 5 Number: 459 Answer: 459 Testing file 6 Number: 516 Answer: 516 Testing file 7 Number: 515 Answer: 515 Testing file 8 Number: 524 Answer: 524 Testing file 9 Number: 482 Answer: 482