Sim, o bom e velho GIF. Amado por sua versatilidade, odiado por suas patentes e parcialmente obsoleto devido às suas limitações (e patentes), o GIF consiste, no centro, de uma paleta de cores e uma imagem indexada por paleta compactada usando o algoritmo LZW.

Sua tarefa é gravar um programa que leia uma imagem no formato ASCII PPM (número mágico "P3") da entrada padrão e grave a mesma imagem (pixel a pixel idêntico) no formato GIF na saída padrão. A saída pode estar no formato binário ou em texto ASCII com cada byte representado por um número entre 0 e 255 (inclusive), separados por espaços em branco.

A imagem de entrada é garantida para não ter mais de 256 cores diferentes.

Pontuação:

Seu programa será testado em 3 imagens de amostra e sua pontuação será calculada da seguinte forma:
tamanho do programa + soma (tamanho da saída - tamanho de referência para cada imagem de amostra) A
pontuação mais baixa vence.

Requisitos:

• Seu programa deve funcionar com qualquer tipo de imagem semelhante de vários tamanhos e não deve se limitar às imagens de amostra. Você pode, por exemplo, restringir as dimensões a múltiplos de 2 ou assumir que a cor máxima em ppm é 255, mas ainda deve funcionar com uma grande variedade de imagens de entrada.
• A saída deve ser um arquivo GIF válido que possa ser carregado com qualquer programa compatível (depois de converter novamente em binário se estiver usando a opção de saída ASCII).
• Você não pode usar nenhuma função de processamento de imagem (embutida ou de terceiros); seu programa deve conter todo o código relevante.
• Seu programa deve ser executável no Linux usando software disponível gratuitamente.
• O código fonte deve usar apenas caracteres ASCII.

Imagens de exemplo:

Aqui estão as três imagens de amostra que serão usadas para a pontuação. Você pode baixar um arquivo zip com os arquivos ppm (use o botão de download na parte superior da página). Ou você pode convertê-los a partir das imagens png abaixo, usando o ImageMagick com o seguinte comando:

convert file.png -compress none file.ppm

Também estou fornecendo as somas de verificação MD5 dos arquivos ppm para confirmação.

1. âmbar

Tamanho de referência: 38055
Soma de verificação MD5 do ppm: d1ad863cb556869332074717eb278080

2. olhos azuis

Tamanho de referência: 28638
soma de verificação MD5 do ppm: e9ad410057a5f6c25a22a534259dcf3a

3. pimentas

Tamanho de referência: 53586
Soma de verificação MD5 do ppm: 74112dbdbb8b7de5216f9e24c2e1a627

Perl, 515 + -2922 + 0 + -2571 = -4978

Outra abordagem. Desta vez, estou tentando salvar a imagem em blocos de tamanho 64xH. Isso é bom de acordo com as especificações, mas alguns softwares podem mostrar apenas o primeiro bloco ou uma animação. Os ladrilhos se comprimem melhor por causa da melhor localização espacial. Ainda faço a compressão normal também para a segunda imagem e escolho o que veio mais curto. Como isso comprime a imagem duas vezes, é duas vezes mais lento em comparação à minha solução anterior.

