Projects and Labs in CS 2

For projects in CS 2, you will sometimes be allowed to work in groups of two. This project, however, is solo. You may discuss high-level ideas with other students, but any viewing, sharing, copying, or dictating of code is forbidden. The projects are intended to be more difficult than the labs; they test how much of the material that lecture and lab introduced that you have actually learned. You will notice that labs are much more straight-forward about how to implement things, whereas projects will have a much larger design component where you have to decide how to set things up. We will ramp up slowly on this; so, for this project, we will still give you a lot of guidance. However, if you get stuck for more than 30 minutes on a bug, you should come to office hours. We want this experience to be an enjoyable one, and nobody really enjoys debugging for hours on end.

Setup

If you haven’t already, do the setup. Otherwise, just register for the project using grinch: https://grinch.caltech.edu/register and clone the repository as explained in the setup instructions.

From CS 1 to CS 2

Caesar Ciphers

A cipher is an algorithm for encrypting or decrypting text. Generally, we call the unencrypted text “plain text” and encrypted version “cipher text”.

Here is an example of text that uses a Caesar cipher (which you will implement in this project):

Notably, the original text is readable, but the encrypted version is not.

A Caesar Cipher is computed by “shifting” each letter of the text by a constant number, \(k\), as if they were in a circle. For example, the following “ring” represents a mapping for a Caesar Cipher where \(k = 4\):

Caesar Cipher Creator (D Tests)

In this part, you will be editing the src/CaesarCipher.java file which has empty methods for you to fill in. As we will be providing you with Python code for these methods, you might find the handout that compares Python and Java syntax on the course website to be helpful.

Implementing the Class

Ultimately, the goal for this part is to take in a piece of text (the “plain text”) and a number of letters to rotate by (the “key”), and output the encrypted text (the “cipher text”). You should begin by reading the main method, which we have written for you, to get a sense of how Java can read from and write to the console.

In Python, there is only one way to represent Strings of length one; however, in Java, there are two. First, we can represent them as a string like in Python. Second, they constitute a separate type called char (or Character). The reason for this distinction is that, because we have types in Java, it is useful to be able to specify that we’re working with a single letter. Unlike in Python, Strings in Java must use double quotes and chars must use single quotes.

The first function you should implement is findIndexInAlphabet. Note that these purple boxes in the specification always indicate a function you will have to write.

public static int findIndexInAlphabet(char c)

def findIndexInAlphabet(c):
    for i in range(len(ALPHABET)):
        if ALPHABET[i] == c:
            return i
    return -1

In Python, you can’t have two methods named the same thing, even if they have different arguments; however, in Java, this is allowed and called method overloading. Next, you will implement two versions of the rot method: one for if we want to rotate a character and another for rotating a String. Second, you should implement the char version.

public static char rot(char c, int amount)

def rot(c, n):
    idx = findIndexInAlphabet(c)
    newIdx = (idx + n) % len(ALPHABET)
    return ALPHABET[newIdx]

Finally, you will write the String version which gets called directly from main.

public static String rot(String line, int amount)

def rot(line, n):
    output = ""
    for c in line:
        output += rot(c, n)
    return output

Running the Tests

Those three functions are the only code you have to write for the CaesarCipher class. The next step is testing the code. Normally, you would test it by running main which you are welcome to do, but we’ve provided you with our tests which do this automatically. On the top right of the IntelliJ interface is a green “play” button which will run the tests whenever the “configuration” directly to the left is set to a “Tests” option. If you make sure it says “D Tests” and hit the play button, the JUnit testing interface should pop up on the bottom.

Caesar Cipher Solver (C Tests)

In the previous part, we encrypted a piece of text using a Caesar Cipher. In this part, we will go in the opposite direction: that is, we will decrypt the cipher text back into the plain text. For a Caesar cipher, this means we need to rotate every letter by \(26 - k\), where \(k\) is the key used to encrypt the text originally. Since there are only \(26\) possible values of \(k\), we can just try all of them and see which one “works best”; this technique is called brute forcing a solution.

For this part, you may not use any fancy String or Collection methods that do all the work for you. (In fact, the automated tests will catch if you try to do this and fail.)

Our general strategy for this part (which you will implement in main) is the following:

• Create a Scanner for the console
• Print out “Type a sentence to decrypt: “ (with no newline)
• Get a line of input from the user
• Break up the line into a list of words
• For each possible rotation of the letters:
• If more than half of the words in the sentence are also in the dictionary
  • Print out the sentence with rotated letters

