Problem Set 5 - Due Tuesday October 16

(Files for Task 1, Task 2, and Subtasks 3a and 3b are due at 23:59 EST. The memory diagram in Subtask 3c is due as a hardcopy paper submission at the beginning of lecture on Tue. Oct. 16.)


  1. Slides and notebooks from Lec 08 (Sequences and Loops), Lec 09 (Iteration, Part 1), and Lec 10 (Lists, Memory Diagrams, and Mutable vs. Immutable Sequences).
  2. Problems and solutions from Lab 05: Loops and Lab 06: Lists
  3. Think Python, Ch. 8: Strings
  4. Think Python, Ch. 7: Iteration
  5. Think Python, Ch. 9: Lists

About this Problem Set

This problem set will give you practice with sequences (strings and lists), operations on sequences, loops on sequences, loops with graphics, and list memory diagrams.

  1. In Task 1 you will create your own function that uses loops to generate pictures with repeating elements from cs1graphics.
  2. In Task 2 (Recommended Partner task), you will create your own functions that use loops to analyze and manipulate strings. 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.)
  3. In Task 3, you will study the connection between Python code and memory diagrams for lists to practice the concepts of mutability and aliasing. Subtask 3c requires submitting a paper hardcopy of a memory diagram. Take a picture or make a copy of your solution to Subtask 3c so you can compare it to our solution before it is graded and returned to you.

Other notes:

All code for this assignment is available in the ps05 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 before you submit.

Task 1: Concentric Circles

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

In this task, you will create a Python file named and define in it the three functions concentricCircles, showConcentricCircles, and circleRow.

Your file should begin with this header, which you should fill out:

# Your name:
# Your username:
# CS111 PS05 Task 1
# Submission date:

You should also import cs1graphics via the following line at the beginning of your code:

from cs1graphics import *

Subtask 1a: concentricCircles

In this subtask, your goal is to generate pictures like the following:

paper1 = Canvas(200, 200)
cybla = concentricCircles(200, 5, 'cyan', 'black')
cybla.move(100, 100)
paper2 = Canvas(400, 400)
grellow = concentricCircles(400, 8, 'green', 'yellow')
grellow.move(200, 200)
paper3 = Canvas(500, 500)
pima = concentricCircles(500, 2, 'pink', 'magenta')
pima.move(250, 250)
paper4 = Canvas(500, 500)
reblu = concentricCircles(500, 13, 'red', 'blue')
reblu.move(250, 250)

In, define the function concentricCircles that fulfills the following contract:

def concentricCircles(size, numCircles, color1, color2):
    """Creates and *returns* a Layer containing numCircles
    circles, all of which are centered at (0,0).
    Let r be the radius of the smallest circle. Then the radii of
    the circles grow in arithmetic progression -- r, 2r, 3r, etc. --
    up to the radius of the largest circle, which is size/2.0.
    The smallest circle is filled with color1 and afterwards the colors 
    alternate between color1 and color2.



Subtask1b showConcentricCircles

If you look at the 4 statements (shown in gray boxes in Task 1a above) that are used to generate each of the concentric circles, you'll note there is a pattern. Capture that pattern by writing a function called showConcentricCircles in the file that fulfills the following contract:

def showConcentricCircles(canvasSize, numCircles, color1, color2):
    """Creates and *returns* a canvasSize x canvasSize white canvas containing
    numCircles concentric circles, with the smallest circle having color1
    and alternating with color2. The title of the canvas should
    be a string representation of the invocation of the showConcentricCircles
    function that created the canvas.

For example, the following invocation produces the canvas below (note the title):

    showConcentricCircles(500, 13, 'red', 'blue')


Subtask 1c: circleRow {task1c}

In this task, your goal is to generate pictures like the following:

single = circleRow(1, 500, 7, 'orange', 'yellow')
triple = circleRow(3, 400, 10, 'red', 'pink')
quint = circleRow(5, 240, 8, 'blue', 'green')
dozen = circleRow(12, 100, 10, 'black', 'white')

In your file, define a function circleRow that fulfills the following contract:

