Homework 3 (Due Sat 17-Sep at 8pm)
Important Notes:
- Read the "Important Notes" at the top of hw1. The same general rules apply to all homework unless otherwise specified.
- This homework is solo. You must not collaborate with anyone (besides current course TA's and faculty) in any way. See the syllabus for more details.
- You will need these starter files:
- For this hw, you may submit up to 7 times, but only your last submission counts.
- Do not use lists, list indexing, or recursion this week. Note that looping over s.split(c) or s.splitlines() is allowed, but you may not store the results of those functions in a variable nor index those results -- you may only loop over them.
- Do not hardcode the test cases in your solutions.
Homework3 overview:
- rotateStringLeft [5 pts]
- applyCaesarCipher [10 pts]
- largestNumber [10 pts]
- topScorer [10 pt]
- collapseWhitespace [15 pts]
- patternedMessage [15 pts]
- mastermindScore [15 pts]
- drawFlagOfTheEU [10 pts]
- drawNiceRobot [10 pts]
- Bonus/Optional: topLevelFunctionNames [1 pt]
- Bonus/Optional: getEvalSteps [1 pt]
- rotateStringLeft(s, n) [5 pts]
Note: To receive credit, do not use loops on this specific problem.
Write the function rotateStringLeft(s, n) that takes a string s and a possibly-negative integer n. If n is non-negative, the function returns the string s rotated n places to the left. If n is negative, the function returns the string s rotated |n| places to the right. So, for example:assert(rotateStringLeft('abcd', 1) == 'bcda') assert(rotateStringLeft('abcd', -1) == 'dabc') - applyCaesarCipher(message, shift) [10 pts]
A Caesar Cipher is a simple cipher that works by shifting each letter in the given message by a certain number. For example, if we shift the message "We Attack At Dawn" by 1 letter, it becomes "Xf Buubdl Bu Ebxo".
Write the function applyCaesarCipher(message, shift) which shifts the givenmessagebyshiftletters. You are guaranteed that message is a string, and that shift is an integer between -25 and 25. Capital letters should stay capital and lowercase letters should stay lowercase, and non-letter characters should not be changed. Note that "Z" wraps around to "A". So, for example:assert(applyCaesarCipher("We Attack At Dawn", 1) == "Xf Buubdl Bu Ebxo") assert(applyCaesarCipher("zodiac", -2) == "xmbgya") - largestNumber(s) [10 pts]
Write the function largestNumber(s) that takes a string of text and returns the largest int value that occurs within that text, or None if no such value occurs. You may assume that the only numbers in the text are non-negative integers and that numbers are always composed of consecutive digits (without commas, for example). For example:largestNumber("I saw 3 dogs, 17 cats, and 14 cows!")returns 17 (the int value 17, not the string "17"). AndlargestNumber("One person ate two hot dogs!")returns None (the value None, not the string "None"). - topScorer(data) [10 pts]
Write the function topScorer(data) that takes a multi-line string encoding scores as csv data for some kind of competition with players receiving scores, so each line has comma-separated values. The first value on each line is the name of the player (which you can assume has no integers in it), and each value after that is an individual score (which you can assume is a non-negative integer). You should add all the scores for that player, and then return the player with the highest total score. If there is a tie, return all the tied players in a comma-separated string with the names in the same order they appeared in the original data. If nobody wins (there is no data), return None (not the string "None"). So, for example:data = '''\ Fred,10,20,30,40 Wilma,10,20,30 ''' assert(topScorer(data) == 'Fred') data = '''\ Fred,10,20,30 Wilma,10,20,30,40 ''' assert(topScorer(data) == 'Wilma') data = '''\ Fred,11,20,30 Wilma,10,20,30,1 ''' assert(topScorer(data) == 'Fred,Wilma') assert(topScorer('') == None)Note: You may want to use both splitlines() and split(',') here! Technically, these both return lists. You may use these in loops, as shown in the notes, but you must not index into them or otherwise use them in ways we have not shown you in the notes. - collapseWhitespace(s) [15 pts]
Without using the s.replace() method, write the function collapseWhitespace(s), that takes a string s and returns an equivalent string except that each occurrence of whitespace in the string is replaced by a single space. So, for example, collapseWhitespace("a\t\t\tb\n\nc") replaces the three tabs with a single space, and the two newlines with another single space , returning "a b c". Here are a few more test cases for you:assert(collapseWhitespace("a\nb") == "a b") assert(collapseWhitespace("a\n \t b") == "a b") assert(collapseWhitespace("a\n \t b \n\n \t\t\t c ") == "a b c ")Once again, do not use s.replace() in your solution. - patternedMessage(message, pattern) [15 pt]
Write the function patternedMessage(message, pattern) that takes two strings, a message and a pattern, and returns a string produced by replacing the non-whitespace characters in the pattern with the non-whitespace characters in the message. As a first example:
call result patternedMessage("Go Pirates!!!", """ *************** ****** ****** *************** """)GoPirates!!!GoP irates !!!GoP irates!!!GoPira
Here, the message is "Go Pirates!!!" and the pattern is a block of asterisks with a few missing in the middle. Notice how the whitespace in the pattern is preserved, but the whitespace in the message is removed. Also, note that any leading or trailing newlines in the pattern are removed. Forgetting to do this is by far the most common source of bugs for this problem.
Here is another example:
call result patternedMessage("Three Diamonds!",""" * * * *** *** *** ***** ***** ***** *** *** *** * * * """)T h r eeD iam ond s!Thr eeDia monds !Th ree Dia m o n
Hint: While you may solve this how you wish, our sample solution did not use replace in any way. Instead, we started with the empy string, and built up the result character by character. How did we determine the next character? Using both the message and the pattern in some way...
Here are two more straightforward examples:
assert(patternedMessage("abc def", "***** ***** ****") == "abcde fabcd efab") assert(patternedMessage("abc def", "\n***** ***** ****\n") == "abcde fabcd efab")
And here is one last example, just for fun:
patternedMessage("Go Steelers!", """ oooo$$$$$$$$$$$$oooo oo$$$$$$$$$$$$$$$$$$$$$$$$o oo$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$o o$ $$ o$ o $ oo o$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$o $$ $$ $$o$ oo $ $ '$ o$$$$$$$$$ $$$$$$$$$$$$$ $$$$$$$$$o $$$o$$o$ '$$$$$$o$ o$$$$$$$$$ $$$$$$$$$$$ $$$$$$$$$$o $$$$$$$$ $$$$$$$ $$$$$$$$$$$ $$$$$$$$$$$ $$$$$$$$$$$$$$$$$$$$$$$ $$$$$$$$$$$$$$$$$$$$$$$ $$$$$$$$$$$$$ $$$$$$$$$$$$$$ '$$$ '$$$'$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ '$$$ $$$ o$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ '$$$o o$$' $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ $$$o $$$ $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$' '$$$$$$ooooo$$$$o o$$$oooo$$$$$ $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ o$$$$$$$$$$$$$$$$$ $$$$$$$$'$$$$ $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ $$$$' '''' $$$$ '$$$$$$$$$$$$$$$$$$$$$$$$$$$$' o$$$ '$$$o '$$$$$$$$$$$$$$$$$$'$$' $$$ $$$o '$$'$$$$$$' o$$$ $$$$o o$$$' '$$$$o o$$$$$$o'$$$$o o$$$$ '$$$$$oo '$$$$o$$$$$o o$$$$' '$$$$$oooo '$$$o$$$$$$$$$' '$$$$$$$oo $$$$$$$$$$ '$$$$$$$$$$$ $$$$$$$$$$$$ $$$$$$$$$$' '$$$' """)
Returns this:
GoSteelers!GoSteeler s!GoSteelers!GoSteelers!GoS teelers!GoSteelers!GoSteelers!GoS te el er s ! Go Steelers!GoSteelers!GoSteelers!GoSteel er s! GoSt ee l e rs !GoSteeler s!GoSteelers! GoSteelers !GoSteel ers!GoSte elers!GoSt eelers!GoSt eelers!GoSt eelers!G oSteele rs!GoSteele rs!GoSteele rs!GoSteelers!GoSteeler s!GoSteelers!GoSteelers !GoSteelers!G oSteelers!GoSt eele rs!GoSteelers!GoSteelers!GoSteelers!GoSteelers!GoSteel ers! GoS teelers!GoSteelers!GoSteelers!GoSteelers!GoSteelers !GoSt eele rs!GoSteelers!GoSteelers!GoSteelers!GoSteelers!GoSt eele rs! GoSteelers!GoSteelers!GoSteelers!GoSteelers!Go Steelers!GoSteele rs!GoSteelers !GoSteelers!GoSteelers!GoSteelers!GoS teelers!GoSteelers !GoSteelers!G oSteelers!GoSteelers!GoSteelers!Go Steel ers! GoSt eelers!GoSteelers!GoSteelers!G oSte elers !GoSteelers!GoSteelers! GoS teel ers!GoSteel ers! GoSte elers !GoSte elers!GoSteele rs!Go Steelers !GoSteelers! GoStee lers!GoSte elers!GoSteeler s!GoSteele rs!GoSteel ers!GoSteele rs!GoSteeler s!GoSteeler s!GoS
Hint: You will almost surely want to print strings to help you debug here, but whitespace can be quite tricky in this problem. So... Instead of usingprint(s)in your debugging, useprint(repr(s)). That way, you can easily see the whitespace. This can make a huge difference in how long this problem takes! We highly recommend using this advice. - mastermindScore(target, guess) [15 pts]
This problem is inspired by the game of Mastermind. We will slightly adapt the game, and then we will not play the entire game, but rather just compute the score for a single guess. Write the function mastermindScore(target, guess) that takes a target string of lowercase letters, like say 'ccba', and then a guess string of the same length and also of lowercase letters, like say 'ddbc', and returns a string describing the matches, with the exact match count first followed by the partial match count.
To do this, we have to compute two different values: the number of characters in the guess that are an exact match -- that is, the same character as the target in the same location. And then we also have to compute the number of characters in the guess that are a partial match -- the right character, but not in the right location. In the example, with a target of 'ccba' and a guess of 'ddbc', 'b' is an exact match, and 'c' is a partial match.
In the example above, we get:assert(mastermindScore('ccba', 'ddbc') == '1 exact match, 1 partial match')If there are multiple matches, report them like so:assert(mastermindScore('abcd', 'aabd') == '2 exact matches, 1 partial match')If there is only one kind of match -- exact or partial -- then leave off the other kind from the report, like so:assert(mastermindScore('efgh', 'abef') == '2 partial matches') assert(mastermindScore('efgh', 'efef') == '2 exact matches')If there are no matches at all, return 'No matches', like so:assert(mastermindScore('ijkl', 'mnop') == 'No matches')Finally, if the two strings are in fact equal, then return 'You win!!!' like so:assert(mastermindScore('wxyz', 'wxyz') == 'You win!!!')Hint: Remember not to include any exactly-matched characters in your computation for partially-matched characters! - drawFlagOfTheEU(canvas, x0, y0, x1, y1) [10 pts] [manually graded]
Write the function drawFlagOfTheEU(canvas, x0, y0, x1, y1) that takes a canvas to draw on, and four values -- x0, y0, x1, y1 -- that describe the rectangular region with left-top at (x0, y0) and right-bottom at (x1, y1). This function should draw the flag of the European Union so that it fills the given rectangular region. Here is that flag:
You should also draw the label "European Union" a bit above the flag. Also note that you may use circles instead of stars. (If you really want to draw stars, you may, but this is considerably harder and won't provide extra points.)
Note: You don't have to be "pixel-perfect" with things like the exact radius of the ring, color matching, etc. Just be visually close, with key details like the number of circles correct. Our solution looks like this:
- drawNiceRobot(canvas, width, height) [10 pts] [manually graded]
Write a function drawNiceRobot(canvas, width, height) that draws a nice robot! This is not meant to be very difficult. We just want to see some really cool robots while grading your homework. Your function must make a drawing using cmu_112_graphics that meets the following criteria:- Easily identifiable as a robot
- Includes at least 10 shapes total, including at least one oval, one rectangle, one non-rectangular polygon, and one line
- Uses at least 4 colors
- Resizes with the canvas. (You may assume that the canvas will always resize proportionally, and you may change the starting proportions in the test case if you want to)
(As a single exception, you may use the function create_arc(...) if you wish, though this is not in the notes. You may read the documentation here.)
Have fun! - Bonus/Optional: topLevelFunctionNames(code) [1 pt]
Write the function topLevelFunctionNames(code) that takes a possibly-multi-line string of Python code, and returns a string with the names of the top-level functions in that code, separated by dots ("."), in the order they appear in the code.
You may assume that the code is syntactically correct, with no non-ascii or non-printable characters in it. You may further assume that every top-level function is defined with a "def" statement, where the "def" is left-flush (so no spaces before the "def"), followed by exactly one space (" "), followed by the function name, followed by no spaces, followed by the open parenthesis for the parameters.
This task is complicated by the fact that there can be multi-line strings in the code, and a "def" inside a multi-line string is not a function definition, and should be ignored.
This is further complicated by the fact that there can be comments (#) in the code, and everything after the comment on that line should be ignored, including any potential string delimiters.
Also, note that comment characters (# or triple-quotes) can appear inside strings, in which case they are not the start of comments, and should be ignored.
Here is a sample test case for you:# f is redefined code = """\ def f(x): return x+42 def g(x): return x+f(x) def f(x): return x-42 """ assert(topLevelFunctionNames(code) == "f.g")And here is another one:# g() is in triple-quotes (""") code = '''\ def f(): return """ def g(): pass""" ''' assert(topLevelFunctionNames(code) == "f") - Bonus/Optional: getEvalSteps(expr) [1 pt]
Write the function getEvalSteps(expr), that takes a string containing a simple arithmetic expression, and returns a multi-line string containing the step-by-step (one operator at a time) evaluation of that expression. For example, this call:getEvalSteps("2+3*4-8**3%3")produces this result (which is a single multi-line string):2+3*4-8**3%3 = 2+3*4-512%3 = 2+12-512%3 = 2+12-2 = 14-2 = 12Here are some considerations and hints:- You are only responsible for legal input as described below. Numbers are limited to non-negative integers.
- Operators are limited to +, -, *, /, //, %, and **.
- All operators are binary, so they take two operands. So there are no unary operators, meaning "-5" is not a legal input. For that, you'd need "0-5".
- In fact, the previous restriction is even stronger: no intermediate value of expr can be negative! So "1-2+3" is not legal, since it would be converted first into "-1+3" which is not legal. So you can safely ignore all such cases.
- There are no parentheses.
- Operators must be evaluated by precedence (** first, then *,/,//,%, then +,-).
- Equal-precedence operators are evaluated left-to-right.
- Evaluation proceeds until a single integer with no operators remains after the equals sign.
- The equal signs must all be stacked directly over each other.
- You may write this however you wish, though you may want to write a helper function that finds the next operator to be applied, and another helper function that just applies a single operator. Something like that. In any case, top-down design is crucial here. And don't forget to thoroughly test your helper functions before using them!
- In our sample solution, we used very few string methods, just "find" and "isdigit". You may use others, but you should not spin your wheels trying to find that awesome string method that will make this problem remarkably easier, as that method does not exist.
- For this function, as any other function, you may not use the eval function, so you will have to write your own equivalent just for the kinds of simple expressions you will deal with here. Eval is dangerous and should be avoided, as it can lead to serious bugs or security holes.