Substitution Cipher Solver (B Tests)

For the last part of this project, we will write a solver for a more complicated cipher in which the mapping between source letters and target letters can be more than just a shift (like in a Caesar Cipher). In particular, we will look at “simple monoalphabetic substitution ciphers” in which the letters are shuffled to create a substitution alphabet and each letter in the source text is replaced with its corresponding letter in the substitution alphabet. For example:

Unlike with Caesar Ciphers, where we can just try every possible key, there are far too many possibilities for substitution ciphers to try them all. Instead, we’ll we’ll use a probabilistic method to only try keys that are likely to be better. To make it even more interesting, we will remove the spaces from the cipher texts for this part as well.

Setting Up A Substitution Cipher

Most of the work in this part will be in implementing a SubstitutionCipher class which will represent a single instance of a substitution cipher key and the corresponding cipher text to decrypt. Your class should store exactly these two things as fields. We represent a key with a Map from Character to Character and the cipher text as just a String. You are now ready to implement the following methods.

public SubstitutionCipher(String ciphertext, Map<Character, Character> key)

Initializes a SubstitutionCipher to use the provided cipher text and key.

public String getCipherText()

Returns the cipher text for this SubstitutionCipher.

public String getPlainText()

Applies the current key to the current cipher text to get a proposed plain text to return.

public SubstitutionCipher randomSwap()

public SubstitutionCipher(String ciphertext)

“Scoring” Phrases and Quadgrams

Ultimately, we will transform an initial random key into keys that fit the text better and better. To figure out if a candidate key is better, we need a way of comparing the “english-ness” of two phrases. We call this idea scoring. To get a score for a phrase, we will split it into rolling chunks of four letters and evaluate their probabilities separately. (Formally, we are making the assumption that each of these chunks is independent, which is not true in general, but is good enough for our purposes.) For example, if we were working with the phrase DOGGIES, we would split it into the chunks: DOGG, OGGI, GGIE, GIES and get the probabilities of each of these. Each of these four letter pieces is called a quadgram.

Computationally, dealing with very small numbers is difficult; so, we will deal with “log probabilities” (also called “log likelihoods”) instead. We have provided you with a class QuadGramLikelihoods which reads in a file of probabilities and provides its user with log likelihoods for all quadgrams. You do not need to understand how it works, but, you are, of course, welcome to read the code. We also used this class in lecture; so, you could look back to those notes.

public double getScore(QuadGramLikelihoods likelihoods)

Returns the sum of the log likelihoods (which you can get from the parameter likelihoods) of each consecutive quadgram in the cipher text. Avoid using getPlainText if your implementation is too slow.

Finding a “Good” Solution

To find a “good solution”, we will put together all the previous pieces into an algorithm called hill climbing which successively improves a random solution. You should implement it as follows.

public SubstitutionCipher getSolution(QuadGramLikelihoods likelihoods)

• Create a cipher with this cipher’s ciphertext and a random key \(C\)
• While fewer than 1000 trials in a row have not resulted in a replacement:
  • Randomly swap two letters in \(C\) to make a new key \(M\)
  • If \(M\) scores better than \(C\):
    • Replace \(C\) with \(M\)

We have implemented a client for your SubstitutionCipher that reads a cipher from the console and uses your class to decrypt it.

Decrypting cryptogram.txt (A Tests)

Committing and Pushing to the Repository

A “commit” is version control language for a chunk of changes that mean something when grouped together. Importantly, commits will only stay locally on your machine until you push them to the gitlab server.

Checking the Results on gitlab

When you go to https://gitlab.caltech.edu, you should see your project01 repository listed. Click on it. All the way on the right, there should be a red “X”, an orange “pause” symbol, a blue “time” symbol, or a green “check” symbol. This symbol indicates the status of the automated tests which will check the correctness of your code. Click on it. On the new page, you should see a table, and under “status”, there should be another symbol. Click on it. The new page will list the “categories” of tests for this repository. These will be some combination of “A”, “B”, “C”, and “D”. These letters indicate what grade you earned on the assessment for passing those tests. If you click on one of them, it will detail for you which sub-tests you passed and failed which might help you debug.

Note that the “A Tests” for project01 are only on gitlab. So, you must check there to make sure you are passing them. It is good practice to always check gitlab after submitting a project or lab in this course.