Problem Set 6 - Due Tue, Oct 23
- 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)
- Problems and solutions from Lab 06 (Lists) and Lab 07 (Nested Lists, List Comprehensions)
- Think Python, Ch. 8: Iteration
- 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.
- 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.
- 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..
- 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.
Like PS05, PS06 is due on a Friday rather than a Tuesdays. Tuesday deadlines will resume after Spring Break.
The CS111 Problem Set Guide gives an overview of psets, including a detailed description of individual and partner tasks.
Follow the style guidelines in the CS 111 Code Style Guide
In Spring 2018, students spent the following times (in hours) on this pset:
Task Average Median 25% took more than 10% took more than Task 1 2.6 2.5 3.0 4.5 Task 2 3.7 3.2 5.0 6.0 Task 2 5.4 5.0 7.0 8.0
We have simplified Task 2 from last semester to provide more scaffolding in an effort to reduce the time taken for this task.
- There is no quiz for this problem set, due to the scheduling of the Midterm Exam on Friday, October 26. So the pset itself will count for 85 points, and the reflection for 15 points.
All code for this assignment is available in the
ps06 folder in
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
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.
listBeauteousPrecariousWordsreturns a list of all English words of a specified length that are both beauteous (contain three consecutive vowels) and precarious (contian exactly one of each of the five vowels, not necessarily in order).
listGoodScrabbleWordsreturns a list of pairs (2-tuples) of words and their Scrabble scores for all English words whose Scrabble score is a above a given threshold.
bestScrabbleWordfinds the best-scoring Scrabble word in the English word list and returns a single pair (a 2-tuple) of this word and its Scrabble score.
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
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
In : listBeauteousPrecariousWords(8) Out: ['sequoias'] In : listBeauteousPrecariousWords(9) Out: ['behaviour', 'facetious', 'nefarious', 'tenacious', 'veracious', 'vexatious'] In : listBeauteousPrecariousWords(10) Out: ['abstemious', 'bivouacked', 'gregarious', 'mendacious', 'precarious'] In : listBeauteousPrecariousWords(14) Out:  In : listGoodScrabbleWords(35) Out: [('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 : bestScrabbleWord() Out: ('quizzically', 43) In : reverseWords('we are never ever getting back together') Out: 'ew era reven reve gnitteg kcab rehtegot'
We have provided the solution file for
In the past, we have written
from cs1graphics import *, which means get everything from the
cs1graphicsmodule. This time, we are only importing the particular named values that will be used in
from vocabulary import englishwords from wordplay import isBeauteous, isPrecarious, scrabbleScore
These functions use various list processing patterns:
listBeauteousPrecariousWordsfunction uses the filtering pattern introduced in Lecture 12 (List Processing Patterns and List Comprehensions)
listGoodScrabbleWordsfunction combines the mapping and filtering patterns from that lecture
bestScrabbleWordfunction uses the accumulating-a-value-from-a-list pattern
reverseWordsuses the mapping pattern.
- This function must discover the maximal scrabble word score. You are not allowed to hardwire this score into your code .
- For simplicity, you may assume there is only one word with the maximal score.
In this subtask you must use loops (and not list comprehensions) to implement the four functions
- use the
splitand optionally the
joinmethods. They work like this:
In : word = 'i like apples' In : word.split() Out: ['i', 'like', 'apples'] In : listOfWords = ['this', 'is', 'a', 'test'] In : ' '.join(listOfWords) Out: 'this is a test' In : ', '.join(listOfWords) Out: 'this, is, a, test'
- You may use the following
reversefunction for reversing a string that is provided in
def reverse(s): return s[::-1]
- use the
- These four functions are tested in the testing code at the end of
wordsearch.pyas well as by Codder.
Subtask 1b: Mapping and Filtering with List Comprehensions
In this subtask, you will define three functions
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.
LCstands for List Comprehension.
Each of your three
LCfunction definitions in this subtask should have a function body containing exactly one statement: a
returnstatement that contains a list comprehension expressions. For example,
listBeauteousPrecariousWordsLCshould have exactly the form:
def listBeauteousPrecariousWordsLC(length): """Returns a list of all english words that are exactly length letters long, contain at least three consecutive vowels, and contain exactly one of each of the five vowels (not necessarily in order). In the body of this function, you should use a list comprehension to process all the words. """ return ... your list comprehension goes here ...
- These three
LCfunctions are tested in the testing code at the end of
wordsearch.pyas well as by Codder.
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:
|'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']|
|'autobiographies'||['au', 'io', 'ie']|
|'mountaineering'||['ou', 'ai', 'ee']|
|'questionnaire'||['ue', 'io', 'ai']|
Subtask 2a: Iteration Tables
There are many different approaches for correctly defining
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:
longestVowelSubstringsfunction 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
keepFirstLetter from PS05,
iteration tables are a powerful technique for designing loops,
especially in nontrivial functions like
So in this subtask you will use iteration tables to help you think
about how to define loop you'll need to define
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
keepFirstLetter from PS05.
A Sample Iteration Table for
Rather than ask you to define iteration tables for
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
|'u'||'u'||['i', 'e', 'u']|
There are three state variables:
char: the current character being processed from the string. (Because the first row of the table shows the values of state variables before the loop starts,
charis not defined in this row.)
vowelSeq: the current sequence of consecutive vowels; it must end with
charis a vowel. (Recall that any row except the first shows the value of the state variable after the loop body has been executed for that iteration.)
longestSeqsSoFar: List of all consecutive vowel sequences with longest length so far.
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
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:
The first tuple contains strings that are the names of all of the state variables;
- Each remaining tuple lists the values in one row of the iteration table.
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.
In the given file
longestVowelSubstrings.py, flesh out the definitions of these
list-of-tuples iteration tables:
computeTable: iteration for `longestVowelSubstrings('compute')
audaciousTable: iteration table for `longestVowelSubstrings('audacious')
beauteousTable: iteration table for `longestVowelSubstrings('beauteous')
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.
CODDER HAS NOT YET BEEN IMPLEMENTED FOR THIS SUBTASK
longestVowelSubstrings function definition
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
forloop. It should not use any list comprehensions.
The file contains the definition of an
isVowelpredicate that you should use in your definition.
longestVowelSubstrings.pyin Canopy will test the
longestVowelSubstringsfunction 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. 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): 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
play(n, players)takes a board dimension,
n, a list of unique player symbols (typically
['X', 'O']) and implements the top-level game logic using several helper functions.
playworks on any board dimension and any non-empty list of unique player symbols.
playNormalruns a traditional Tic Tac Toe game.
initializeBoard(n)returns a blank board of size
n x n. A board is represented as a list of lists of strings. Each inner list is a row. Blank cells are represented by the string
In : initializeBoard(3) Out: [['_', '_', '_'], ['_', '_', '_'], ['_', '_', '_']]
When a cell is marked by the X player, it will be represented by
'X', and by
'O'when it is marked by the O player.
playMove(coordinates, player, board)marks the player's symbol in the board cell at the given coordinates, a (row, column) pair tuple.
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.
You are provided with the following
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.
In this problem, you will implement the following helper functions (plus several
more of your own design) to complete the implementation of
Do not change
displayBoard(board)prints the board, with a single space between cells in each row, and each row on a separate line. As with all the helper functions you defined,
displayBoardmust work on any
n x nboard, not just a
3 x 3board.
In : emptyBoard = initializeBoard(3) In : displayBoard(emptyBoard) _ _ _ _ _ _ _ _ _ In : testBoard = [['X', '_', '_'], ['X', 'O', '_'], ['O', 'X', '_']] In : displayBoard(testBoard) X _ _ X O _ O X _ In : displayBoard([['X', '_', '_', 'X'], ['X', 'O', '_' '_'], ['O', 'X', '_', '_'], ['O', '_', 'X', '_']]) X _ _ X X O _ _ O X _ _ O _ X _
requestMove(player)takes one argument, the player's name (a string), prompts the user (using the prompt shown below) for an input specifying row and column indices of the cell to mark, and returns the indices as a pair (a 2-tuple):
- The user should enter the indices separated by a comma in the
row,col. For example, typing
0,1would indicate row 0, column 1.
Assume that the string is well-formed (i.e., it always contains two integers separated by a comma). If the user enters a malformed string such as
'1, 0', it is fine for your program to crash.
In : requestMove('O') Player O: Enter the row,column coordinates of your play, separated by comma: 0,1 Out: (0, 1) In : requestMove('X') Player X: Enter the row,column coordinates of your play, separated by comma: 3,-2 Out: (3, -2) In : requestMove('X') Player X: Enter the row,column coordinates of your play, separated by comma: -273,1729 Out: (-273, 1729)
- The user should enter the indices separated by a comma in the form
isValidMove(coordinates, board)takes a pair (a 2-tuple) of
(row, col)coordinates and a board and returns a boolean indicating whether (
True) or not (
False) the coordinates describe an empty cell within the bounds of the board.
In : isValidMove((0,2), testBoard) Out: True In : isValidMove((3,2), testBoard) Out: False In : isValidMove((1,-2), testBoard) Out: False
Note that in an
n x nboard, a coordinate
cis valid if and only if
cis an integer and 0 <=
Trueif and only if both coordinates are valid and the cell at those coordinates is empty; otherwise it returns
getValidMove(player, board)takes a player's name (a string) and a board and uses
isValidMoveto prompt the user repeatedly for the coordinates of a move, until the user enters valid coordinates.
getValidMovereturns the first pair (2-tuple) of valid coordinates entered by the user.
In : coords = getValidMove('O', testBoard) Player O: Enter the row,column coordinates of your play, separated by comma: 0,3 Your move is outside the board, or in a filled cell. Please try again. Player O: Enter the row,column coordinates of your play, separated by comma: 0,0 Your move is outside the board, or in a filled cell. Please try again. Player O: Enter the row,column coordinates of your play, separated by comma: 0,2 In : coords Out: (0, 2) In : playMove(coords, 'O', testBoard) In : displayBoard(testBoard) X _ O X O _ O X _
won(player, board)checks if the player (typically 'X' or 'O') has won in this board. For example, X wins if there is a row, column, or diagonal in the board of all X's.
wonmust work on any
n x nboard, not just
3 x 3.
In : won('X', [['X', 'O', '_'], ['X', 'X', 'O'], ['X', '_', 'O']]) Out: True In : won('O', [['X', 'O', '_'], ['X', 'X', 'O'], ['X', '_', 'O']]) Out: False In : won('X', [['X', '_', '_', '_'], ['O', 'X', 'O', '_'], ['_', '_', 'X', '_'], ['_', '_', 'O', 'X']]) Out: True
wonfunction is a bit more involved than the others. There are many possible ways to approach this function. You should break it down into separate small helper functions to check for four distinct types of wins. Use divide-conquer-glue and at least 4 additional helper functions to implement
won. Our solution uses 6 small helper functions in addition to
Start by thinking of how to implement it for a 3x3 board, by drawing out some boards on paper and seeing what makes a winning Tic Tac Toe board, before you start coding. Then generalize to
n x n, still on paper. Finally, when you have an understanding of how to break down the problem in a general way, begin writing code.
Test your individual helper functions as you go. Once you have implemented a check for one type of win, test it before implementing checks for the next type of win. Glue together your checks for the separate types of wins as simply and elegantly as possible in
splitwith no arguments splits the string into a list along spaces. To split along commas, pass ',' as an argument.
In : word = 'ice cream,bananas'.split(',') Out: ['ice cream', 'bananas']
getValidMoveshould use a
wonfunction so that it (and any helper functions it uses) don't do unnecessary work. For example, When checking if the row
O X Xor
X O X' is a win forX
, one approach is to count the number ofX
s and see if this is equal to the length of the row (3 in this case). But a better approach is returnFalse
as soon as anyO` is encountered. Similar remarks hold for checking columns and diagonals for wins.
You do not need to use list comprehensions in this task, but may use them if you find them helpful.
Ctrl+C(press both keys simultaneously) to break out of an endless loop.
tictactoe.pyincludes test cases for
won. You'll need to test
playinteractively in Canopy.
- Codder will test your program for behavior, implementation, and style.
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
How to turn in this Problem Set
Softcopy (electronic) submission
- Save your final
longestVowelSubstringsfiles in the
- Each team member should save their
tictactoe.pyfile in their
- Save your filled out
- Note: It is critical that the name of the folder you submit is
ps06, and your submitted files are
honorcode.py. In other words, do not rename the folder that you downloaded, do not create new files or folders, and do not delete or re-name any of the existing files in this folder. We have automated scripts to check your electronic submission: an improperly named folder or a folder with impropertly named files will not count as a valid submission. Improperly named files or functions will incur penalties.
- Drop your entire
ps06folder in your
dropfolder on the
csserver using Cyberduck by 11:59pm on the DUE DATE = Tuesday October 23, 2018.
- Failure to submit a code file before the deadline will result in zero credit for that code on PS06.
Hardcopy (paper) submission
There is no hardcopy submission. Problem set submission is entirely electronic.