Problem Set 6 - Due Tuesday, October 29, 2019


  1. Slides and notebooks from Lec 09 (Iteration 1), Lec 10 (Lists, Memory Diagrams, and Mutable vs. Immutable Sequences), Lec 11 (List Processing Patterns and List Comprehensions), and Lec 12 (Testing and Debugging)
  2. Problems and solutions from Lab 06 (Lists), Lab 07 (List Comprehensions), and Lab 08 (Testing and Debugging).
  3. Think Python, Ch. 8: Iteration
  4. Think Python, Ch. 10: Lists

About this Problem Set

This problem set will give you practice with lists, for and while loops, list comprehensions, testing, and debugging.

In Task 3, having a partner is optional, but strongly recommended. If you want to have a partner, use this shared Google Doc.

All code for this assignment is available in the ps06 folder in the cs111/download directory within your cs server account. This assignment also uses the Codder program to help you do a final check for Tasks 1 and 2 and parts of Task 3 but you are expected to do some of your own testing as well.

Task 0: Scrambled Solutions

This is an individual problem which you must complete on your own, although you can ask for help from the CS111 staff.

This time we have only one puzzle for you to solve to review the solution to problem set 5 task 2. Go to:

CS 111 Puzzles

and select the option under Problem Set 5.

As before, please download and submit your solution files, and email if you run into trouble.

Task 1: Word Search

This task is an individual problem which you must complete on your own, though you may ask for help from the CS111 staff.

Subtask 1a: Mapping, Filtering, and Accumulating with Loops

This task is a continuation of Task 1 from PS05. In that task, you wrote the functions that included isBeauteous, isPrecarious, and scrabbleScore.

You will use these functions to write three new functions that use a list of English words to find and return words that fulfill a certain property, stored in lists and tuples.

Additionally, you will write a function, reverseWords, that takes any sentence as a string of space-separated words, and returns a string where every word is reversed.

Fill out the body of these functions in the file following the contracts in that file.

Notice that the file imports the functions from as well as a list of words from This list is called englishwords, and is the list that your functions must search through.

Sample Executions

In [1]: listBeauteousPrecariousWords(8)
Out[1]: ['sequoias']

In [2]: listBeauteousPrecariousWords(9)
Out[2]: ['behaviour', 'facetious', 'nefarious', 'tenacious', 'veracious', 'vexatious']

In [3]: listBeauteousPrecariousWords(10)
Out[3]: ['abstemious', 'bivouacked', 'gregarious', 'mendacious', 'precarious']

In [4]: listBeauteousPrecariousWords(14)
Out[4]: []

In [5]: listGoodScrabbleWords(35)
Out[5]: [('acquaintanceships', 35), ('compartmentalized', 35),
 ('compartmentalizing', 36), ('cryptographically', 35),
 ('czechoslovak', 35), ('czechoslovakia', 37),
 ('czechoslovakian', 38), ('czechoslovakians', 39),
 ('czechoslovaks', 36), ('electroencephalograph', 36),
 ('electroencephalographs', 37), ('embezzlement', 36),
 ('embezzlements', 37), ('extemporization', 35),
 ('extemporizations', 36), ('jazzily', 35), ('mozambiquean', 36),
 ('mozambiqueans', 37), ('overcapitalizations', 35),
 ('psychoanalytically', 36), ('psychokinetically', 36),
 ('psychopathically', 36), ('quinquagesimas', 35),
 ('quizzed', 35), ('quizzical', 38), ('quizzically', 43),
 ('quizzing', 36), ('schizophrenically', 41),
 ('schizophrenics', 35), ('sympathizingly', 37)]

In [6]: bestScrabbleWord()
Out[6]: ('quizzically', 43)

In [7]: reverseWords('we are never ever getting back together')
Out[7]: 'ew era reven reve gnitteg kcab rehtegot' 


Subtask 1b: Mapping and Filtering with List Comprehensions

In this subtask, you will define three functions named listBeauteousPrecariousWordsLC, listGoodScrabbleWordsLC, and reverseWordsLC that behave exactly like the correspondingly named functions from subtask 1a. The difference is that the function definitions in this subtask must use list comprehensions rather than explicit loops to perform all mapping and filtering on lists.


Ungraded Challenge

For additional ungraded mapping entertainment (use a separate file if you write this code), implement a function called keyboardLeopard that takes three arguments: (1) an arbitrarily long string containing sentences, paragraphs, etc.; (2) a "bad" word to be censored; and (3) a funny word with which to replace the "bad" word. The function must return a version of the first string where every occurrence of the "bad" word is replaced by the funny word. Extend the function to take a list of "bad"/funny word pairs and rewrite the original string to replace all occurrences of each "bad" word with its corresponding funny word in this list of pairs. See here for more inspiration.

Task 2: The Sum Game

This task is an individual problem which you must complete on your own, though you may ask for help from the CS111 staff.

This task involves a simple one-player game that we'll call the Sum Game. The game is parameterized over a positive integer n. The game has two sums named sumA and sumB that are initially 0. At each move of the game, the player is presented with a random integer between between 1 and n (inclusive) and must choose whether to add this number to sumA or sumB. The player wins the game when the two sums are equal.

