Please read through the entire lab before starting!
Also, as always, run update21 to create your
cs21/labs/07 directory and grab any starting point files.
All your lab 7 code should be in this directory.
Note that this is a two-part lab, split over two weeks. For this week,
you will focus on using top-down design to create the overall
structure of the program. Once your proposed structured has been reviewed
and approved, you will use incremental implementation and testing
to complete the full lab.
Goals
- Apply Top Down Design to designing a solution to a larger
programming problem.
- Practice implementing the design of a larger program using function
stubs.
- Practice with incremental implementation and testing.
- Reading program input from files.
- More practice with strings, lists, and functions.
Cryptoquote
Our lab this week and next is to write a program that plays
the Cryptoquote game. Here is an example to try out:
an on-line cryptoquote puzzle.
Cryptoquote is a word puzzle where the alphabetic characters in a quote
are encoded using a single letter simple substitution cipher.
The player guesses
the decoded puzzle one letter at a time. By making use of common
letter patterns in English words, a player can make informed guesses at
decodings, and then use subsequent decoded parts of words to make good
guesses at decoding other letters.
For example, there are not too many single letter words in English
language, so in an encoded 4-word phrase like the following:
r eizx yifowuxb myrxtyx!
it is very likely that
r is the encoding for either the
letter
a or the letter
i. The letter
e is also the most common letter in English words, but not as common
as the first letter in words. Looking at this puzzle,
x might be the encoding for the letter
e in this phrase.
With these guesses, the decoded parts of the phrase look like this (the
decoded guesses are shown in uppercase, and the still encoded in lowercase):
I eizE yifowuEb myrEtyE!
Next, based on these guesses,
the player may be able to make other guesses for letter decodings
(this is actually a pretty hard puzzle, but guessing that
i
encodes some vowel is probably a pretty good guess). The answer is:
I LOVE COMPUTER SCIENCE!
r eizx yifowuxb myrxtyx!
For this lab you will use top-down design. We are giving you two weeks
to complete this program. However, we require your
initial top-down design due this Saturday (March 18) and the
full implementation the following week (March 25).
It is highly recommended that you
submit your top-down design before the due date so that we can give you
feedback before you start your implementation.
See below for your Top-Down design requirements.
Examples and Program Requirements
Here are some examples of running a cryptoquote program:
- example #1: an example that is solved to
completion.
- example #2: an example where user
chooses to quit before solving.
- example #3: an example with some
error detection and handling.
Your program's output does not need to be identical to these
examples; you have some freedom in how you want your game to look.
Requirements
Here are our requirements for the game:
- The program should print out adequate instructions throughout the
game, both introducing the game and feedback and prompts for user's guesses
(see examples).
- The program will read in phrases from a file, and randomly choose
one for the current game.
- The quote should be encoded using a letter substitution cipher. The
shuffle function from the random library might be useful for creating
the encoding (see example below).
- Only alphabetic characters in the puzzle should be encoded, punctuation
and whitespace characters should be left un-encoded. All alphabetic
characters in the quote should be converted to lowercase before encoding.
- The fully encoded phrase and the partially decoded phrase based
on the user's guessed decodings should be displayed at each round of
play. Use uppercase characters for decoded, and lowercase for encoded
letters in the phrase (see the examples).
- The program needs to support a user choosing different decodings for
the same encoded letter as the game progresses. For example,
the user may make an initial incorrect decoding guess for an
encoded letter that she later re-guesses with the correct decoding guess
(example #1 shows an example of this).
- There should be an option for the user to quit the game without
solving (see example #2: if the user enters
"quit" when prompted for a letter, the game ends).
- The result: solved or quit should be displayed, as should the quote
at the end of the game. (see the end of example #1,
and example #2)
- There should be good error detection and handling for bad input
values.
- Your program must handle invalid user input properly by
re-asking for a value (see example #3).
Quote File Format
Each quote in the quote file is on a separate line:
first quote.
second quote. Quotes can have any CAPitalization, and any punctuation and white space!!!!
third quote
...
last quote
With the starting point code is an example quote file
(
cryptoquotes.txt).
We also encourage you to create your own input quote files for testing.
Top-down design requirements
You must complete, submit, and obtain feedback on your top-down design
before beginning implementation.
Special procedures for this two-week lab:
Please ensure you meet the following requirements
before submitting your TDD. Remember, for the
design of a program:
- main() must be completely written. Recall that main
performs high-level (big)
steps without focusing on details.
- Your main should call the functions you create in your
design, in the appropriate order, and with arguments that match parameters. Return values
should be saved in main(), even if you don't do anything with them yet.
- Every function should be stubbed out with parameters,
a block comment, and a return statement. They don't need to do anything yet, except
possibly call other functions.
- If your function is meant to return something, you should return a dummy value of the appropriate type (e.g., return 0 for an int).
- Each function should also print a simple statement "in function X" so that
you can run the program and see if your design matches the control flow. You can delete this
when you begin implementation.
- The program must run without errors (although it doesn't play the game yet)
- Your design must have several functions (at least 5).
Each function must be function worthy (i.e.,
not a trivial task) and also demonstrate encapsulation
(one clearly defined purpose).
Utilize iterative refinement to break down some of your larger
high-level steps into even more functions. Look for any common repeated
patterns of code, and see if you can generalize into a function that
you call multiple places instead.
Here is a simple example of a top-down design.
Tips
- You will likely need to keep track of a few strings as the program
runs as well as some lists. Think about state you need, look at the example
output to help you determine this.
- You will need to keep track of encoding for an alphabet and guessed
decodings for each letter. To do this you will want to keep several lists of
single character strings. One way to keep track of encodings is to have
one list of single letter strings and a corresponding list of encodings.
The encoding for the letter in position i in the letter strings is in position
i in the encodings string. For example, the encoding for letter[1]
is encoding[1]:
letters = ['a', 'b', 'c']
encoding = ['x', 'p', 'q']
(Alternatively, you could use relative ordering
of alphabetic character ascii values to implicitly keep mappings for letters and
only keep the encoding array. If you want to try this, see the
ord function example here: string and list in Python).
- At each step, you should create a new answer string that contains all
unguessed encoded letters as their encoded value and all guessed letters as
their guessed decoding. Still unguessed encoded could be lowercase encodings
(like in the examples) or you could use some non-alpha char (like dashes) for
unguessed letters. All guesses should be uppercase chars in the answer-so-far string.
- It may be useful to create a short test string for the quote as
you test your program's functionality. For example, instead of setting the
quote string to a random quote from the file, just assign it to a known
short string:
quote = "testing 123!" # only the "testing" part should be encoded
This way you can test out parts of your program's functionality on a smaller
test string, and one that you know each time. This will also allow you to
test out some functionality before you have the "get a random quote from
a file" part working.
- Here is some information about str and list in Python,
some that may be particularly useful for this lab:
- Some string methods:
ch = 'H'
ch.isalpha() # True
ch.isdigit() # False
ch = ch.lower() # ch gets new string 'h'
ch = 'p'
ch = ch.upper() # ch gets new string 'P'
- Converting lists to strings and strings to lists
s = "hello"
l = list(s) # l is ['h', 'e','l','l','o']
l = ['F', 'r', 'e', 'y', 'a']
name = "".join(l) # name is string with value "Freya"
- Some list functions that might be useful for this lab:
from random import shuffle
l = ['a', 'b', 'c', 'd']
shuffle(l) # randomly shuffles the values in the list
- Read this information about File I/O in Python.
- For this assignment, we recommend using either the readlines method
(to read the entire file contents into a list of strings, where each item
in the list is a line from the file) or a for loop (to read the
file like a sequence, one line at a time).
Extra Challenges
These do not affect your grade, so please only attempt them after
completing the rest of your lab.
- Add a graphics interface to the game using the graphics library.
- Keep track of the number of incorrect decoded guesses and output
that value at the end of the game, along with a message that is appropriate
to the number of wrong guesses (maybe with a category of player ranked
by number of incorrect guesses). For example:
You are a Cryptoquote Champion:
you solved the puzzle with no incorrect guesses!!!
or
You are a Cryptoquote Master:
you Solved the puzzle making only 3 incorrect guesses!
or
You are a Cryptoquote Novice:
you Solved the puzzle, but you had 11 incorrect guesses.
- Add support for multi-line quotes. Longer quotes
are easier to solve, but printing them all on a single
line is messy due to line wrapping. A better solution
is to allow a long quote to span multiple lines in both
the file and the output of your program. However, this
version requires some more care in reading in the quotes
from a file and choosing a random quote.
If you try this extension, do it in a different file from your
main lab 7 solution (cp and then implement multi-line quotes
in multicryptoquote.py):
cp cryptoquote.py multicryptoquote.py
For this case you need
to change the format of the input file to add a delimiter to signify
the beginning of a new quote (since each quote will span multiple lines
in the file). For example, you could create a quote file in which the quotes
are separated by a line of 5 '=' characters:
=====
first quote.
quotes can span multiple lines.
=====
second quote. Quotes can have any
capitalization, and any punctuation and white space!!!!
=====
next quote
=====
last quote
Here is an example run of this version with a three line quote.
- Add support to the multi-line version for listing the quote and its decoding so far, one line
at a time. For example (here I'm using the '-' character to represent
unguessed decodings):
I- RE-O--I-I-- THE HU---IT- OF OUR FELLOW -EI--- WE ---
us ylmepsuxusp rgl gvansurq eh evy hlffec oluspj, cl knq
OUR-EL-E- THE HI-HE-T TRI-UTE
evyjlfzlj rgl gupgljr ryuovrl.
THUR-OO- --R-H-LL
-- rgvypeeb anyjgnff
- Some versions of the game include letter frequencies below each encoded
letter. Add letter frequencies (how many of each letter are in the solution)
to your game. In the example below, there are 2 A's in the solution, 3 S's, 3 T's, 4 I's, etc:
A STITCH IN TIME SA_ES NINE.
P RIKIFJ KB IKEY RPDYR BKBY.
2 334311 43 3413 32133 3433
Submit
- Part1: Top-Down-Design and program stubs.
once you are satisfied with your design-cryptoqyote.py
program design, run handin21 and email your instructor notifying
him/her that you have submitted your design.
- Part2: complete program.
once you are satisfied with your cryptoqyote.py
program, fill out the questionnaire in README-07.txt.
Then run handin21 a final time to make sure we have
access to the most recent versions of your files.