15-110: Principles of Computing

15-110 Spring 2011 Homework 2
Due Sunday, 30-Jan, at 10pm

Same basic directions as hw1, so read those carefully (replacing "hw1" with "hw2", where appropriate, of course).

Additional notes (read these carefully):

Start with hw2.zip, which contains starter files with important test code for all the non-bonus questions. Download this file and unzip it to start your hw. Do not change the names of those files and do not change the names of the functions in those files!
When you are ready to submit hw2, place Hw2.txt (or whatever you call your free-response file) and your bonus answers in the hw2 folder, zip it up, and submit hw2.zip as your one and only file to Autolab.
Note that the test code we provide you is not necessarily complete. We typically use more test cases when we grade your submissions. You may elect to add more test cases on your own, though, to help you test your solutions.
Note that docx format will no longer be accepted (for all future hw's). If you use Word, save your files in doc and not docx format.
Portions marked SOLO must be solved entirely on your own (you may discuss with course staff, but not with each other or any outside sources). See syllabus for details.
This week, you may not use "if" statements (conditionals), "for" or "while" statements (loops), recursion, or collections (lists, dictionaries, etc). Since we have not covered these yet, this should not be a concern for most of you. That said, solutions that use "if", "for", "while", etc, will receive half credit for those portions.
Unless indicated otherwise, you are not responsible for malformed input. For example, in Rock Paper Scissors, you can assume the inputs are always "rock", "paper", or "scissors".

Hints:

We used "find" several times in our sample solutions. For example, "abcdefg".find("c") returns 2. Very handy.
We also used abs, min, max, and, or, + (string concatenation), /, %, and slicing (s[i:j]), which you might also find useful.
We also used several "helper functions". If you find yourself doing something repeatedly, you should place that logic in its own function that you can call repeatedly. We call that a "helper function".

Practice:

To help you get started, here are some hw2 practice problems (with solutions and short video tutorials)
Also, the first video in those practice problems shows how to get started on hw2. Check it out!

SOLO Problem-Solving (with Data and Expressions) [35 pts]

SOLO Rock Paper Scissors Winner [10 pts]
Write the function rockPaperScissorsWinner (in the file hw2-solo.py). This function takes two strings, where each string is one of "rock", "paper", or "scissors". The function returns True if the first player wins in a game of Rock, Paper, Scissors, and False otherwise. Who wins? Rock beats scissors, scissors beats paper, and paper beats rock. No other combinations win. Here are some test cases for you:

    assert(rockPaperScissorsWin("rock", "rock") == False)
    assert(rockPaperScissorsWin("rock", "scissors") == True)
    assert(rockPaperScissorsWin("scissors", "rock") == False)
SOLO Simple Pig Latin [10 pts]
Write the function simplePigLatin (in the file hw2-solo.py). This function takes a single string made up of two lowercase words (each with at least one letter in them) separated by one space. The function returns a string with the same two words converted to a simple kind of "Pig Latin". To convert a word to Pig Latin, move the first letter to the end and then add "ay". Do this for each word. Thus, "go team" becomes "ogay eamtay". To keep things simple, make no distinction for words starting with vowels or consonants. Here are some test cases for you:

    assert(simplePigLatin("go team") == "ogay eamtay")
    assert(simplePigLatin("pig latin") == "igpay atinlay")
    assert(simplePigLatin("i see") == "iay eesay")
    assert(simplePigLatin("oh my") == "hoay ymay")
SOLO Dovetail [15 pts]
Background: consider all the (x,y) points in the first quadrant:

... ... ... ... ... ...
(0,4) (1,4) (2,4) (3,4) (4,4) ...
(0,3) (1,3) (2,3) (3,3) (4,3) ...
(0,2) (1,2) (2,2) (3,2) (4,2) ...
(0,1) (1,1) (2,1) (3,1) (4,1) ...
(0,0) (1,0) (2,0) (3,0) (4,0) ...

Say we wanted to label all of these (x,y) points in some order using the positive integers (why? for now, just for the fun of it, though later in the course we'll make use of this technique to prove some amazing things). We could try to number them horizontally, like so:

... ... ... ... ... ...
(0,4) (1,4) (2,4) (3,4) (4,4) ...
(0,3) (1,3) (2,3) (3,3) (4,3) ...
(0,2) (1,2) (2,2) (3,2) (4,2) ...
(0,1) (1,1) (2,1) (3,1) (4,1) ...
1(0,0) 2(1,0) 3(2,0) 4(3,0) 5(4,0) ...

Unfortunately, this will fail because we will never finish labeling points on the x-axis alone, so we will never number any points above the x-axis. No good!

Instead, we can label on increasing diagonals away from the origin, like so:

...   ...   ... ...   ... ...
11(0,4)   (1,4)   (2,4) (3,4)   (4,4) ...
7(0,3) 12(1,3)   (2,3) (3,3)   (4,3) ...
4(0,2) 8(1,2) 13(2,2) (3,2)   (4,2) ...
2(0,1) 5(1,1) 9(2,1) 14(3,1) (4,1) ...
1(0,0) 3(1,0) 6(2,0) 10(3,0) 15(4,0) ...

We added colors for each diagonal to make this clearer. We start with the yellow diagonal, which has just 1 pair in it, (0,0), which we label pair #1. We proceed to the green diagonal, labeling (0,1) with 2, and then (1,0) with 3. Next is the cyan diagonal, labeling (0,2) as 4, (1,1) as 5, and (2,0) as 6. Then the orange diagonal for points 7 through 10. Then the purple diagonal for points 11 through 15. And so on.

In this way, if we were patient enough and kept adding more and more diagonals, we could assign a unique integer to every single (x,y) pair in the first quadrant. This sort of encoding of two integers into a single integer is a form of dovetailing.

Your task: Write the function doveTail (in the file hw2-solo.py). This function takes two integers x and y, and returns the integer label for that (x,y) pair. Here are some test cases for you (with colors matching the example table above):

    assert(doveTail(0,0) == 1)
    assert(doveTail(0,1) == 2)
    assert(doveTail(1,0) == 3)
    assert(doveTail(0,2) == 4)
    assert(doveTail(1,1) == 5)
    assert(doveTail(2,0) == 6)
    assert(doveTail(0,3) == 7)
    assert(doveTail(1,2) == 8)
    assert(doveTail(2,1) == 9)
    assert(doveTail(3,0) == 10)
    assert(doveTail(0,4) == 11)
    assert(doveTail(1,3) == 12)

Hints:

Notice that the sum of (x + y) is constant along each diagonal of (x,y) pairs. For example, the (x,y) pairs in the orange column all add to 3. The pairs in the purple column all add to 4.
Also notice that there is 1 pair on the first diagonal, 2 pairs on the second, and so on. So, how many total (x,y) pairs are there on the first D diagonals?
Finally, you may wish to use this formula: 1 + 2 + ... + N = N(N+1)/2

Collaborative Problem-Solving (with Data and Expressions) [45 pts]

Int to Playing Card [10 pts]
Background: In week 1, we considered how to include a Playing Card in the Data Abstraction Hierarchy. Then, in week 2 lecture and/or recitation, we wrote a function that converts a Playing Card into a single integer (the problem with a sample solution can be found here). Here, you will write this conversion in the opposite direction, converting an integer back into a Playing Card.

Your task: Write the function intToPlayingCard (in the file hw2-collab.py). This function takes an integer that is the result of encoding a Playing Card as we described at the link above, and returns the 2-character string representation of that same card.   Here are some test cases for you:

    assert(intToPlayingCard(0) == "2C")
    assert(intToPlayingCard(12) == "AC")
    assert(intToPlayingCard(13) == "2D")
    assert(intToPlayingCard(25) == "AD")
    assert(intToPlayingCard(26) == "2H")
    assert(intToPlayingCard(38) == "AH")
    assert(intToPlayingCard(39) == "2S")
    assert(intToPlayingCard(51) == "AS")
Note Step [10 pts]
Background: This problem and the next problem concern musical notes. There are 12 such notes in an octave. We can label these as such:
C, C#, D, D#, E, F, F#, G, G#, A, A#, B
Here, we pronounce "C#" as "C sharp", and it is the note between C and D (on the piano keyboard, the sharps are the black keys). Every sharp note can also be represented as a flat note (for example, "Bb" is "B flat"), where "C#" is the same note (just labeled differently) as "Db", "D#" is the same as "Eb", and so on. So we can also label the notes as such:
C, Db, D, Eb, E, F, Gb, G, Ab, A, Bb, B

Your task: write the function noteStep (in the file hw2-collab.py). This function takes a string representing one musical note (perhaps with a sharp or flat), and returns the number of steps (technically, half-steps or semi-tones) that one must take to get to that note starting from C. So here are the test values for every output:

    assert(noteStep("C") == 0)
    assert(noteStep("C#") == 1)
    assert(noteStep("Db") == 1)
    assert(noteStep("D") == 2)
    assert(noteStep("D#") == 3)
    assert(noteStep("Eb") == 3)
    assert(noteStep("E") == 4)
    assert(noteStep("F") == 5)
    assert(noteStep("F#") == 6)
    assert(noteStep("Gb") == 6)
    assert(noteStep("G") == 7)
    assert(noteStep("G#") == 8)
    assert(noteStep("Ab") == 8)
    assert(noteStep("A") == 9)
    assert(noteStep("A#") == 10)
    assert(noteStep("Bb") == 10)
    assert(noteStep("B") == 11)

Hint: Remember that you may not use "if" statements this week!
Note Distance [10 pts]
Background: we will define the distance between two notes as the minimum number of steps required to get from one note to the other. There is this minor complication: the 12 notes listed above actually appear repeatedly as one octave after another, and when computing note distances, you should consider the possibility of using notes from different octaves. So, for example, C and B seem to be 11 step apart. Only if we start at C and go down 1 step, we will reach the B from the preceding octave. And so C and B are only 1 step apart.

Your task: write the function noteDistance (in the file hw2-collab.py). This function takes two strings representing two different notes, and returns the distance in steps between these two notes. Here are some test cases for you:

    assert(noteDistance("G", "G") == 0)
    assert(noteDistance("G#", "Ab") == 0)
    assert(noteDistance("C", "B") == 1)
    assert(noteDistance("B", "C") == 1)
    assert(noteDistance("C#", "A#") == 3)
    assert(noteDistance("Db", "A#") == 3)
    assert(noteDistance("A#", "C#") == 3)
    assert(noteDistance("C", "F#") == 6)
    assert(noteDistance("C", "Gb") == 6)
    assert(noteDistance("C", "G") == 5)

Hint: you may find it helpful to call your noteStep function from your noteDistance function.
Is Drivable [15 pts]
Write the function isDrivable (in the file hw2-collab.py). This function takes a string containing between 1 and 5 2-letter state abbreviations separated by dashes. For example, the string "PA-NY-MA" represents a path starting in Pennsylvania (PA), heading through New York (NY), and ending in Massachusetts (MA). This path is drivable because each state borders the next state in the list. By contrast, the path "PA-MA-NY" is not drivable, since Pennsylvania does not border Massachusetts. Your function should return True if the given path is drivable, and False otherwise. To keep things manageable, you are only responsible for the 9 northeastern states (Pennsylvania, New York, New Jersey, Connecticut, Rhode Island, Massachusetts, Vermont, New Hampshire, and Maine). Here are some test cases for you:

    assert(isDrivable("PA") == True)
    assert(isDrivable("PA-NY-VT") == True)
    assert(isDrivable("PA-VT-NY") == False)
    assert(isDrivable("NY-PA-NJ-NY-MA") == True)
    assert(isDrivable("NY-PA-NJ-NY-ME") == False)

Hint: You may wish to write a helper function here, say one that takes two states and returns True if those states are neighbors and False otherwise. Also, you need to deal with paths that have fewer than 5 states (and then without using "if" statements) -- that's the hard part of the problem!

Readings in Computational Thinking [20 pts]

A Journalist's Introduction to Computational Thinking [10 pts]
Read “A journalist’s introduction to computational thinking” by Kim Pearson (scroll down the page a little to view this article). In that article, she lists 10 traditional practices in journalism that are increasingly informed by computational thinking. List the 3 items in this list that you found most compelling, and briefly explain why.
The Value of a Computer Science Education [10 pts]
Read “The Value of a Computer Science Education” by Kevin Carey. In that article, he says: “Writing, in other words, is just coding by a different name.” Explain.

Bonus/Optional: inverseDoveTail [3 pts]
The dovetailing process we used earlier in this assignment to map (x,y) pairs to integers is reversible: that is, we could take these single integers and turn them back into the original (x,y) pairs. Write the function inverseDoveTail (in the file hw2.collab.py) that does just that: it takes a non-negative integer and returns the corresponding (x,y) pair. To return a pair of numbers, place them in parentheses (what Python calls a tuple).   Here are some test cases for you:

    assert(inverseDoveTail(1) == (0,0))
    assert(inverseDoveTail(2) == (0,1))
    assert(inverseDoveTail(3) == (1,0))
    assert(inverseDoveTail(4) == (0,2))
    assert(inverseDoveTail(5) == (1,1))
    assert(inverseDoveTail(6) == (2,0))
    assert(inverseDoveTail(7) == (0,3))
    assert(inverseDoveTail(8) == (1,2))
    assert(inverseDoveTail(9) == (2,1))
    assert(inverseDoveTail(10) == (3,0))
    assert(inverseDoveTail(11) == (0,4))
    assert(inverseDoveTail(12) == (1,3))

Hint: You might find math.ceil(x) a useful function here (we did).
Bonus/Optional: Week #2 Bonus/Honors Topic [6 pts]
This bonus activity serves two purposes: (1) to expose you to interesting, somewhat more challenging concepts that extend the topics covered in this assignment; and (2) to give you a sense of what the Honors mini will be like (as it will follow this same basic format, with about the same rigor). Total time invested in this activity should be around 1.5 to 2 hours (which is about half the expected time for future Honors assignments), and you must complete the entire activity to receive credit.

Bonus Lecture
A lecture covering this week's bonus topics will be presented on Tuesday 25-Jan at 4:30pm in DH 1212, and should last about 45 minutes (again, about half the expected time for future Honors lectures). Attendance is encouraged but not required (and space may be limited, so we will have a sign-up sheet for those interested). A video of the lecture will be made available (perhaps online or perhaps via DVD's to loan). If you do not attend the lecture, then watch this video (in its entirety and with the same focused attention that you would have in the classroom). Also, here are the lecture notes.
Bonus Assignment

Note #1: Place your answers in the files hw2-bonus.py and hw2-bonus.doc (or whatever other legal extension you wish to use), and add those files to your hw2 folder before zipping it up and submitting hw2.zip. If you do not know how to do this, ask your CA for help.

Note #2: Each part of this bonus assignment is worth 3 points, and you may submit one or both parts for credit.

An infinite set is countable if you can provide a one-to-one mapping to the positive integers. We said that the entire set of integers (positive, zero, and negative) are countable. Here, you will count them and then provide Python functions to do the mapping and the reverse mapping.

First, figure out how you can (invertibly) map the entire set of (possibly-negative) integers onto the set of positive integers. Whatever mapping you use, all the domain values between -K and +K (inclusive) must map to range values between 1 and (2K+1) (also inclusive), for any value K. Then, answer these questions:

Describe in a sentence or two of English how your mapping works.
What will 0 map to?
What will +1 map to?
What will -1 map to?
What will +K map to?
What will -K map to?
List, in order, the values that will map to 1, 2, 3, 4, and 5.

Write the (invertible) function integerToPositiveInteger, that takes a possibly-negative integer and returns the corresponding positive integer in your mapping.
Write the function positiveIntegerToInteger, that inverts the previous function, undoing the mapping. Thus, this must be true:
integerToPositiveInteger(positiveIntegerToInteger(K)) == K # for all K in the positive integers
and
positiveIntegerToInteger(integerToPositiveInteger(K)) == K # for all K in the (possibly-negative) integers
Write the two test functions testIntegerToPositiveInteger and testPositiveIntegerToInteger. Be thorough in your testing. For example, you may use loops in some interesting way.
Finally, combine your work here with your work on doveTail in hw2 to write the function z2ToInteger that counts Z² (that is, the ordered pairs (x,y) of (possibly-negative) integers). That is, this function takes two (possibly-negative) integers and (invertibly) map them to the positive integers. You should be able to write this function in one line if you use the other functions properly. Fascinating!

Write a short (no more than half a page) English description of the Halting Problem, written for a lay audience. Describe the problem, the reasoning behind the proof that there is no possible solution, and the implications in a way that someone without a technical background could understand and appreciate.