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

Read these instructions first!

This entire hw is strictly SOLO, in the same way hw1-part2, hw2, and hw3 were, so you may not even discuss the problems with any other students or anyone except the course staff.

This week onwards, we grade for style at full value, according to the 15-112 style guide. Style deductions are no longer halved, so you may lose up to 10 points in style.

We will also grade for top-down design and test functions, of course! And you may not use any globals, not even a global canvas.

There is no starter file this week. Submit a single file, hw4.py. Be sure to include your name and andrew id at the top. And be sure to place all the non-autograded problems below the #ignore_rest line!

Starting this week, you may use strings, in addition to graphics, loops, and conditionals, 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 5 submissions max to Autolab. As usual, only your last one counts.

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).

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 ("").

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".

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:

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:

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!

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.

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

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