15-112 Spring 2015 Homework 8
Due Monday, 23-Mar, at 10pm

Read these instructions first!

This hw is entirely SOLO.

Starting this week, you may use OOP, exceptions, and recursion, in addition to sets and maps,2d lists, event-based animations, 1d-lists, tuples, strings, graphics, loops and conditionals.

This hw has two parts -- hw8a covers OOP and hw8b covers recursion. Note that you may (and should) use iteration (while and for loops) in hw8a, but you may not use iteration in hw8b. Be sure to submit hw8a.py and hw8b.py separately.

If you know what itertools are, don't use them to get around using recursion. If you don't know what itertools are, you may safely ignore this item.

Portions of this hw are autograded. You may make up to 5 submissions each of hw8a and hw8b. As usual, only your last one counts.

Do not use global variables! Do use test functions! Do use helper functions!

Here are a few important hints:
- You may use eval() and also exceptions (try/except) in csvToObjects.
- As usual, you may not use strings in numeric problems (like nthLeftTruncatablePrime).
- In your recursion problems, you may have stack overflow exceptions after a depth of 50-100 or so. This means your solutions may work for small n, but not for even moderately large n. For example, nthLeftTruncatablePrime(n) may fail around n=51 or so. That is ok for this hw. We'll discuss a workaround for this problem next week.
- As discussed below, we really want you to keep Frogger simple. For instance, you may keep your intersection tests really simple, so for example, if the frog is a circle and the log is a rectangle, then you don't need to do circle-rectangle collision stuff but instead can stick with rectangle-rectangle or even point-rectangle (using the center of the frog) collision if you wish (which you should).
- Also as discussed below, Frogger is underspecified, with lots of small design decisions left to you. So please do not post to piazza asking for us to decide these for you. This is good practice for your term project. Just make good decisions and have confidence in yourself. You can do this!

Hw8a: OOP (iteration allowed)

CA-led mini-lectures [5 pts] [manually graded]
As announced on piazza, as part of hw8, you must attend at least one of these (we'll take attendance, so there's nothing you need to submit as part of hw8 for this). While you only have to attend one session, you may optionally attend as many as you wish. There are some really interesting topics here, so enjoy!!!! And the CA's will lead a bunch more of these lectures in the coming weeks. Great stuff (and thanks, CA's)!

Here are the lectures topics and times. Note that these will be in WEH 7500 unless otherwise noted:
- Tuesday 8pm-9pm: Image Manipulation (analyzing images)
- Tuesday 9pm-10pm: pygame (a powerful Python game platform)
- Wednesday 6pm-7pm: 1-player AI (playing games like 15-puzzle, sudoku, etc)
- Wednesday 7pm-8pm: 2-player AI (playing games like chess, checkers, othello, etc)
- Wednesday 8pm-9pm: OpenCV (using webcams)
- Thursday 7pm-8pm: OpenCV (repeat) in DH 2210
- Sunday 8am-9am: Topic TBD. Meet in Citadel Commons, GHC 5th Floor.
For those who have university-approved conflicts with every single one of these timeslots, you need to contact your professor directly, listing each conflict, in order to be excused from the hw8 requirement.

5-to-10-minute TP meetings [5 pts] [manually graded]
See f14-hw8-#1 for details. These will be 5 minutes, but may expand to 10 minutes at your CA's discretion.

csvToObjects(csv) [10 pts] [autograded]
Write the function csvToObjects(csv) that takes a single string of comma-separated data (as would be saved, say, by a spreadsheet like Excel if you save-as into CSV format), and returns a list of objects (instances of the Struct class) where each object corresponds to a row of data, and values for that row are stored in attributes corresponding to the column labels (which are in the first row of the data). This is less confusing than it sounds, and a test function should clear up any confusions, so look this over carefully:
```
def testCsvToObjects():
    print "Testing csvToObjects()...",
    csv = """\
name,age,gpa
fred,18,3.6
wilma,19,3.8"""
    data = csvToObjects(csv)
    assert(len(data) == 2)
    fred = data[0]
    wilma = data[1]
    assert(fred.name == "fred")
    assert(fred.age == 18)
    assert(fred.gpa == 3.6)
    assert(wilma.name == "wilma")
    assert(wilma.age == 19)
    assert(wilma.gpa == 3.8)
    print "passed!"
```

