Desafío

Escriba un programa que comprima y descomprima el texto ASCII sin pérdidas. Debe estar especializado para trabajar bien con palíndromos, incluidos los palíndromos que no distinguen entre mayúsculas y minúsculas y signos de puntuación. La mejor compresión con la fuente más pequeña gana.

Puntuación

total_bytes_saved / sqrt(program_size) - Mayor puntaje gana

total_bytes_savedes cuántos bytes son más pequeñas las cadenas comprimidas que los originales, total en los casos de prueba a continuación. program_sizees el tamaño en bytes del código fuente de los programas de compresión y descompresión. El código compartido entre los dos solo debe contarse una vez.

Por ejemplo, si hay 10 casos de prueba y un programa de 100 bytes guardó 5 bytes en 7 casos de prueba, 10 cada uno en 2 de ellos, pero el último caso de prueba fue 2 bytes más largo, la solución obtendría 5,3. ( (7 * 5 + 10 * 2 - 2) / sqrt(100) = 5.3)

Casos de prueba

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

Reglas

1. Se aplican lagunas estándar.
2. La compresión debe funcionar en todas las cadenas de texto ASCII imprimibles (bytes 32-126, inclusive), no solo palíndromos. Sin embargo, en realidad no tiene que ahorrar espacio para ninguna entrada.
3. La salida puede ser cualquier secuencia de bytes o caracteres, independientemente de su implementación o representación interna (las cadenas, las listas y las matrices son juegos justos, por ejemplo). Si codifica para UTF-8, cuente bytes, no caracteres. Las cadenas anchas (por ejemplo, UTF-16 o UTF-32) no están permitidas a menos que los únicos puntos de código posiblemente utilizados estén entre 0 y 255.
4. La compresión / descompresión incorporada no está permitida.

En aras de nuestro propio disfrute, publique las cadenas comprimidas con su código fuente.

ACTUALIZACIÓN 1: La puntuación cambió de total_bytes_saved / program_sizea total_bytes_saved / sqrt(program_size)para dar más peso a una mejor compresión y menos peso al golf agresivo. Ajuste sus puntajes en consecuencia.

ACTUALIZACIÓN 2: arreglado wasitacaroraratisaw?para serwasitacaroracatisaw?

JavaScript (ES6), 3.143 (81 bytes guardados, programa de 664 bytes)

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

Ahora que estoy bastante satisfecho con este programa (y el sistema de puntuación), escribiré un poco de explicación.

La idea básica es comprimir la entrada en una cadena de bits, luego comprimir cada conjunto de 8 bits en un byte. Para fines de explicación, simplemente manipularé la cadena de bits.

La cadena de bits se puede separar en varias secciones:

input  -> Taco Cat.
output -> 0101000000100011011111110100001100100011101011100000000

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

El encabezado es un mapeo muy simple:

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

Los datos de las cartas también son bastante simples. Primero, todas las no letras se extraen de la cadena y todas las letras se convierten a mayúsculas. Si la cuerda resultante es un palíndromo, la mitad invertida se despoja. Luego se aplica esta asignación:

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

Esta sección se termina con 111. Después de eso vienen los datos de estilo, que almacenan datos en mayúsculas / minúsculas y no letras. Esto funciona así:

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

Entonces, siguiendo el ejemplo que se muestra arriba, tenemos

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

Cuando se alcanza el final de la cadena de bits, todos los caracteres restantes de los datos de la letra se agregan al resultado. Esto nos ahorra tener que hacer un último 000...001y nos permite truncar estos bits de la cadena.

Pasando por los casos de prueba:

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 bytes guardados, programa de 641 bytes)

Cambié mi enfoque un poco. Ahora funciona bien en palíndromos imperfectos. No hay cadenas comprimidas que sean más largas que la entrada. Los palíndromos perfectos de longitud uniforme siempre se comprimirán al 50% del tamaño original.

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

Resultados

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

Y como beneficio adicional, ahorra 6 bytes en mi palíndromo incorrecto que tenía antes.

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

Explicación

La descompresión usa una pila. Los puntos de código del 32 al 127 se tratan literalmente. Si un carácter es una letra, también se inserta un valor en la pila. Los valores 128-192 se usan para letras mayúsculas y minúsculas, por lo que la letra mayúscula ( o^32debido a cómo se presenta ASCII) se inserta en la pila y la letra normal se agrega a la cadena. Los valores 192-255 se usan para agregar letras sin empujar a la pila, por lo que esto se usa cuando las letras no coinciden y para la letra del medio en palíndromos de longitud impar. Los puntos de código 1-15 indican que la pila debería aparecer esa cantidad de veces. Los puntos de código 17-31 son similares, pero imprimen un espacio primero antes de aparecer en la pila. También hay una instrucción implícita de "pop hasta vacío" al final de una entrada.

El compresor funciona desde ambos extremos y se pliega en letras coincidentes como valores 1-31. Se salta sobre las no letras. Cuando las letras coinciden pero el caso no, agrega 64 a la letra izquierda e incrementa la letra derecha. Esto le permite ahorrar espacio IManAmRegalAGermanAmI. En el medio o cuando las letras no coinciden, son 128 a ambos lados. No puedo agregar allí porque necesito evitar el caso especial donde left == right. Al plegar los marcadores pop vecinos en el lado derecho, tengo que verificar que el vecino no se desborde en el punto de código 16 porque lo necesito para los espacios. (Esto no es realmente un problema para ninguna de las cadenas de casos de prueba)

EDITAR 1 : No más versiones sin golf.

Python3, 1.833 (25 bytes guardados, programa de 186 bytes)

Simplemente codificación de entropía de igual probabilidad de orden 0. Sin optimizaciones específicas de palíndromo.

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, puntuación: 1.355 (20 bytes guardados / 218 (107 + 111) bytes)

Función de compresión (contiene tres caracteres ASCII no imprimibles):

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

Función de descompresión (contiene dos caracteres ASCII no imprimibles):

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

Explicación:

Pruébalo en línea.

Solo comprime palíndromos perfectos.

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