Problem Set 6 - Due Fri, Mar 16

.py files for Tasks 1, 2b, and 3 due at 23:59 EDT; paper copy of Task 2a iteration tables due in lecture on Friday March 16 at 23:59 EDT (slip them under Lyn's office door = SCI E126).

Reading

  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 Patternss 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. Take a picture or make a copy of your iteration tables so you can compare it to our solution before grading is finished..
  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. Remember that you can talk with other people about high-level problem-solving strategies, but sharing code in an Honor Code violation.

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 PS5. 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 wordsearch.py following the contracts in that file.

Notice that the file imports the functions from wordplay.py as well as a list of words from vocabulary.py. 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' 

Notes

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.

Notes

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']
'computer' ['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:

Before writing any code for a function that involves loops, it's a good idea to get clear in your mind how each loop is going to solve the problem at hand.

As presented in slides 9-14 -- 9-15 of Lec 09, iteration tables are a great way to do this. 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.

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.

Iteration Tables

An iteration table has these features:

Iteration Table Example

Below is an iteration table example for the keepFirstLetter function from PS05 Task 2b Mystery Speech on the input phrase 'You say "Goodbye" and I say "Hello"'

There are three state variables:

  1. char: the current character of the string being processed
  2. lettersSeen: a string with one occurrence of the lowercase version of each letter seen so far.
  3. newPhrase: a string with all nonletters and the first occurrence of each letter seen so far.


The first row of the table shows the initial empty string values of lettersSeen and newPhrase before the first character has been processed.

Every other row begins with the character being processed at that step.

The iteration rules being applied at every step are:

In this example, there are no special early termination conditions. The loop end after the last character of the input string is processed.

char lettersSeen newPhrase
'' ''
'Y' 'y' 'Y'
'o' 'yo' 'Yo'
'u' 'you' 'You'
' ' 'you' 'You '
's' 'yous' 'You s'
'a' 'yousa' 'You sa'
'y' 'yousa' 'You sa'
' ' 'yousa' 'You sa '
'"' 'yousa' 'You sa "'
'G' 'yousag' 'You sa "G'
'o' 'yousag' 'You sa "G'
'o' 'yousag' 'You sa "G'
'd' 'yousagd' 'You sa "Gd'
'b' 'yousagdb' 'You sa "Gdb'
'y' 'yousagdb' 'You sa "Gdb'
'e' 'yousagdbe' 'You sa "Gdbe'
'"' 'yousagdbe' 'You sa "Gdbe"'
' ' 'yousagdbe' 'You sa "Gdbe" '
'a' 'yousagdbe' 'You sa "Gdbe" '
'n' 'yousagdben' 'You sa "Gdbe" n'
'd' 'yousagdben' 'You sa "Gdbe" n'
' ' 'yousagdben' 'You sa "Gdbe" n '
'I' 'yousagdbeni' 'You sa "Gdbe" n I'
' ' 'yousagdbeni' 'You sa "Gdbe" n I '
's' 'yousagdbeni' 'You sa "Gdbe" n I '
'a' 'yousagdbeni' 'You sa "Gdbe" n I '
'y' 'yousagdbeni' 'You sa "Gdbe" n I '
' ' 'yousagdbeni' 'You sa "Gdbe" n I '
'"' 'yousagdbeni' 'You sa "Gdbe" n I "'
'H' 'yousagdbenih' 'You sa "Gdbe" n I "H'
'e' 'yousagdbenih' 'You sa "Gdbe" n I "H'
'l' 'yousagdbenihl' 'You sa "Gdbe" n I "Hl'
'l' 'yousagdbenihl' 'You sa "Gdbe" n I "Hl'
'o' 'yousagdbenihl' 'You sa "Gdbe" n I "Hl'
'"' 'yousagdbenihl' 'You sa "Gdbe" n I "Hl"'

Your Task

Before you write any Python code for the longestVowelSubstrings function, you will use iteration tables on a few concrete examples to design the state variables and update rules for a one-loop iterative algorithm for this function.

For this subtask you will submit a hardcopy document (can be handwritten or done in a word processor) containing the following parts:

  1. A list of state variables for your iteration. Give the name of each state variable, and describe what it does. Note that one of your state variables should be the iteration variable of the for loop = the current character of the string being processed.

  2. The update rules for each state variable except the current character.

  3. Four iteration tables showing how your update rules work on each of these input strings:

    • 'computer'
    • 'inequalities'
    • 'audacious'
    • 'beauteous'

As in the example from the previous section, this algorithm does not have any early termination conditions and will stop only after all of the characters in the input string have been processed.

Subtask 2b: longestVowelSubstrings function definition

The file longestVowelSubstrings.py 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 your iteration design from Subtask 2a. Your definition should use only one loop -- a for loop. It should not use any list comprehensions.

The file contains the definition of an isVowel predicate that you should use in your definition.

Running longestVowelSubstrings.py in Canopy will test the longestVowelSubstrings function on all the examples shown at the very beginning of this task.

Codder will also check these (and perhaps other) examples, as well as check your function for style and implementation details (e.g., verify that you only use one loop).


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.

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):
X X O
_ _ O
_ _ _

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

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

Player O wins!
X X O
_ X O
_ _ O

We have provided 3 functions in the tictactoe.py file in your ps06 folder:

Notice that play is called within the body of if __name__ == '__main__', as we have seen in many psets. The code in this block will be executed only when run directly from tictactoe.py, and not when it is imported elsewhere.

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) + '):'
        displayBoard(board)

        # 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!'
            displayBoard(board)
            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.'
    displayBoard(board)
    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. Do not change play itself.

Notes



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 honorcode.py file.


How to turn in this Problem Set

Hard-Copy Submission

Bring to lecture on Friday March 16 the paper copy of your Task 2a (Iteration Tables). Submit your paper copy of Task 2a iteration tables by 23:59 EDT on Friday March 16 by slipping it under Lyn's office door (SCI E126). Include your name and lecture section on your submission.

Take a picture or make a copy of your solution so you can compare it to our solution before grading is finished.

Soft-Copy Submission