Wyzwanie

Napisz program, który bezstratnie kompresuje i dekompresuje tekst ASCII. Powinien specjalizować się w pracy z palindromami, w tym palindromami bez rozróżniania wielkości liter i interpunkcji. Najlepsza kompresja z najmniejszym źródłem wygrywa.

Punktacja

total_bytes_saved / sqrt(program_size) - Najwyższy wynik wygrywa

total_bytes_savedjest liczbą bajtów mniejszych skompresowanych ciągów niż oryginałów, łącznie w poniższych przypadkach testowych. program_sizeto rozmiar w bajtach kodu źródłowego programów kompresujących i dekompresujących. Kod dzielony między nimi musi być policzony tylko raz.

Na przykład, jeśli istnieje 10 przypadków testowych, a program 100-bajtowy zapisał 5 bajtów na 7 przypadków testowych, po 10 na 2 z nich, ale ostatni przypadek testowy był o 2 bajty dłuższy, rozwiązanie uzyskałoby wynik 5,3. ( (7 * 5 + 10 * 2 - 2) / sqrt(100) = 5.3)

Przypadki testowe

• tacocat
• toohottohoot
• todderasesareddot
• amanaplanacanalpanama
• wasitacaroracatisaw?
• Bob
• IManAmRegalAGermanAmI
• DogeeseseeGod
• A Santa at NASA
• Go hang a salami! I'm a lasagna hog.

Zasady

1. Obowiązują standardowe luki.
2. Kompresja musi działać na wszystkich drukowanych ciągach tekstowych ASCII (bajty 32-126 włącznie), a nie tylko na palindromach. Jednak tak naprawdę nie musi oszczędzać miejsca na żadne dane wejściowe.
3. Wyjściem może być dowolna sekwencja bajtów lub znaków, niezależnie od ich implementacji lub wewnętrznej reprezentacji (ciągi, listy i tablice są na przykład fair game). Jeśli kodujesz do UTF-8, licz bajty, a nie znaki. Szerokie ciągi znaków (np. UTF-16 lub UTF-32) są niedozwolone, chyba że jedynymi możliwymi zastosowanymi punktami kodowymi są między 0 a 255.
4. Wbudowane kompresje / dekompresje są niedozwolone.

Ze względu na naszą przyjemność publikuj skompresowane ciągi wraz z kodem źródłowym.

AKTUALIZACJA 1: Punktacja została zmieniona z total_bytes_saved / program_sizena total_bytes_saved / sqrt(program_size), aby zwiększyć wagę do lepszej kompresji, a mniej do agresywnego golfa. Dostosuj odpowiednio swoje wyniki.

AKTUALIZACJA 2: ustalona wasitacaroraratisaw?nawasitacaroracatisaw?

JavaScript (ES6), 3.143 (81 bajtów zapisanych, program 664 bajtów)

R='replace',S=String.fromCharCode,T=c=>c.charCodeAt(),U='toUpperCase',V='0000000',W=(a,b,c=2)=>a.toString(c).slice(b),X=x=>'0b'+x,Y=a=>[...a].reverse().join``,Z=/[^]/g
C=s=>S(...((Y(q=s[U]()[R](/[^A-Z]/g,m=''))==q?(q=q.slice(0,p=-~q.length/2),p%1&&10):11)+q[R](Z,x=>W(T(x),2))+111+s[R](Z,c=>/[a-z]/.test(c)?W("00",m,m=1):m+(/[A-Z]/.test(c,m='')?"01":W(c<'!'?2:T(c)+384)))+V).match(/(?!0+$).{8}/g).map(X))
D=s=>{s=s[R](Z,c=>W(256+T(c),1))+V;M=r=>(s=s[R](p=s.match(`^${r}|`)[0],''),p);for([,a]=M`1.|0`,t=u=i='';!M`111`;)t+=W(X(M`.{5}`)-~8,0,36);for(t+=W(Y(t),a?a/0:1);p;)u+=M`0(?=00)|00?1`?(c=t[i++])?+p[1]?c[U]():c:'':M`10`?' ':M`11`&&S(X(M`.{7}`));return u+W(t,i)}

Teraz, gdy jestem dość zadowolony z tego programu (i systemu oceniania), napiszę trochę wyjaśnienia.

Podstawową ideą jest skompresowanie danych wejściowych w ciąg bitów, a następnie skompresowanie każdego zestawu 8 bitów w bajt. Dla celów wyjaśnienia po prostu manipuluję ciągiem bitów.

Ciąg bitów można podzielić na kilka sekcji:

input  -> Taco Cat.
output -> 0101000000100011011111110100001100100011101011100000000

0      | 10100 00001 00011 01111 111 | 01 00001 10 01 0001 110101110
header | letter data                 | styling data

