# Solving the 2014 APL Problem Solving Competition – Cryptography Problem 3

This post is the continuation of the series where we examine some of the problems selected for the 2014 APL Problem Solving Competition. In this post we’ll conclude looking at the cryptography problems from Phase II that we started looking at in a previous blog post and continued in a further blog post.

## Cryptography Problem 3 – Playfair Cipher

The first task is to convert a string into a 5×5 Playfair table. The solution makes straightforward use of APL primitives:

• Unique (`∪`) to remove duplicate characters from the string.
• Without (`~`) to find the rest of the alphabetic characters that are not mentioned in the string, and again to remove the character J.
``````PlayfairTable←{
k←∪⍵
5 5⍴(k,⎕A~k)~'J'
}``````

Here it is in action:

``````      ⊢table←PlayfairTable'KENNETHEIVERSON'
KENTH
IVRSO
ABCDF
GLMPQ
UWXYZ``````

To encrypt a message we need to take two characters at a time, find their coordinates in the 5×5 Playfair table, swap their column coordinates and look up the letters at the new coordinates. There are lots of tricks in the code below of which we’ll describe just a few:

• To process the message two characters at a time, appending to the result as we go, we use a tail-recursive dfn whose left argument accumulates the result. For an introduction to this technique see this implementation of the Fibonacci function.
• To find letters in the Playfair table we first look them up in the ravel (i.e. the linearised form) of the table, and then use Encode (`⊤`) to convert this linear index into a pair of coordinates. Decode (`⊥`) does the opposite, converting a pair of coordinates back into a linear index.
• Mix (`↑`) and Split (`↓`) are used to convert between two different representations of the coordinates of the two characters we’re encoding: either as a flat 2×2 matrix, or as a nested 2-vector of 2-vectors. The choice of representation is largely a matter of taste, and it might be fun to play with this part of the code. You could tweak it to work entirely with the flat representation, or entirely with the nested representation, rather than converting back and forth between them.
``````PlayfairEncrypt←{
⎕IO←0                       ⍝ To aid arithmetic modulo 5.
t←⍺                         ⍝ The Playfair table.
m←⍵,(2|≢⍵)/'Z'              ⍝ Add a Z if the message length is odd.
((m='J')/m)←'I'             ⍝ Convert J to I in the message.
0=≢⍵:⍺                  ⍝ Finished: return the accumulated encrypt.
1=≢⍵:⍺ ∇ ⍵,'X'          ⍝ Only one character left: add an X.
p←2↑⍵
=/p:⍺ ∇(⊃⍵),'X',1↓⍵     ⍝ Duplicate character: insert an X.
c←(⍴t)⊤(,t)⍳p           ⍝ Coords of each letter in the table.
c←{
=/1↑⍵:↑(⍴t)|0 1+↓⍵  ⍝ Same row: move to the right.
=/1↓⍵:↑(⍴t)|1 0+↓⍵  ⍝ Same column: move down.
0 1⌽⍵               ⍝ Else swap column coords.
}c
p←(,t)[(⍴t)⊥c]          ⍝ Look up new coords in table.
(⍺,p)∇ 2↓⍵              ⍝ Tail recursion.
}m
}``````

Here it is in action:

``````      ⊢cipher←table PlayfairEncrypt'HELLOWORLD'
KNMWQVZVVMCY``````

(Note that this result is slightly different from that given in the original problem description, because of some confusion about the rules for handling duplicate letters and odd message lengths, which were clarified later in the student competition forums.)

Decryption is very similar to encryption. The differences are:

• Letters found in the same row of the table need to move left instead of right, and letters in the same column need to move up instead of down.
• We don’t need to worry about the input having an odd length, or containing the letter J.

Hence the code for `PlayfairDecrypt` is shorter than but very similar to `PlayfairEncrypt`:

``````PlayfairDecrypt←{
⎕IO←0                       ⍝ To aid arithmetic modulo 5.
t←⍺                         ⍝ The Playfair table.
0=≢⍵:⍺                  ⍝ Finished: return the accumulated encrypt.
p←2↑⍵
c←(⍴t)⊤(,t)⍳p           ⍝ Coords of each letter in the table.
c←{
=/1↑⍵:↑(⍴t)|0 ¯1+↓⍵ ⍝ Same row: move to the left.
=/1↓⍵:↑(⍴t)|¯1 0+↓⍵ ⍝ Same column: move up.
0 1⌽⍵               ⍝ Else swap column coords.
}c
p←(,t)[(⍴t)⊥c]          ⍝ Look up new coords in table.
(⍺,p)∇ 2↓⍵              ⍝ Tail recursion.
}⍵
}``````

Here it is in action:

``````      table PlayfairDecrypt cipher
HELXLOWORLDX``````