# CS21 Lab 7: Top-Down Design: Cryptoquote

Top-Down Design due by midnight on Saturday, March 18
Full solution due by midnight on Saturday, March 25

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:

• Create design-cryptoquote.py first, into which you will implement your solution to the top-down design part of this assignment.
• After you have a working design (see below), run handin21 to turn it in! Then, send your professor a short email, letting them know your design is done. We will take a look at each design and send you comments (usually within a day or two).
• After you have the design done, and have heard back from your professor, copy your design-cryptoquote.py file to cryptoquote.py, and implement the full game in cryptoquote.py:
  cp design-cryptoquote.py cryptoquote.py

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

• 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

• 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

1. 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.
2. Part2: complete program.