def circleRow(numCirclesInRow, size, numCircles, color1, color2):
    """Creates and *returns* a numCirclesInRow*size x size white canvas 
    containing numCirclesInRow circles, each of which is a concentric circle. 
    The distance between the center of each circle is size. The title of the 
    canvas should be a string representation of the invocation of the circleRow 
    function that created the canvas.



Task 2: Word Play

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

Subtask 2a: Word Properties

We are interested in some fun properties of written words.

  1. Does the word use only the top row of keys (i.e., 'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p') on the keyboard? Examples are typewriter and pretty.
  2. Does a word contain at least three vowels in a row? Examples are beautiful and delicious.
  3. Does a word contain exactly one occurrence of each of the five vowels? Examples are education and tambourine.
  4. What is the Scrabble value of the word? This is determined by adding the points assigned by Scrabble to each letter, which are:
A = 1 B = 3 C = 3 D = 2 E = 1 F = 4
G = 2 H = 4 I = 1 J = 8 K = 5 L = 1
M = 3 N = 1 O = 1 P = 3 Q = 10 R = 1
S = 1 T = 1 U = 1 V = 4 W = 4 X = 8
Y = 4 Z = 10

Your task is to flesh out the definitions of the functions in the provided file Your functions should not be sensitive to capitalization (see examples below).

In [2]: isTopRow('typewriter') # topRow words use only top row keys
Out[2]: True

In [3]: isTopRow('Pretty')
Out[3]: True

In [4]: isTopRow('bunny')
Out[4]: False

In [5]: isTopRow('sequoia')
Out[5]: False

In [6]: isBeauteous('delicious') # Beauteous words have at least 
Out[6]: True                     # three consecutive vowels

In [7]: isBeauteous('sequoia') 
Out[7]: True

In [8]: isBeauteous('education') 
Out[8]: False

In [9]: isBeauteous('royal') 
Out[9]: False

In [10]: isPrecarious('education') # Precarious words have 
Out[10]: True                      # exactly one of each vowel

In [11]: isPrecarious('sequoia') # 'sequoia' is both beauteous *and* precarious!
Out[11]: True

In [12]: isPrecarious('auction') # No 'e'
Out[12]: False

In [13]: isPrecarious('precautionary') # Six total vowels covering all five, but with two 'a's
Out[13]: False

In [14]: isPrecarious('insidious') # Five vowels, but no 'a' or 'e'
Out[14]: False

In [15]: scrabbleScore('juxtapose')
Out[15]: 25

In [16]: scrabbleScore('quiz')
Out[16]: 22

In [17]: scrabbleScore('Wellesley')
Out[17]: 15

In [18]: scrabbleScore("I'm a n00b!") # Nonletter characters have score 0
Out[18]: 9



Subtask 2b: Mystery Speech


What would English sound like if we were not allowed to use each letter more than once in a sentence? Would one still be able to understand it? Let's try it out with some famous (or not) phrases. Can you guess them? (The phrases are shown at the end of this subtask).

In []: keepFirstLetter(somePhrase1)
Out[]: 'To be r n  '
In []: keepFirstLetter(somePhrase2)
Out[]: 'The king s da, lo v  !'
In []: keepFirstLetter(somePhrase3)
Out[]: 'We ar nv  gti bck oh'
In []: keepFirstLetter(somePhrase4)
Out[]: 'Only Victr s kd xeg a pu f h j q   BMW   z'
In []: keepFirstLetter(somePhrase5)
Out[]: 'Quizes ar dfclt o py n wv xh, b g mk j.'

In this subtask, you'll flesh out the body of the function keepFirstLetter which transforms string phrases as shown above. This function is also part of the file.

def keepFirstLetter(phrase):
    """Returns a new string that contains only the first occurrence of a
       letter from the original phrase.
       The first letter occurrence can be upper or lower case.
       Non-alpha characters (such as punctuations and space) are left

There are different approaches for writing the keepFirstLetter function, but we want you to use a particular approach indicated by the iteration table in the next subsection.

Iteration Tables

Before writing any code for a function that involves a loop, it's a good idea to get clear in your mind how the 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 an iteration table to help you think about how to design the loop you'll need in keepFirstLetter.

