Algoritmos e Estrutura de Dados I - AE22CP - 2012/2 |
|
Bruno César Ribas e Willian Zalewski |
- Prólogo
- O problema das imagens
- Formato de Entrada
- Compactação
- Descompactação
- Execução
- Exemplos de Entrada e Saída
- Ranking
- Prazos
- Critérios da Correção
- Curiosidades
Prólogo
Parabéns! Finalmente você foi aceito para fazer parte do grupo do Rick, afinal após salvar a pele dele e do filho por diversas vezes você realmente merecia. Mas em uma conversa com Michonne, pude perceber que quem realmente avaliou a sua permanência no grupo foi o Carl.
Infelizmente não temos tempo para comemoração! O governador está solto em algum lugar que não sabemos e para evitar maiores problemas vamos colocar sensores para rastrear qualquer atividade.
Conseguimos encontrar diversas câmeras que funcionam com energia solar em um galpão abandonado, as câmeras são boas, embora consigam armazenar imagens apenas em tons de cinza, no formato PGM.
Precisamos armazenar todas as imagens para poder identificar potenciais ataques em nosso lar.
O problema das imagens
Recursos computacionais hoje em dia são extremamente raros e difíceis de conseguir, por isso você tem dar um jeito para armazenar todas essas imagens.
Daryl também pediu que você armazenasse todas as plantas de ambientes que já passamos para poder ter sempre em mãos quando necessário, afinal não sabemos onde nossa luta com o governador pode acontecer.
Glenn conseguiu apenas alguns pendrives de 128G para conseguir armazenar tudo e por isso você precisa compactar essas imagens para evitar o uso total dos nossos dispositivos.
Formato de Entrada
As imagens das câmeras são guardadas em formato PGM ascii.
O Formato PGM ascii em tons de cinza é bastante simples. O formato possui um cabeçalho de 3 linhas contendo, respectivamente, nas linhas:
- P2
- essa linha informa o tipo do arquivo e P2 significa PGM ascii
- Colunas Linhas
- 2 inteiros representando a dimensão da imagem, primeiro quantas colunas e depois quantas linhas
- Cor mais clara
- Um inteiro representando o valor da cor mais clara, lembre que 0 sempre é preto e a cor mais clara sempre é o branco (quando em tons de cinza).
As câmeras armazenam as imagens em tons de cinza com 8-bit de definição, então a nossa cor mais clara no máximo será 255.
Veja o exemplo de uma imagem que possui apenas um ponto branco no centro:
P2 5 5 255 0 0 0 0 0 0 0 0 0 0 0 0 255 0 0 0 0 0 0 0 0 0 0 0 0
Compactação
O seu programa deverá receber pela entrada padrão uma imagem PGM em tons de cinza e deverá imprimir na saída padrão a imagem compactada.
A maneira de compactação fica a seu critério e o formato de saída também. A única exigência é que a imagem compactada comece com a linha 'cP2', que representa PGM ascii compactada.
Descompactação
Como qualquer programa que compacta algum conteúdo ele também deve descompactar e por isso sempre que seu programa receber na entrada padrão uma imagem compactada ele deve imprimir na saída padrão a imagem descompactada.
Um programa está certo quando a descompactação gera uma igual a imagem original.
Execução
A entrada e saída do programa devem ser feitas pela entrada e saída padrão ( como se estivesse lendo as informações pelo teclado)
exemplo de execução:
time ./meuprograma < mapa.pgm > mapa-compactado.cpgm time ./meuprograma < mapa-compactado.cpgm > mapa-descompactado.pgm
Onde "meuprograma" é o nome do executável do trabalho (pode ser outro nome qualquer), e "mapa.pgm" é o arquivo que contém a foto da câmera, ou a planta de um ambiente. O arquivo "mapa-compactado.cpgm" é o arquivo que armazenará a saída do seu programa.
Quando executar o seu programa da forma indicada abaixo , o sinal '<' significa que o conteúdo do 'mapa.pgm' será passado ao programa como se ele estivesse sendo lido do teclado. E o sinal '>' significa que tudo que o seu programa imprimir na saída padrão será salvo em 'mapa-compactado.cpgm'. E 'time' é comando que contará o tempo de execução do seu programa.
A segunda execução significa que o programa receberá como entrada o arquivo compactado e imprimirá o mesmo descompactado, salvando em mapa-descompactado.pgm.
Para saber se o arquivo descompactado ficou igual ao original basta executar o comando:
diff mapa.pgm mapa-descompactado.pgm
Se o comando diff não imprimir nada na tela significa que os dois arquivos são iguais, caso contrário ele imprimirá as linhas com diferenças.
Como os compactadores estão específicos para imagem nem sempre o formato do arquivo descompactado pode ser igual ao original (pode ter diferença de linhas e colunas no arquivo mas com o mesmo conteúdo), por isso essa unicidade do compactador específico pode ser resolvida pelo comando:
(tr -d '\n' < original; echo; tr -d '\n' < descompactado)|uniq -d|wc -l
Onde 'original' é substituído pelo nome do arquivo de imagem original e o 'descompactado' pelo nome do arquivo gerado pelo processo da descompactação do seu programa. Se a resposta da execução for '1' significa que as duas imagens são identicas, se '2' é porque existe alguma diferença entre elas.
Exemplos de Entrada e Saída
- mapa-2013-01-29 PGM.bz2 PNG
- mapa-2013-02-01 PGM.bz2 PNG
- mapa-2013-02-03 PGM.bz2 PNG
- mapa-2013-02-11 PGM.bz2 PNG
- Walking PGM.bz2 PNG
- Zombie PGM.bz2 PNG
Não se limite a esses exemplos, crie seus próprios exemplos!
Para converter alguma imagem em formato PGM ascii basta executar o seguinte comando:
$ convert -compress none imagemoriginal.jpg nova.pgm
Onde 'imagemoriginal.jpg' é alguma imagem que vocês queira converter (pode ser png, jpg, pdf, tiff, gif e muitos outros) e 'nova.pgm' é o nome que você quer salvar a sua imagem pgm ascii, o nome pode ser qualquer um mas tem que colocar a extensão pgm.
O comando convert vem pelo pacote 'imagemagick', no ambiente centralizado (boot pela rede) ele já está instalado, mas em sua casa basta instalar o pacote 'imagemagick', no ubuntu seria da seguinte forma pela linha de comando:
$ sudo apt-get install imagemagick
Ranking
O ranking será feito por disputas diárias. Para participar basta enviar o código que o sistema copilará e executará.
Para participar do Ranking o seu código deve funcionar em LINUX, recomendamos o uso do Ubuntu. Se o sistema não conseguir compilar seu programa apenas será avisado que não conseguiu e nada mais.
- A tabela de execuções pode ser vista em: AQUI
Prazos
- Prazo de entrega: Dia 26 de Abril de 2013
- O sistema de submissão será encerrado às 23h50.
Critérios da Correção
Atualizado 15/04/2013
- O trabalho vale 100 pontos
- O rank definirá 2 limiares definidos como "Simples" e "Super Simples"
- Os limiares darão pela soma do tamanho dos arquivos compactados do RANK;
- Quando a soma for maior que a soma do "Super Simples" o trabalho valerá no máximo 50 pontos;
- Quando a soma ficar entre o "Simples" e "Super Simples" o trabalho valerá no máximo 80ponts;
- Quando a soma for menor que "Simples" e "Super Simples" o trabalho valerá no máximo 100pontos;
- O rank definirá 2 limiares definidos como "Simples" e "Super Simples"
- Os trabalhos que apenas replicam as imagens terão nota automaticamente em 0 (Zero)
- Se for necessário efetuar alguma ordenação, NÃO utilizar o método Bolha
- Os trabalhos serão executados contra todas imagens publicadas no rank.
- Se o programa falhar em qualquer imagem terá um desconto de 20 pontos, e
desconto adicional de 5 pontos para cada imagem que falhar.
- Se falhar em apenas 1 imagem terá um desconto de 20pontos, se falhar em 2 imagens o desconto será de 25pontos, em 3 imagens desconto de 30pontos, e assim por diante.
- Se o programa falhar em 50% ou mais dos imagens, terá nota automaticamente em 0.
- Se o programa falhar em qualquer imagem terá um desconto de 20 pontos, e
desconto adicional de 5 pontos para cada imagem que falhar.
- Os programas que não falharem em nenhuma imagem entrarão na rodada especial
para receber até 10 pontos extras
- Na rodada especial será executado uma nova imagem
- Se o programa falhar na rodada especial terá um desconto de 10 pontos
- Os 3 melhores programas receberão 10 pontos extras.
- Além da rodada automática os trabalhos passarão pelas seguintes
avaliações:
- Será considerado o código:
- Otimização
- Limpeza do código
- Criatividade
- Defesa individual do código quando a T2 - P2 >= 4
- Será considerado o código:
Curiosidades
A brincadeira com PGM também já foi feita AQUI e AQUI também
---
Last Modified: Mon Apr 15 23:59:42 2013.