Nagłówek jest bardzo prostym odwzorowaniem:

0  -> odd-length palindrome
10 -> even-length palindrome
11 -> non-palindrome

Dane listowe są również dość proste. Po pierwsze, wszystkie nie-litery są wydobywane z ciągu, a wszystkie litery są konwertowane na wielkie litery. Jeśli powstały ciąg jest palindromem, odwrócona połowa jest usuwana. Następnie stosuje się to mapowanie:

A -> 00001
B -> 00010
C -> 00011
D -> 00100
...
Z -> 11010

Ta sekcja jest zakończona 111. Potem przychodzą dane dotyczące stylizacji, w których przechowywane są duże / małe litery i nie-litery. Działa to tak:

01 -> next letter as uppercase
0...01 (n 0s) -> next (n-1) letters as lowercase
10 -> space
11xxxxxxx -> character with code point 0bxxxxxxx

Przechodząc przez powyższy przykład, mamy

header: 0 -> palindrome
letter data: 10100 00001 00011 01111 111 -> taco
styling data:
  01        -> T
  00001     -> aco
  10        -> <space>
  01        -> C
  0001      -> at
  110101110 -> .

Po osiągnięciu końca ciągu bitowego wszystkie pozostałe znaki z danych literowych są dołączane do wyniku. To oszczędza nam konieczności wykonywania ostatniego 000...001i pozwala nam skrócić te bity z łańcucha.

Przeglądając przypadki testowe:

tacocat -> 3 bytes (-4)
    24 bits: 010100000010001101111111
toohottohoot -> 5 bytes (-7)
    35 bits: 10101000111101111010000111110100111
todderasesareddot -> 7 bytes (-10)
    49 bits: 0101000111100100001000010110010000011001100101111
amanaplanacanalpanama -> 8 bytes (-13)
    59 bits: 00000101101000010111000001100000110000001011100000100011111
wasitacaroracatisaw? -> 11 bytes (-9)
    84 bits: 010111000011001101001101000000100011000011001001111111000000000000000000001110111111
Bob -> 2 bytes (-1)
    16 bits: 0000100111111101
IManAmRegalAGermanAmI -> 13 bytes (-8)
    98 bits: 00100101101000010111000001011011001000101001110000101100111010100010100101000001010100000010100101
DogeeseseeGod -> 7 bytes (-6)
    54 bits: 000100011110011100101001011001100101111010000000000101
A Santa at NASA -> 8 bytes (-7)
    63 bits: 100000110011000010111010100000011110110010000011000011001010101
Go hang a salami! I'm a lasagna hog. -> 20 bytes (-16)
   154 bits: 1000111011110100000001011100011100001100110000101100000010110101001111010011000000110001100000000111010000110011101001110011000110000000001100000111010111

Python 2: 2.765 (zapisano 70 bajtów, program 641 bajtów)

Trochę zmieniłem swoje podejście. Teraz działa dobrze na niedoskonałych palindromach. Nie ma skompresowanych ciągów, które będą dłuższe niż wejście. Idealne palindromy o równej długości zawsze będą kompresować do 50% oryginalnego rozmiaru.

A=lambda x:chr(x).isalpha()
def c(s):
 r=bytearray(s);q=len(r);L=0;R=q-1;v=lambda:R+1<q and r[R+1]<15
 while L<=R:
  while not A(r[L])and L<R:L+=1
  while not A(r[R])and R:
   if v()and r[R]==32:r[R]=16+r.pop(R+1)
   R-=1
  j=r[L];k=r[R]
  if A(j)*A(k):
   if L!=R and j&31==k&31:
    r[L]+=(j!=k)*64;r[R]=1
    if v():r[R]+=r.pop(R+1)
   else:r[L]|=128;r[R]|=128
  L+=1;R-=1
 while r[-1]<16:r.pop()
 return r
def d(s):
 r='';t=[]
 for o in s:
  if 15<o<32:r+=' ';o-=16
  while 0<o<16:r+=chr(t.pop());o-=1
  if o==0:continue
  if 127<o<192:o-=64;t+=[o^32]
  elif o>192:o-=128
  elif A(o):t+=[o]
  r+=chr(o)
 while t:r+=chr(t.pop())
 return r

Wyniki