#!perl -n0
sub r{$r.=1&"@_">>$_ for 0..log(@d|256)/log 2}
@k=/(\d+) (\d+)/;
@l=map{$$_||=(push(@t,split$"),++$i)}/\d+ \d+ \d+/g;
print+GIF89a,pack(vvCxxC768,@k,~8,@t);
sub v{($w,$h)=@_;for$k(0.."@k"/$w-1){
$k*=$w;$r='';@d=();@p=grep+($z++-$k)%"@k"<$w,@l;
$"=' ';$_="@p ";$"='|';while(/./){
r 256;%d=map{($_,$_-1)}@d=1..256;
$d{$&}=@d+2,r$d{$1},unshift@d,$&while@d<4095&&s/^(@d) (\d*)/$2/}
r 257;$_=pack"b*",$r;
$h.=pack"Cv4n(C/a)*",44,$k,0,$w,$k[1],8,/.{0,255}/gs
}$b=$h if!$b||length$b>length$h}
"@k"%64||v 64;v"@k";print"$b;"

Perl, 354 + 12 + 0 + -1 = 365 418 9521 51168 56639

Existe algum erro no meu código ou a segunda imagem é otimizada para um codificador específico, pois uma mudança aparentemente insignificante reduziu exatamente o tamanho da referência. Leva cerca de 30s-60s por imagem.

Versão Golfed.

#!perl -n0
sub r{$r.=1&"@_">>$_ for 0..log(@d|256)/log 2}
@k=/(\d+) (\d+)/;
@p=map{$$_||=(push(@t,split$"),++$i)}/\d+ \d+ \d+/g;
$_="@p ";$"='|';while(/./){
r 256;%d=map{($_,$_-1)}@d=1..256;
$d{$&}=@d+2,r$d{$1},unshift@d,$&while@d<4095&&s/^(@d) (\d*)/$2/}
r 257;$_=pack"b*",$r;
print+GIF89a,pack(vvCxxC768,@k,~8,@t),
pack("Cx4vvn(C/a)*",44,@k,8,/.{0,255}/gs),';'

A única decisão que um compressor GIF pode tomar é quando redefinir o dicionário LZW. Em geral, devido ao modo como as imagens para esta tarefa foram escolhidas, o melhor momento para fazer isso é cada código 4096, que é o momento em que o dicionário transborda. Com esse limite, o dicionário nunca transborda, o que economiza alguns bytes na implementação. É assim que funciona em detalhes:

#!perl -n0
# function to add one codeword to the output stream @r.
# the current codeword length is based on the dictionary size/
sub r{push@r,map"@_">>$_,0..log(@d|256)/log 2}
# get the dimensions into @k
@k=/(\d+) (\d+)/;
# get pixel indexes to @p and palette to @t
@p=map{$$_||=(push(@t,split$"),++$i)}/\d+ \d+ \d+/g;
# convert index table into space separated string 
$_="@p ";$"='|';
# LZW encoder; while something to encode
while(/\S/){
# output reset code
r 256;
# reset code dictionary $d is the last code number,
# %d is the map of codes and @d list of codes
$d=257;%d=map{($_,$_-1)}@d=1..256;
# find codes using regexp, stop at dictionary overflow
while($d<4096&&s/^(@d) (\d*)/$2/){
unshift@d,$&;$d{$&}=++$d;r$d{$1}}}
# end LZW encoder; output end code
r 257;
# convert bit string @r to bytes $f
vec($f,$j++,1)=$_ for@r;
# output header up to the color table
print+GIF89a,pack(vvCvC768,@k,~8,0,@t),
# output rest of the header
pack(Cv4CC,44,0,0,@k,0,8),
# output the LZW compressed data $f slicing into sub-blocks
$f=~s/.{0,255}/chr(length$&).$&/egsr,';'

Perl, 394 + -8 + 0 + -12 = 374

Adicionar uma heurística para adivinhar o ponto de redefinição melhora a compactação um pouco, mas não o suficiente para justificar o código extra:

#!perl -n0
sub r{$r.=1&"@_">>$_ for 0..log(@d|256)/log 2}
@k=/(\d+) (\d+)/;
@p=map{$$_||=(push(@t,split$"),++$i)}/\d+ \d+ \d+/g;
$_="@p ";$"='|';while(/./){
r 256;%d=map{($_,$_-1)}@d=1..256;
$d{$&}=@d+2,r$d{$1},unshift@d,$&while
(@d<4001||(/((@d) ){11}/,$&=~y/ //>12))&@d<4095&&s/^(@d) (\d*)/$2/}
r 257;$_=pack"b*",$r;
print+GIF89a,pack(vvCxxC768,@k,~8,@t),
pack("Cx4vvn(C/a)*",44,@k,8,/.{0,255}/gs),';'

CJam, pontuação 155 + 35306 + 44723 + 21518 = 101702

Apenas uma implementação de referência idiota. É lento, não faz nenhuma compressão real e não é um jogo de golfe.

"GIF89a":iS*SqN/S*S%1>:i3/:M0=2<256f{md\}S*:ZS247S0S0SM1>_|:PL*_,768\m0a*+S*S44S0S0S0S0SZS0S8SM1>Pf{\a#}254/256a*{512+2b1>W%}%:+8/{W%2b}%255/{_,S@S*S}/0S59