CMU 15-112 Fall 2017: Fundamentals of Programming and Computer Science
Lab 9 (Due Thursday 26-Oct, at 10pm)

This lab is Collaborative. No solo work allowed!. Work in groups of 2-3 (and the same group the whole time). See the syllabus for more details. Be sure to list your collaboration partners (name and andrew id) in a comment on the first line of your submitted file.
Even though this is collaborative, you may not directly copy any code from anyone, and you may not electronically share your code with anyone.
Be a good lab partner! Help everyone in your lab group, and accept their help if you need it. Don't be in a hurry to finish the problems. Instead, take your time and be sure that everyone in the lab group is following and understanding. The goal is to learn, not just to finish.
Please use the starter file, which contains tests for the OOP question: lab9.py
You should make use of this week's linter: cs112_f17_week9_linter.py
This week you may use up to 5 submissions. Only your last submission counts.
Do not use for loops or while loops this week.
Do not hardcode the test cases in your solutions.
As usual, there are no late days for this lab.

Group Form [5 pts]:
Fill out one form found here. This is due Thursday by 11:59pm. Even if you work on the lab alone (which you shouldn't do), you should still fill out the form, and simply enter your name without any partner scores.

If you need a new group, fill out this form to be assigned to one.

recursive alternatingSum(L) [15 pts] [autograded]
Write the function alternatingSum(L) that takes a possibly-empty list of numbers, L, and returns their alternating sum, where every other value is subtracted rather than added. For example:
alternatingSum([1,2,3,4,5]) returns 1-2+3-4+5 (that is, 3)
If L is empty, return 0.

recursive powersOf3ToN(n) [20 pts] [autograded]
Write the function powersOf3ToN(n) that takes a possibly-negative float or int n, and returns a list of the positive powers of 3 up to and including n, or None (not an empty list) if no such values exist. As an example, powersOf3ToN(10.5) returns [1, 3, 9].

recursive binarySearchValues(L, v) [20 pts] [autograded]
Write the function binarySearchValues(L, v) that takes a sorted list L and a value v and returns a list of tuples, (index, value), of the values that binary search must check to verify whether or not v is in L. As an example, say:
```
   L = ['a', 'c', 'f', 'g', 'm', 'q']
   v = 'c'
```
Binary search always searches between some lo and hi index, which initially are 0 and (len(L)-1). So here, lo=0 and hi=5. The first index we try, then, is mid=2 (the integer average of lo and hi). The value there is 'f', so we will add (2, 'f') to our result.

Since 'f' is not the value we are seeking, we continue, only now we are searching from lo=0 to hi=1 (not hi=2 because we know that index 2 was too high!).

Now we try mid=0 (the integer average of lo and hi), and so we add (0, 'a') to our result.

We see that 'a' is too low, so we continue, only now with lo=1 and hi=1. So we add (1, 'c') to our result. We found 'c', so we're done. And so we see:
```
    L = ['a', 'c', 'f', 'g', 'm', 'q']
    v = 'c'
    assert(binarySearchValues(L, v) == [(2,'f'), (0,'a'), (1,'c')])
```
Hint: Do not slice the list L, but rather adjust the indexes into L.

Book class [40 pts] [autograded]
Write the Book class so that it passes testBookClass, and uses the OOP constructs we learned this week as appropriate.

def testBookClass():
    print("Testing Book class...", end="")
    # A Book has a title, and author, and a number of pages.
    # It also has a current page, which always starts at 1. There is no page 0!
    book1 = Book("Harry Potter and the Sorcerer's Stone", 
                 "J. K. Rowling", 309)
    assert(str(book1) == "Book<Harry Potter and the Sorcerer's Stone by " + 
                         "J. K. Rowling: 309 pages, currently on page 1>")
    book2 = Book("Carnegie Mellon Motto", "Andrew Carnegie", 1)
    assert(str(book2) == "Book<Carnegie Mellon Motto by Andrew Carnegie: " +
                         "1 page, currently on page 1>")
                         
    # You can turn pages in a book. Turning a positive number of pages moves
    # forward; turning a negative number moves backwards. You can't move past
    # the first page going backwards or the last page going forwards
    book1.turnPage(4) # turning pages does not return
    assert(book1.getCurrentPage() == 5)
    book1.turnPage(-1)
    assert(book1.getCurrentPage() == 4)
    book1.turnPage(400)
    assert(book1.getCurrentPage() == 309)
    assert(str(book1) == "Book<Harry Potter and the Sorcerer's Stone by " + 
                         "J. K. Rowling: 309 pages, currently on page 309>")
    book2.turnPage(-1)
    assert(book2.getCurrentPage() == 1)
    book2.turnPage(1)
    assert(book2.getCurrentPage() == 1)
    
    # You can also put a bookmark on the current page. This lets you turn
    # back to it easily. The book starts out without a bookmark.
    book3 = Book("The Name of the Wind", "Patrick Rothfuss", 662)
    assert(str(book3) == "Book<The Name of the Wind by Patrick Rothfuss: " + \
                         "662 pages, currently on page 1>")
    assert(book3.getBookmarkedPage() == None)
    book3.turnPage(9)
    book3.placeBookmark() # does not return
    assert(book3.getBookmarkedPage() == 10)
    book3.turnPage(7)
    assert(book3.getBookmarkedPage() == 10)
    assert(book3.getCurrentPage() == 17)
    assert(str(book3) == "Book<The Name of the Wind by Patrick Rothfuss: " + \
                         "662 pages, currently on page 17, page 10 bookmarked>")
    book3.turnToBookmark()
    assert(book3.getCurrentPage() == 10)
    book3.removeBookmark()
    assert(book3.getBookmarkedPage() == None)
    book3.turnPage(25)
    assert(book3.getCurrentPage() == 35)
    book3.turnToBookmark() # if there's no bookmark, don't turn to a page
    assert(book3.getCurrentPage() == 35)
    assert(str(book3) == "Book<The Name of the Wind by Patrick Rothfuss: " + \
                         "662 pages, currently on page 35>")
    
    # Finally, you should be able to compare two books directly
    book5 = Book("A Game of Thrones", "George R.R. Martin", 807)
    book6 = Book("A Game of Thrones", "George R.R. Martin", 807)
    book7 = Book("A Natural History of Dragons", "Marie Brennan", 334)
    book8 = Book("A Game of Spoofs", "George R.R. Martin", 807)
    assert(book5 == book6)
    assert(book5 != book7)
    assert(book5 != book8)
    book5.turnPage(1)
    assert(book5 != book6)
    book5.turnPage(-1)
    assert(book5 == book6)
    book6.placeBookmark()
    assert(book5 != book6)
    print("Done!")

CMU 15-112 Fall 2017: Fundamentals of Programming and Computer Science Lab 9 (Due Thursday 26-Oct, at 10pm)

CMU 15-112 Fall 2017: Fundamentals of Programming and Computer Science
Lab 9 (Due Thursday 26-Oct, at 10pm)