Implementação da cifra Kamasutra
Este é o exercício 3.1.31. do livro Computer Science An Interdisciplinary Approach, de Sedgewick & Wayne:
Escreva um filtro KamasutraCipher que recebe duas cadeias de caracteres como argumento de linha de comando (as cadeias de caracteres de chave) e, em seguida, lê cadeias de caracteres (separadas por espaços em branco) da entrada padrão, substitui cada letra conforme especificado pelas cadeias de caracteres de chave e imprime o resultado na saída padrão. Esta operação é a base de um dos primeiros sistemas criptográficos conhecidos. A condição para as strings de chave é que elas devem ter o mesmo comprimento e que qualquer letra na entrada padrão deve aparecer exatamente em uma delas. Por exemplo, se as duas chaves são THEQUICKBROWN e FXJMPSVLAZYDG, então fazemos a tabela
THEQUICKBROWN
FXJMPSVLAZYDG
o que nos diz que devemos substituir F por T, T por F, H por X, X por H e assim por diante ao filtrar a entrada padrão para a saída padrão. A mensagem é codificada substituindo cada letra por seu par. Por exemplo, a mensagem MEET AT ELEVEN é codificada como QJJF BF JKJCJG. A pessoa que recebe a mensagem pode usar as mesmas teclas para recebê-la de volta.
Aqui está o meu programa:
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 é uma API simples escrita pelos autores do livro. Verifiquei meu programa e funciona.
Existe alguma maneira de melhorar meu programa?
Agradecimentos para sua atenção.
Respostas
A implementação parece boa, só tenho algumas sugestões.
Princípio de responsabilidade única
O método encryptparece ter muita responsabilidade:
- Lê a entrada do usuário
- Criptografa a entrada
- Envia o resultado para o console
Uma definição de SRP é "Uma classe deve ter apenas um motivo para mudar". Mas há muitos motivos para KamasutraCiphermudar:
- A entrada pode vir de
System.in, arquivo, banco de dados, etc. - A biblioteca
StdInmuda. - A saída precisa ir para um arquivo, etc.
- A saída precisa ser formatada de maneira adequada para o usuário
- etc ..
A única responsabilidade de KamasutraCipherdeve ser criptografar (ou descriptografar) uma string e retornar o resultado.
A interface pode ser refatorada a partir deste:
public class KamasutraCipher {
public static void encrypt(String s, String t)
}
Para:
public class KamasutraCipher {
public KamasutraCipher(String key1, String key2)
public String encrypt(String s)
}
Agora a única razão para KamasutraCiphermudar é para otimizações ou se o algoritmo Kamasutra mudar, mas isso não vai acontecer tão cedo.
Toda a lógica para solicitar a entrada e produzir a saída é enviada para o main.
Strings são imutáveis
Em Java, as strings são objetos imutáveis e qualquer modificação em uma string cria uma nova string. Portanto, esta parte:
String temp = word;
word = temp.substring(0,i) + String.valueOf(t.charAt(j)) + temp.substring(i+1);
Pode ser alterado para:
word = word.substring(0,i) + t.charAt(j) + word.substring(i+1);
Otimização
A complexidade do método encrypté O(m*n)onde mestá o comprimento da string de entrada e né o comprimento da chave. (ignorando os métodos de Stringe o loop while).
Uma maneira mais eficiente seria usar um mapa para armazenar as chaves da string. Por exemplo, dadas as chaves de string ABC e FGH , o mapa conteria:
- A -> F
- B -> G
- C -> H
- F -> A
- G -> B
- H -> C
O método encryptentão se torna uma pesquisa simples no mapa, reduzindo a complexidade para 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();
}
SpringBuildernos permite economizar memória criando a string de resultado com mais eficiência. keyMapé criado no construtor porque as chaves não mudam após a inicialização.
Validação de entrada
qualquer letra na entrada padrão deve aparecer exatamente em um deles (chaves)
Conforme mencionado por outros, este é um requisito que precisa ser tratado, possivelmente no método encrypt.
Para as exceções, você pode usar em IllegalArgumentExceptionvez de RuntimeException.
Código refatorado
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));
}
}
}
Marc cobriu muito do terreno, mas gostaria de apontar algumas coisas que ele não mencionou explicitamente e adicionar mais alguns comentários.
- "public static void encrypt (String s, String t)". Observe como Marc substituiu os nomes opacos "s" e "t" por outros mais significativos. Em geral, nomes curtos não são nossos amigos. O uso de "s" por Marc como um nome de argumento em seu método encrypt () é, IMHO, OK neste contexto, pois o método é tão curto, mas em geral prefere nomes mais longos e expressivos.
- "String.valueOf (word.charAt (i)). Equals (String.valueOf (s.charAt (j)))" String.charAt (int) retorna um valor char , que é na verdade um (razoavelmente) pequeno inteiro. Você não precisa envolver dois caracteres em Strings e usar String.equals () para compará-los. Você pode apenas dizer "word.charAt (i) == s.charAt (j)".
- Nem sua solução nem a de Marc realmente verificam se as duas sequências de teclas não compartilham caracteres nem contêm duplicatas.
- A especificação do problema sugere que, se a palavra a ser criptografada contiver um caractere que não esteja nas cadeias de caracteres, será um erro. Nem a sua solução nem a de Marc a tratam como tal.
Como alternativa à solução de Marc, vou delinear uma estratégia de pesquisa alternativa no lugar do Mapa de Marc. (Não vou codificá-lo - seria um exercício mais útil para você fazer isso.)
Se você criar uma matriz de caracteres de tamanho Character.MAX_VALUE, poderá preenchê-la com caracteres substitutos e simplesmente acessá-los usando caracteres de entrada como seu índice. As entradas não atribuídas na matriz (para caracteres não fornecidos nas cadeias de caracteres de chave) serão inicializadas com o caractere nulo (de acordo com a especificação do idioma ).
[Observação: ignorei as unidades de código substituto na suposição de que a entrada dos OPs não as envolveria ...]