Project 1: The Enigma

UPDATES:

Introduction

This programming assignment is intended to exercise a few useful data structures and an object-based view of a programming problem. There is some background reading, but the necessary program is not (or rather need not be) terribly big. The conceptual video walkthrough is located here, which we HIGHLY RECOMMEND watching.

We will be grading largely on whether you manage to get your program to work (according to our tests). In addition, we will be looking at your own tests (which you should be sure to turn in as well). While we have supplied a few unit tests and some simple acceptance tests and testing utilities, the tests in the skeleton are entirely inadequate for testing your program (you should be writing your own tests). There is also a stylistic component: the grading machinery require that your program pass a mechanized style check (style61b), which mainly checks for formatting and the presence of comments in the proper places. See the Style Guide for a brief description of the style rules. You may change any of the code we've provided, as long as the resulting program works according to the specifications here.

First, make sure that everything in your repository is properly updated and checked in. Before you start, the command

cd  ~/repo
git status

should report that the directory is clean and that there are no untracked files that should be added and committed. Never start a new assignment without doing this.

To obtain the skeleton files (and set up an initial entry for your project in the repository), you can use the command sequence

git fetch shared
git merge shared/proj1 -m "Get proj1 skeleton"

from your Git working directory (repo). Should we update the skeleton, you can use exactly the same sequence (with an appropriate change in the -m parameter) to update your project with the same changes.

NOTE: Be sure to read the "Advice" and "Common Bugs" sections before you start coding! Also, it can be tempting to just pull the code and jump right in, but you'll be much better off if you at least skim the spec all the way through beforehand. One of the hardest parts of Enigma is the conceptual understanding; make sure you give this spec its due dilligence.

Background

You may have heard of the Enigma machines that Germany used during World War II to encrypt its military communications. If you have not, I recommend you read the wikipedia page on them, or similar resource, especially the part about design and operation. This video shows what one version of the machine looked like and how it operated. This project involves building a simulator for a generalized version of this machine (which itself had several versions.) Your program will take descriptions of possible initial configurations of the machine and messages to encode or decode (the Enigma algorithms were reciprocal, meaning that encryption is its own inverse operation.)

The Enigmas effect a substitution cipher on the letters of a message. That is, at any given time, the machine performs a permutation—a one-to-one mapping—of the alphabet onto itself.

