Output: Standard Output (stdout)
Memory limit: 100 megabytes
Time limit: 1.0 seconds
Playfair cipher spying mission has come back, after many months, to request a translation. You have been asked to write a program that uses a given Playfair square to encrypt a key! You may recall from Round 1 that we constructed this Playfair square. However, you do not need to have done the previous problem to do this one.
You will be given the following 5 x 5 grid of characters which was constructed using the keyword
wheatstone. Your program should use this to encrypt given messages. Columns go down the grid and rows go across the grid to the right.
w h e a t s o n b c d f g i k l m p q r u v x y z
Remember: i and j are considered equivalent characters in a Playfair square.
Consider the plaintext
We look at each sequential pair of letters,
le. Then for each pair of letters, we construct a rectangle around the pair using the above grid.
ju, the rectangle would be:
d f g i <- remember i == j l m p q u v x y
i is the top right corner (since
i are equivalent) and
u is the bottom left corner. This 'sub-rectangle' is taken from the bottom left corner of the 5 x 5 key given above. Our program will always use this same grid to build sub-rectangles.
To get the encrypted text, take the opposite corners of the rectangles, with the letter in the same row as the first plaintext letter coming first. Thus
ju encrypts to
However, this method does not deal with letters in the same row/column or pairs of letters that are the same. Lucky, the full set of encryption steps are outlined below...
Hint: Skip steps 1, 2, 4, & 5 below for an easier starting point then build up to the final solution.
Take two letters at a time.
- If these two letters are the same, then insert an
xcharacter between them. For example, if you had the text
ssh, it should be processed as two pairs. The first would be
sxand the second
xhas effectively been inserted between them. However, the text
psstdoes not require an
xsince it splits into pairs
- If the message has an odd number of characters, add an
xto the end to make the last pair. For example,
foexso we can process two pairs. However, the previous example
sshdidn't need an
xsince we added one in the middle which made it even in length.
- Find the position of the characters in the Playfair square.
- If the letters appear in the same column of the square, replace them with the letters immediately below respectively (wrapping around to the top of the grid if needed). For example, if you had the pair
abthey would encrypt to
biby moving down one.
- If the letters appear on the same row of the square, replace them with the letters immediately to the right (wrapping around to the left if needed). For example,
- If none of the conditions above are met, we must have a rectangle like in the first example using
- The first letter encrypts to the character on the same row which is on the other side of the rectangle. For example,
din the above example.
- The second letter encrypts to the character on the same row which is on the other side of the rectangle. For example,
yin the above example. Getting the correct order is important. Remember to always check to respective row.
Some picture examples are available HERE (from Wikipedia).
The plaintext on one line. There will be no capitals, punctuation, or spaces. The plaintext will be at least 1 and at most 1000 characters. A plaintext will never contain two consecutive
The encrypted ciphertext on one line.
Subtasks are cumulative.
Subtask 1 (40%) The plaintext will be of even length and not require any
xcharacters to be added, all pairs will create a rectangle. i.e. you can ignore rules 1, 2, 4 & 5.
Subtask 2 (30%) The plaintext will be of even length and not require any
xcharacters to be added. i.e. you can ignore rules 1 & 2.
- Subtask 3 (30%) The full solution.
If you are spending too long on this problem, move on and give the subtasks of the next problem a go for some easy points.
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2