CPSC 225

Intermediate Programming

Fall 2018

Programming Assignment 1: Solitaire Encryption

Muddiest Points: Thu Sep 13 at 5pm
Due: Fri Sep 28 at the start of class

Introduction

In Neal Stephenson’s novel Cryptonomicon, two characters use an encryption system based on a deck of playing cards to exchange secret messages. This encryption system (known as “Solitaire”) was designed by Bruce Schneier (a well-known cryptologist and security expert) specifically for the book. Your job in this assignment will be to implement encryption and decryption engines using this system.

The purpose of this assignment is give you some practice with linked lists, outside of the usual insert-into-a-linked-list and remove-from-a-linked-list examples that come up when talking about data structures. It also provides an example of a case where choosing the right data structure – in this case, doubly-linked circular lists – can make solving a problem easier. (As you are working on the program, consider what would be involved if you used an array instead of a linked list.)

This assignment also hammers home the idea of decomposing a complex task into smaller subtasks and testing each subtask separately – if you do not do this, verifying that your program works (and figuring out what when wrong if it doesn’t) will be very difficult.

Preliminaries

Remember that this is an individual assignment – everyone should do the assignment themselves and hand in their own solution.
There is a lot of information in the handout – you’ll want to read carefully through the whole thing, but not all at once!
- First look through the section and subsection headers to notice what the handout covers.
- Read through the section about the solitaire algorithm carefully and make sure you understand how it works.
- Read through the specifications (both overview and detailed) to make sure you understand what the program should do and how your code should be organized. Don’t worry about memorizing all the detailed specifications – read to note what there are details about and to make sure you understand what you need to do for each thing.
- Read through the Implementation Details and Notes sections, again to note what there are details about and to make sure you understand what is being said. You do not need to memorize all the details.
When you are ready to start writing code, go back to the relevant sections of the handout and read them more carefully.
There is some provided code (described under “Provided Code”); you’ll need to import the files from /classes/cs225/solitaire into your project.

Muddiest Points

Send an email with one or two questions about things you find confusing or unclear, something you aren’t sure how to do, what you anticipate to be the most difficult part or the part you are most apprehensive of, etc – in short, aspects of the assignment that you find to be the muddiest. Try to identify specific points as much as possible.

Getting Started

Once you have read through the handout and understand the solitaire encryption algorithm, implement the program from the bottom up – start with SolitaireDeck and then move on to KeystreamGenerator and SolitaireEncoder before getting to the main program. (A big picture approach – starting with main, then moving on to SolitaireEncoder, KeystreamGenerator, and finally SolitaireDeck – is also possible, but you won’t be able to test SolitaireEncoder and KeystreamGenerator without some non-trivial effort in writing placeholder code and so it is easier just to properly implement the building blocks first.)

Write method comments before you write the body of the method! Abstraction is very important in this program – the encryption algorithm is fairly complex, but it is built out of small pieces which are gradually connected into bigger chunks. Knowing (and documenting) each method’s job allows you to forget about the details of how it was implemented when you want to focus on using it as a piece in something larger.

Work incrementally! Tackle one method at a time: understand what it is supposed to do, write the method header and comments, implement the method body, and then test it (write and implement the test cases) before moving on to the next. In fact, you can even write many of the test cases before writing the method body! This is good for making sure you understand what the method is supposed to do. (And if you don’t understand a method, ask!) Note that if you are using the big picture approach, most (or all) of your tests won’t pass until you get the lowest-level methods in SolitaireDeck implemented. It is still useful to think about (and write) test cases before implementing the method bodies, however.

Also, draw pictures! Drawing out the linked list structure for the before and after state of a small example can be very helpful for figuring out what you need to do to carry out the task.

