Problem Set 6 - Due Tue, Oct 23


  1. Slides and notebooks from Lec 09 (Iteration 1), Lec 10 (Lists, Memory Diagrams, and Mutable vs. Immutable Sequences), Lec 11 (Iteration 2), and Lec 12 (List Processing Patterns and List Comprehensions)
  2. Problems and solutions from Lab 06 (Lists) and Lab 07 (Nested Lists, List Comprehensions)
  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, loops (including nested ones), and list comprehensions.

  1. In Task 1, you will write functions that create lists through accumulation and list comprehensions. This is a continuation of the Word Play task from PS05.
  2. In Task 2, you will use iteration tables to design a loop and then implement this loop.

  3. In Task 3 (Recommended Partner task) you will write building block functions for a Tic Tac Toe games, using lists. Use this shared Google Doc to find a pair programming partner and record your partner.

Other notes:

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 all three tasks before you submit.

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 2 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 should 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 should 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: Longest Vowel Substrings

In this task, you will first design and then define a function longestVowelSubstrings that returns a list of all the longest substrings of consecutive vowels in given string in the order that they appear in the string. Here are numerous examples of the input/output behavior of this function:

Input Output
'bunny' ['u']
'success' ['u', 'e']
'compute' ['o', 'u', 'e']
'universal' ['u', 'i', 'e', 'a']
'transcendentalism' ['a', 'e', 'e', 'a', 'i']
'extracurricular' ['e', 'a', 'u', 'i', 'u', 'a']
'overcapitalized' ['o', 'e', 'a', 'i', 'a', 'i', 'e']
'aquifer' ['ui']
'evacuate' ['ua']
'confidentialities '[ia', 'ie']
'inequalities' ['ua', 'ie']
'internationalization '[io', 'io']
'unquestionable' ['ue', 'io']
'visualizations' ['ua', 'io']
'weatherproofed' ['ea', 'oo']
'autobiographies' ['au', 'io', 'ie']
'mountaineering' ['ou', 'ai', 'ee']
'questionnaire' ['ue', 'io', 'ai']
'incautious' ['iou']
'audacious' ['iou']
'inauspicious' ['iou']
'beautifies' ['eau']
'bureaucracies' ['eau']
'consanguineous' ['eou']
'beauteous' ['eau', 'eou']
'squeegeeing' ['uee', 'eei']
'sequoia' ['uoia']
'obsequiousness' ['uiou']
'queueing' ['ueuei']
'wryly' ['']

Subtask 2a: Iteration Tables

There are many different approaches for correctly defining longestVowelSubstrings. Some involve using multiple loops. For example, you could first use one loop to find the length of the longest vowel substring, and then use another loop to collect the list of all vowel substrings with that length.

However, in this task you are subject to this requirement:

Requirement: Your longestVowelSubstrings function must use exactly one loop. Solutions using more than one loop are not allowed.

How do you go about designing this loop?

As seen in slides 9-14 -- 9-15 of Lec 09 and Task 2b keepFirstLetter from PS05, iteration tables are a powerful technique for designing loops, especially in nontrivial functions like longestVowelSubstrings. So in this subtask you will use iteration tables to help you think about how to define loop you'll need to define longestVowelSubstrings.

Although you might think that creating iteration tables might cost extra time, they typically can save you lots of time by helping you design a correct loop from the beginning rather than wasting time debugging incorrect loops.

If you've forgotten the parts of an iteration table, now would be a good time to review the summary of iteration tables in Task 2b keepFirstLetter from PS05.

A Sample Iteration Table for longestVowelSubstrings

Rather than ask you to define iteration tables for longestVowelSubstrings from scratch, we'll give you an iteration table for one example input and ask you to show that you understand it by generating the iteration tables for three other inputs.

Below is the iteration table for the loop in longestVowelSequence('inequalities'):

char vowelSeq longestSeqsSoFar
'' ['']
'i' 'i' ['i']
'n' '' ['i']
'e' 'e' ['i', 'e']
'q' '' ['i', 'e']
'u' 'u' ['i', 'e', 'u']
'a' 'ua' ['ua']
'l' '' ['ua']
'i' 'i' ['ua']
't' '' ['ua']
'i' 'i' ['ua']
'e' 'ie' ['ua', 'ie']
's' '' ['ua', 'ie']

There are three state variables:

It is possible to have additional state variables, but only three are needed. For example, a longestLengthSoFar state variable could maintain the length of the longest consecutive vowel sequence seen so far. But this state variable is not strictly needed, since it can always be calculated from longestSeqsSoFar (how?).

As in the example from Task 2b keepFirstLetter from PS05, this algorithm for longestVowelSubstrings does not have any early termination conditions and will stop only after all of the characters in the input string have been processed.

Based on this example, you should figure out the iteration rules that determine how the value of each state variable in a nonfirst row is determined from the values of the state variables in the the previous row. You don't have to write down these rules, but you will need to understand them to create three more iteration tables.

Representing an Iteration Table as a List of Tuples

An iteration table can be represented in Python as a list of tuples in which the length of each tuple is the number of state variables:

For example, here is a Python list of tuples for the above iteration table:

inequalitiesTable = [
    ('char', 'vowelSeq', 'longestSeqsSoFar'), 
    (None, '', ['']), 
    ('i', 'i', ['i']), 
    ('n', '', ['i']), 
    ('e', 'e', ['i', 'e']),
    ('q', '', ['i', 'e']),
    ('u', 'u', ['i', 'e', 'u']), 
    ('a', 'ua', ['ua']), 
    ('l', '', ['ua']), 
    ('i', 'i', ['ua']),
    ('t', '', ['ua']),                     
    ('i', 'i', ['ua']),                     
    ('e', 'ie', ['ua', 'ie']), 
    ('s', '', ['ua', 'ie'])

Note that the None value is used to represent an empty slot in the first row of the table.

Your Task

In the given file, flesh out the definitions of these two list-of-tuples iteration tables:


Codder will test the that the structure of your three list-of-tuples iteration tables are valid, but the content of the three tables will not be checked by Codder until the final grading pass after submission.


Subtask 2b: longestVowelSubstrings function definition

The file contains a skeleton for the the longestVowelSubstrings function along with some testing support.

In this subtask, you will flesh out the definition of longestVowelSubstrings so that it implements the iteration rules you used when you fleshed out the iteration tables in Subtask 2a.



Task 3: Tic Tac Toe

This task is a Recommended partner problem in which it is strongly recommended that you work with a partner as part of a two-person team. Use this shared Google Doc to find a pair programming partner and record your partner.

You will write a program to help you and a friend play Tic Tac Toe.

Here is an example transcript of running this program. Note that the row and column coordinates are 0-indexed.

Current board (turn 0):
_ _ _
_ _ _
_ _ _

Player X: Enter the row,column coordinates of your play, separated by comma: 1,3
Your move is outside the board, or in a filled cell. Please try again.

Player X: Enter the row,column coordinates of your play, separated by comma: 0,0
Current board (turn 1):
X _ _
_ _ _
_ _ _

Player O: Enter the row,column coordinates of your play, separated by comma: 1,2
Current board (turn 2):
X _ _
_ _ O
_ _ _

Player X: Enter the row,column coordinates of your play, separated by comma: 0,1
Current board (turn 3):
X X _
_ _ O
_ _ _

Player O: Enter the row,column coordinates of your play, separated by comma: 0,2
Current board (turn 4):
_ _ O
_ _ _

Player X: Enter the row,column coordinates of your play, separated by comma: 1,1
Current board (turn 5):
_ X O
_ _ _

Player O: Enter the row,column coordinates of your play, separated by comma: 2,2
Current board (turn 6):
_ X O
_ _ O

Player O wins!
_ X O
_ _ O

We have provided 5 functions in the file in your ps06 folder:

Understanding play:

You are provided with the following play function, which runs the TicTacToe game, invoking various helper functions along the way. You should carefully study this play function so that you understand how each of the helper functions you are defining will be used. Do not change this definition of the play function in any way!

def play(n, players):
    Main function:
    * n should be the dimensions of the board
    * players should be a non-empty list of unique strings, serving
      as the symbol of each player.
      Typically, there are two players, but any number is supported.

    Creates a new board of size n x n and alternates between the given
    players, prompting for moves until game is won or tied

    # Create n x n game board
    board = initializeBoard(n)

    # Iterate over turns. Board has n*n cells, so there at most n*n turns.
    for turn in range(n*n): 

        # Select player by turn.
        player = players[turn % len(players)] 

        # Display board.
        print 'Current board (turn ' + str(turn) + '):'

        # Prompt player for a move.  Update the board.
        playMove(getValidMove(player, board), player, board)

        # Check for a win by player.
        if won(player, board):

            # Display winning player and final board
            print 'Player', player, 'wins!'
            return # Exit from loop early since game is done

    # Reaching here means the board is full after n*n moves,
    # but no player has won.    
    print 'Game is tied.'
    return # Not necessary to say this, but indicates play function is done.

Your task:

In this problem, you will implement the following helper functions (plus several more of your own design) to complete the implementation of play. You should not change play itself, nor should you change any of the other provided functions.


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

Softcopy (electronic) submission

Hardcopy (paper) submission

There is no hardcopy submission. Problem set submission is entirely electronic.