Introduction to Computer Science: The Way of the Program — Homework 4

Due by 11:59pm Tuesday, October 3

Reading

Automated Tester Program

  1. Download the file hw4tester.py and put it in your Downloads folder. You will also need autotester_base.py, but if you already downloaded it during lab and put it in Downloads, you don't need to download it again.

  2. Put all of your code for this assignment in a file named assign4.py, and copy-and-paste the following two lines into your file at the very top:

    import sys,os;sys.path.append(os.path.join(os.path.expanduser('~'),'Downloads'))
from hw4tester import *

  3. To use the autotester, type test(function_name) at the Python prompt to test an individual function on a set of predefined test cases. For example, to test your phone function, you would simply type test(phone). You can also run individual test cases by typing test(function_name, case_number). For example, to see case number 2 for phone in detail, type test(phone, 2). To see a "verbose" report of all test cases for phone in detail, type vtest(phone). To test all of your functions in sequence, type testall().

Programming Exercises

  1. Include all of your programs from Lab 4 in your assign4.py file.

  2. Write a program called solidbox() that prompts the user for a number n and then prints a solid rectangular "box" of dots (periods) with n rows containing n dots in each row.

    >>> solidbox()
Enter box size: 3
...
...
...

>>> solidbox()
Enter box size: 10
..........
..........
..........
..........
..........
..........
..........
..........
..........
..........

  3. Write a program called outlinebox() that asks the user for a number n and then prints the dotted outline of a box of width and height n, using periods. To do this, first construct two strings using string concatenation and repetition (the + and * operators): one string to use for the top and bottom rows (all dots), and another one for the intermediate rows (dots and spaces). Then print out the box one row at a time using a for-loop. For example: 

    >>> outlinebox()
Enter box size: 5
.....
.   .
.   .
.   .
.....

>>> outlinebox()
Enter box size: 8
........
.      .
.      .
.      .
.      .
.      .
.      .
........

  4. Write a program called randkey() that prints out a random key for use with the substitution cipher program that we developed in class. A random key is a string consisting of all 52 lowercase and uppercase letters of the alphabet in some randomized order. Here is one approach: start with a string s containing all 52 letters, and a new empty string k. Choose a random letter from s and add it to the end of k. Then remove the letter from s. Continue this process until all letters have been transferred from s to k. After 52 steps, k will contain all the letters in some random order. Hints: you can use the random.choice function from the random library to choose a random letter from a string. For example, random.choice("abcde") might give "d". To remove a letter, build a new string consisting of all letters up to (but not including) the one to be removed, followed by the rest of the letters in the string, like the removeLetter() program that we developed in class. Examples:

    >>> randkey()
ZeTixwCyKhXSAljFzUWsVrvdupOIMtnRacgNbLQfYPBqEDHmJokG

>>> randkey()
pqvzHYwoCXgmLBVfFcyMEruNIDTOkaKsdiWGthAUlSbjeZxJPRQn

>>> randkey()
qQCvOPteIspnNWwhRHLgcmUEjJSYAuDzoTVBaFGyKdlMirXZbxfk

  5. The disadvantage of a completely random encryption key is that it can be very difficult to remember. Another approach is to have the user enter a password of their choice, and then construct a key based on the password. Write a program called passkey() that prompts the user for a password containing only lowercase and uppercase letters (no punctuation or spaces) and generates a key using the algorithm illustrated below:

    1. Start with a key consisting of all lowercase and uppercase letters of the alphabet: 
      abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
    2. Get a password from the user: 
      TopSecreT
    3. Split the alphabet into two parts based on the first letter of the password: (1) from the beginning up to, but not including, the letter, and (2) from the letter to the end of the alphabet. Then swap the two parts: 
         abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
=> TUVWXYZabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRS
    4. Remove all letters from the key that appear in the password: 
         TUVWXYZabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRS
