Desafio

Escreva um programa que comprima e descompacte o texto ASCII sem perdas. Deve ser especializado para funcionar bem com palíndromos, incluindo palíndromos que não diferenciam maiúsculas de minúsculas e que não pontuam pontuação. A melhor compactação com a menor fonte ganha.

Pontuação

total_bytes_saved / sqrt(program_size) - Maior pontuação ganha

total_bytes_savedé quantos bytes menores as seqüências compactadas são do que os originais, total nos casos de teste abaixo. program_sizeé o tamanho em bytes do código-fonte dos programas de compactação e descompactação. O código compartilhado entre os dois precisa ser contado apenas uma vez.

Por exemplo, se houver 10 casos de teste e um programa de 100 bytes salvou 5 bytes em 7 casos de teste, 10 cada em 2 deles, mas o último caso de teste tiver 2 bytes mais, a solução terá 5,3. ( (7 * 5 + 10 * 2 - 2) / sqrt(100) = 5.3)

Casos de teste

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

Regras

1. Aplicam-se brechas padrão.
2. A compactação deve funcionar em todas as seqüências de texto imprimíveis ASCII (bytes 32-126, inclusive), não apenas nos palíndromos. Na verdade, ele não precisa economizar espaço para nenhuma entrada.
3. A saída pode ser qualquer sequência de bytes ou caracteres, independentemente de sua implementação ou representação interna (seqüências de caracteres, listas e matrizes são jogos justos, por exemplo). Se estiver codificando para UTF-8, conte bytes, não caracteres. Cadeias de caracteres largas (por exemplo, UTF-16 ou UTF-32) não são permitidas, a menos que os únicos pontos de código possivelmente usados ​​estejam entre 0 e 255.
4. Os componentes de compactação / descompactação não são permitidos.

Para nosso próprio prazer, publique as strings compactadas com seu código-fonte.

ATUALIZAÇÃO 1: A pontuação mudou de total_bytes_saved / program_sizepara total_bytes_saved / sqrt(program_size)para dar mais peso à melhor compressão e menos peso ao golfe agressivo. Ajuste sua pontuação de acordo.

ATUALIZAÇÃO 2: corrigida wasitacaroraratisaw?para serwasitacaroracatisaw?

JavaScript (ES6), 3.143 (81 bytes salvos, 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)}

Agora que estou bastante satisfeito com este programa (e o sistema de pontuação), vou escrever uma explicação.

A idéia básica é compactar a entrada em uma sequência de bits e, em seguida, compactar cada conjunto de 8 bits em um byte. Para fins de explicação, manipularei a string de bits.

A cadeia de bits pode ser separada em várias seções:

input  -> Taco Cat.
output -> 0101000000100011011111110100001100100011101011100000000

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

O cabeçalho é um mapeamento muito simples:

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

Os dados das cartas também são bastante simples. Primeiro, todas as não letras são extraídas da sequência e todas as letras são convertidas em maiúsculas. Se a sequência resultante for um palíndromo, a metade invertida será removida. Então esse mapeamento é aplicado:

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

Esta seção termina com 111. Depois disso, vêm os dados de estilo, que armazenam dados em maiúsculas / minúsculas e sem letras. Isso funciona assim:

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

Então, seguindo o exemplo mostrado acima, temos

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

Quando o final da sequência de bits é atingido, todos os caracteres restantes dos dados da letra são anexados ao resultado. Isso nos impede de ter que fazer uma última000...001 e nos permite truncar esses bits da string.

Passando pelos casos de teste:

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

Mudei de abordagem um pouco. Agora funciona bem em palíndromos imperfeitos. Não há seqüências de caracteres compactadas que serão mais longas que a entrada. Palíndromos perfeitos de comprimento uniforme sempre comprimirão 50% do tamanho 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)

E como bônus, ele salva 6 bytes no meu palíndromo incorreto que eu tinha antes.

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

Explicação

A descompressão usa uma pilha. Os pontos de código de 32 a 127 são tratados literalmente. Se um caractere é uma letra, um valor também é enviado para a pilha. Os valores 128-192 são usados ​​para letras com maiúsculas e minúsculas; portanto, a letra com maiúsculas e minúsculas (o^32 por causa de como o ASCII é organizado) é empurrada para a pilha e a letra normal é adicionada à sequência. Os valores 192-255 são usados ​​para adicionar letras sem empurrar para a pilha; portanto, isso é usado quando as letras não correspondem e para a letra do meio em palíndromos de comprimento ímpar. Os pontos de código 1 a 15 indicam que a pilha deve ser exibida esse número de vezes. Os pontos de código 17 a 31 são semelhantes, mas primeiro imprimem um espaço antes de sair da pilha. Há também uma instrução implícita "pop até vazia" no final de uma entrada.

O compressor trabalha nas extremidades e dobras em letras correspondentes como valores de 1 a 31. Ele pula sobre não letras. Quando as letras correspondem, mas o caso não corresponde, adiciona 64 à letra esquerda e incrementa a letra direita. Isso permite economizar espaço IManAmRegalAGermanAmI. No meio ou quando as letras não coincidem, ele representa 128 para os dois lados. Não posso adicionar lá porque preciso evitar o caso especial em queleft == right . Ao dobrar marcadores pop vizinhos no lado direito, tenho que verificar se o vizinho não transbordará para o codepoint 16, porque preciso disso para espaços. (Na verdade, isso não é um problema para nenhuma das sequências de casos de teste)

EDIT 1 : Não há mais versão não destruída.

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

Apenas codificação de entropia simples com igual probabilidade de ordem 0. Não há otimizações específicas do 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, pontuação: 1.355 (20 bytes salvos / 218 (107 + 111) bytes)

Função Compactar (contém três caracteres ASCII não imprimíveis):

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

Função descomprimir (contém dois caracteres ASCII não imprimíveis):

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

Explicação:

Experimente online.

Comprime apenas palíndromos perfeitos.

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