UVa: Problema 458 - The Decoder
Outro problema da lista de iniciantes do UVa. Nesse post vamos resolver o Problema 458 - The Decoder.
Descrição do Problema:
Escreva um programa de decodificar um conjunto de caracteres em uma mensagem válida. O programa deve ler um arquivo que contém caracteres codificados e "imprimir" (output) exatamente a mensagem decodificada. A chave de codificação é exatamente uma única operação aritmética simples baseado no conjunto de caracteres ASCII.
Entendendo o Problema:
No enunciado também colocam 3 exemplos de input e output:
Exemplo de Input:
1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5
1PIT'pz'h'{yhklthyr'vm'{ol'Pu{lyuh{pvuhs'I|zpulzz'Thjopul'Jvywvyh{pvu5
1KLJ'pz'{ol'{yhklthyr'vm'{ol'Kpnp{hs'Lx|pwtlu{'Jvywvyh{pvu5
Exemplo de Output:
*CDC is the trademark of the Control Data Corporation.
*IBM is a trademark of the International Business Machine Corporation.
*DEC is the trademark of the Digital Equipment Corporation.
Esse é um problema relativamente simples e a única coisa que precisamos é uma tabela ASCII para comparar os caracteres:
Vamos então começar a comparar as mensagens. Vamos pegar os 3 primeiros caracteres da primeira mensagem: "1JK".
- Na tabela ASCII, o caractere "1" corresponde ao decimal 49. Precisamos transformar esse caractere no "*", que na tabela corresponde ao decimal 42.
- O caractere "J" corresponde ao decimal 74, e precisamos transformar no caractere "C", que corresponde ao decimal 67.
- O caractere "L" corresponde ao decimal 76, e precisamos transformar no caractere "D", que corresponde ao decimal 68.
Se reparar, sempre estamos voltando 7 caracteres:
- 49 - 42 = 7
- 74 - 67 = 7
- 76 - 68 = 7
Então para decodificar é só subtrair 7 do código decimal!
Código:
[code lang="java" firstline="1" toolbar="true" collapse="false" wraplines="false"]
package com.loiane.volume0;
import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.EOFException;
import java.io.IOException;
/**
* Problem 458 - The Decoder
*
* Just shift each character ASCII Codes 7 characters down. (7 is perfect number)
*
* Problem Link:
* http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=94&page=show_problem&problem=399
*
* Runtime: 1.548s
*
* @author Loiane Groner
* https://loiane.com
* http://loianegroner.com
*/
public class P458 {
public static void main(String[] args) throws IOException {
DataInputStream in = new DataInputStream(System.in);
DataOutputStream output = new DataOutputStream(System.out) ;
byte ch;
try {
while (true) {
ch = decode(in.readByte());
output.writeByte(ch);
output.flush();
}
} catch (EOFException eof) {}
}
public static byte decode(byte ch){
if (ch != 10 && ch != 13)
ch = (byte)(ch - 7);
return ch;
}
public static String decodeLine(String line){
byte[] bytes = line.getBytes();
byte[] decoded = new byte[bytes.length];
for (int i=0; i<bytes.length; i++){
decoded[i] = decode(bytes[i]);
}
return new String(decoded);
}
}
[/code]
Dicas:
Com Java, só funcionou com DataInputStream e DataOutputStream, pois já lê diretamente o código co caractere. Tentei ler com BufferedReader ou Scanner (maneiras tradicionais de ler input do UVa), mas não funcionou.
Como o problema não fala de nenhuma condição de parada, temos que ter até encontrar o final do arquivo/input (EOF). Para fazer isso, usamos um while(true) - sim, é feio fazer isso, mas no UVa é a única solução com Java. E nesse caso a condição de parada vai ser uma exceção e deixamos o catch em branco mesmo (outra coisa feia) - não façam isso em sistemas comerciais, esses problemas são apenas para brincar!
Tempo de execução no UVa: 1.548s
Testando Entrada e Saída:
[code lang="java" firstline="1" toolbar="true" collapse="false" wraplines="false"]
package com.loiane.test.volume0;
import static org.junit.Assert.assertEquals;
import org.junit.Test;
import com.loiane.volume0.P458;
/**
* Test Case
* Problem 458 - The Decoder
*
* @author Loiane Groner
* https://loiane.com
* http://loianegroner.com
*/
public class TestP458 {
@Test
public void testProblem548(){
final String input1 = "1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5";
final String input2 = "1PIT'pz'h'{yhklthyr'vm'{ol'Pu{lyuh{pvuhs'I|zpulzz'Thjopul'Jvywvyh{pvu5";
final String input3 = "1KLJ'pz'{ol'{yhklthyr'vm'{ol'Kpnp{hs'Lx|pwtlu{'Jvywvyh{pvu5";
final String output1 = "*CDC is the trademark of the Control Data Corporation.";
final String output2 = "*IBM is a trademark of the International Business Machine Corporation.";
final String output3 = "*DEC is the trademark of the Digital Equipment Corporation.";
assertEquals(output1, P458.decodeLine(input1));
assertEquals(output2, P458.decodeLine(input2));
assertEquals(output3, P458.decodeLine(input3));
}
}
[/code]
Bons códigos!