=> UVWXYZabdfghijklmnqstuvwxyzABCDEFGHIJKLMNOPQR
    5. Remove all duplicate letters from the password: 
      TopSecreT  => TopSecr
    6. Add the modified password to the beginning of the key: 
      TopSecrUVWXYZabdfghijklmnqstuvwxyzABCDEFGHIJKLMNOPQR

    Examples:

    >>> passkey()
Enter a password: TopSecreT
TopSecrUVWXYZabdfghijklmnqstuvwxyzABCDEFGHIJKLMNOPQR

>>> passkey()
Enter a password: opensesame
opensamqrtuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZbcdfghijkl

>>> passkey()
Enter a password: Pineapple
PineaplQRSTUVWXYZbcdfghjkmoqrstuvwxyzABCDEFGHIJKLMNO

EXTRA CREDIT PROBLEMS (OPTIONAL):

You should finish the other problems first before working on these.

  1. Write a program called diagonalbox() that asks the user for a number n and prints out a dotted box of width and height n, with a diagonal running from the top left corner of the box to the bottom right corner, as shown below.

    >>> diagonalbox()
Enter box size: 10
..........
..       .
. .      .
.  .     .
.   .    .
.    .   .
.     .  .
.      . .
.       ..
..........

  2. Write a program called base2decimal that asks the user for a numerical base from 2 to 36, and a string of digits representing a number written in that base, and converts the number to base 10. Assume that bases greater than 10 use uppercase letters from A to Z as extra digits, as needed. For example, the base 16 number FAB4 can be converted to base 10 as follows: 

    >>> base2decimal()
What base (2-36) do you want? 16
Enter a number written in base 16: FAB4
FAB4 in base 16 equals 64180 in base 10

>>> base2decimal()
What base (2-36) do you want? 11
Enter a number written in base 11: 77
77 in base 11 equals 84 in base 10

>>> base2decimal()
What base (2-36) do you want? 36
Enter a number written in base 36: 2KRAZY
2KRAZY in base 36 equals 155798638 in base 10

  3. Substitution ciphers are not very secure, and can easily be broken by analyzing the frequencies of letters in the encrypted text. The so-called Vigenere cipher overcomes this problem by encoding a letter using one of several possible letter mappings (instead of using the same one for all letters, as in a substitution cipher). Which mapping to use depends on the letter's position in the text, and is determined by a password provided by the user. For example, if the message to be encoded is "the eagle has landed", and the password is "DaVinci", we line up the message and password like this, adding as many repetitions of the password as necessary:

    password:  D a V i n c i D a V i n c i D a V i n c
 message:  t h e _ e a g l e _ h a s _ l a n d e d

    To encode the initial t of the message, we use a shifted version of the full lowercase and uppercase alphabet beginning with D (the first letter of the password) as our key, so t maps to W

       abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
                      |
   DEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzABC

    The next letter h of the message is encoded using a shifted key beginning with a (the second letter of the password), so it maps to h

       abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
          |
   abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

    The next letter e uses a shifted key beginning at V, so it maps to Z

       abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
       |
   VWXYZabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTU

    For simplicity, we'll assume that non-alphabetic characters such as spaces and punctuation just map to themselves. The second e, however, uses a key beginning at n, so it maps to r this time:

       abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
       |
   nopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklm

    And so on, for all characters in the message. The final encrypted message is: WhZ rcoOe pnu Oailrf

    Write a program called vigenere() that prompts the user for a message and a password, and encrypts the message using the Vigenere cipher. You may assume that the password will contain no spaces or punctuation (but the message might). For example:

    >>> vigenere()
Enter a message: the eagle has landed
Enter a password: DaVinci
WhZ rcoOe pnu Oailrf

>>> vigenere()
Enter a message: the microphone is hidden in the EGGROLLS!!!
Enter a password: soysauce
LvC mCevGDFGny mK FAdxgr wL tBg WUejOfNW!!!

Turning in Your Homework