9
\$\begingroup\$

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())
        {
            String word = StdIn.readString();
            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[0], args[1]);
    }
}

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?

Thanks for your attention.

\$\endgroup\$
14
\$\begingroup\$

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[0], args[1]);
        while (!StdIn.isEmpty()) {
            String input = StdIn.readString();
            System.out.println(cipher.encrypt(input));
        }
    }
}
\$\endgroup\$
5
  • 2
    \$\begingroup\$ Since you know the length of the encoded string, you should consider setting the capacity of the StringBuilder: new StringBuilder(s.length()). Or just directly use a char array. \$\endgroup\$
    – RoToRa
    Sep 4 '20 at 7:16
  • 1
    \$\begingroup\$ You just missed the point that any letter in standard input must appear in exactly one of the keys. Aside of that I have the same result as your sample but with Stream instead of loops. \$\endgroup\$
    – gervais.b
    Sep 4 '20 at 7:33
  • \$\begingroup\$ @RoToRa good point, I updated the answer with your suggestion. \$\endgroup\$
    – Marc
    Sep 4 '20 at 10:40
  • \$\begingroup\$ @gervais.b yep I missed that, answer updated. \$\endgroup\$
    – Marc
    Sep 4 '20 at 10:44
  • 1
    \$\begingroup\$ @Marc Thank you very much. I'm still not familiar to OOP (although I'm not sure whether you used it or not). I try to assimilate the above information gradually. \$\endgroup\$ Sep 4 '20 at 12:23
5
\$\begingroup\$

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...]

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.