UVa: Problema 458 - The Decoder

03 Nov 2011
3 mins read

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

Se reparar, sempre estamos voltando 7 caracteres:

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!