Below is an iteration table example for the keepFirstLetter function from on the input string 'Amy says, "Me?"'

char lettersSeen newPhrase
'' ''
'A' 'a' 'A'
'm' 'am' 'Am'
'y' 'amy' 'Amy'
' ' 'amy' 'Amy '
's' 'amys' 'Amy s'
'a' 'amys' 'Amy s'
'y' 'amys' 'Amy s'
's' 'amys' 'Amy s'
',' 'amys' 'Amy s,'
' ' 'amys' 'Amy s, '
'"' 'amys' 'Amy s, "'
'M' 'amys' 'Amy s, "'
'e' 'amyse' 'Amy s, "e'
'?' 'amyse' 'Amy s, "e?'
'"' 'amyse' 'Amy s, "e?"'

An iteration table has these features:

Your Task

Flesh out the body of the function keepFirstLetter in so that it implements the strategy indicated by the above iteration table. In particular, it should use a for loop with iteration variable named char that updates two state variables named lettersSeen and newPhrase.



There are Canopy and Codder tests cases for this subtask.

Fun Ungraded Challenge:

If you manage to create a meaningful English phrase which after passing through keepFirstLetter contains all the letters of the alphabet, please post it to the Google Group. We will add them to the mystery phrases for the next semester. *Credit to Riley Rettig and Jennifer Chang for creating somePhrase4; Alissa Tinney and Isabel Bryant for creating somePhrase5.

Task 3: Memory Diagrams

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

This problem involves memory diagrams. You should review the notation and conventions for memory diagrams explained in Lec 10 before starting this problem.

Subtask 3a: Matching Code to Memory Diagrams

In this subtask you are given these 18 code snippets (named CODE01 through CODE18) and these 9 memory diagrams (named A through <span style="color:magenta;font-weight:bold;"">I). Your goal is to match each code snippet with the corresponding memory diagram. (An earlier version of this problem indicated that some snippets could generate errors, but none of the given 18 snippets generates an error; so sorry for that confusion!).

This subtask is based on a midterm exam problem given during a previous semester. The goal of the problem was to write a sequence of statements to create memory diagram A:

There were a dizzying number of solutions, some of which created memory diagram A, some of which created other memory diagrams, and some of which generated errors. The code snippets CODE01 through CODE18 are adapted from actual student solutions to this problem.

You will express your answers in the given file by assigning the given variables CODE01 through CODE18 (initially defined to be the value None) to be one of the strings 'A' through 'I' (to indicate that it creates the diagram named by that string). (An earlier version of this problem indicated that some variables could be assigned the string 'ERROR', but none of the snippets generates an error, so the string 'ERROR' should not be used. Also, the earlier version mentioned diagram J, which doesn't exist, so the string 'J' should not be used either.)

For this subtask, running Codder will check that all of your variables are defined to be valid strings, but it will not tell you whether or not your answers are correct. That will be done only during the final grading phase.


Subtask 3b: Modifying Memory Diagram A

Assume that the value of variable x is the list with memory diagram A:

In this subtask, you will flesh out the body of the function A_to_K in that takes as its single parameter a list named L, and modifies it in such a way that after calling A_to_K(x), the structure of x has been changed to that of memory diagram K:

In the body of A_to_K, your code should satisfy the following restrictions:

For this subtask, running Codder will check that your A_to_K function satisfies the above restrictions and performs the correct modifications when called on the list x from diagram A and will report any discrepancies.


Subtask 3c: Drawing a Modified Memory Diagram

Assume that the value of variable x is the list with memory diagram A:

In this subtask, you will draw the final memory diagram that shows the structure of the list x after executing the following sequence of statements:

x[3] = [x[1], x[0], x[2][0]]
x[1].insert(0, x[2])
x[2][0] = x[2][1] + x[1][1] + x[3][0][0][0] 

You should submit a hardcopy of your diagram at the beginning of lecture on Tue. Oct. 16.


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

Hardcopy (paper) submission

Bring to lecture on Tuesday, October 16 the paper copy of your Subtask 3c. Include your name and 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.

Softcopy (electronic) submission