'tacocat' <==> 'tac\xef'
4/7 (3 bytes saved)
'toohottohoot' <==> 'toohot'
6/12 (6 bytes saved)
'todderasesareddot' <==> 'todderas\xe5'
9/17 (8 bytes saved)
'amanaplanacanalpanama' <==> 'amanaplana\xe3'
11/21 (10 bytes saved)
'wasitacaroracatisaw?' <==> 'wasita\xe3ar\xef\x09?'
12/20 (8 bytes saved)
'Bob' <==> '\x82\xef'
2/3 (1 bytes saved)
'IManAmRegalAGermanAmI' <==> 'I\x8d\xa1n\x81m\x92e\xa7\xa1\xec'
11/21 (10 bytes saved)
'Dogeeseseegod' <==> '\x84ogees\xe5'
7/13 (6 bytes saved)
'A Santa at NASA' <==> 'A S\xa1\xaeta\x12\x14'
9/15 (6 bytes saved)
"Go hang a salami! I'm a lasagna hog." <==> "\x87o hang a salam\xa9!\x11'\x01\x11\x17\x13."
24/36 (12 bytes saved)

Jako bonus oszczędza 6 bajtów mojego niewłaściwego palindromu, który miałem wcześniej.

'wasita\xe3ar\xef\x02\xf2\x06?' <==> 'wasitacaroraratisaw?'
6 bytes saved

Wyjaśnienie

Dekompresja używa stosu. Punkty kodowe od 32-127 są traktowane dosłownie. Jeśli znak jest literą, wartość jest również wypychana na stos. Wartości 128–192 są używane dla liter z odwróconą wielkością liter, więc litera z odwróconą wielkością liter (o^32 ze względu ASCII) jest wypychana na stos, a normalna litera jest dodawana do łańcucha. Wartości 192-255 są używane do dodawania liter bez pchania na stos, więc jest to stosowane, gdy litery nie pasują, a dla środkowej litery w palindromach o nieparzystej długości. Punkty kodowe 1-15 wskazują, że stos powinien zostać wyskakujący tyle razy. Punkty kodowe 17–31 są podobne, ale drukują najpierw spację, zanim wyskoczą ze stosu. Na końcu wejścia znajduje się również domyślna instrukcja „pop aż pusta”.

Kompresor działa z obu końców i składa się w pasujące litery o wartościach 1-31. Pomija znaki inne niż litery. Gdy litery się zgadzają, ale nie ma to miejsca, dodaje 64 do lewej litery i zwiększa prawą literę. Pozwala to zaoszczędzić miejsceIManAmRegalAGermanAmI . Na środku lub gdy litery się nie zgadzają, to po obu stronach 128. Nie mogę tam dodać, ponieważ muszę unikać specjalnego przypadku, w którym left == right. Składając sąsiednie znaczniki pop po prawej stronie, muszę sprawdzić, czy sąsiedni nie przepełni się w punkcie kodowym 16, ponieważ potrzebuję tego dla spacji. (W rzeczywistości nie stanowi to problemu dla żadnego z ciągów przypadków testowych)

EDYCJA 1 : Nigdy więcej wersji bez golfa.

Python3, 1.833 (zapisane 25 bajtów, program 186 bajtów)

Po prostu proste kodowanie entropijne równego prawdopodobieństwa 0 rzędu. Brak optymalizacji specyficznych dla palindromu.

def C(s):
    u=0
    for c in s:u=u*96+ord(c)-31
    return u.to_bytes((u.bit_length()+7)//8,'big')
def D(a):
    u,s=int.from_bytes(a,'big'),''
    while u:s,u=s+chr((u%96)+31),u//96
    return s[::-1]

Java 8, wynik: 1,355 (20 bajtów zapisanych / 218 (107 + 111) bajtów)

Funkcja kompresji (zawiera trzy niedrukowalne znaki ASCII):

s->{int l=s.length();return s.contains(new StringBuffer(s).reverse())?s.substring(l/2)+(l%2<1?"":""):s;}

Funkcja dekompresji (zawiera dwa niedrukowalne znaki ASCII):

s->{return s.contains("")?new StringBuffer((s=s.replaceAll("","")).substring(s.length()&1^1)).reverse()+s:s;}

Wyjaśnienie:

Wypróbuj online.

Kompresuje tylko idealne palindromy.

s->{                      // Method with String as both parameter and return-type
  int l=s.length();       //  Get the length of the input
  return s.contains(new StringBuffer(s).reverse())?
                          //  If the input is a palindrome:
    s.substring(l/2)      //   Only return the second halve of the String
    +(l%2<1?"":"")        //   + either one (if even) or two (if odd) unprintables 
   :                      //  Else:
    s;}                   //   Simply return the input again

s->{                      // Method with String as both parameter and return-type
  return s.contains("")?  //  If the input contains an unprintable:
    new StringBuffer((s=s.replaceAll("",""))
                          //   Remove the unprintables
                     .substring(s.length()&1^1))
                          //   And take either the full string (if even),
                          //   or minus the first character (if odd)
    .reverse()            //    And reverse that part
    +s                    //   And append the rest of the input (minus the unprintables)
   :                      //  Else:
    s;}                   //   Simply return the input again