Overview

Weight: This assignment will count for approximately 7% of your final grade.
Due Date: Monday, January 29, 2007 (by 11:59PM) (corrected from Jan. 22)
In this assignment you will explore use of some of the features of Python.

Turning in your assignment

Note the following directions carefully. Points will be deducted for incorrectly named files and functions. All code should be developed in the one directory. Each problem solution should be placed in a separate file within that directory with a .py extension, e.g., trans.py. When you are done and certain that everything is working correctly, create a tarred, gzipped copy of your directory by executing

  tar cf one.tar one; gzip one.tar

or zip it on a Windows system. Turn in the tarred, gzipped or zipped directory using the turn-in page. The file you upload should be named one.tar.gz or one.zip. On the upload page, write a comment indicating whether your code is intended for Unix/Linux or Windows -- programs' behavior may differ slightly between the two systems; your code only has to work on one or the other. You may turn in your assignment as many times as you like. Only the last one submitted before the deadline will be graded.

The work you turn in is to be your own personal work. You may not work together with another student, copy code from the web, or anything else that lets you avoid solving the problems for yourself. If you are stuck contact the TA or me, not other students.

Grading

The assignment will be marked for good programming style (appropriate algorithms, good indentation and appropriate comments), as well as clean compilation and correction execution. Good python style favors for loops rather than while loops (when possible) for reasons discussed in class. Also, code to do the same thing (or something easily parameterizable) at different points in a program should not be duplicated but extracted into a callable function.

Warmup -- trans.py -- 30%

The text of a message can be hidden by applying a translation function to each character.

Write a function trans(ttable, s). trans translates its string argument, s, according to its translation table argument, ttable. Argument ttable will consist of a tuple (pair) of strings (s1, s2). s1 and s2 must be the same length with each character appearing at most once in each string. The meaning of the ttable is that a character in the input string, s, that appears in string s1 at position p should be translated to the character at position p in s2. If an input character does not appear in s1 it should appear in the output unchanged. In the implementation of trans you must first build a dictionary representing the ttable and must not use python's built-in translate function or method.
Hint: the first thing to figure out is what a dictionary is good for in this problem.

Write a function untrans(ttable,s) taking the same arguments as trans but mapping each character from s2 to the character at the same position in s1. Thus untrans(tt, trans(tt, s)) yields s. In implementing untrans you must use python's translate built-in string method. Look at the definition of maketrans in the string module for help in building the needed translation table argument for translate. (translate requires a different representation of the translation table than is used by trans and untrans).

Both trans and untrans must be implemented in a file named trans.py. We will test your functions by using code similar to:

   import trans
   print trans.trans((s1,s2),s)

for various values of s1, s2, and s.

histo.py - 30%

Write a function, histo(s) in file histo.py. The function returns a list of characters in the input string s each paired with its frequency. Characters must appear in the list ordered from most frequent to least frequent. For example, histo('implemented') is [('e',3), ('m',2), ('d',1),('t',1), ('i',1), ('p',1), ('l',1), ('n',1), ]. (Characters with the same frequency may appear in any order.) Your code will be tested by using code similar to:

   import histo
   print histo.histo(s)

for various values of s. Required: Use an implementation of sorting from the Python library. Do not write your own sort. Hint: By now you should be familiar with using dictionaries and should be able to write a function that builds the histogram in a single pass over the input string.

digraphs.py - 30%

A digraph is a pair of characters that occur adjacent to one another in a text. By convention we write each digraph between a pair of '/' characters to make it easier to see where the blanks are. For example the digraphs at the beginning of the previous sentence are /A /, / d/, /di/, /ig/, etc. Digraph frequency counts are helpful in cryptological analysis of some ciphers.

The digraphs(s) function returns a list containing the number of times each digraph occurs in s. Digraphs must be listed from most frequently occurring to least frequently occurring. Digraphs that do not occur in the input (0 occurrences) should not be listed in the output.

Here is what the function might return on some hypothetical sample input: [('/e /', 83), ('/ t/', 66), ('/ a/', 56), ('/in/', 53), ('/th/', 52), ('/ </', 48), ('/co/', 47), ('/re/', 44), ('/de/', 44), ('/s /', 44), ('/to/', 42), ('/he/', 41), ('/n /', 40), ('/d /', 38), ('/ o/', 37), ('/t /', 36), ('/or/', 36), ('/ i/', 34), ('/an/', 33), ('/r /', 32), ('/. /', 31), ('/ d/', 30)]

Cryptogram - 10%

Use your trans, histo, and digraph functions to try to figure out the following cryptogram. If you haven't solved one of these before you may want to look on the web for hints on the relative frequencies of letters and digraphs in the English language. You can use your functions to try out different possibilities and get clues about the translation being used. (Digits and punctuation are not changed in this cryptogram.)

Hint: use your trans function to translate the uppercase cryptogram characters to lowercase plaintext characters to make it visually apparent which characters have been translated.

Put your answer in a file called cryptogram.txt and zip/tar it along with the rest of the files making up this assignment.

Do not reveal your answer to other students.

ABCDE FEDGBC, BH DGI FEDGBCJ, KJ DGI LBMMILDKNI COAI BP DGI LHIODBHJ BP ABCDE FEDGBC'J PMEKCQ LKHLRJ,
O SHKDKJG DIMINKJKBC LBAITE JUIDLG JGBV DGOD PKHJD OKHIT KC 1969.
O DBDOM BP 45 IFKJBTIJ VIHI AOTI BNIH PBRH JIHKIJ.
GBVINIH, DGI FEDGBC FGICBAICBC TINIMBFIT PHBA DGI BHKQKCOM DIMINKJKBC JIHKIJ KCDB
JBAIDGKCQ ARLG QHIODIH, KC JLBFI OCT KAFOLD: KD JFOVCIT DBRHKCQ JDOQI JGBVJ,
PBRH PKMAJ, CRAIHBRJ OMSRAJ, JINIHOM SBBUJ OCT O JFKC-BPP JDOQI ARJKLOM OJ VIMM OJ
KCJFKHKCQ DGI COAI BP O FHBQHOAAKCQ MOCQROQI.