| CPSC 225 | Intermediate Programming | Spring 2025 |
The projects are opportunities to work on larger programs, and to bring together and apply topics from the course. This assignment provides 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.)
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 much more difficult.
The checkpoint deadline is a guideline for pacing. There isn't anything to hand in, but you should treat it like a real deadline — if you aren't on track to meet it, you run a greater risk of not completing the project on time.
Fixing problems is an important component of learning, and most assignments will have an opportunity for revise-and-resubmit. The resubmit deadline will be announced when the initial handin is handed back, and will generally allow a week or so for revision.
Revise-and-resubmit requires there to be something to revise and feedback to act on — it is not intended as a de facto extension. To be eligible for revise-and-resubmit, there must be some effort put into the assignment (a 3 or higher) for the original handin.
Late work is generally not accepted. If circumstances beyond your control prevent you from making any progress on an assignment before it is due, you are at significant risk of falling behind in the course. Come talk to me ASAP!
You may use the course materials (slides, examples) posted on the course webpage and the course Canvas site as well as the textbook.
You are encouraged to come to office hours and Teaching Fellows for help with thinking through getting started, Java help, debugging help, or help with anything else you might be stuck on.
The use of generative AI (such as ChatGPT), homework help websites, or other resources (friends, YouTube, etc) as learning cheats is not permitted. "As a learning cheat" means generating, finding, copying, etc code that you incorporate directly or with only minor modifications into your solution. The most egregious version of this is generating the entire program, but the prohibition applies to even small sections of code as well.
Using other resources as learning aids is permitted, but you are strongly encouraged to utilize the course materials, office hours, and Teaching Fellows as your primary sources of help. "As a learning aid" is to understand concepts — e.g. getting examples of loops to understand how to write loops in general or the specific syntax for loops in Java, not their specific application to this program. ("An example of a program to play flip" is a solution, not an example, and is not a learning aid.)
To hand in your work:
Make sure that your name is in an @author tag at the beginning of each file that you modified, and that all of your Java files have been auto-formatted and saved.
Copy the entire solitaire project directory to your handin directory. Make sure that you end up with solitaire directly inside your handin directory, with the Java files themselves in a src folder inside solitaire. Don't introduce extra directories or leave some out!
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.
The idea of encryption is to facilitate the sending of secret messages over an open channel - the sender encodes the message in a way that appears as nonsense to anyone who might see it, but which the intended recipient can decode to obtain the original message. This is essential in the age of online transactions - you don't want someone to see that credit card number you are sending over the Internet!
A simple and well-known encryption method is the Caesar cipher. In this scheme, each letter in the original message is replaced by the letter k positions later in the alphabet. For example, with a shift of 3 (k=3), A would be replaced with D, B would be replaced with E, C would be replaced with F, and so forth. (Wrap around at the end of the alphabet, so X would be replaced with A, Y with B, and Z with C.) To decrypt the message, just apply the process in reverse - replace D with A, E with B, etc.
This is not a very secure scheme, as there are only 25 possible shifts and it wouldn't take long, even by hand, to try them all and decipher the message. However, if a different shift amount is used for each character... The idea of Solitaire is to generate a series of shift values (called a keystream) instead of using the same shift for every character. The name "Solitaire" comes from the use of a deck of cards to generate the keystream values. (It is designed to be a secure encryption scheme that can be carried out by hand in the field.)
The details of the Solitaire algorithm that you'll be implementing can be found in the section Solitaire — Technical Description below.
Your task is to create a program which allows the user to encrypt and decrypt text using a slightly modified version of the original Solitaire Encryption Algorithm as described in the section Solitaire — Technical Description below. 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.
In creating this program, you'll write five classes:
An overview of the program organization and the specifics of the classes you should implement, including their instance variables, constructors, and methods, can be found in the Code Specifications section below. You should read through that whole section to gain an understanding of what you'll be doing before you start implementing. Note that you must use the provided code and create/implement the classes and methods as described below — you will not receive credit otherwise.
Additional requirements:
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. This includes checking class invariants and creating testers as described for each class.
Make sure that the program doesn't crash if used incorrectly.
Your code should reflect good coding style. Javadoc comments should be present for all classes and methods and comments should include necessary information (including preconditions) without also including unnecessary or inappropriate information. Also choose descriptive names and follow consistent and standard conventions for naming and whitespace. It is strongly recommended that you follow the 225 programming standards. Autoformat will take care of many potential whitespace-related issues, including improper indentation and too-long lines. Use blank lines for grouping and organization within longer methods.
Create a new Eclipse project named solitaire.
The provided code for this project has been provided only in compiled form. Add the provided jar file to your project and your project's build path as was done in lab 2:
In the Files application (not Eclipse!), create a folder lib inside your solitaire project folder and copy /classes/cs225/solitaire/solitaire.jar into the lib folder.
In Eclipse, right-click on the solitaire project name in the Package Explorer and choose Refresh. You should now see the lib directory and the jar file inside in the Package Explorer.
Right-click on solitaire.jar and choose Build Path → Add to Build Path. You should see a "Referenced Libraries" section appear for the project in the Package Explorer.
Read through the Solitaire — Technical Description section to understand the Solitaire algorithm. Your goal is to understand it at the level of being able to carry it out with a deck of cards — or a string representation of a deck of cards as shown in the examples.
Read about circular doubly-linked lists (see the Other Notes) section and make sure you understand how the deck will be stored.
Read through the task description above and the program organization in the Code Specifications section below to understand the overall organization of the assignment.
Implement and test the classes described in the Code Specifications section in order. Be sure to read through the whole section for each class before you start implementing, as there is often more information about class elements after the bulleted list of elements. Thorough testing is important, especially for SolitaireDeck, as it will be very difficult to debug a problem with encryption or decryption if all you know is that you aren't getting the original message back when you try to decrypt something.
To be on track, you should have implemented and tested the SolitaireDeck class by the checkpoint deadline given at the beginning of this handout. Of course, being ahead of that is even better!
This program is organized into five main classes:
There are also two supporting classes provided in solitaire.jar:
Click on the links for the API documentation on how to use these classes.
Implement the classes described below. Name methods as specified, and define parameters in the order listed. Be sure include Javadoc comments for the class and each method. Also identify any class invariants and method preconditions in the appropriate comments and add runtime checks for those conditions where it is productive to do so.
Create a class SolitaireTester with a main program containing the standard are-assertions-on boilerplate you've seen in the testers in lab 2, lab 4, and Omino.
As you implement the rest of the classes below, add tester subroutines for each method being tested as well as specific test cases for those methods in the style of the testers from lab 2, lab 4, and Omino.
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 Other Notes section below for more information on circular doubly-linked lists.
Instance variables:
Constructors:
takes the deck size as a parameter and initializes the deck accordingly
(non-public) takes the deck size and a deck string as parameters and initializes the deck accordingly
The first 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
The second constructor is for testing (why it isn't public). The deck string should be in the same form that the toString method produces. You can split such a string into an array with a separate value for each card using String's split method, as in Omino:
String str = "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";
String[] cards = str.split(" +");
Methods:
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 Deck Operations)
a method toString() which returns a string representation of the deck
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.
Correctness:
The SolitaireDeck operations perform complex manipulations of the deck structure, and there is plenty of potential for making a mistake in the linked list manipulations. While it is difficult to state anything too specific about the correct result of an operation without having a specific starting state, it is possible to state two class invariants: that the linked list structure is consistent (for every node a, the previous of a's next and the next of a's previous should both be a) and that the deck contains (only) cards 1..n and two jokers. Furthermore, checking these invariants is at least somewhat easier than the deck manipulations themselves.
Add the following helper methods, then use assertions to check the class invariants (structure and content) at the end of every method that modifies the linked list in any way. Don't forget to turn on assertion checking in the main program in SolitaireTester! (Refer back to lab 2 if you don't remember how to do this.)
a private helper method checkStructure() which returns true if the linked list structure is consistent (for every node a, the previous of a's next and the next of a's previous should both be a) and false otherwise
a private helper method checkContents() which returns true if the deck contains cards 1..decksize plus joker A and joker B (and nothing else) and false otherwise
Hint: 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 counting the number of nodes in the deck and verifying that is decksize+2 (with no duplicates found).
Testing:
Add test cases to SolitaireTester for the public constructors and methods of SolitaireDeck. The descriptions of the deck operations include examples — use those as a starting point, but be sure to add additional test cases as needed to cover all of the behaviors and possible special cases.
How do you know if a method worked? For the deck-manipulation operations, a correct result is a valid list structure (verified by checking the class invariations) and the cards in the deck being in the right order — compare string representations of the deck to check the card order.
KeystreamGenerator handles generating the keystream values.
Instance variables:
the deck to use (type SolitaireDeck)
Constructor:
takes the deck size and a passphrase as parameters, then creates a new deck of that size to initialize the instance variable and keys the deck using the passphrase (as described in Keying the Deck)
Methods:
a method nextKeystreamValue() which generates and returns the next keystream value (as described in Keystream Generation)
Testing:
Add test cases to SolitaireTester to cover the public constructors and methods. But there are a couple of wrinkles...
Wrinkle #1 is that the result of a constructor is correctly-initialized instance variables — in this case, a correctly keyed deck. But there aren't any methods in KeystreamGenerator to provide access to the deck. To address this, add a helper method to support testing:
a non-public getter getDeckString() which returns a string representation of the deck
Wrinkle #2 is how do you know what the expected result is for a particular test case? Keying the deck and then generating keystream values are complex operations, and it's not meant to be easy to figure out the answer without going through the process to generate it. 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 encryption example provides starting state and expected output for keystream initialization and the first keystream value - two test cases! The 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. While these test cases aren't necessarily a comprehensive set of cases, it's better than nothing.
SolitaireEncoder handles the actual encryption and decryption processes. It has only static methods.
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 a new KeystreamGenerator keyed with the specified passphrase before carrying out the encryption or decryption process described in the Encryption and Decryption sections.
Testing:
Add test cases for encrypt and decrypt. As with KeystreamGenerator, you are testing a complex process and there's not a shortcut to knowing the right answer without following that process. However, the example in the Encryption section provides one message and its encrypted version, which can be used as a test case for both encryption and decryption. It is also the case that decryption should undo encryption, so you can test for bugs in one of the processes by checking that the result of decryption matches the original message,
SolitaireMain contains the main program, which should allow the user to encrypt and decrypt messages as described.
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.
For example: (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
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).
Your program should be robust - it should not crash, do something unexpected, or work incorrectly if the user does not use it correctly. Error messages should be user-friendly.
Testing:
Test your program by running it. All of the encryption and decryption functionality should be covered by your test cases in SolitaireTester, so the only tests you should need at this point are that the user interaction is correct and that the main program is robust.
Extra credit features are things you can add for extra credit. Make sure you complete the requirements of the assignment first, however, before tackling extra credit options!
Some options:
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.)
Modify the main program so that it can also be used to encrypt/decrypt files. Add menu items "ef" and "df" for "encrypt file" and "decrypt file", then prompt the user for the input and output filenames. Note that there should only be one call to encrypt or decrypt for the entire file - don't do a line at a time.
Add a commandline option for file encryption/decryption where the action ("e" for encrypt, "d" for decrypt), passphrase, input filename, and output filename are specified as commandline parameters. For example:
java SolitaireMain e "secret key" myfile.txt encrypted.txt
The result should be written to the output file (encrypted.txt in the example).
If no commandline parameters are specified, the program should work as normal - display the menu and prompt the user for the necessary information.
The original 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
There are four operations that are applied to the deck of cards as part of carrying out the Solitaire algorithm: two kinds of joker swaps, triple cuts, and count cuts. Each is described below.
In a joker swap, joker A is swapped with the card that comes after it in the deck. For example: (bold underline 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
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.
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
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
In order to successfully exchange messages, the person decrypting the message must use the same sequence of keystream values as the person encrypting the message - which means that both parties must start with their decks of cards arranged in the same way. The process of arranging the cards in the deck in a certain order is known as keying the deck.
Since directly communicating the order of the cards in the deck is cumbersome, a secret passphrase (known only to the two parties who are exchanging messages) is used instead - 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).
Repeat the following steps for each character of the passphrase:
If the character is not a letter (e.g. space, punctuation), skip it.
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.
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).
Do a second count cut, using the number from the previous step as the number of cards to count.
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 the next 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.
To encrypt a message:
Initialize the keystream generator (see Keying the Deck").
For each character in the original message:
If the character is not a letter (e.g. a space, punctuation, a number), skip it.
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 the next keystream value (see Keystream Generation).
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.
Convert the number back into a letter. (1=A, 2=B, etc) This is the encrypted letter.
The encrypted message is just the resulting sequence of encrypted letters.
For example, consider the message you'll never guess this message! and the passphrase SECRET KEY.
First, start with the deck in order:
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
Key the deck using the passphrase:
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
Encrypt the message: (the example shows the steps applied to the whole message at once, but note that you should go through all five steps for each character in turn)
Skip non-letters.
youllneverguessthismessage
Convert letters to numbers.
y o u l l n e v e r g u e s s t h i s m e s s a g e 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 keystream values.
For the first keystream value:
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 keystream value is 22 - the 22 is 27 cards from the top (starting with 0) and isn't a joker.
Repeating this process for the rest of the characters in the message results in the following keystream values:
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
Add the number for the letter to the keystream value.
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 back to letters.
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 final encrypted message: UKTUMUXRMOSPGVWSADBUHPJSFC
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 keystream generator must be initialized the same way it was when the encryption process was started.
To decrypt a message:
Initialize the keystream generator (see Keying the Deck).
For each character in the encrypted message:
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 the next keystream value (see Keystream Generation").
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.
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.
This assignment is based on materials by Lester McCann.