Here is a transcript of the Sum Game played with 5 as an argument:

In []: sumGame(5)
Welcome to the Sum Game!
Move 1: sumA is 0 and sumB is 0.

Add 3 to sumA or sumB (enter A or B)? A
Move 2: sumA is 3 and sumB is 0.

Add 2 to sumA or sumB (enter A or B)? B
Move 3: sumA is 3 and sumB is 2.

Add 2 to sumA or sumB (enter A or B)? sumB
sumB is not valid. You must enter 'A' or 'B' (or 'a' or 'b'). Try again.

Add 2 to sumA or sumB (enter A or B)? bcd
bcd is not valid. You must enter 'A' or 'B' (or 'a' or 'b'). Try again.

Add 2 to sumA or sumB (enter A or B)? b
Move 4: sumA is 3 and sumB is 4.

Add 3 to sumA or sumB (enter A or B)? A
Move 5: sumA is 6 and sumB is 4.

Add 5 to sumA or sumB (enter A or B)? B
Move 6: sumA is 6 and sumB is 9.

Add 2 to sumA or sumB (enter A or B)? a
Move 7: sumA is 8 and sumB is 9.

Add 1 to sumA or sumB (enter A or B)? A
Both sumA and sumB are 9. You win the game after 7 moves!

Note that the player chooses sumA by entering A or a, and chooses sumB by entering B or b. Any other input (including any longer string beginning with A, a, B, or b) is considered invalid, and the player is prompted to enter another input.

Your task is to flesh out the definition of the sumGame function in to implement this game.




Task 3: Longest Runs

In this problem, having a partner is optional, but is strongly recommended. If you want to find a partner, use this shared Google Doc.

In this task, you will write tests for, debug buggy versions of, and finally write a longestRun function that finds the longest sequence of numbers in a list where each number increases by 1 (which we call a "run"). For example, in the list:

[1, 3, 4, 5, 7, 8, 10]

There are four runs:

The longest run is [3, 4, 5]. If there are multiple runs of the same (longest) length in a sequence, the last one should be returned.

Subtask 3a: Test Cases

Before you start writing longestRun, you should make sure that you thoroughly understand its intended behavior. For example, what does it do when given an empty list? What if there are no runs of more than 1 number? What if the entire sequence is one long run? These kind of questions can be expressed as test cases: examples of input to a program along with desired output. Because our function accepts one input (the list of numbers) and has one output (the longest run, as a list), we can write a test case as a tuple which contains both of these. So the example shown above when written as a test case would be:

([1, 3, 4, 5, 7, 8, 10], [3, 4, 5])

Notice that our tuple just has the argument value as the first element, and the expected/correct result as the second element.

For this subtask, you are required to write six test cases for longestRun. They must include at least:

  1. One test case with an empty list as the input. Notice that the correct output for this case has not been specified in the description of the problem above. We will specify it here: your result for this test case should be an empty list (same as the input).
  2. One test case where none of the numbers in the list forms a run with any adjacent number (equivalently, each item is part of its own length-1 run). This test case must have at least 3 elements.
  3. One test case where the entire list is a run, with at least three elements.
  4. Three more test cases, which can be whatever you want, as long as they aren't the same as any of the required cases above (or each other).

Define each of your test cases as elements of the longestRunTests variable that's defined in the supplied file: that variable should contain a list of seven tuples, each of which have two elements (the six cases you add, plus the original test case that's already present in the file).

