15-112 Spring 2016 Homework 3
Due Sunday, 31-Jan, at 10pm
Read these instructions first!
- This hw is SOLO. See the syllabus for details.
- There is no starter file this week. Remember: all the code above the #ignore_rest line is autograded, and all the code below it is ignored.
- Starting this week, you may use strings, but (as usual) you may not use constructs we have not yet covered (lists, sets, maps, recursion, etc), unless explicitly allowed below.
- This week you may only make up to 8 submissions max to Autolab. As usual, only your last one counts.
- This week we will start grading for style. As this is the first such week, style deductions will be half-weighted, with a maximum of -5 points deducted for style issues.
-
patternedMessage(message, pattern) [20 pts]
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.
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...
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 - encodeRightLeftCipher(message, rows) [20 pts]
Background: A right-left cipher, a kind of route cipher, is a fairly simple way to encrypt a message. It takes two values, some plaintext and a number of rows, and it first constructs a grid with that number of rows and the minimum number of columns required, writing the message in successive columns. For example, if the message is WEATTACKATDAWN, with 4 rows, the grid would be:
W T A W E A T N A C D T K A
We will assume the message only contains uppercase letters. We'll fill in the missing grid entries with lowercase letters starting from z and going in reverse (wrapping around if necessary), so we have:W T A W E A T N A C D z T K A y
Next, we encrypt the text by reading alternating rows first to the right ("WTAW"), then to the left ("NTAE"), then back to the right ("ACDz"), and back to the left ("yAKT"), until we finish all rows. We precede these values with the number of rows itself in the string. So the encrypted value for the message WEATTACKATDAWN with 4 rows is "4WTAWNTAEACDzyAKT".
With this in mind, write the function encodeRightLeftCipher(message, rows) that takes an all-uppercase message and a positive integer number of rows, and returns the encoding as just described. - decodeRightLeftCipher(encodedMessage) [20 pts]
Write the function decodeRightLeftCipher, which takes an encoding from the previous problem and runs it in reverse, returning the plaintext that generated the encoding. For example, decodeRightLeftCipher("4WTAWNTAEACDzyAKT") returns "WEATTACKATDAWN". - bestStudentAndAvg(gradebook) [20 pts]
Background: for this problem, a "gradebook" is a multiline string where each row contains a student's name (one word, all lowercase) followed by one or more comma-separated integer grades. A gradebook always contains at least one student, and each row always contains at least one grade. Gradebooks can also contain blank lines and lines starting with the "#" character, which should be ignored.
With this in mind, write the function bestStudentAndAvg(gradebook), that takes a gradebook and finds the student with the best average (ignoring the case where there is a tie) and returns a string of that student's name followed by a colon (":") followed by his/her average (rounded to the nearest integer). For example, here is a test case:gradebook = """ # ignore blank lines and lines starting with #'s wilma,91,93 fred,80,85,90,95,100 betty,88 """ assert(bestStudentAndAvg(gradebook) == "wilma:92"))
Note: you most likely will want to use both s.split(",") and s.splitlines() in your solution. - topLevelFunctionNames(code) [20 pts]
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"), following 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 (#) 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) [2 pts]
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.
- Bonus/Optional: bonusDecode [3 pts; 1 pt each]
- Bonus/Optional: bonusDecode1(msg) [1 pt]
For this problem, you are given the function bonusEncode1(msg). This function takes a string, msg, and returns an encoded version of the string. The encoding is fairly straightforward. Your job is to write the corresponding decoder. Specifically, write the function bonusDecode1(msg) so that, for any string s:assert(bonusDecode1(bonusEncode1(s)) == s)
To make things more interesting, you are not given the function bonusEncode1(msg), but rather you are given the result of calling that function on itself, so you have the encoded version of the encoder! You still write the plaintext decoder! Here is the encoded encoder:efg cpovtEodpef1(nth): sftvmu = "" gps d jo nth: jg (d.jtmpxfs()): d = dis(pse('b') + (pse(d) - pse('b') + 1)%26) sftvmu += d sfuvso sftvmuHave fun! - Bonus/Optional: bonusDecode2(msg) [1 pt]
Same basic problem: write bonusDecode2(msg) given this self-encoded version of bonusEncode2(msg):ddd 7jhnkvd1c00N(5aX): 0MZ0QX = "" I = HHEuyq.izinm_nftscoo + kkh7b3.Y2Z0a8 PXZ O MQ SAMEB(GyG(DIv)): e = kpc[c] 1X (R VZ Z): I = R[(O.CEIx(u) - v) % tlt(t)] j5ij9g += U 3P33ZU WIVWMT - Bonus/Optional: bonusDecode3(msg) [1 pt]
Once more: write bonusDecode3(msg) given this self-encoded version of bonusEncode3(msg):100,1,1,-70,66,13,-1,7,-2,-46,41,-11,12,-11, 1,-50,-11,69,6,-12,-62,17,-48,22,0,0,0,82,-13, 14,2,-9,8,-84,29,-29,2,0,-24,22,0,0,0,80, 2,-13,17,-86,29,-29,16,-38,22,0,0,0,70,9,3, -82,73,-73,73,5,-78,82,-17,13,-7,-2,-61,68,-7,9, -70,69,6,-12,-62,0,17,-48,22,0,0,0,0,0,0, 0,67,18,-3,0,-82,29,-29,79,3,-14,-60,69,6,-12, -12,14,-12,-52,-31,22,0,0,0,0,0,0,0,73,-3, -70,8,74,-13,14,2,-9,8,-84,1,28,-29,2,0,7, 17,-26,82,-13,14,2,-9,8,-84,11,18,-29,2,10,-10, -24,22,0,0,0,0,0,0,0,73,-3,-70,8,0,65, -62,6,-8,-9,5,-5,17,4,-21,29,0,-29,16,-7,17, -26,82,-13,14,2,-9,8,-84,11,18,-29,2,58,18,-76, -24,22,0,0,0,0,0,0,0,82,-13,14,2,-9,8, -84,11,18,-29,83,1,-2,-74,59,18,-3,0,-82,13,-13, 80,2,-13,17,-77,-31,22,0,0,0,0,0,0,0,80, 2,-13,17,-86,29,-29,67,18,-3,0,-104,22,0,0,0, 82,-13,15,1,-3,-4,-78,82,-13,14,2,-9,8
- Bonus/Optional: bonusDecode1(msg) [1 pt]