Note: It is recommended that you finish lab 3 (about linked lists) before you start implementing the SolitaireDeck methods. There’s plenty you can do on this assignment before then, though – write method headers and comments for all of the classes (with placeholder return statements for those that return a value so the code will compile), develop and implement black-box and common special case test cases for the two testers (all the tests will fail at this point, but that’s OK), and write the main program. You can even implement KeystreamGenerator and SolitaireEncoder though you won’t be able to fully test them unless you put some effort into writing meaningful placeholders for the SolitaireDeckmethods, and as that involves linked list manipulations, you might as well move on to SolitaireDeck instead.

The Solitaire Algorithm

You’ll be implementing a slightly modified version of the original Solitaire Encryption Algorithm. This modification sacrifices some of the security of the original algorithm, but makes it a bit easier to implement without really changing the flavor of the algorithm.

The Solitaire algorithm is based on a standard deck of 52 playing cards, plus two jokers. To make things a little more manageable, you’ll be implementing a simplified version of Solitaire using a half-deck of just 26 cards plus two jokers. Furthermore, the cards will be represented with just the numbers 1-26 instead of suit and value. The jokers should be distinguishable in some way – we’ll call them “joker A” and “joker B”. For example:

1 23 25 27B 2 22 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 27A 26 8 3 24 6 4

Deck Operations

There are three operations that are applied to the deck of cards as part of carrying out the Solitaire algorithm: joker swaps, triple cuts, and count cuts. Each is described in turn.

Joker Swap – Joker A

In a joker swap, joker A is swapped with the card that comes after it in the deck. For example: (bold highlights the changes)

before: 1 23 25 27B 2 22 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 27A 26 8 3 24 6 4
after:  1 23 25 27B 2 22 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 26 27A 8 3 24 6 4

If joker A is last, it is still swapped with the next card (which happens to be the top card when the deck is treated as a continuous loop). The card considered to be the top card doesn’t change.

before: 1 23 25 27B 2 22 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 4 26 8 3 24 6 27A
after:  1 27A 23 25 27B 2 22 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 4 26 8 3 24 6

This is still a swap, since the sequence of cards surrounding 27A in the “before” deck is … 24 6 27A 1 23 25 … and in the “after” deck is … 24 6 1 27A 23 25 … It’s just that we don’t move the top card to the bottom of the deck to take the former bottom card’s position.

Note that if joker A is first, the top card of the deck does change:

before: 27A 1 23 25 27B 2 22 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 26 8 3 24 6 4
after:  1 27A 23 25 27B 2 22 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 26 8 3 24 6 4

Joker Swap – Joker B

A joker swap involving joker B is similar, but joker B is moved down two cards in the deck by performing two swaps.

before: 1 23 25 27B 2 22 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 26 27A 8 3 24 6 4
after:  1 23 25 2 22 27B 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 26 27A 8 3 24 6 4

The cases of joker B being the last or next-to-last card in the deck are handled similarly to joker A. The top card of the deck only changes if joker B is the first card, not if joker B is merely swapped with the top card.

Triple Cut

In a triple cut, the cards above the first joker (the one closest to the top of the deck) are exchanged with the cards below the second joker. For this step, it doesn’t matter which joker is A or B.

before: 1 23 25 2 22 27B 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 26 27A 8 3 24 6 4
after:  8 3 24 6 4 27B 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 26 27A 1 23 25 2 22

Count Cut

A count cut involves several steps:

Remove the bottom card from the deck.

before: 8 3 24 6 4 27B 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 26 27A 1 23 25 2 22
after:  8 3 24 6 4 27B 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 26 27A 1 23 25 2

Count down a specified number of cards from the top of the deck, counting the top card as 1. (How many cards to count is specified as a parameter to this operation.) For example, counting down 22 cards means that the 26 is the current card.

Do a cut: put the cards you just counted through at the bottom of the deck.

before: 8 3 24 6 4 27B 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 26 27A 1 23 25 2
after:  27A 1 23 25 2 8 3 24 6 4 27B 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 26

Add the original bottom card (which you removed) back to the bottom of the deck.

