Tantangan

Tulis program yang mengkompres dan mendekompresi teks ASCII tanpa kehilangan. Ini harus dikhususkan untuk bekerja dengan baik dengan palindrom, termasuk palindrom yang tidak peka huruf besar dan kecil. Kompresi terbaik dengan sumber terkecil menang.

Mencetak gol

total_bytes_saved / sqrt(program_size) - Kemenangan skor tertinggi

total_bytes_savedadalah berapa banyak byte lebih kecil dari string yang dikompresi daripada aslinya, total di seluruh test case di bawah ini. program_sizeadalah ukuran dalam byte kode sumber dari kedua program kompresi dan dekompresi. Kode yang dibagikan di antara keduanya hanya perlu dihitung satu kali.

Misalnya, jika ada 10 kasus uji dan program 100 byte menyelamatkan 5 byte pada 7 kasus uji, masing-masing 10 dari 2 kasus, tetapi kasus uji terakhir 2 byte lebih lama, solusinya akan mencetak 5,3. ( (7 * 5 + 10 * 2 - 2) / sqrt(100) = 5.3)

Uji Kasus

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

Aturan

1. Celah standar berlaku.
2. Kompresi harus bekerja pada semua string teks ASCII (byte 32-126, inklusif) yang dapat dicetak, bukan hanya palindrom. Namun sebenarnya tidak perlu menghemat ruang untuk input apa pun.
3. Output dapat berupa urutan byte atau karakter, terlepas dari implementasinya atau representasi internal (string, daftar, dan array adalah semua permainan yang adil, misalnya). Jika penyandian ke UTF-8, hitung byte, bukan karakter. String lebar (mis. UTF-16 atau UTF-32) tidak diizinkan kecuali jika satu-satunya codepoint yang mungkin digunakan adalah antara 0 dan 255.
4. Kompresi / dekompresi bawaan tidak diizinkan.

Demi kesenangan kita sendiri, posting string terkompresi dengan kode sumber Anda.

UPDATE 1: Skor berubah dari total_bytes_saved / program_sizemenjadi total_bytes_saved / sqrt(program_size)untuk memberi lebih banyak bobot untuk kompresi yang lebih baik dan lebih sedikit berat untuk golf agresif. Sesuaikan skor Anda sesuai.

UPDATE 2: diperbaiki wasitacaroraratisaw?menjadiwasitacaroracatisaw?

JavaScript (ES6), 3,143 (81 byte disimpan, 664 byte program)

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)}

Sekarang saya cukup puas dengan program ini (dan sistem penilaian), saya akan menulis sedikit penjelasan.

Ide dasarnya adalah untuk mengompresi input ke dalam string bit, kemudian kompres setiap set 8 bit menjadi byte. Untuk keperluan penjelasan, saya hanya akan memanipulasi string bit.

String bit dapat dipisahkan menjadi beberapa bagian:

input  -> Taco Cat.
output -> 0101000000100011011111110100001100100011101011100000000

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

Header adalah pemetaan yang sangat sederhana:

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

Data surat juga cukup sederhana. Pertama, semua non-huruf diekstraksi dari string, dan semua huruf dikonversi menjadi huruf besar. Jika string yang dihasilkan adalah palindrom, bagian yang dibalik dilucuti. Kemudian pemetaan ini diterapkan:

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

Bagian ini diakhiri dengan 111. Setelah itu muncul data styling, yang menyimpan data huruf besar / kecil dan non-huruf. Ini berfungsi seperti ini:

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

Jadi melalui contoh yang ditunjukkan di atas, kami punya

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

Ketika akhir string bit tercapai, semua karakter yang tersisa dari data huruf ditambahkan ke hasilnya. Ini menyelamatkan kita dari keharusan melakukan yang terakhir 000...001dan memungkinkan kita untuk memotong bit-bit ini dari string.

Mengalami kasus uji:

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 (70 byte disimpan, program 641 byte)

Saya mengubah pendekatan saya sedikit. Sekarang bekerja dengan baik pada palindrom yang tidak sempurna. Tidak ada string terkompresi yang akan lebih panjang dari input. Palindrom panjang rata yang sempurna akan selalu kompres hingga 50% dari ukuran aslinya.

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

Hasil

'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)

Dan sebagai bonus, menghemat 6 byte pada palindrome yang salah yang saya miliki sebelumnya.

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

Penjelasan

Dekompresi menggunakan stack. Codepoints dari 32-127 diperlakukan secara harfiah. Jika karakter adalah huruf, nilai didorong ke tumpukan juga. Nilai 128-192 digunakan untuk huruf terbalik, sehingga huruf terbalik ( o^32karena bagaimana ASCII diletakkan) akan didorong ke tumpukan dan huruf normal akan ditambahkan ke string. Nilai 192-255 digunakan untuk menambahkan huruf tanpa mendorong ke tumpukan, jadi ini digunakan ketika huruf tidak cocok dan untuk huruf tengah dalam palindrom panjang aneh. Codepoints 1-15 menunjukkan bahwa tumpukan harus muncul beberapa kali. Codepoints 17-31 serupa, tetapi mereka mencetak spasi terlebih dahulu sebelum muncul dari tumpukan. Ada juga instruksi "pop hingga kosong" implisit di akhir input.

Kompresor bekerja dari kedua ujung dan lipatan dalam huruf yang cocok sebagai nilai 1-31. Itu melompati non-huruf. Ketika huruf cocok tetapi kasingnya tidak, itu menambahkan 64 ke huruf kiri dan menambah huruf kanan. Ini memungkinkannya menghemat ruang IManAmRegalAGermanAmI. Di bagian tengah atau ketika huruf-hurufnya tidak cocok, huruf itu berada di kedua sisi. Saya tidak dapat menambahkan di sana karena saya perlu menghindari kasus khusus di mana left == right. Ketika melipat spidol tetangga di sisi kanan, saya harus memeriksa bahwa spanduk tetangga tidak akan meluap ke codepoint 16 karena saya membutuhkannya untuk spasi. (Ini sebenarnya bukan masalah bagi string kasus uji apa pun)

EDIT 1 : Tidak ada lagi versi ungolfed.

Python3, 1,833 (25 byte disimpan, program 186 byte)

Pengodean entropi probabilitas-sama dengan probabilitas-0 yang sederhana. Tidak ada optimasi spesifik palindrome.

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, skor: 1,355 (20 byte disimpan / 218 (107 + 111) byte)

Fungsi kompres (berisi tiga karakter ASCII yang tidak dapat dicetak):

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

Fungsi dekompresi (berisi dua karakter ASCII yang tidak dapat dicetak):

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

Penjelasan:

Cobalah online.

Hanya kompres palindrom yang sempurna.

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