Be careful to make sure that you have commas after each element of the longestRunTests list, otherwise Python may think that you are trying to call a function, instead of defining a list of tuples (you are allowed to include a comma after the last element in a list, and you should take advantage of this so that if you add a test case later, you don't need to remember to add a comma to the previous line).

Once you have defined your test cases, run your file through Codder: it will report in detail whether you have defined them correctly. Getting the test cases right is important: if you get them wrong, you won't get the function right either because your test cases will lead you away from the correct answer, which is why we provide a full check of your test cases via Codder.

Subtask 3b: Testing Function

Now that you have test cases, the next step is to write a function that will test your longestRun function when you build it. This function should run each of the test cases in the longestRunTests variable, and report the results, including whether the test passed (the result matched the expected result) or failed (it didn't). For now, let's define a blank version of longestRun so that we can test our testing function: copy the following code into your file.

def longestRun(numbers):
    return [3, 4, 5]

We know that this code will fail all of our test cases, except the example case, so we can use it to test our testing function.

Next, define a function called testLongestRun, which does the following:

  1. It doesn't take any parameters.
  2. Uses a for loop to iterate through the test cases stored in the longestRunTests variable.
  3. For each test case, calls the longestRun function with the parameter from that test case, and compares the result against the expected result specified by that test case.
  4. If the actual output matches the expected output, it will print a version of this exact message that contains the specific input and output for that test case:

    --pass: '[1, 3, 4, 5, 7, 8, 10]' => '[3, 4, 5]'
  5. If the actual output does not match the expected output, it will print a version of this message instead:

    !!FAIL: '[]' => '[3, 4, 5]' (should be '[]')
    • Note that the messages use single quotes to show clearly which parts of the message are inputs and/or outputs, and prints the input, then the actual output, and if the test failed, it finally prints the expected output. The output will be different depending on how you defined your test cases.

When you are done with your testLongestRun function, use Codder to check it. Again, we are giving you detailed Codder feedback because this testing function will help you with the next part of this problem.

Note that your testLongestRun function must operate on the longestRunTests test cases, and it must call the longestRun function.

Subtask 3c: Debugging

Near the bottom of your starter file are six function definitions for different versions of longestRun, named longestRun0 through longestRun5. One of these is the correct implementation, and the rest are somehow incorrect. Your task is to do two things:

  1. Figure out which version is correct using your testLongestRun function.
  2. To figure out why the other versions are incorrect, implement alternative versions of each function which include added print statements.

First, edit your testLongestRun function to call longestRun0 instead of longestRun when it is performing tests. Ideally, your testLongestRun function should only call longestRun once and store the result, so that you only need to edit one line of code to make this change.

Note: when you are done testing, you MUST edit your testLongestRun function to call just longestRun instead of any of the debugging versions.

Next, run testLongestRun and inspect the results (you can do this in the console). If all the tests pass, it is potentially the correct implementation. But if all of your tests pass for more than one of the versions, you will need to figure out which one is actually buggy and add an extra test case or two to double-check this.

Repeat this process until you have identified which version of longestRun is correct, adding any new test cases that you feel are useful.

Now, we'd like to know why these implementations are buggy, and to do that, we can add print statements so that the code will show us a record of what happens. For each of the longestRun# functions given in the starter code, add print statements in the following places:

  1. At the very start of the function print the name of the function (e.g., print('longestRun0')).
  2. On the line immediately before the loop, print the string 'number : currentRun : bestRun' which will act as a header for the information printed within the loop.
  3. On the first line of the loop, add a print statement that prints the values of the variables number, currentRun, and bestRun, separated by colons surrounded by spaces, like this:

    4 : [3, 4] : [3, 4]

    or like this:

    5 : [3, 4, 5] : [3, 4, 5]

    For full credit, you must use the .format function to print this text.

  4. Within the loop, in each implementation there is an if/else statement that checks whether to add to the current run or create a new run. There is also an if statement that checks whether to record the current run as the new best run. We'd like Python to tell us which statements were executed, so add print statements for the following:
    • For the case where we are adding to the loop, on the first line of the if statement body, print the exact text:
      --add to run
    • For the else case where we create a new run, print the exact text:
      --new run
    • For case where we record a new best run, again on the first line of the corresponding if body, print the exact text:
      --new best
  5. Finally, at the end of the entire function right before the return statement, print an arrow using =>, a space, and then print the value that is about to be returned from the function.

You must add these seven print statements to each of the longestRun# functions.

Once you have versions that print their output, run them in the console to see what it looks like. Using these versions, for each of the longestRun# functions, define a bug# variable that holds one of these strings:

At this point, your test cases should include at least one test for which each of the incorrect versions of longestRun fails that test (you will be graded on this). These tests can be thought of as counter-examples, because they demonstrate why that version does not work. For each of the longestRun# functions, define a counterExample# variable that holds a test case (tuple of input/output values) copied from your longestRunTests list. For the correct implementation, set its counterExample# variable to None.

As an example of how to do this, if longestRun4 fails to give the correct result for the input [1, 3, 4, 5, 7, 8, 10], you could assign:

counterExample4 = ([1, 3, 4, 5, 7, 8, 10], [3, 4, 5])

(Notice how the counterExample4 value is a test case: the second element is the correct output for the given input, not the incorrect output returned by longestRun4.)

Subtask 3d: allLongestRuns

Now that you've identified the correct implementation of longestRun, your next task is to implement a similar function called allLongestRuns. allLongestRuns works like longestRun, except that instead of returning the longest run, it returns a list containing all runs tied for longest, in the same order they appear in the original list. So if the input is:

[1, 2, 3, 5, 8, 9, 10, 12, 13]

...the output would be:

[ [1, 2, 3], [8, 9, 10] ]

...because the longest sequence length is three, and there are two sequences that are tied for longest. Just as with longestRun, if the input is an empty list, the result will be an empty list. If there is only one longest run, the output will be a list containing that run (which it itself a list), so for example, for the input:

[1, 2, 4, 5, 6]

...the output would be:

[[4, 5, 6]]

For this task, there are no Codder tests: if you want to make sure your function works, you should write your own tests like you just did for longestRun (you can even probably define some very similar test cases, and your testing function can also be almost identical).

Make sure you do not edit any of your answers to previous parts when you are writing allLongestRuns.

Note: you are required to fill in the docstring for allLongestRuns. You should do this first to solidify your understanding of the problem.

Task 4: Honor Code Form

As in the previous psets, your honor code submission for this pset will involve defining entering values for the variables in the file.

How to turn in this Problem Set