# Implementation of Kamasutra cipher

Posted on

Problem

This is exercise 3.1.31. from the book Computer Science An Interdisciplinary Approach by Sedgewick & Wayne:

Write a filter KamasutraCipher that takes two strings as command-line
argument (the key strings), then reads strings (separated by
whitespace) from standard input, substitutes for each letter as
specified by the key strings, and prints the result to standard
output. This operation is the basis for one of the earliest known
cryptographic systems. The condition on the key strings is that they
must be of equal length and that any letter in standard input must
appear in exactly one of them. For example, if the two keys are
THEQUICKBROWN and FXJMPSVLAZYDG, then we make the table

T H E Q U I C K B R O W N

F X J M P S V L A Z Y D G

which tells us that we should substitute F for T, T for F, H for X, X
for H, and so forth when filtering standard input to standard output.
The message is encoded by replacing each letter with its pair. For
example, the message MEET AT ELEVEN is encoded as QJJF BF JKJCJG. The
person receiving the message can use the same keys to get the message
back.

Here is my program:

``````public class KamasutraCipher
{
public static void encrypt(String s, String t)
{
int m = s.length();
int n = t.length();
if (m != n)
{
throw new RuntimeException("The key lengths must be equal");
}
while (!StdIn.isEmpty())
{
int wordLength = word.length();
for (int i = 0; i < wordLength; i++)
{
for (int j = 0; j < m; j++)
{
if (String.valueOf(word.charAt(i)).equals(String.valueOf(s.charAt(j))))
{
String temp = word;
word = temp.substring(0,i) + String.valueOf(t.charAt(j)) + temp.substring(i+1);
}
else if (String.valueOf(word.charAt(i)).equals(String.valueOf(t.charAt(j))))
{
String temp = word;
word = temp.substring(0,i) + String.valueOf(s.charAt(j)) + temp.substring(i+1);
}
}
}
System.out.print(word + " ");
}
}
public static void main(String[] args)
{
encrypt(args, args);
}
}
``````

StdIn is a simple API written by the authors of the book. I checked my program and it works.

Is there any way that I can improve my program?

Solution

The implementation looks good, I just have a few suggestions.

## Single-responsibility principle

The method `encrypt` seems to have a lot of responsibility:

1. Reads the input from the user
2. Encrypts the input
3. Outputs the result to the console

One definition of SRP is “A class should have only one reason to change”. But there are many reasons for `KamasutraCipher` to change:

1. The input may come from `System.in`, file, database, etc.
2. The library `StdIn` changes.
3. The output needs to go to a file, etc.
4. The output needs to be formatted nicely for the user
5. etc..

The only responsibility of `KamasutraCipher` should be to encrypt (or decrypt) a string and return the result.

The interface can be refactored from this:

``````public class KamasutraCipher {
public static void encrypt(String s, String t)
}
``````

To:

``````public class KamasutraCipher {
public KamasutraCipher(String key1, String key2)
public String encrypt(String s)
}
``````

Now the only reason for `KamasutraCipher` to change is for optimizations or if the Kamasutra algorithm changes, but the latter is not going to happen soon.

All the logic for requesting the input and producing the output is pushed to the `main`.

## Strings are immutable

In Java strings are immutable objects, and any modification to a string creates a new string. Therefore this part:

``````String temp = word;
word = temp.substring(0,i) + String.valueOf(t.charAt(j)) + temp.substring(i+1);
``````

Can be changed to:

``````word = word.substring(0,i) + t.charAt(j) + word.substring(i+1);
``````

## Optimization

The complexity of the method `encrypt` is `O(m*n)` where `m` is the length of the input string and `n` is the length of the key. (ignoring the methods of `String` and the while loop).

A more efficient way would be to use a map to store the string keys. For example, given the string keys ABC and FGH, the map would contain:

• A -> F
• B -> G
• C -> H
• F -> A
• G -> B
• H -> C

The method `encrypt` then becomes a simple lookup on the map, reducing the complexity to `O(m)`:

``````public String encrypt(String s) {
StringBuilder sb = new StringBuilder(s.length());
for (int i = 0; i < s.length(); i++) {
Character c = s.charAt(i);
sb.append(keyMap.get(c));
}
return sb.toString();
}
``````

`SpringBuilder` lets us save some memory by creating the result string more efficiently. `keyMap` is created in the constructor because the keys don’t change after initialization.

## Input validation

any letter in standard input must appear in exactly one of them (keys)

As mentioned by others this is a requirement that needs to be handled, possibly in the method `encrypt`.

For the exceptions you can use `IllegalArgumentException` instead of `RuntimeException`.

## Refactored code

``````public class KamasutraCipher {

private final Map<Character,Character> keyMap;

public KamasutraCipher(String key1, String key2) {
if (key1.length() != key2.length()) {
throw new IllegalArgumentException("The key lengths must be equal");
}
keyMap = new HashMap<>();
for (int i = 0; i < key1.length(); i++) {
keyMap.put(key1.charAt(i), key2.charAt(i));
keyMap.put(key2.charAt(i), key1.charAt(i));
}
}

public String encrypt(String s) {
StringBuilder sb = new StringBuilder(s.length());
for (int i = 0; i < s.length(); i++) {
Character c = s.charAt(i);
if(!keyMap.containsKey(c)) {
throw new IllegalArgumentException(String.format("'%c' is not in the keys", c));
}
sb.append(keyMap.get(c));
}
return sb.toString();
}

public static void main(String[] args) {
KamasutraCipher cipher = new KamasutraCipher(args, args);
while (!StdIn.isEmpty()) {
System.out.println(cipher.encrypt(input));
}
}
}
``````

Marc has covered much of the ground, but I’d like to point out a couple of things he didn’t explicitly mention and add some further comments.

• “public static void encrypt(String s, String t)”. Notice how Marc replaced the opaque names “s” and “t” with more meaningful ones. In general short names are not our friends. Marc’s use of “s” as an argument name in his encrypt() method is, IMHO, OK in this context as the method’s so short, but in general prefer longer more expressive names.
• “String.valueOf(word.charAt(i)).equals(String.valueOf(s.charAt(j)))”
String.charAt(int) returns a char value, which is actually a (fairly) small integer. You don’t need to wrap two chars in Strings and use String.equals() to compare them. You can just say “word.charAt(i) == s.charAt(j)”.
• Neither your solution nor Marc’s actually checks that the two keystrings share no characters, nor contain duplicates.
• The problem specification suggests that if the word to be encrypted contains a character not in the keystrings, it’s an error. Neither your solution nor Marc’s treats it as such.

As an alternative to Marc’s solution, I’ll outline an alternative lookup strategy in place of Marc’s Map. (I’m not going to code it – it would be a more useful exercise for you to do so.)

If you create an array of chars of size Character.MAX_VALUE, you can populate it with substitute characters and simply access that using input characters as your index.
Unassigned entries in the array (for characters not supplied in the key strings) will be initialised to the null character (as per the language specification).

[Note: I have ignored surrogate code units on the assumption that the OPs input won’t involve them…]