- destructiveRemoveEvens(L) [5 pts] [autograded]
Write the function destructiveRemoveEvens(L) that takes a possibly-empty
list L that you can assume contains only integers. The function
destructively removes all the even integers from L. As with most
destructive functions, this function returns None.
- nondestructiveRemoveEvens(L) [5 pts] [autograded]
Write the function nondestructiveRemoveEvens(L) that works the
same as the previous function, only this version is
nondestructive, so it does not modify L and it returns a new
list without the evens.
Note: you may not simply call destructiveRemoveEvens() here,
nor can you copy-paste-edit that code. Thus, instead of copying
the list L and then destructively mutating it to get the answer,
you need to build up a new list from scratch.
- areaOfPolygon(L) [10 pts] [autograded]
Write the function areaOfPolygon(L) that takes a list of (x,y) points that are guaranteed to be in either clockwise or counter-clockwise order around a polygon, and returns the area of that polygon, as described
here. For example (taken from that text), areaOfPolygon([(4,10), (9,7), (11,2), (2,2)]) returns 45.5 (at least the result is almostEqual to 45.5).
Here is a sample test function for you:
def testAreaOfPolygon():
print("Testing areaOfPolygon()...", end="")
assert(almostEqual(areaOfPolygon([(4,10), (9,7), (11,2), (2,2)]), 45.5))
assert(almostEqual(areaOfPolygon([(9,7), (11,2), (2,2), (4, 10)]), 45.5))
assert(almostEqual(areaOfPolygon([(0, 0), (0.5,1), (1,0)]), 0.5))
assert(almostEqual(areaOfPolygon([(0, 10), (0.5,11), (1,10)]), 0.5))
assert(almostEqual(areaOfPolygon([(-0.5, 10), (0,-11), (0.5,10)]), 10.5))
print("Passed!")
- evalPolynomial(coeffs, x) [10 pts] [autograded]
Background: we can represent a polynomial as a list of its coefficients. For example, [2, 3, 0, 4] could represent the polynomial 2x**3 + 3x**2 + 4. With this in mind, write the function evalPolynomial(coeffs, x) that takes a list of coefficients and a value x and returns the value of that polynomial evaluated at that x value. For example, evalPolynomial([2,3,0,4], 4) returns 180 (2*4**3 + 3*4**2 + 4 = 2*64 + 3*16 + 4 = 128 + 48 + 4 = 180).
- multiplyPolynomials(p1, p2) [10 pts] [autograded]
Background: we can represent a polynomial as a list of its coefficients. For example, [2, 3, 0, 4] could represent the polynomial 2x3 + 3x2 + 4. With this in mind,
write the function multiplyPolynomials(p1, p2) which takes two lists representing polynomials as just described, and returns a third list
representing the polynomial which is the product of the two. For example, multiplyPolynomials([2,0,3], [4,5]) represents the problem (2x**2 + 3)(4x + 5), and:
(2x**2 + 3)(4x + 5) = 8x**3 + 10x**2 + 12x + 15
And so this returns the list [8, 10, 12, 15].
- solvesCryptarithm(puzzle, solution) [15 pts] [autograded]
Background: a cryptarithm is a puzzle where we start with a simple arithmetic statement but then we replace all the digits with letters (where the same digit is replaced by the same letter each time). We will limit such puzzles to strings the form "A + B = C" (always exactly one space on either side of '+' and '='), where A, B, and C are positive integers. For example, "SEND + MORE = MONEY" is such a puzzle. The goal of the puzzle is to find an assignment of digits to the letters to make the math work out properly. For example, if we assign 0 to "O", 1 to "M", 2 to "Y", 5 to "E", 6 to "N", 7 to "D", 8 to "R", and 9 to "S" we get:
S E N D 9 5 6 7
+ M O R E + 1 0 8 5
--------- ---------
M O N E Y 1 0 6 5 2
And so we see that this assignment does in fact solve the problem! Now, we need a way to encode a possible solution. For that, we will use a single string where the index of the letter corresponds to the digit it represents. Thus, the string "OMY--ENDRS" represents the assignments listed above (the dashes are for unassigned digits).
With this in mind, write the function solvesCryptarithm(puzzle, solution) that takes two strings, a puzzle (such as "SEND + MORE = MONEY") and a proposed solution (such as "OMY--ENDRS"). Your function should return True if substituting the digits from the solution back into the puzzle results in a mathematically correct addition problem, and False otherwise. You do not have to check whether a letter occurs more than once in the proposed solution, but you do have to verify that all the letters in the puzzle occur somewhere in the solution (of course). You may not use the eval() function. Also, you almost surely will want to write at least one well-chosen helper function.
- bestScrabbleScore(dictionary, letterScores, hand) [20 pts] [autograded]
Background: in a Scrabble-like game, players each have a hand, which is a list of lowercase letters. There is also a dictionary, which is a list of legal words (all in lowercase letters). And there is a list of letterScores, which is length 26, where letterScores[i] contains the point value for the ith character in the alphabet (so letterScores[0] contains the point value for 'a'). Players can use some or all of the tiles in their hand and arrange them in any order to form words. The point value for a word is 0 if it is not in the dictionary; otherwise it is the sum of the point values of each letter in the word, according to the letterScores list (pretty much as it works in actual Scrabble).
In case you are interested, here is a list of the actual letterScores for Scrabble:
letterScores = [
# a, b, c, d, e, f, g, h, i, j, k, l, m,
1, 3, 3, 2, 1, 4, 2, 4, 1, 8, 5, 1, 3,
# n, o, p, q, r, s, t, u, v, w, x, y, z
1, 1, 3,10, 1, 1, 1, 1, 4, 4, 8, 4,10
]
Note that your function must work for any list of letterScores that is provided by the caller.
With this in mind, write the function bestScrabbleScore(dictionary, letterScores, hand) that takes 3 lists -- dictionary (a list of lowercase words), letterScores (a list of 26 integers), and hand (a list of lowercase characters) -- and finds the highest-scoring word in the dictionary that can be formed by some arrangement of some set of letters in the hand.
- If there is only one highest-scoring word, return it and its score in a tuple.
- If there are multiple highest-scoring words, return a tuple with two elements: a list of all the highest-scoring words in the order they appear in the dictionary, then the score.
- If no highest-scoring word exists (ie, if no legal words can be formed from the hand), return None instead of a tuple.
The dictionary in this problem is a list of words, and thus not a true Python dictionary (which we haven't taught you and you may not use in this assignment)! It is ok to loop through the dictionary, even if the dictionary we provide is large.
Hint #1: You should definitely write helper functions for this problem! In fact, try to think of at least two helper functions you could use before writing any code at all.
Hint #2 (important!):
Do not create permutations of the letters at all -- that is, do not
try to generate all the possible ways to arrange the hand! If you do, your solution will take too long and Autolab will time out (hence, fail).
Also, you may not use itertools for this problem. In any case,
there's a much simpler way to find all the legal words in the
given dictionary that you can create,
as suggested by the next hint...
Hint #3: We found it enormously helpful
to write a helper function
that takes a word and a hand, and tells whether or not that
word could be constructed using that hand.
How might you use that function to help solve this problem?
- Bonus / Optional: runSimpleProgram(program, args) [up to 2.5 pts] [autograded]
Both of the bonus problems in this hw are a bit more involved,
but are really fun and interesting (or so we think -- we hope you agree!).
Again, these are worth just a few points, so do these for the love of learning.
First, carefully watch
this video that describes this problem:
Then, write the function runSimpleProgram(program, args) that works as described in the video, taking a legal program (do not worry about syntax or runtime errors, as we will not test for those cases) and runs it with the given args, and returns the result.
Here are the legal expressions in this language:
- [Non-negative Integer]
Any non-negative integer, such as 0 or 123, is a legal expression.
- A[N]
The letter A followed by a non-negative integer, such as A0 or A123, is a legal expression, and refers to the given argument. A0 is the value at
index 0 of the supplied args list. It is an error to get or set arg values
that are not supplied. And you may
ignore these errors, as we will not test for them!
- L[N]
The letter L followed by a non-negative integer, such as L0 or L123, is a legal expression, and refers to the given local variable. It is ok
to get an unassigned local variable, in which case its value should be 0.
- [operator] [operand1] [operand2]
This language allows so-called prefix expressions, where the operator
precedes the operands. The operator can be either + or -, and the
operands must each be one of the legal expression types listed above
(non-negative integer, A[N] or L[N]).
And here are the legal statements in this language (noting that
statements occur one per line, and leading and trailing whitespace
is ignored):
- ! comment
Lines that start with an exclamation (!), after the ignored whitespace, are comments and are ignored.
- L[N] [expr]
Lines that start with L[N] are assignment statements, and are followed by the expression (as described above) to be stored into the given local variable. For example:
L5 - L2 42
This line assigns (L2 - 42) into L5.
- [label]:
Lines that contain only a lowercase word followed by a colon are labels, which are ignored except for when they are targets of jump statements.
- JMP [label]
This is a jump statement, and control is transferred to the
line number where the given label is located.
The given label will always exist in our test cases.
- JMP+ [expr] [label]
This is a conditional jump, and control is transferred to the
line number where the given label is located only if the given
expression is positive. Otherwise, the statement is ignored.
- JMP0 [expr] [label]
This is another kind of conditional jump, and control is transferred
only if the given expression is 0.
- RTN [expr]
This is a return statement, and the given expression is returned.
Hints:
- Do not try to translate the program into Python! Even if you could do so, it is not allowed here. Instead, you are
going to write a so-called interpreter. Just keep track of the local variables, and move line-by-line through the program, simulating the
execution of the line as appropriate.
- You will find it useful to keep track of the current line number.
- How long do you run the program? Until you hit a RTN statement! You may assume that will always eventually happen.
- We used strip, split, and splitlines in our sample solution,
though you of course may solve this how you wish.
Finally, here is a sample test function for you. You surely will
want to add some addition test cases. In fact, a hint would be to
build your function incrementally, starting with the simplest test
cases you can think up, which use the fewest expression and statement
syntax rules. Then add more test cases as you implement more of
the language.
def testRunSimpleProgram():
print("Testing runSimpleProgram()...", end="")
largest = """! largest: Returns max(A0, A1)
L0 - A0 A1
JMP+ L0 a0
RTN A1
a0:
RTN A0"""
assert(runSimpleProgram(largest, [5, 6]) == 6)
assert(runSimpleProgram(largest, [6, 5]) == 6)
sumToN = """! SumToN: Returns 1 + ... + A0
! L0 is a counter, L1 is the result
L0 0
L1 0
loop:
L2 - L0 A0
JMP0 L2 done
L0 + L0 1
L1 + L1 L0
JMP loop
done:
RTN L1"""
assert(runSimpleProgram(sumToN, [5]) == 1+2+3+4+5)
assert(runSimpleProgram(sumToN, [10]) == 10*11//2)
print("Passed!")
- Bonus / Optional: Solving Puzzles with Combinatoric Generators [up to 2.5 pts] [autograded]
Note: while this has a long
writeup, don't be daunted! You can do it! And it's really cool.
Also, you can get partial credit for solving just the early
parts of this problem. Enjoy!!!
Here, we will learn about combinatoric generators, then use these
to solve two interesting puzzles: subsetSum and cryptarithms (yes, the
same cryptarithms mentioned above).
- Understanding generators
Consider the following function:
def specialRange(n):
# seemingly the same as range(n), but omits multiples of 3
result = [ ]
for x in range(n):
if (x % 3 != 0):
result.append(x)
return result
This function appears to work the same as range(n), but
omits the multiples of 3. To wit:
for v in specialRange(10):
print(v) # prints 1 2 4 5 7 8
Yep, this looks like it works just fine. But it doesn't!
Let's try that last example again, only with a much larger
range, up to 10**8 say. And we can't print out so many values,
so we'll break after we print the first value, like so:
# this time we'll see a problem....
for v in specialRange(10**8):
print(v)
break
Did you see the problem? There was a huge delay before anything
printed. Why? Because we are constructing an enormous list of values,
and Python must build the whole list before we can use any of it.
At 10**8 that takes a long time. By 10**10 it may take impossibly long,
plus we will also soon run out of memory. So this is clearly
not working well for large n.
As you may have guessed, there is a better way. We can convert
our specialRange function into a generator. Instead of constructing
a list and returning it, we can yield each value that we would
have placed on the list. Python stops running the function at that
point, uses the yielded value, then starts the function right where
it left off to get the next yielded value. Awesome!
To make this work, we simply change our specialRange function from this:
def specialRange(n):
# seemingly the same as range(n), but omits multiples of 3
result = [ ]
for x in range(n):
if (x % 3 != 0):
result.append(x)
return result
To this:
def specialRange(n):
# this time as a generator!
for x in range(n):
if (x % 3 != 0):
yield x
Then re-run the examples above that use specialRange(n),
and you will see that they work
exactly the same with the generator, only there is no delay
at all, even for huge n. Try this:
for v in specialRange(10**50):
# 10**50 is ridiculously huge, yet this still works just fine with a generator
print(v)
break
The generator never creates the list, it just creates one value of
the list at a time. This is a beautiful solution!
- The allSublists(L) generator
Now you get to actually write your own generator! The goal
is to the write the generator allSublists(L) that takes a possibly-empty
list L, and generates all the sublists of L -- that is, all the lists
made up of some (or all) of the elements of L. If L was a set and
not a list, this is what we would call the powerset of L.
Here are some test cases:
assert(sorted(allSublists([1])) == [ [], [1] ])
assert(sorted(allSublists([3, 5])) == [ [], [3], [3, 5], [5] ])
assert(sorted(allSublists([6,7,8])) == [ [], [6], [6, 7], [6, 7, 8],
[6, 8], [7], [7, 8], [8] ])
We include a call to sorted in the test cases because
your generator can produce the sublists in any order (so we sort
them and compare the result to the sorted order).
Now, how to do this? We will first observe that a list with N elements
in it has 2**N sublists (think about that). Then, we realize that we
can have a counter k run from 0 to (2**N)-1, and we can use that counter
to generate the kth sublist. How? By considering k in base 2, and
using 0's to exclude values and 1 to include them in the sublist.
You may have to re-read that a couple times. Plus, an example would help.
Say we have the list L = [5,6,7,8]. Here, N=4, and there are 2**4 or 16 sublists. So we run k from 0 to 15 inclusive. What happens when k is,
say, 13? Well, 13 in base 2 is 1101. We use those 4 digits to determine
whether each of the 4 values of the list L are in this sublist:
L = [ 5, 6, 7, 8 ]
k = 1 1 0 1 (13)
Look at the figure above, and see that there is a 1 under 5, 6, and 8,
and a 0 under 7. So when k==13, the sublist is [5, 6, 8].
Use this technique to write the generator allSublists(L).
Also, as a hint, you probably should write getKthBinaryDigit(n, k),
which works the same as getKthDigit(n, k) only in binary instead of decimal
(basically, change the 10 to a 2 and you're done).
- Solving subsetSum
Ok, now we can use that generator to solve a real problem!
The problem we will try to solve is called subsetSum.
Given a list L, return a sublist of L that sums to 0, or
return None if no such sublist exists. We will discuss this
problem a lot more, later on in this course, since it has
some fascinating properties. For now, we'll just try to
solve it.
How do we solve it? Quite easily at this point, in fact.
We just use the allSublists generator you just wrote, and
check if each sublist sums to 0 (using sum(sublist)).
This should be quick!
One word of caution: while this does solve the problem,
the solution is very slow (in fact, exponentially slow).
So only test it on very small lists.
In any case, the starter file includes testSolveSubsetSum
to help check if you got this step right.
- The heapsAlgorithmForPermutations(L) generator
Ok, so we now understand generators and how they can be
used to solve some kinds of puzzle problems (basically by
trying every possible answer). We'll move on to a new
kind of generator. This time, instead of allSublists, we
are interested in permutations. That is, for a list L,
every possible way to order the values in L.
There are numerous ways to solve this, but we will use a specific
approach: namely, the iterative (non-recursive)
form of Heap's Algorithm. You can read about it
on the linked Wikipedia page if you wish, or not, as you can
do this problem without fully understanding how Heap's
Algorithm works. You just have to translate it into a Python
generator. This is the pseudocode from that website:
procedure generate(n : integer, A : array of any):
//c is an encoding of the stack state. c[k] encodes the for-loop counter for when generate(k+1, A) is called
c : array of int
for i := 0; i < n; i += 1 do
c[i] := 0
end for
output(A)
//i acts similarly to the stack pointer
i := 0;
while i < n do
if c[i] < i then
if i is even then
swap(A[0], A[i])
else
swap(A[c[i]], A[i])
end if
output(A)
//Swap has occurred ending the for-loop. Simulate the increment of the for-loop counter
c[i] += 1
//Simulate recursive call reaching the base case by bringing the pointer to the base case analog in the array
i := 0
else
//Calling generate(i+1, A) has ended as the for-loop terminated. Reset the state and simulate popping the stack by incrementing the pointer.
c[i] := 0
i += 1
end if
end while
Your task here is to closely translate that pseudocode into
the generator heapsAlgorithmForPermutations(L).
Here are some test cases for you:
assert(sorted(heapsAlgorithmForPermutations([1])) == [[1]])
assert(sorted(heapsAlgorithmForPermutations([1,2])) == [
[1,2], [2,1]
])
assert(sorted(heapsAlgorithmForPermutations([3,1,2])) == [
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
])
Important Hint: use yield copy.copy(A)
instead of yield A. This avoids a challenging bug
to find based on aliasing.
- Solving cryptarithms
Ok, we're on the last step! Here, we will use the permutation generator
you just wrote to solve cryptarithms! First, read the solvesCryptarithm
problem above. Here, instead of testing if a solution
solves a cryptarithm, we will find the solution that
solves a cryptarithm. Sweet!
- solveCryptarithm
We will write the function solveCryptarithm(puzzle) like so:
- extract the 3 words from the puzzle (so go from 'SEND + MORE = MONEY' to the list ['SEND', 'MORE', 'MONEY']).
- generate a string of the unique letters in the 3 words in the puzzle (so for 'SEND + MORE = MONEY', this would be 'SENDMORY'
(in any order)).
- augment that string with dashes so it is of length 10 (so
the string above becomes 'SENDMORY--'
- Now we observe that any possible solution to the puzzle
must be a permutation of the string we just made.
This is key. So...
- We use the generator we just wrote to generate every possible
permutation of the string, and we check each one in turn
to see if it does in fact solve the puzzle. If so, we return
it (actually, as you will see in the test cases, we return
a more-nicely-formatted version of it). If none of the permutations
solves the puzzle, then we return None.
That's it. We're done! Except... This runs SO slowly that it is
almost not even testable. Ugh. So... We will modify the problem
a little bit, constraining it so that we can in fact test it.
- solveCryptarithmWithMaxDigit
For that, we will add a maxDigit, and require that the
solution not contain any digits larger than maxDigit. Thus,
we change solveCryptarithm(puzzle) to
become solveCryptarithmWithMaxDigit(puzzle, maxDigit).
This way, we only construct permutations of strings of length
(maxDigit+1), and then we append (10 - (maxDigit+1)) dashes to
those strings to make candidate solutions to use as above.
Read this a few times and think about it!
Here is a test function for you:
def testSolveCryptarithmWithMaxDigit():
print(' Testing solveCryptarithmWithMaxDigit()...', end='')
assert(solveCryptarithmWithMaxDigit('RAM + RAT = ANT', 4) == '''\
RAM + RAT = ANT
120 + 123 = 243''')
assert(solveCryptarithmWithMaxDigit('ANT + CAT = EEL', 4) == None)
assert(solveCryptarithmWithMaxDigit('ANT + CAT = EEL', 5) == '''\
ANT + CAT = EEL
125 + 315 = 440''')
print('Passed!')
- countCryptarithmsWithMaxDigit
Ok, we are getting close. To best test these puzzles, it would
be nice to find puzzles that have a single unique solution (can you
see why?). Ok, let's do that. For this, you will write the function
countCryptarithmsWithMaxDigit(puzzle, maxDigit).
This requires just a tiny change or two to the function
you just wrote,
solveCryptarithmWithMaxDigit(puzzle, maxDigit).
Instead of returning the first match, now you just count all
the matches, and return that count. That's it!
- getAllSingletonCryptarithmsWithMaxDigit
Ok, now we can write the last function for this exercise,
getAllSingletonCryptarithmsWithMaxDigit(words, maxDigit).
This function takes a list of words, from which it will generate
possible puzzles. Then it will call your countCryptarithmsWithMaxDigit function on each such puzzle,
and if the result is 1, then that means that that puzzle has a
single unique solution (with the maxDigit restriction). Great!
We will include that puzzle in our result, which is just a multiline
string of all such puzzles.
Note that your output must list the puzzles in alphabetical order.
Note that 'A + B = C' and 'B + A = C' are considered the same
problem, so only the first would be included in our answer, as
'A' is alphabetically before 'B'.
To do that, our function first sorts the words,
which helped to that end.
We also included 3 nested 'for' loops -- one for each of the 3
words in the puzzle.
Finally, here is a test function you may want to closely study:
def testGetAllSingletonCryptarithmsWithMaxDigit():
print(' Testing getAllSingletonCryptarithmsWithMaxDigit()...', end='')
words = ['EEL', 'RAM', 'CAT', 'BEE', 'FLY',
'HEN', 'RAT', 'DOG', 'ANT']
assert(getAllSingletonCryptarithmsWithMaxDigit(words, 3) == '')
assert(getAllSingletonCryptarithmsWithMaxDigit(words, 4) == '''\
RAM + RAT = ANT
120 + 123 = 243''')
assert(getAllSingletonCryptarithmsWithMaxDigit(words, 5) == '''\
ANT + CAT = EEL
125 + 315 = 440
ANT + CAT = HEN
105 + 315 = 420
ANT + RAT = EEL
125 + 315 = 440
ANT + RAT = HEN
105 + 315 = 420
BEE + EEL = FLY
411 + 112 = 523''')
words = ['DEER', 'BEAR', 'GOAT', 'MULE', 'PUMA',
'COLT', 'ORCA', 'IBEX', 'LION', 'WOLF']
assert(getAllSingletonCryptarithmsWithMaxDigit(words, 5) == '')
assert(getAllSingletonCryptarithmsWithMaxDigit(words, 6) == '''\
BEAR + DEER = IBEX
4203 + 1223 = 5426
COLT + GOAT = ORCA
4635 + 1605 = 6240''')
print('Passed!')
That's it, you made it, you solved two really interesting problems
using two different combinatorial generators. Great job!!!!