Tak, stary dobry GIF. Uwielbiany za swoją wszechstronność, nienawidzony za patenty i częściowo przestarzały ze względu na swoje ograniczenia (i patenty), GIF składa się zasadniczo z palety kolorów i obrazu indeksowanego paletą skompresowanego przy użyciu algorytmu LZW.

Twoim zadaniem jest napisanie programu, który odczytuje obraz w formacie ASCII PPM (magiczna liczba „P3”) ze standardowego wejścia i zapisuje ten sam obraz (identyczny piksel po pikselu) na standardowym wyjściu. Dane wyjściowe mogą mieć postać binarną lub tekst ASCII, przy czym każdy bajt jest reprezentowany przez liczbę od 0 do 255 (włącznie), oddzielone białymi spacjami.

Gwarantujemy, że obraz wejściowy nie będzie miał więcej niż 256 różnych kolorów.

Punktacja:

Twój program zostanie przetestowany na 3 przykładowych obrazach, a twój wynik zostanie obliczony jako:
rozmiar programu + suma (rozmiar wyjściowy - rozmiar odniesienia dla każdego przykładowego obrazu)
Wygrywa najniższy wynik.

Wymagania:

• Twój program musi działać z dowolnymi podobnymi obrazami o różnych rozmiarach i nie może być ograniczony do przykładowych obrazów. Można na przykład ograniczyć wymiary do wielokrotności 2 lub założyć, że maksymalny kolor na minutę to 255, ale nadal powinien działać z szeroką gamą obrazów wejściowych.
• Dane wyjściowe muszą być poprawnymi plikami GIF, które można załadować dowolnym zgodnym programem (po konwersji z powrotem na plik binarny, jeśli używana jest opcja wyjścia ASCII).
• Nie możesz używać żadnych funkcji przetwarzania obrazu (wbudowanych lub zewnętrznych), twój program musi zawierać cały odpowiedni kod.
• Twój program musi być uruchamialny w systemie Linux przy użyciu ogólnodostępnego oprogramowania.
• Kod źródłowy musi używać tylko znaków ASCII.

Przykładowe obrazy:

Oto 3 przykładowe obrazy, które zostaną wykorzystane do oceny. Możesz pobrać archiwum zip z plikami ppm (użyj przycisku pobierania na górze tej strony). Lub możesz przekonwertować je z poniższych obrazów png, używając ImageMagick za pomocą następującego polecenia:

convert file.png -compress none file.ppm

Podaję również sumy kontrolne MD5 plików ppm w celu potwierdzenia.

1. bursztyn

Rozmiar odniesienia: 38055
MD5 suma kontrolna ppm: d1ad863cb556869332074717eb278080

2. niebieskie oczy

Rozmiar odniesienia: 28638
MD5 suma kontrolna ppm: e9ad410057a5f6c25a22a534259dcf3a

3. papryka

Rozmiar odniesienia: 53586
MD5 suma kontrolna ppm: 74112dbdbb8b7de5216f9e24c2e1a627

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

Inne podejście. Tym razem próbuję zapisać obraz w kafelkach o rozmiarze 64xH. Jest to zgodne ze specyfikacjami, ale niektóre programy mogą wyświetlać tylko pierwszy kafelek lub animację. Płytki lepiej się kompresują ze względu na lepszą lokalizację przestrzenną. Nadal robię też normalną kompresję dla drugiego obrazu i wybieram to, co było krótsze. Ponieważ kompresuje to obraz dwukrotnie, jest dwa razy wolniejszy w porównaniu do mojego poprzedniego rozwiązania.

#!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

W moim kodzie jest jakiś błąd lub drugi obraz jest zoptymalizowany dla konkretnego kodera, ponieważ pozornie nieznaczna zmiana dokładnie zmniejszyła rozmiar do odwołania. Trwa około 30s-60s na zdjęcie.

Wersja golfowa.

#!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),';'

Jedyną decyzją, jaką może podjąć kompresor GIF, jest czas resetu słownika LZW. Zasadniczo ze względu na sposób wyboru obrazów dla tego zadania najlepszym momentem na wykonanie tego jest 4096 kodów, czyli moment, w którym słownik się przepełni. Przy takim limicie słownik nigdy się nie przepełnia, co oszczędza kilka bajtów w implementacji. Oto jak to działa szczegółowo:

#!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

Dodanie heurystyki w celu odgadnięcia punktu resetowania poprawia nieco kompresję, ale nie wystarcza, aby uzasadnić dodatkowy kod:

#!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, wynik 155 + 35306 + 44723 + 21518 = 101702

Tylko głupia implementacja odniesienia. Jest powolny, nie kompresuje się i nie gra w golfa.

"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