Plain substitution ciphers are easy to break (you've probably seen puzzles in newspapers that consist of breaking such ciphers). The Enigma, however, implements a progressive substitution, different for each subsequent letter of the message. This made decryption considerably more difficult.

The device consists of a simple mechanical system of (partially) interchangeable rotors (Walzen) that sit side-by-side on a shaft and make electrical contact with each other. Most of these rotors have 26 contacts on both sides, which are wired together internally to effect a permutation of signals coming in from one side onto the contacts on the other (and the inverse permutation when going in the reverse direction). To the left of the rotors, one could select one of a set of reflectors (Umkehrwalzen), with contacts on their right sides only, and wired to connect half of those contacts to the other half. A signal starting from the rightmost rotor enters through one of the 26 possible contacts, flows through wires in the rotors, "bounces" off the reflector, and then comes back through the same rotors (in reverse). Because the reflector's permutation was always a derangement (a permutation that never maps a letter to itself), the return route from the reflector was always different from the route to the reflector. As a result, the entire process always permuted each letter to a different one. (This was a significant cryptographic weakness, as it turned out. It doesn't really do a would-be code-breaker any good to know that some letters in an encrypted message might be the same as the those in the plaintext if he doesn't know which ones. But it does a great deal of good to be able to eliminate possible decryptions because some of their letters are the same as in the plaintext.)

Each rotor and each reflector effects a different permutation, and the overall effect depends on their configuration: which rotors and reflector are used, what order they are placed in the machine, and which rotational position they are initially set to. This configuration is the first part of the secret key used to encrypt or decrypt a message.

In what follows, we'll refer to the selected reflector and rotors in a machine's configuration as 1 through N, with 1 being the reflector, and N the rightmost rotor (the first rotor the signal passes through). In our simulator, N (the number of rotors, including the reflector) will be a configuration parameter. In actual Enigma machines, it was fixed for any given model (the Kreigsmarine (Navy) used $N=5$ (four rotors and reflector) and the Wehrmacht used $N=4$.)

The overall permutation changes with each successive letter because some rotors rotate after encrypting a letter. Each rotor has a circular ratchet on its right side and an "alphabet ring" on its left side that fits over the ratchet of the rotor to its left. Before a letter of a message is translated, spring-loaded pawls (levers)—one to the right of each rotating rotor—try to engage the ratchet on the right side of their rotors and thus rotate its rotor by one position, changing the permutation performed by the rotor.

The pawl on the rightmost rotor (N) always succeeds, so that rotor N (the "fast" rotor) rotates one position before each character is inputted. The pawls pushing the other rotors, however, are normally blocked from engaging their rotors by the alphabet ring on the left side of the rotor to their right.

This ring usually holds the pawl away from its own ratchet, preventing the rotor wheel to its left from moving. However, the rings have notches in them (either one or two in the original Enigma machines), and when the pawl is positioned over a notch in the ring for the rotor to its right, it slips through to its own rotor and pushes it forward. A "feature" of the design called "double stepping" (corrected in other versions of the Enigma, since it reduced the period of the cipher) is that when a pawl is in a notch, it also moves the notch itself and the rotor the notch is connected to. Since the notch for rotor $i$ is connected to rotor $i$, when the pawl of rotor $i - 1$ slips through into the notch for rotor $i$, rotors on both sides of the pawl move (so rotor $i-1$ and rotor $i$ move).

The effect of advancing a wheel is to change where on the wheel any given signal enters or leaves. When a wheel is in its 'A' setting in the machine, then a signal that arrives from the right at, say, the 'C' position, goes into the 'C' contact on the wheel. Likewise, a signal that leaves the wheel from its left 'C' contact exits at the 'C' position. When the wheel is rotated by one to its 'B' setting, a signal that arrives at the 'C' position goes instead into the 'D' contact on the wheel, and a signal that leaves through the 'D' contact does so at the 'C' position. It's easier to calculate if we use numbers 0--25 rather than letters ('A' is 0, 'B' is 1, etc.). Then, when the wheel is in its $k$ setting, a signal entering at the $p$ position enters the $p+k \bmod 26$ contact on the wheel, and a signal exiting through the $c$ contact does so at the $c - k \bmod 26$ position. For example, Figure 1 shows one of the rotors from the real Enigma machines (called rotor "I") and the effect of moving from its 'A' to its 'B' setting.

Rotor Example

Figure 1. Permutations performed by a rotor in its 'A' and 'B' settings. The italicized alphabets at the top and bottom indicate the letters corresponding to the positions around the rotor. The inner alphabets indicate the positions along the rotor itself. The rotor depicted was designated 'I' in the original Enigma machine used by the German military.

Let's illustrate with a much simplified version. Suppose our alphabet has only the letters A-C and we have four rotors (numbered 1-4) each of which has one notch on its ring at the C position. Suppose also that there are 3 pawls, one for each of rotors 2-4. We will still refer to these as pawls 2-4, to maintain that pawl $i$ belongs to rotor $i$. There is no pawl for rotor 1, which will therefore not rotate. We'll start with the rotors set at AAAA. These letter correspond to only the positions of the rotors, and not the characters that are being translated. The next 19 positions are as follows:

AAAB  AAAC  AABA  AABB  AABC  AACA  ABAB  ABAC
ABBA  ABBB  ABBC  ABCA  ACAB  ACAC  ACBA  ACBB
ACBC  ACCA  AAAB

As you can see,

So the advancement of the rotors, while similar to that of the wheels of an odometer, is not quite the same. If it were, then the next position after AACA would be AACB, rather than ABAB. Also, it would take 27 steps to return to the initial configuration instead of 18.

Take the time to really understand the above example. It will save you time when implementing the above behavior. Furthermore, convince yourself of the fact that each rotor can only advance at most one position per character inputted.

In this project, you'll simulate the path of each signal and indicate where (at what letter position) it comes out. In the actual Enigma machines, the contacts on the rightmost rotor's right side connect with stationary input and output contacts, which run to keys that, when pressed, direct current to the contact from a battery or, when not pressed, direct current back from the contact to a light bulb indicating a letter of the alphabet. Since a letter never encrypts or decrypts to itself after going back and forth through the rotors, the to and from directions never conflict.

When the machines were in use, The German Navy used a machine with five rotor slots and 12 rotors to choose from:

Given just this equipment, there are 614,175,744 possible configurations (or keys):

Especially by today's standards, this is not a large key size (less than 30 bits). To make things more difficult for code-breakers, therefore, the Enigma incorporated a plugboard (Steckerbrett) between the keyboard and the rightmost wheel. It acted as a non-moving, configurable rotor. The operator could choose any set of disjoint pairs of letters by means of cables placed between them on the plugboard. Each selected pair would then be swapped going into the machine from the keyboard and coming out into the indicator lights. Thus, if the operator connected ("steckered") the letters A and P, then P would be substituted for each A typed and vice versa. If the ingoing letter was A, it would enter the rightmost rotor as a P, and if the ingoing letter was P, it would enter the rotor as an A. Likewise, if an ingoing letter was encrypted to P by the other rotors, it would display as A, and letters encrypted as A would display as P.

Describing Permutations

Since the rotors and the plugboard implement permutations, we'll need a standard way to describe them. We could simply have a table showing each letter and what it maps to, but we'll use a more compact notation known as cycle representation. The idea is that any permutation of a set may be described as a set of cyclic permutations. For example, the notation

(AELTPHQXRU) (BKNW) (CMOY) (DFG) (IV) (JZ) (S)

describes the permutation in Figure 1. It describes seven cycles:

The inverse permutation just reverses these cycles:

Each letter appears in one and only one cycle, so the mapping is unambiguous. As a shorthand, we'll say that if a letter is left out of all cycles, it maps to itself (so that we could have left off "(S)" In the example above.)

Figure 2 shows the permutations corresponding to the rotors used in the German Navy's Enigma machine.

Rotor Permutation (as cycles) Notch
Rotor I (AELTPHQXRU) (BKNW) (CMOY) (DFG) (IV) (JZ) (S) Q
Rotor II (FIXVYOMW) (CDKLHUP) (ESZ) (BJ) (GR) (NT) (A) (Q) E
Rotor III (ABDHPEJT) (CFLVMZOYQIRWUKXSG) (N) V
Rotor IV (AEPLIYWCOXMRFZBSTGJQNH) (DV) (KU) J
Rotor V (AVOLDRWFIUQ)(BZKSMNHYC) (EGTJPX) Z
Rotor VI (AJQDVLEOZWIYTS) (CGMNHFUX) (BPRK) Z and M
Rotor VII (ANOUPFRIMBZTLWKSVEGCJYDHXQ) Z and M
Rotor VIII (AFLSETWUNDHOZVICQ) (BKJ) (GXY) (MPR) Z and M
Rotor Beta (ALBEVFCYODJWUGNMQTZSKPR) (HIX)
Rotor Gamma (AFNIRLBSQWVXGUZDKMTPCOYJHE)
Reflector B (AE) (BN) (CK) (DQ) (FU) (GY) (HW) (IJ) (LO) (MP) (RX) (SZ) (TV)
Reflector C (AR) (BD) (CO) (EJ) (FN) (GT) (HK) (IV) (LM) (PW) (QZ) (SX) (UY)

Figure 2. The rotors used in the Naval Enigma, showing the permutations they implement and the point(s) at which there are notches that allow their left neighbor rotor to advance. Thus, when Rotor I is at 'Q' and the machine advances, the rotor to the left of Rotor I will advance. The Beta and Gamma rotors and the reflectors do not rotate. Some trivia: The reflectors shown here are the "thin" versions of the reflectors used in the naval M4 Enigma machine. The B reflector together with the Beta rotor in the 'A' position had the same effect as the usual ("thick") B reflector in the older three-rotor M3 Enigma machine (likewise the C reflector with the Gamma rotor). This allowed the M4 to encrypt and decrypt messages to and from M3 Enigmas. Source: Tony Sale's pages.

An Example

As an example of a translation, consider the set of rotors from Figure 2, and suppose that

We input the letter 'Y', which causes the following steps:

  1. The pawls all move. This causes rotor 5 to advance from E to F. The other two pawls are not over notches, so rotors 3 and 4 do not move.
  2. The letter 'Y' enters the plugboard and is converted to 'F'.
  3. The letter 'F' enters the right side of rotor 5 (an I rotor) at position 5, since 'F' is the 5th letter of the alphabet numbering from 0. Since the current setting of rotor 5 is 'F', the signal enters the rotor at position $5$, but hits contact $5+5=10$, or 'K'.
  4. According to Figure 2, rotor I converts 'K' to 'N' (letter number 13). Because the setting of rotor I is 'F', however, the signal actually comes out at letter position $13-5=8$ ('I').
  5. The 'I' signal from rotor 5 now goes into the right side of rotor 4. Since rotor 4 is a IV rotor and is in the 'L' (or 11) setting, the 'I' enters at contact $8+11=19$ ('T'), and is translated to 'G' (6), which comes out at position $6-11=-5 = 21 \bmod 26$, the fifth letter from the end of the alphabet ('V').
  6. The 'V' from rotor 4 goes now to the right side of rotor 3, a III rotor in setting 'X' (23). The signal enters the rotor at contact $21+23 = 44 = 18 \bmod 26$ ('S'), is translated to 'G' (6), which exits at position $6 - 23 = -17 = 9 \bmod 26$ ('J').
  7. Rotor 2 (Beta) is in position 'A', and thus translates 'J' to 'W'.
  8. Rotor 1 (B) converts the 'W' to 'H' and bounces it back to the left side of rotor 2.
  9. Rotor 2 (Beta in the 'A' position) converts 'H' on its left to 'X' (23) on its right.
  10. The 'X' from rotor 2 now goes into the $23 + 23 = 46 = 20 \bmod 26$ ('U') contact on the left side of rotor 3 (III in setting 'X'), and is converted to 'W' (22), which comes out at position $22-23=-1=25 \bmod 26$ ('Z') on the right side of rotor 3.
  11. 'Z' now enters the left side of rotor 4 (IV in setting 'L') at $25+11=36=10 \bmod 26$ ('K'), and is translated to 'U' (20), which comes out at position $20 - 11=9$ ('J') on the right side of rotor 4.
  12. The 'J' from rotor 4 enters the left side of rotor 5 (I at setting 'F') at contact $9 + 5= 14$ ('O'), is translated to 'M' (12), and comes out at position $12 - 5 = 7$ ('H') on the right side of rotor 5.
  13. Finally,the letter 'H' is converted to 'Z' by the plugboard.

Therefore, 'Y' is converted to 'Z'. Figure 3 is a visual depiction of this example. It shows the rotors after rotation; you can see the resulting setting of the last four rotors (AXLF) as the letters at the top of those rotors.

Translation of Y to Z

Figure 3. Conversion of one character by the Enigma machine through the plugboard, rotors I, IV, III, Beta, reflector B, and then (in red) back in reverse sequence. The letters at the top of the four moving rotors are the current setting (after the rotors advance), which would be showing in the machine's window. As shown, this setting modifies at which contacts on the rotors characters enter and leave. For example, rotor III is set so that the contact at the top (0) position enters at 'X' (letter 23 in the alphabet, numbering from 0), and therefore the 21 position enters at 'S' (letter 18 in the alphabet), because 21 + 23 = 44 = 18 mod 26.

The above is an example of just one conversion. The pawls attempt to rotate the rotors before each letter is converted! After a total of 12 characters are converted, the rotor settings will have become 'AXLQ'. Just before the next character is converted, rotor 5 will advance to 'R' and, since its notch is at position 'Q', rotor 4 will advance to 'M', so that the rotor configuration will be 'AXMR' before the 13th character is converted. After an additional 597 characters have been converted, the configuration will be 'AXIQ'. The character after that will advance rotor 5 to 'R' and rotor 4 to 'J', giving 'AXJR'. The next character will advance 5 to 'S', and, since rotor IV's notch is at 'J', rotor 3 will advance to 'Y'. Also, as rotor 3's pawl advances rotor 3, it also moves the notch on rotor 4, advancing rotor 4 to 'K', so that the configuration goes from 'AXJR' to 'AYKS'. Rotor 3 in this case has a notch at 'V', but since rotor 2 has no pawl, rotor 3's notch never has any effect.

At this point, you can check your understanding of the machine using this Conceptual Check quiz. This quiz is not worth any points, and is only meant as a resource to ensure you understand the above details.

Input and Output

To run your program on the command line, first compile all of your files with

    make

After compiling, you can use the command

    java -ea enigma.Main [configuration file] [input file] [output file]

to run your program. The configuration file contains descriptions of the machine and the available rotors. The data are in free format. That is, they consist of strings of non-whitespace characters separated by arbitrary whitespace (spaces, tabs, and newlines), so that indentation, spacing, and line breaks are irrelevant. Each configuration file has the following contents:

For example, the German Naval Enigma machine as discussed in An Example would be described with this configuration file:

          ABCDEFGHIJKLMNOPQRSTUVWXYZ
          5 3
          I MQ      (AELTPHQXRU) (BKNW) (CMOY) (DFG) (IV) (JZ) (S)
          II ME     (FIXVYOMW) (CDKLHUP) (ESZ) (BJ) (GR) (NT) (A) (Q)
          III MV    (ABDHPEJT) (CFLVMZOYQIRWUKXSG) (N)
          IV MJ     (AEPLIYWCOXMRFZBSTGJQNH) (DV) (KU)
          V MZ      (AVOLDRWFIUQ)(BZKSMNHYC) (EGTJPX)
          VI MZM    (AJQDVLEOZWIYTS) (CGMNHFUX) (BPRK)
          VII MZM   (ANOUPFRIMBZTLWKSVEGCJYDHXQ)
          VIII MZM  (AFLSETWUNDHOZVICQ) (BKJ) (GXY) (MPR)
          Beta N    (ALBEVFCYODJWUGNMQTZSKPR) (HIX)
          Gamma N   (AFNIRLBSQWVXGUZDKMTPCOYJHE)
          B R       (AE) (BN) (CK) (DQ) (FU) (GY) (HW) (IJ) (LO) (MP)
                    (RX) (SZ) (TV)
          C R       (AR) (BD) (CO) (EJ) (FN) (GT) (HK) (IV) (LM) (PW)
                    (QZ) (SX) (UY)

The input file to your program will consist of a sequence of messages to decode, each preceded by a line giving the initial settings. Given the configuration file above, a settings line looks like this:

	`* B Beta III IV I AXLE (YF) (ZH)`.

The asterisk must appear in the first column. Other items on the line may be separated from each other by tabs and blanks; adjacent items that are rotor names or consist entirely of letters from the alphabet must be so separated. This particular example means that the rotors used are reflector B, and rotors Beta, III, IV, and I, with rotor I in the rightmost, or fast, slot. The four letters of the following word (AXLE in the example) give the initial positions of rotors 2-5, respectively (i.e., not including the reflector). Any number of steckered pairs may follow (including none). In our example, the remaining parenthesized items indicate that the letter pair Y and F and the pair Z and H are steckered (swapped going in from the keyboard and going out to the lights).

In general for this particular configuration, rotor 1 is always the reflector; rotor 2 is Beta or Gamma, and each of 3-5 is one of rotors I-VIII. Convince yourself of this based on the configuration file. A rotor may not be repeated.

After each settings line comes a message on any number of lines. Each line of a message consists only of letters (here meaning characters from the specified alphabet), spaces, and tabs (0 or more). The program should ignore the blanks and tabs. The end of message is indicated either by the end of the input or by a new configuration line (distinguished by its leading asterisk). The machine is not reset between lines, but continues stepping from where it left off on the previous message line. Because the Enigma is a reciprocal cipher, a given translation may either be a decryption or encryption; you don't have to worry about which, since the process is the same in any case!

Output the translation for each message line in groups of five characters, separated by a space (the last group or the last set of characters on a line may have fewer characters, depending on the message length). Figure 3 contains an example that shows an encryption followed by a decryption of the encrypted message. Since we have yet to cover the details of File I/O, you will be provided the File IO machinery for this project.

             Input                              |         Output
* B Beta III IV I AXLE (HQ) (EX) (IP) (TR) (BY) | QVPQS OKOIL PUBKJ ZPISF XDW
FROM HIS SHOULDER HIAWATHA                      | BHCNS CXNUO AATZX SRCFY DGU
TOOK THE CAMERA OF ROSEWOOD                     | FLPNX GXIXT YJUJR CAUGE UNCFM KUF
MADE OF SLIDING FOLDING ROSEWOOD                | WJFGK CIIRG XODJG VCGPQ OH
NEATLY PUT IT ALL TOGETHER                      | ALWEB UHTZM OXIIV XUEFP RPR
IN ITS CASE IT LAY COMPACTLY                    | KCGVP FPYKI KITLB URVGT SFU
FOLDED INTO NEARLY NOTHING                      | SMBNK FRIIM PDOFJ VTTUG RZM
BUT HE OPENED OUT THE HINGES                    | UVCYL FDZPG IBXRE WXUEB ZQJO
PUSHED AND PULLED THE JOINTS                    | YMHIP GRRE
   AND HINGES                                   | GOHET UXDTW LCMMW AVNVJ VH
TILL IT LOOKED ALL SQUARES                      | OUFAN TQACK
   AND OBLONGS                                  | KTOZZ RDABQ NNVPO IEFQA FS
LIKE A COMPLICATED FIGURE                       | VVICV UDUER EYNPF FMNBJ VGQ
IN THE SECOND BOOK OF EUCLID                    |
                                                | FROMH ISSHO ULDER HIAWA THA
* B Beta III IV I AXLE (HQ) (EX) (IP) (TR) (BY) | TOOKT HECAM ERAOF ROSEW OOD
QVPQS OKOIL PUBKJ ZPISF XDW                     | MADEO FSLID INGFO LDING ROSEW OOD
BHCNS CXNUO AATZX SRCFY DGU                     | NEATL YPUTI TALLT OGETH ER
FLPNX GXIXT YJUJR CAUGE UNCFM KUF               | INITS CASEI TLAYC OMPAC TLY
WJFGK CIIRG XODJG VCGPQ OH                      | FOLDE DINTO NEARL YNOTH ING
ALWEB UHTZM OXIIV XUEFP RPR                     | BUTHE OPENE DOUTT HEHIN GES
KCGVP FPYKI KITLB URVGT SFU                     | PUSHE DANDP ULLED THEJO INTS
SMBNK FRIIM PDOFJ VTTUG RZM                     | ANDHI NGES
UVCYL FDZPG IBXRE WXUEB ZQJO                    | TILLI TLOOK EDALL SQUAR ES
YMHIP GRRE                                      | ANDOB LONGS
GOHET UXDTW LCMMW AVNVJ VH                      | LIKEA COMPL ICATE DFIGU RE
OUFAN TQACK                                     | INTHE SECON DBOOK OFEUC LID
KTOZZ RDABQ NNVPO IEFQA FS                      |
VVICV UDUER EYNPF FMNBJ VGQ                     |
Figure 4. Sample input and output (using the Naval cipher).

Editing Main

Within Main.java, you will be working with Scanners. We recommend that before you tackle this portion of the project you do homework 4, as there will substantial practice on that assignment. Inside of Main.java you will deal with a substantial amount of input handling (involving both valid and invalid inputs). Do not assume that all of your inputs will be well-formed and do your best to make sure that you handle all cases where the input is not what is expected.

In addition to this, in Main.java, you will need to print output in a way that matches our sample output file. The Unix convention is that every line ends with a newline \n (we say that newline is a line terminator rather than a line separator), so make sure that your output file also includes a newline at the end. If your output seems exactly the same as the expected output, but you are failing a test, chances are that there is an issue with newlines.

Handling Errors

You can see a number of opportunities for input errors:

A significant amount of a program will typically be devoted to detecting such errors, and taking corrective action. In our case, the main program is set up in such a way that the only corrective action needed is to throw an EnigmaException with an explanatory message. The existing code in the main program will catch this exception, print its message, and exit with a standard Unix error indication. The skeleton supplies a simple static utility method, error, which provides a convenient way to create error exceptions. There are examples of its use in the skeleton (see Main.java).

Testing

Check out these testing videos for some explanations about the Enigma testing framework!

Here is the full suite of test files for enigma! (EDIT 3/1 4:30pm PT: If you downloaded test.zip already, please download it again to get the correct 03-carroll.conf)

Firstly, running java -ea enigma.Main [configuration file] [input file] [output file] with the --verbose flag:

java -ea enigma.Main --verbose [configuration file] [input file] [output file]

will give you more information about the execution of your Enigma program as it encrypts a given message. Use this feature to see how each rotor changes before each encrypted character and the internal permutations that take place as each character is encrypted.

We have set up the Makefiles in the proj1 directory and in the enigma subdirectory to have targets check and unit. In order to use make, you'll need to install it, which you should have done in HW1.

Once installed, the command

make unit

will run all the unit tests. If you try this on the skeleton, you'll see that, unsurprisingly, it fails all these tests, giving you an indication of what needs to be changed. Use the IntelliJ debugger to assist in passing these test cases. The unit tests provided with the skeleton are nowhere near comprehensive. Passing the unit tests included with the skeleton is not an indication that your code is correct, you should write additional tests to ensure correctness as detailed in Lab 6

The command make acceptance in the proj1 directory will run acceptance tests, which run the program and check its outputs against expected output using the script testing/test-correct, as well as make sure your program is reporting errors when it should using the script testing/test-error.

The command make acceptance will run test-correct on all of the input files in the testing/correct directory, and test-error on all of the input files in the testing/error directory. As with unit tests, the acceptance tests included with the skeleton are nowhere near comprehensive.

Usually, you will probably want to use the command make check for testing, which runs both the unit and acceptance tests. By the time you finish the project make check should report no errors. If your python command is python rather than python3 you will need to use make PYTHON=python check to run the acceptance tests.

Running Enigma in IntelliJ

As touched upon above, you can run your program on the command line. In this section, we will cover how to run Enigma in IntelliJ with input and output files. This allows you to step through the acceptance tests in the debugger.

Navigate to the Main class in your project. Try clicking the green play button next to the main method in Main, and select 'Run Main.main()'. If you haven't previously inputted arguments, you should see an error like this:

No Argument Error

We got this error because we haven't passed in any arguments to the program! Notice that between 1 and 3 arguments can be passed in:

At the top right hand side of your screen, you should see a dropdown menu now labeled Main. You should click the dropdown and select 'Edit Configurations...'

Edit Configurations

A window should pop up, and you should be able to enter in your arguments in the Program Arguments bar. For this example, create a file called riptide.in in your testing/correct/ directory with the following contents:

* B Beta I II III AAAA (TD) (KC) (JZ)
I WAS SCARED OF CODING IN JAVA
I WAS SCARED OF USING GIT
AND STARTING ALL THESE PROJECTS
COMPILER KEEPS GETTING MAD AT ME
NOW MY PROJECT ONLY RUNS IN MY DREAMS
OH OH ALL THESE MERGE CONFLICTS

If you've copied the file into your directory, you should be able to refer to your default.conf configuration file and the riptide.in file. Make sure you specify the correct path to your files, with respect to your Working Directory.

Program Arguments

To add the -ea flag, which enables assertions (otherwise any assert statements will be ignored, which is not the case on the grader), click the "Modify Options" dropdown, then "Add VM options", and enter -ea into the "VM Options" box that appears. Click "OK" to save this configuration.

This is equivalent to specifying the program arguments as such:

java -ea enigma.Main [configuration file] [input file] [output file]

Now run Main.main(). We haven't specified an output file, so you should see the output of your program in standard output. If you're wondering, you've just encrypted a verse in the Summer 2017 CS61BL Musical!

As a reference, you should see output like that below (if you have completed much of the project). You're welcome to make a new output file and add that to your program arguments if you prefer the output get written to a file.

Expected Output

Comparing with the Staff Solution

You can see expected output from the staff solution by running staff-enigma <conf file> <input file>. If you are unable to run the command staff-enigma, you should run the following command cd ~/cs61b-software; git pull to get the most up to date cs61b-software files on your computer.

In order to redirect your output to a certain file (rather than just having it outputted) you can add >> filename at the end of each command, for example, staff-enigma <conf file> <input file> >> file1.out

You can run staff-enigma with the --verbose option to see more details about each conversion being made as each character moves through the machine (e.g. staff-enigma --verbose <conf file> <input file>). This will show the succession of conversions each character goes through in each step, preceded by the rotor settings for that step. The first and last conversions are from the plugboard. This ignores the ring setting—that is, it acts as if the ring is at the default position (0 = first letter of alphabet). However, you will only have to worry about ring settings if you do the extra credit.

To compare your files with the staff files, you can run sdiff file1 file2 or use an online diffchecker. A standard debugging workflow for acceptance tests would be:

  1. Run the staff solution using staff-enigma on the test's configuration and input file, redirecting the output to a file.
  2. Run your program using java -ea enigma.Main on the test's configuration and input file, redirecting the output to a file.
  3. Use a diffchecker or manually inspect the output files to figure out where they differ.
  4. Use the IntelliJ debugger to step through the translation that you are differing on to determine the source of the mismatch.

Extra Credit

If after completing your solution, you are for some reason hankering for more, you can, for 2 points of extra credit, implement the last missing piece of the Enigma: the ring setting (Ringstellung). The alphabet rings are so called because they are marked with the letters of the alphabet. It is these letters that appear in the panel of the machine and indicate the current settings of the rotors. In the real Enigma, the rotors' rings are adjustable. Think of the positions on a rotor as being numbered from 0, with 0 being the usual position of the first letter of the alphabet on the ring. The ring can be turned to make any letter of the alphabet correspond to that 0 position instead. If, for example, we have the usual upper-case alphabet, and we set the ring of rotor III so that "B" is at the 0 position, then when the setting of that rotor is "B", the rotor will convert "J" to "T", just as that rotor would normally translate "J" when in the "A" position. Likewise, when at the "D" setting, it would translate as it normally would in the "C" setting.

Besides affecting the meaning of the rotor settings, the alphabet ring also carries the notches that allow adjacent rotors to move. The III rotor, for example, has a notch at its "V" position. Normally, this comes into play when the rotor is at its 21 position, since "V" is letter number 21 in the alphabet (numbering from 0). But when the alphabet ring is set so that "B" is at the 0 position, the notch occurs at the rotor's 20 position.

To specify the ring setting, we add an additional string to the configuration line. For example, the line

 * B Beta III IV I AXLE AAAA (BQ)

is the same as what we have been writing as

 * B Beta III IV I AXLE (BQ)

That "AAAA" is the (optional) ring setting; for the usual alphabet, "AAAA" is the default setting. The reflector (B) does not have an adjustable ring. The line

 * B Beta III IV I AXLE BEAR (BQ)

says that the ring setting of the Beta rotor is "B", the III rotor is "E", IV is "A", and I is "R".

Your solution must still handle configuration lines without the ring setting.

Checkpoint

By Friday, February 25th, (2/25) at 11:59PM you must have completed the following deliverables in order to receive 4 points. The checkpoint is not extra credit, and will be factored into your final project grade.

  1. Manually translate your cs61b three letter code using the following configuration file:

    abcdefghijklmnopqrstuvwxyz
4 3
I Ma     (wordle) (is) (fun)
II Mb    (tears) (boing) (lucky)
III Mm   (quack) (froze) (twins) (glyph)
B R      (az) (by) (cx) (dw) (ev) (fu)
         (gt) (hs) (ir) (jq) (kp) (lo) (mn)

    and the settings line:

    * B III II I maa (az) (mn)

    Put only the encryption in the provided blank checkpoint.txt file.

  2. All of your code compiles.
  3. Pass 5 out of 6 of the Permutation and MovingRotor unit tests provided with the skeleton.

To elaborate on deliverable 1, if your three letter code was tab you should on paper pass these letters through the machine specified by the above configuration and settings line. Do not reset the machine after each character is translated. As a sanity check, tab would translate to jzt. If you had the three letter code tab, you would put jzt into checkpoint.txt. See the Checkpoint Translation Walkthrough video for an example of this process.

There will be no velocity limits on the checkpoint autograder, which is not the case for the full project grader. Submit to the checkpoint by committing it and tagging it as follows (the tag is proj1a not proj1):

git tag proj1a-0     # Or proj1a-1, etc.
git push
git push --tags

Grading Details

Project 1 is due Friday, 3/4 at 11:59 PM PT. The project is worth 24 points (the total score for this project is 28 points, with the checkpoint included). Your score on gradescope will be your final score for the assignment.

You will be able to submit to the Project 1 gradescpe autograder starting on Friday, 2/18. The tests included in the skeleton code are not the full suite of tests that will be run on your submission. The intention is that you write tests for your code, and do not rely on autograder submissions to debug problems. To encourage this, you will only be able to submit to the autograder once every 3 hours, and limited error output will be displayed.

Starting 3/1, the autograder will show more information about why you are failing some tests, and what the tests that you are failing contain. Starting 3/4, you will be able to submit to the grader 4 times every hour, and in the last hour before the deadline, there are no restrictions on submissions to account for any last minute issues such as wifi or git problems.

As a warning, you will not be able to complete the project if you wait to start or test your code until full autograder logs are available 3 days before the deadline. You should plan to start early, and write your own extensive tests for this assignment.

Advice

You can watch this getting started video for some advice on getting started in video form.

First, get started immediately, of course. Don't just jump in and code, though. Make sure you understand the specifications (which have their subtleties) and plan out how you're going to meet them. Read the skeleton code and understand the design. Figure out how to break this problem down into small pieces, and how to implement and test them one piece at a time. Know in detail how you're going to do something before writing a line of Java code for it. In particular, take some time to understand how the rotors work, and especially how the rotor position modifies the permutation.

Don't allow things to remain mysterious to you, or they'll surely bite you at some point. You don't have to use any of the skeleton code we've provided as long as the command java enigma.Main works as specified. However, if you find yourself throwing something away because you don't understand it, STOP! You're allowing yourself to be mystified by something that is intended to be simple.

There is a fair amount of string-hacking involved. The Java library can help you. Look at the documentation of String, HashMap, ArrayList, and Scanner in the on-line Java library documentation. We particularly invite you to consider the constructors and the methods

From String From ArrayList From HashMap From Scanner
charAt add get next
replaceAll get put nextInt
split size hasNext()
startsWith hasNext(...)
substring nextLine
toUpper
trim
indexOf

Be creatively lazy. Feel free to browse the Java library for useful stuff, even if you haven't seen it in class. If you find yourself writing:

if (rotor.equals("I") {
    if (c == 'A')
        e = 'E';
    else if (c == 'B')
        e = 'K';
    ...
}

or something equally hideous, STOP! you are doing something wrong!

You can write JUnit tests and acceptance tests (see the testing directory) before you write a line of code. Be particularly careful to include tests that at one point caused your program to fail (regression tests) so that you can be sure you don't backslide when you make further changes. There's no reason you can't have tests that you fail, by the way; they'll serve to remind you of things you still need to do.

Use the git repository. Frequently commit your work so that you'll never have to reconstruct too much if your files somehow vanish mysteriously.

Above all, it is always fair to ask for help and advice. We don't ever want to hear about how you've been beating your head against the wall over some problem for hours. If you can't make progress, don't waste your time guessing or bleeding: ask. If nobody's available to ask, do something else (or get some sleep).

A Plan of Attack some TAs found useful was

Common Bugs

  1. % in Java is remainder, and has different behavior from what you might expect with negative numbers. Please see the provided method wrap for modular conversions, or see what the body of wrap does and replicate this if you prefer to use your own methods.