15-112 Fall 2014 Homework 4
Due Monday, 22-Sep, at 10pm

Read these instructions first!
  1. vowelCount(s) [5 pts] [autograded]
    Write the function vowelCount(s), that takes a string s, and returns the number of vowels in s, ignoring case, so "A" and "a" are both vowels. The vowels are "a", "e", "i", "o", and "u". So, for example:
       vowelCount("Abc def!!! a? yzyzyz!")
    returns 3 (two a's and one e).

  2. leastFrequentLetters(s) [10 pts] [autograded]
    Write the function leastFrequentLetters(s), that takes a string s, and ignoring case (so "A" and "a" are treated the same), returns a lowercase string containing the least-frequent alphabetic letters that occur in s, each included only once in the result and then in alphabetic order. So:
       leastFrequentLetters("aDq efQ? FB'daf!!!")
    returns "be". Note that digits, punctuation, and whitespace are not letters! Also note that seeing as we have not yet covered lists, sets, maps, or efficiency, you are not expected to write the most efficient solution. Finally, if s does not contain any alphabetic characters, the result should be the empty string ("").

  3. longestSubpalindrome(s) [10 pts] [autograded]
    Write the function longestSubpalindrome(s), that takes a string s and returns the longest palindrome that occurs as consecutive characters (not just letters, but any characters) in s. So:
       longestSubpalindrome("ab-4-be!!!")
    returns "b-4-b". If there is a tie, return the lexicographically larger value -- in Python, a string s1 is lexicographically greater than a string s2 if (s1 > s2). So:
       longestSubpalindrome("abcbce")
    returns "cbc", since ("cbc" > "bcb"). Note that unlike the previous functions, this function is case-sensitive (so "A" is not treated the same as "a" here). Also, from the explanation above, we see that longestSubpalindrome("aba") is "aba", and longestSubpalindrome("a") is "a".

  4. makeLetterTypePieChart(text, winWidth=500, winHeight=500) [25 pts] [manually graded]
    Write the function makeLetterTypePieChart that takes one required parameter -- some text (which is just a string) -- and two optional parameters, the winWidth and winHeight. The function displays a window of the given size and fills it with a pie chart that indicates the number of vowels, consonants, and other characters in the text, with these constraints:
    1. The fill color for vowels should be pink, consonants should be cyan, and others should be lightGreen.
    2. Do not count whitespace characters at all. Hint: the isspace method can be handy here.
    3. Draw the labels in 12-point Arial bold, formatted exactly as noted in the images below -- the letter type, and then in parentheses, the number of that letter type "of" the total number of non-whitespace characters, a comma, and then that ratio as an integer percentage.
    4. Center the text in the center of the pie wedge.
    5. The pink wedge (if it is present) must start at the vertical, followed counterclockwise by cyan, then lightGreen.
    6. Do not draw a wedge if there are no characters of that type.
    7. If all the characters are of a single type, draw a whole circle, with the label centered in the circle.
    8. If there are no vowels, consonants, or other non-whitespace characters, then display "No data to display" centered in the window, in 20-point Arial bold.
    9. The pie chart should fill 90% of the smaller of the window's width or height.

    For example, this call:
       makeLetterTypePieChart("AB, c de!?!")
    produces this result:


    And this call:
       makeLetterTypePieChart("AB e")
    produces this result:


    And this call:
       makeLetterTypePieChart("A")
    produces this result:


    And this call:
       makeLetterTypePieChart(" ")
    produces this result:


    Note: to do this, you will need to use the canvas.create_arc method. This method takes 4 required parameters, the bounding box of a circle, and then two more named (keyword) parameters -- the start angle of the arc, in degrees, and the so-called extent (or angle from the start angle to the end angle), also in degrees.

    For example, in a 300x300 window, these calls:
       canvas.create_rectangle(100, 100, 250, 250) # to see the bounding box
       canvas.create_arc(100, 100, 250, 250, start=90, extent=45, fill="blue")
    produces this result:


  5. runSimpleTortoiseProgram(program, winWidth=500, winHeight=500) [25 pts] [manually graded]
    In addition to the Tkinter which we all know and love, Python usually comes with another graphics package called "Turtle Graphics", which you can read about here. We will definitely not be using turtle graphics in this problem (and you may not do so in your solution!), but we will instead implement a small turtle-like (or maybe turtle-inspired) graphics language of our own. We'll call it Tortoise Graphics.

    First, we need to understand how Tortoise Graphics programs work. Your tortoise starts in the middle of the screen, heading to the right. You can direct your tortoise with the following commands:

    • color name
      Set the drawing color to the given name, which is entered without quotes, and which can be "red", "blue", "green", or any other color that Tkinter understands. It can also be "none", meaning to not draw.

    • move n
      Move n pixels straight ahead, where n is a non-negative integer, while drawing a 4-pixel-wide line in the current drawing color. If the drawing color is "none", just move straight ahead without drawing (that is, just change the tortoise's location).

    • left n
      Turn n degrees to the left, without moving, where n is a non-negative integer.

    • right n
      Turn n degrees to the right, without moving, where n is a non-negative integer.

    Commands are given one-per-line. Lines can also contain comments, denoted by the hash sign (#), and everything from there to the end-of-line is ignored. Blank lines and lines containing only whitespace and/or comments are also ignored.

    With this in mind, write the function runSimpleTortoiseProgram(program, winWidth=500, winHeight=500) that takes a program as specified above and runs it, displaying a window (which is 500x500 by default) with the resulting drawing from running that program. Your function should also display the tortoise program in that window, in a 10-point font, in gray text, running down the left-hand side of the window (say 10 pixels from the left edge). Don't worry if the program is longer than can fit in the window (no need to scroll or otherwise deal with this). Also, you are not responsible for any syntax errors or runtime errors in the tortoise program.

    For example, this call:
    runSimpleTortoiseProgram("""
    # This is a simple tortoise program
    color blue
    move 50
    
    left 90
    
    color red
    move 100
    
    color none # turns off drawing
    move 50
    
    right 45
    
    color green # drawing is on again
    move 50
    
    right 45
    
    color orange
    move 50
    
    right 90
    
    color purple
    move 100
    """, 300, 400)
    

    produces this result in a 300x400 window:


    And this call:
    runSimpleTortoiseProgram("""
    # Y
    color red
    right 45
    move 50
    right 45
    move 50
    right 180
    move 50
    right 45
    move 50
    color none # space
    right 45
    move 25
    
    # E
    color green
    right 90
    move 85
    left 90
    move 50
    right 180
    move 50
    right 90
    move 42
    right 90
    move 50
    right 180
    move 50
    right 90
    move 43
    right 90
    move 50  # space
    color none
    move 25
    
    # S
    color blue
    move 50
    left 180
    move 50
    left 90
    move 43
    left 90
    move 50
    right 90
    move 42
    right 90
    move 50
    """)
    

    produces this result in a 500x500 window:


  6. getEvalSteps(expr) [25 pts] [autograded]
    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
                 = 12
    

    Here 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.
    • Some more hints and suggestions for this problem will be provided at recitation this week. Don't miss it!


  7. Bonus
    Each of these problems leave some design decisions up to you. They are manually graded, so we allow and encourage some flexibility in your designs. As is typical for bonus, grading will be largely all-or-nothing, though for near-misses we may assign half-credit.

    • Bonus: runTortoiseProgramWithErrorChecking [2.5 pts bonus] [manually graded]
      Write the function runTortoiseProgramWithErrorChecking, that works as above, but also adds the ability to detect and reasonably deal with syntax and runtime errors in the tortoise program. Include in the canvas output some report of the nature of the error and the line of code (in the tortoise program) on which it occurred.

    • Bonus: runTortoiseProgramWithLoops [2.5 pts bonus] [manually graded]
      Write the function runTortoiseProgramWithLoops, that works as above, but also adds loops to the tortoise language spec, and makes them work in your interpreter. For example, to draw a 100x100 square, you would loop 4 times with the body being to move 100 and turn right 90.

    • Bonus: betterGetEvalSteps [2.5 pts bonus] [manually graded]
      Write the function betterGetEvalSteps, that works as getEvalSteps above, but also works with negative numbers and negative intermediate results. Also, add parentheses.