before: 27A 1 23 25 2 8 3 24 6 4 27B 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 26 
after:  27A 1 23 25 2 8 3 24 6 4 27B 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 26 22

Keystream Generation

The central part of the Solitaire algorithm is the generation of a keystream – a sequence of numeric values which will then be used to encrypt or decrypt a message. To generate a single value in the keystream:

Do a joker swap with joker A.
Do a joker swap with joker B.
Do a triple cut.
Do a count cut, using the value of the card at the bottom of the deck as the number of cards to count.
Look at the top card’s value and count down that many cards from the top of the deck, counting the top card as 0. If the resulting card isn’t a joker, return that card’s value as the next value in the keystream. If that card is a joker, go back to step 1 and repeat the whole process until you get to a card that isn’t a joker.

For example:

start:              1 23 25 27B 2 22 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 27A 26 8 3 24 6 4
after joker A swap: 1 23 25 27B 2 22 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 26 27A 8 3 24 6 4
after joker B swap: 1 23 25 2 22 27B 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 26 27A 8 3 24 6 4
after triple cut:   8 3 24 6 4 27B 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 26 27A 1 23 25 2 22
after count cut:    27A 1 23 25 2 8 3 24 6 4 27B 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 26 22

The next keystream value is 22 – the 22 is 27 cards from the top (starting with 0) and isn’t a joker.

Encryption

So what do you do with those keystream values? They are used for encryption and decryption.