objectsToCsv(data) [10 pts] [autograded]
Write the function objectsToCsv(objects) that basically works like csvToObjects, only in reverse. That is, it takes a list of objects (which you may assume are all instances of Structs, and all have the same attributes, though with different values), and returns a CSV string, formatted as described above. One thing: the column labels must be alphabetized (check out the example below for details). Again, a test function is invaluable here, so:
```
def testObjectsToCsv():
    print "Testing objectsToCsv()...",
    data = [Struct(name="fred", age=18, gpa=3.6),
            Struct(name="wilma", age=19, gpa=3.8)]
    csv = objectsToCsv(data)
    # note that expected csv must have labels in alphabetical order
    expectedCsv = """\
age,gpa,name
18,3.6,fred
19,3.8,wilma"""
    assert(csv == expectedCsv)
    print "passed!"
```

OOPy Frogger [30 pts] [manually graded]
Write the function playOopyFrogger() that takes no parameters and runs an interactive game of Frogger (see here for details). Actually, your Frogger should be quite simplified: you only need cars (two kinds, that run at different speeds), trucks that are slower than cars, logs of different lengths, and turtles, and each can be drawn with only rectangles or ovals (where each type gets its own unique combination of shape and color, so, say, all the turtles are red circles). You need to use instances of these classes: SlowCar, FastCar, Truck, Log, Turtle (the details of these classes are left for you to decide). Your game must also use our class-based animation, so it must create a class that extends eventBasedAnimation.Animation, as in this week's notes. Many design decisions are left to you. Have fun and be creative, but do not go crazy with this -- it is just one part of one hw. The focus is on OOP more than graphics and great gameplay, so keep it simple, but still make sure that basic gameplay works (so there is a score, a timer, some number of remaining lives, and a hi score, all as in the screenshot at the top of the Wikipedia page). Again, keep your graphics very simple. And have fun!

Bonus/Optional: 3d Tetris [5 pts, manually graded]
Note that this is available to everyone, even if you submitted play3dTetris as earlier bonus. In that case, you may resubmit it here, but you should make at least one clear improvement to it (and include a comment at the top of the file describing that improvement).

Write the function play3dTetris() that takes no arguments and plays a 3d version of Tetris, similar for example to this video. Include a help screen when the user presses 'h', which explains the controls. Do this using Tkinter, so keep the graphics as simple as you can while still looking 3d. Keep your time on this capped to 5 hours or less. Have yet more fun!

Hw8b: Recursion (iteration not allowed!)
Notes:

Every problem in hw8b must be solved using recursion. No iteration is allowed in hw8b.py (no while or for loops, no itertools, etc).

You may (and in some cases really should) use helper functions. You may not use "for" or "while". Some of these are the break-down-into-smaller-problems kind of problems, others are the count-up sort.

For longestSubpalindrome, as we discussed in lecture, you will want to test every possible substring -- you may wish to think about how you would solve this iteratively, and adapt that to a recursive solution.

As usual, you may not use strings in numeric problems (like nthLeftTruncatablePrime).

In your recursion problems, you may have stack overflow exceptions after a depth of 50-100 or so. This means your solutions may work for small n, but not for even moderately large n. For example, nthLeftTruncatablePrime(n) may fail around n=51 or so. That is ok for this hw. We'll discuss a workaround for this problem next week.

nthLeftTruncatablePrime [10 pts] [autograded]
Adapted from f14-hw2. Without using any iteration, write the recursive function nthLeftTruncatablePrime(n). See here for details. So nthLeftTruncatablePrime(0) returns 2, and nthLeftTruncatablePrime(10) returns 53.

carrylessAdd [10 pts] [autograded]
Adapted from f14-hw2. First, read the first page (page 44) from here about Carryless Arithmetic. Fun! Then, without using any iteration, write the recursive function carrylessAdd(x, y) that takes two non-negative integers x and y and returns their carryless sum. As the paper demonstrates, carrylessAdd(785, 376) returns 51.

longestDigitRun [10 pts] [autograded]
Adapted from f14-hw2. Without using any iteration, write the recursive function longestDigitRun(n) that takes an int value n and returns the digit that has the longest consecutive run, or the smallest such digit if there is a tie. So, longestDigitRun(117773732) returns 7 (because there is a run of 3 consecutive 7's).

longestSubpalindrome [10 pts] [autograded]
Adapted from f14-hw4. Without using any iteration, write the recursive 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 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". Note that longestSubpalindrome("") is "".

15-112 Spring 2015 Homework 8 Due Monday, 23-Mar, at 10pm

15-112 Spring 2015 Homework 8
Due Monday, 23-Mar, at 10pm