To encrypt a message (such as you'll never guess this message!), perform the following steps for each character: (the example shows the process applied to each character of the entire message at once)

If the character is not a letter (e.g. a space, punctuation, a number), skip it.
```
youllneverguessthismessage
```
Convert the letter to a number. (A=1, B=2, C=3, etc) Treat capital and lowercase letters as equivalent (so both ‘A’ and ‘a’ convert to 1, etc).
```
25 15 21 12 12 14 5 22 5 18 7 21 5 19 19 20 8 9 19 13 5 19 19 1 7 5
```
Generate a keystream value, as described above.
```
22 22 25 9 1 7 19 22 8 23 12 21 2 3 4 25 19 21 9 8 3 23 17 18 25 24
```
(The first 22 is the value generated in the “keystream generation” example; the other values come from continuing to generate keystream values from that point.)

Add the number for the letter to the keystream value. If the sum is greater than 26, subtract 26 so you end up with a number between 1 and 26.

  25 15 21 12 12 14  5 22  5 18  7 21 5 19 19 20  8  9 19 13 5 19 19  1  7  5
+ 22 22 25  9  1  7 19 22  8 23 12 21 2  3  4 25 19 21  9  8 3 23 17 18 25 24
-----------------------------------------------------------------------------
  21 11 20 21 13 21 24 18 13 15 19 16 7 22 23 19  1  4  2 21 8 16 10 19  6  3

Convert the number back into a letter. (1=A, 2=B, etc) This is the encrypted letter.

  21 11 20 21 13 21 24 18 13 15 19 16 7 22 23 19 1 4 2 21 8 16 10 19 6 3
   U  K  T  U  M  U  X  R  M  O  S  P G  V  W  S A D B  U H  P  J  S F C

The encrypted message is just the resulting sequence of encrypted letters: UKTUMUXRMOSPGVWSADBUHPJSFC

Decryption

Decryption is nearly the same as encryption. However, it is vital that the same sequence of keystream values be generated – this means that for decryption, the deck must be started in the same order that it was in when the encryption process was started.

Once the deck has been properly initialized (see “Keying the Deck”), decrypt a message by performing the following steps for each character:

Convert the letter to a number. (A=1, B=2, C=3, etc) Treat capital and lowercase letters as equivalent (so both ‘A’ and ‘a’ convert to 1, etc).
Generate a keystream value, as described above.
Subtract the keystream value from the number for the letter. If the result is less than or equal to 0, add 26 so you end up with a number between 1 and 26.
Convert the number back into a letter. (1=A, 2=B, etc) This is the decrypted letter.

The decrypted message is just the sequence of decrypted letters – aside from the missing spaces and punctuation, this should be the same as the original message.

Keying the Deck

In order to successfully exchange messages, the person decrypting the message must have her deck arranged in the same order as the person encrypting the message. The process of arranging the cards in the deck in a certain order is known as keying the deck, and must be done before starting to encrypt or decrypt a message.

One way to key the deck is to use a secret passphrase known only to the two parties who are exchanging messages. This method uses the Solitaire algorithm itself to rearrange a deck in a known order into a new order according to the passphrase – the passphrase is essentially a shorthand for specifying the deck order. To key the deck using a passphrase:

Start with the cards of the deck arranged in order from the lowest card to the highest card (and joker A before joker B).
```
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27A 27B
```
Repeat the following steps for each character of the passphrase:
1. If the character is not a letter (e.g. space, punctuation), skip it.
2. Do a joker swap with joker A.
3. Do a joker swap with joker B.
4. Do a triple cut.
5. Do a count cut, using the value of the card at the bottom of the deck as the number of cards to count.
6. Convert the current letter of the passphrase to a number. (A=1, B=2, C=3, etc) Treat capital and lowercase letters as equivalent (so both ‘A’ and ‘a’ convert to 1, etc).
7. Do a second count cut, using the number from the previous step as the number of cards to count.

For example, carrying out this process for the passphrase SECRET KEY results in the keyed deck:

1 23 25 27B 2 22 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 27A 26 8 3 24 6 4

Specifications

Overview

Your program should allow users to encrypt and decrypt messages using the Solitaire encryption algorithm. The following is a sample transcript of what it should look like when your program is run: (input entered by the user is shown with bold underline to distinguish it from your program’s output)

enter passphrase: secret key

encrypt, decrypt, or quit? [e/d/q] e
enter message: you'll never guess this message!

encrypted: UKTUMUXRMOSPGVWSADBUHPJSFC

encrypt, decrypt, or quit? [e/d/q] d
enter encrypted message: UKTUMUXRMOSPGVWSADBUHPJSFC

decrypted: YOULLNEVERGUESSTHISMESSAGE

encrypt, decrypt, or quit? [e/d/q] q

In particular, the user should first be prompted for a passphrase. The program should then repeatedly ask the user whether she wants to encrypt a message, decrypt a message, or quit. Quitting should end the program; in the other cases, the user should be prompted for the message to encrypt or decrypt and the result displayed.

The same passphrase should be used for the entire session – don’t re-prompt for a new passphrase after each encryption or decryption. Passphrases and messages are assumed to be a single line, though they may contain other whitespace (such as spaces or tabs).

Detailed Specifications

Code Structure

Name your Eclipse project solitaire (exactly like that, lowercase and all).

You will also need the four classes (SolitaireDeck, KeystreamGenerator, SolitaireEncoder, and SolitaireMain) with the instance variables, constructors, and methods described in the “Implementation Details” section. You may add private elements (such as methods and instance variables) to these classes if needed, but do not change or omit any of the specified elements.

Internal Correctness

There’s lots of room for things to go wrong when manipulating linked lists, so doing everything you can to help you catch and track down bugs is essential. Thus, the following are requirements (as well as being good ideas):

Javadoc-style comments for all classes and methods. For methods, be sure to fully specify the method’s contract: describe its job, parameters, and return value (if any).
Identify and check preconditions for all methods. Think carefully about allowed parameter values for methods!
Add private validity-checking methods checkContents() and checkStructure() to SolitaireDeck (see “Validity Checking” in the “Notes” section). That these methods return true should be postconditions for all methods in SolitaireDeck (including constructors) – use assertions to check them! (And remember to turn assertions on when you run your program; see “Assertions” in the “Notes” section.)

Testing

There’s lots of room for things to go wrong when manipulating linked lists, so making sure that the building blocks – the methods in SolitaireDeck and KeystreamGenerator – work is essential for having the whole program work. Thus, the following is a requirement (as well as being a good idea):

Write a tester SolitaireDeckTester to thoroughly (but concisely) test each non-trivial method of SolitaireDeck.
Write a tester KeystreamGeneratorTester to test each non-trivial method of KeystreamGenerator. (See the note on test cases for KeystreamGenerator in the “Notes” section below.)

Follow the style from class and lab for your testers – the main programs should be a list of test cases identified in comments with code implementing the test case after each block of comments. Automate the testing as much as possible – check that the actual output matches what is expected and print out “PASSED” or “FAILED” (along with enough information to identify each test case) instead of just printing the actual output and having to look at it to determine whether or not the test succeeded. You may need to add additional methods to your classes to support testing; see the note on designing for testing in the “Notes” section below.

You should develop a complete but concise set of test cases, but don’t worry about finding the absolute smallest set possible – you will lose points for having many redundant tests (and for missing important cases), but sometimes it’s easier to just include tests for two cases that appear different even if careful reasoning would reveal that one case is actually covered by the other. That’s OK.

Robustness

Your program should be robust – identify cases where the user could input something that the program doesn’t expect, and handle it gracefully. Nothing the user can do should be able to crash the program!

Extra Credit Features

Some options for extra credit:

Encrypt non-letter characters such as digits and punctuation in the message instead of stripping them out. For this you will need to choose a deck size larger than 26, and you will need to decide on a way to map each character to an appropriate integer. Doing this as elegantly as possible is a bit of a challenge. (Note that SolitaireDeck and KeystreamGenerator should already accommodate any size of deck, so you’ll just need to modify the steps where you convert between numbers and letters.)
Make your program work with decks of any size. For decks larger than 26 cards, you’ll be able to encrypt non-letter characters such as digits and punctuation (see the first extra credit option). For any size of deck, any characters whose value is not represented in the deck should be skipped for both passphrase and message. For example, a deck of size 5 can accommodate 5 characters, so any characters other than ABCDE in the passphrase and message should be skipped. The user should be prompted for the deck size along with the passphrase when the program starts, and that deck size should be used for the remainder of that session.
Modify the main program so that it can also be used to encrypt/decrypt files. The action (“e” for encrypt, “d” for decrypt), passphrase, and filename should be specified as commandline parameters. For example:
```
  java SolitaireMain e "secret key" /home/bridgeman/myfile.txt
```
If no commandline parameters are specified, the program should revert to the normal behavior (prompting the user for the information). The result should be printed on the screen. Note that there should only be one call to encrypt or decrypt for the entire file – don’t do a line at a time.

Implementation Details

Provided Code

You have been provided with two classes, SolitaireCard and DoubleListNode. SolitaireCard represents a single card in the deck. It has constructors for creating regular (non-joker) cards and jokers and getters for retrieving the card’s information. DoubleListNode represents a node in a doubly-linked list which can store a SolitaireCard as its element. It has the expected constructors and getters.

You will need to look at these classes to see how to use them (pay attention to the public constructors and methods), but you should not change them in any way.

`SolitaireDeck`

The class SolitaireDeck represents the deck of cards used to generate keystream values. It stores the cards and supports deck-manipulation operations like joker swaps, triple cuts, and count cuts. For flexibility, this is designed to support any size of deck (≥ 1); note that “deck size” does not include jokers, so a deck with size 26 actually contains 28 cards.

The cards should be stored using a circular doubly-linked list. See the “Notes” section below for more information on circular doubly-linked lists.

SolitaireDeck should have the following: (details below)

instance variables for the head of the circular doubly-linked list (the top of the deck) and the deck size
a constructor which takes the deck size as a parameter and initializes the deck accordingly
a getter getDeckSize() which returns the deck size
getters getTopCard() and getBottomCard() which return the SolitaireCard in the respective positions
a getter getNthCard(n) which returns the nth SolitaireCard from the top of the deck (n=0 means the top card)
methods swapJokerA(), swapJokerB(), tripleCut(), and countCut(n) which carry out the respective operations (as described in the “Deck Operations” section)
a method toString() which returns a string representation of the deck

The constructor should initialize the deck to contain the specified number of cards (with values 1..n) plus two jokers (A and B). The jokers should both have the value n+1 where n is the deck size. The cards should be in order by value from 1..n with the two jokers at the end (joker A before joker B). For a deck size of 26, this will be:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27A 27B

For countCut(n), count the top card as 1 and make the cut after the nth card. Thus n=1 means to cut the deck after the top card, n=2 means to cut the deck after the second card, and so forth. n < 1 doesn’t make sense.

toString should list the values of each card in order from the top of the deck, separated by spaces. For example:

1 23 25 27B 2 22 10 11 12 13 14 15 16 17 18 19 20 21 7 5 9 27A 26 8 3 24 6 4

Note that SolitaireCard‘s toString already produces the correct string representation for a single card, so you just need to put them together into a single string for the whole deck.

`KeystreamGenerator`

KeystreamGenerator handles generating the keystream values. It should have the following elements:

an instance variable for the deck to use (type SolitaireDeck)
a constructor which takes the deck size as a parameter and creates a new deck of that size to initialize the instance variable
a method key(passphrase) which takes a passphrase as a parameter and uses that passphrase to key the deck (as described in “Keying the Deck”)
a method nextKeystreamValue() which generates and returns the next keystream value (as described in “Keystream Generation”)

`SolitaireEncoder`

SolitaireEncoder actually implements the Solitaire algorithm. It has two static methods:

encrypt, which takes a message, the passphrase, and the deck size as parameters and returns the encrypted message
decrypt, which takes an encrypted message, the passphrase, and the deck size as parameters and returns the decrypted message

Both methods will need to create and key a new KeystreamGenerator using the specified passphrase before carrying out the encryption or decryption process described in “Encryption” and “Decryption”.

`SolitaireMain`

SolitaireMain contains the main program. The main program implements the user interface described in the Overview section – it prompts the user for the necessary information, invokes SolitaireEncoder‘s encrypt or decrypt methods as needed to do the actual encryption and decryption, and displays the results.

Notes

Circular Doubly-Linked Lists

Recall from class the difficulties of moving backwards in a linked list – any time we needed a node before the current node, it was necessary to start at the head and scan forward. A doubly-linked list solves this problem because each node stores both next and previous pointers – you can then back up by simply following the previous pointer instead of the next pointer. (When you change the list structure, be sure to update both the next and previous pointers of each node as needed.)

A circular list is one in which the last node’s next pointer refers back to the first node instead of being null. (In a doubly-linked circular list, the first node’s previous pointer similarly refers to the last node.) There is still a head pointer to locate a node in the list – in the case of the deck, this indicates the top card in the deck.

Some care is needed to properly print or otherwise visit all of the nodes in a circular linked list – you can’t just go until you reach null! Draw a picture of an example and trace through your code by hand to make sure you have gotten the logic right.

An advantage of circular lists is that you can often avoid having to special-case things involving the last node of the list. For example, you don’t have to special-case the handling of the jokers at the end of the list in the joker swap operations if you use a circular list.

Validity Checking

The SolitaireDeck operations perform complex manipulations of the deck structure, and there is lots of potential for making a mistake in the linked list manipulations. It’s also difficult to state anything too specific about the correct result of an operation without having a specific starting state – a correct result comes from correctly following the right process, but postconditions and other invariants within a method require a statement about state (variable values) rather than process.

What you can think about, though, are properties of a valid result – it’s difficult to say what will result from a joker swap without referring to the process of swapping a joker, but you do know that the deck should still contain cards 1..n and two jokers without duplicates, and that a consistent circular linked list structure requires that for every node a, the previous of a‘s next and the next of a‘s previous should both be a. Furthermore, carrying out those checks of validity is at least somewhat easier than the deck manipulations themselves.

The specifications section split this validity checking into two methods: checkContents() should check the contents of the deck (the deck contains cards 1..decksize plus joker A and joker B – and nothing else) and checkStructure() should check the linked list structure (i.e. that for every node a, the previous of a‘s next and the next of a‘s previous are a, and that counting through decksize+2 cards both forward and backward gets you back to the head node). Both methods should return true if the check passes (the contents and structure are correct) and false otherwise.

Note: to check the contents, you need a way to know at a given node whether or not that node’s value has already been seen and, at the end, that there aren’t any values missing. The first problem can be solved with a boolean array – use a value of false in slot i to mean that value i has not yet been seen in the deck and true to mean that it has. (The jokers will need to be special-cased since they both have the same value, but you could use slot 0 for joker A and the slot corresponding to the value for joker B.) For each node, check the value of that slot before setting it – if it is already true, a duplicate entry has been found. The second problem can be solved by either checking that there are no false values in the array once the entire deck has been gone through, or by just going through decksize+2 nodes without running into any duplicates.

Assertions

Refer back to the notes from class about writing assertions in your code, and to lab 2 for how to tell Eclipse to turn on assertion checking when you run the program. Note that turning on assertions is for a particular main program, so you’ll need to repeat the process for each of your tester main programs. (Also potentially SolitaireMain, though if you’ve tested well, you know everything works…)

To turn off assertion checking, remove the -ea from the VM arguments in the run configuration. (Though there’s no need to do that here – the work done to do the checks isn’t going to take long enough to be noticeable for this program.)

Designing for Testing

Setting up starting state and input and checking expected output may require access to the internals of a class that there isn’t public access to. In this case, you will need to create specific deck configurations other than the everything-in-order deck that the SolitaireDeck constructor creates. You also may want to check the state of the deck after each of the KeystreamGenerator methods. As a result, add two default access (not public, private, or protected) operations:

a constructor for SolitaireDeck which takes an array of SolitaireCards and the deck size as parameters, and builds the deck to contain those cards in the specified order
a getter getDeckString() in KeystreamGenerator which returns a string representation of the deck

Note that getDeckString() just needs to call toString() on the KeystreamGenerator‘s deck instance variable – you’ve already done the hard work of producing a string representation of a deck.

Test Cases for `KeystreamGenerator`

To check that a test passed, you need to be able to determine the expected output for a given input. For the methods in KeystreamGenerator, this can be a complicated task – you essentially have to trace through what your code is supposed to be doing by hand, without making any mistakes. What to do?

First, note that the most complicated parts of the KeystreamGenerator methods are the deck manipulations done by SolitaireDeck; the KeystreamGenerator methods just connect them together. That means that if you know that the SolitaireDeck methods work (which you do, because you wrote a thorough tester for them), you can probably reason fairly confidently that the KeystreamGenerator methods are correct.

Second, note that the description of generating keystream values and keying the deck below contain examples – which means you know the starting state and the expected output. Two test cases! The encryption example also shows a series of keystream values – it’s a little unusual as a test case, but you could generate a bunch of keystream values and check that your answers match the example. A couple of examples don’t prove that your code works, but it’s better than nothing.

Handin and Grading

Make sure all your Java files have been auto-formatted and saved.
Copy your solitaire project folder (and its contents) into your handin directory in /classes/cs225/handin.
Check that everything got handed in correctly – your handin directory should contain a directory solitaire which in turn contains a subdirectory src with your .java files.

The grading criteria for programs is given on the Policies page. Syntax, functionality, robustness, commenting, and readability will all be graded for this assignment. Functionality includes addressing all of the specifications, including things like naming your project and classes (exactly) as directed.

Credits

This assignment is based on materials by Lester McCann.