Quem quer ser um vencedor da complexidade de Kolmogorov?

22

Sua missão hoje é inventar um compressor de texto.

Tarefa

Você escreverá duas funções:

  • O empacotador é uma função que aceita uma sequência de caracteres ASCII (U + 0000 a U + 007F) e gera uma sequência Unicode (U + 0000 a U + 10FFFF), contendo o menor número possível de caracteres.

  • O desempacotador é uma função que aceita uma string Unicode codificada e gera exatamente a string ASCII original.

Entrada

A única entrada autorizada é a sequência ASCII (para o empacotador) e a sequência Unicode empacotada (para o desempacotador). Sem entrada do usuário, sem conexão à Internet, sem uso do sistema de arquivos.

Suas funções podem ter acesso a esta lista de palavras em inglês . Você pode usar essa lista como um arquivo txt local ou copiar seu conteúdo no código-fonte como uma sequência ou uma matriz de sequências .

Você não pode codificar os trechos abaixo em suas funções.

Saída

A única saída autorizada para ambas as funções é uma sequência.

A saída do desempacotador deve conter exatamente os mesmos caracteres que a entrada do empacotador.

Suas entradas e saídas podem usar qualquer codificação de caracteres compatível com todos os Unicode (UTF-8/16/32, GB18030, ...), pois sua pontuação dependerá apenas do número de caracteres Unicode na saída. Porém, por favor, precise qual codificação você está usando.

Para contar o número de caracteres Unicode na sua saída, você pode usar esta ferramenta: http://mothereff.in/byte-counter

Pontuação

Sua entrada deve ser capaz de compactar e descompactar os 10 trechos de texto a seguir (que tirei neste fórum).

Sua pontuação será a soma dos tamanhos de suas 10 cadeias compactadas (em caracteres Unicode) + o tamanho de suas duas funções (também em caracteres Unicode)

Não conte o tamanho do dicionário, se você o usar.

Inclua em suas entradas a "pontuação" de cada snippet e sua versão compactada.

Menor pontuação ganha.

Dados

Aqui estão os trechos a serem codificados para calcular sua pontuação:

1: Rick Roll (1870b): Não somos estranhos ao código do golfe, você conhece as regras, e eu também

Não somos estranhos para amar
Você conhece as regras e eu também
Um compromisso total é o que estou pensando
Você não conseguiria isso de nenhum outro cara
Eu só quero te dizer como estou me sentindo
Tenho que fazer você entender

Nunca vou desistir de você
Nunca vou te decepcionar
Nunca vou correr e te abandonar
Nunca vou fazer você chorar
Nunca vou me despedir
Nunca vou mentir e te machucar

Nos conhecemos há tanto tempo
Seu coração está doendo, mas
Você é muito tímido para dizer isso
Por dentro, nós dois sabemos o que está acontecendo
Conhecemos o jogo e vamos jogar
E se você me perguntar como estou me sentindo
Não me diga que você é cego demais para ver

Nunca vou desistir de você
Nunca vou te decepcionar
Nunca vou correr e te abandonar
Nunca vou fazer você chorar
Nunca vou me despedir
Nunca vou mentir e te machucar

Nunca vou desistir de você
Nunca vou te decepcionar
Nunca vou correr e te abandonar
Nunca vou fazer você chorar
Nunca vou me despedir
Nunca vou mentir e te machucar

(Ooh, desista de você)
(Ooh, desista de você)
(Ooh)
Nunca vou dar, nunca vou dar
(Desistir de TI)
(Ooh)
Nunca vou dar, nunca vou dar
(Desistir de TI)

Nos conhecemos há tanto tempo
Seu coração está doendo, mas
Você é muito tímido para dizer isso
Por dentro, nós dois sabemos o que está acontecendo
Conhecemos o jogo e vamos jogar

Eu só quero te dizer como estou me sentindo
Tenho que fazer você entender

Nunca vou desistir de você
Nunca vou te decepcionar
Nunca vou correr e te abandonar
Nunca vou fazer você chorar
Nunca vou me despedir
Nunca vou mentir e te machucar

Nunca vou desistir de você
Nunca vou te decepcionar
Nunca vou correr e te abandonar
Nunca vou fazer você chorar
Nunca vou me despedir
Nunca vou mentir e te machucar

Nunca vou desistir de você
Nunca vou te decepcionar
Nunca vou correr e te abandonar
Nunca vou fazer você chorar
Nunca vou me despedir
Nunca vou mentir e te machucar

2: O Jogador de Golfe (412b): Golfe-ASCII-art

      '\. . 18 >>
        \. ' |
       O >>. 'o |
        \. |
        / \. |
       / /. ' |
 jgs ^^^^^^^ `^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^

3: o número de diamantes (233b): imprima este diamante

        1
       121
      12321
     1234321
    123454321
   12345654321
  1234567654321
 123456787654321
12345678987654321
 123456787654321
  1234567654321
   12345654321
    123454321
     1234321
      12321
       121
        1

4: o alfabeto quatro vezes (107b): imprime o alfabeto quatro vezes

a B C D e F G H I J K L M N o p q R S T U V W x y Z
qwertyuiopasdfghjklzxcvbnm
pyfgcrlaoeuidhtnsqjkxbmwvz
zyxwvutsrqponmlkjihgfedcba

5: Letra de Old McDonald's (203b): Função Old MacDonald

O velho MacDonald tinha uma fazenda, EIEIO,
E naquela fazenda ele tinha uma vaca, EIEIO,
Com um moo moo aqui e um moo moo lá,
Aqui um moo, há um moo, em todo lugar um moo moo,
O velho MacDonald tinha uma fazenda, EIEIO!

6: Rock ao redor do relógio lyrics (144b): Rock ao redor do relógio

1, 2, 3 horas, 4 horas rock,
5, 6, 7 horas, rocha das 8 horas,
9, 10, 11 horas, rock das 12 horas,
Hoje vamos agitar o dia todo.

7: Olá Mundo (296b): Diga "Olá" ao mundo na arte ASCII

 _ _ _ _ _ _ _
| | | | ___ | | ___ __ _____ _ __ | | __ | |
| | _ | | / _ \ | | / _ \ \ \ / \ / / _ \ | '__ | / _` | |
| _ __ / | | (_) \ VV / (_) | | | (_ | | _ |
| _ | | _ | \ ___ | _ | _ | \ ___ () \ _ / \ _ / \ ___ / | _ | | _ | \ __, _ (_)
                    | /

8: Bênção irlandesa (210b): Uma antiga bênção irlandesa

Que a estrada suba ao seu encontro
Que o vento esteja sempre em suas costas
Que o sol brilhe quente em seu rosto
As chuvas caem suavemente sobre seus campos
E até nos encontrarmos novamente
Que Deus te segure na cavidade de Sua mão

9: Havia uma velha senhora (1208b): Havia uma velha senhora

Havia uma velha senhora que engoliu uma mosca.  
Eu não sei por que ela engoliu aquela mosca,  
Talvez ela morra.

Havia uma velha senhora que engoliu uma aranha,  
Isso se contorceu e se mexeu dentro dela.  
Ela engoliu a aranha para pegar a mosca,  
Eu não sei por que ela engoliu aquela mosca,  
Talvez ela morra.

Havia uma velha senhora que engoliu um pássaro,  
Que absurdo engolir um pássaro.  
Ela engoliu o pássaro para pegar a aranha,  
Ela engoliu a aranha para pegar a mosca,  
Eu não sei por que ela engoliu aquela mosca,  
Talvez ela morra.

Havia uma velha senhora que engoliu um gato,  
Imagine isso para engolir um gato.  
Ela engoliu o gato para pegar o pássaro,  
Ela engoliu o pássaro para pegar a aranha,  
Ela engoliu a aranha para pegar a mosca,  
Eu não sei por que ela engoliu aquela mosca,  
Talvez ela morra.

Havia uma velha senhora que engoliu um cachorro,  
Que porco engolir um cachorro.  
Ela engoliu o cachorro para pegar o gato,  
Ela engoliu o gato para pegar o pássaro,  
Ela engoliu o pássaro para pegar a aranha,  
Ela engoliu a aranha para pegar a mosca,  
Eu não sei por que ela engoliu aquela mosca,  
Talvez ela morra.

Havia uma velha senhora que engoliu um cavalo,  
Ela morreu, é claro.

10: endereço de gettysburg (1452b): quão aleatório é o endereço de gettysburg

Há quatro anos e sete anos atrás, nossos pais criaram neste continente uma nova nação, concebida em liberdade, e dedicada à proposição de que todos os homens são criados iguais. Agora estamos envolvidos em uma grande guerra civil, testando se essa nação, ou qualquer nação tão concebida e tão dedicada, pode durar muito tempo. Nós somos encontrados em um grande campo de batalha daquela guerra. Viemos para dedicar uma parte desse campo, como um local de descanso final para aqueles que aqui deram suas vidas para que aquela nação pudesse viver. É totalmente apropriado e apropriado que façamos isso. Mas, em um sentido mais amplo, não podemos dedicar, não podemos consagrar, não podemos santificar esse terreno. Os homens valentes, vivos e mortos, que lutaram aqui, a consagraram, muito acima do nosso pobre poder de acrescentar ou prejudicar. O mundo notará pouco, nem lembrará por muito tempo o que dizemos aqui, mas nunca pode esquecer o que eles fizeram aqui. É para nós que os vivos devem ser dedicados aqui ao trabalho inacabado que os que lutaram aqui até agora avançaram tão nobremente. É melhor que estejamos aqui dedicados à grande tarefa que nos resta - que, dentre esses mortos honrados, recebamos uma crescente devoção àquela causa pela qual eles deram a última medida completa de devoção - que aqui resolvemos com veemência que esses mortos não morreram em vão - que esta nação, sob Deus, terá um novo nascimento da liberdade - e que o governo do povo, pelo povo, pelo povo, não pereça da terra.

Total (não compactado): 6135 caracteres / bytes.

Diverta-se!

xem
fonte
7
Não é um desafio inventar uma linguagem, é um desafio para comprimir alguma coisa.
23714 Justin
2
Acho que não incluir o tamanho do compilador / executor (compressor / descompressor) na partitura torna esse desafio um pouco aberto. Em algum momento, a linha entre o dicionário e a codificação será muito fina.
Dennis
2
Darn, e aqui eu já estava escrevendo private static final String RICK_ROLL_RETURN = "We're no strangers to love...
Graph Theory
1
Não acho que você tenha abordado a observação de Dennis.
Peter Taylor
1
@ xem Acho que o post pode ser melhorado organizando as informações em seções como # Tarefa, # Entrada, # Saída, # Classificação. Também acho que o tamanho do código-fonte do compressor e do descompressor deve ser incluído na pontuação. Isso não fere nada, mas resolve o problema apontado por Dennis.
Rainbolt

Respostas:

6

Haskell - 5322 pontos

Bytes de código: 686

Tamanho original : 6147 = 1871+415+234+108+204+145+297+211+1209+1453

Tamanho codificado: 4636 = 1396+233+163+92+153+115+197+164+979+1144

Ponto : 686+ 4636

Compactação de caracteres: ~25%

Código

Otimizações à parte, isso armazena valores entre 0e 7fem caracteres unicode como seus principais fatores.

Não diminui o número de bytes da saída codificada, apenas reduz o número de caracteres unicode. Por exemplo, o teste nº 4 contém 108caracteres e a saída codificada 92,. Seus respectivos tamanhos são, no entanto, 108e 364bytes.

import Data.Bits
import Data.List
import Data.Numbers.Primes
import qualified Data.Text as T
a=nub$concat$map(primeFactors)[0..127]
d(a:r)c=let s=shift c 5in if s<=0x10ffffthen d r(s+a)else c:d r a
d[]c=[c]
f(a:r)=let o=a.&.0x1fin(if o/=a then f((shiftR a 5):r)else f r)++[o]
f[]=[]
g=T.pack.map(toEnum).(\(a:r)->d r a).concatMap j.map(map(\x->head$elemIndices x a)).map(primeFactors.fromEnum).T.unpack
h=T.pack.map(toEnum.product.map((!!)a)).i.f.reverse.map(fromEnum).T.unpack
i(a:r)=let z=a`clearBit`4;x=if a`testBit`4then(take z$repeat$head r,tail r)else splitAt z r in[fst x]++i(snd x)
i[]=[]
j x@(a:_)=let l=length x in if(take l(repeat a))==x then[l`setBit`4,a]else[l]++x
j[]=[0]

Como funciona

  • Codificação

    1. Cada caractere é convertido em seu equivalente numérico, vamos chamar esse número n.
    2. né então convertido em uma lista de seus principais fatores ps,.
      • Por conveniência, os números de 0 a 127 têm 32 fatores primos comuns, excluindo 1. Isso significa que eles, os fatores, podem ser armazenados como índices em apenas 5 bits.
      • 1 é um caso especial e é representado por uma lista vazia.
    3. Com psa codificação agora pode começar.
      1. Cada número de psé convertido em seu índice na lista de 32 fatores exclusivos (no código acima, esta lista é identificada como a).
      2. (Lembre-se de que neste momento estamos lidando com uma lista de índices de fatores primos). Para prosseguir para a próxima etapa, é psnecessário achatar. Para preservar a integridade dos dados, cada lista é convertida em outra lista de duas partes
        1. O primeiro elemento armazena seu comprimento e se ele é composto do mesmo fator.
          • Existem no máximo 6 fatores principais por lista, essas informações são armazenadas nos 3 bits mais à direita. O quinto bit é usado como sinalizador para indicar se a lista é composta por um único fator.
        2. Os elementos restantes são os próprios índices ou um único índice, se houver menos de dois fatores diferentes na lista.
      3. Essas listas são concatenadas em uma única lista nivelada fs.
    4. Os elementos de fspodem então ser compactados em caracteres unicode usando deslocamento de bits.
  • Decodificação

    • Execute as etapas de codificação ao contrário.
    • Se você está se perguntando como isso 1se encaixa, eu gostaria de lembrá-lo disso product [] == 1.

Testes

Usar essa interface para teste seria doloroso, então usei essa função para fornecer os resultados abaixo.

edTest f = do
    t <- readFile f
    let txt = T.pack t
        enc = g txt
        dec = h enc
        tst = txt == dec
    putStrLn $ (show $ T.length txt) ++ "," ++ (show $ T.length enc) ++ "," ++ (show $ T.length dec)++","++(show tst)
    putStrLn $ if not tst then T.unpack txt ++ "\n---NEXT---\n" ++ T.unpack dec else ""


λ> edTest "1"
1871,1396,1871,True

λ> edTest "2"
412,233,412,True

λ> edTest "3"
234,163,234,True

λ> edTest "4"
108,92,108,True

λ> edTest "5"
204,153,204,True

λ> edTest "6"
145,115,145,True

λ> edTest "7"
297,197,297,True

λ> edTest "8"
211,164,211,True

λ> edTest "9"
1209,979,1209,True

λ> edTest "10"
1453,1144,1453,True

Amostra

A saída da função de codificação gpara o teste nº 4 é essa
"\99429\582753\135266\70785\35953\855074\247652\1082563\68738\49724\164898\68157\99429\67973\1082404\587873\73795\298017\330818\198705\69861\1082435\595009\607426\36414\69873\855074\265249\346275\67779\68738\77985\1082513\821353\132131\101410\247652\1082562\49724\164898\67649\594977\34915\67746\50273\135265\103997\563265\103457\1086021\99399\584802\70753\73889\34882\582722\411459\67779\68740\1084516\1082563\1091681\103491\313282\49724\164897\68705\135741\69858\50241\607426\35905\608421\1082435\69858\50274\71777\43075\298018\280517\1082404\67971\36017\955425\67665\919600\100452\132129\214883\35057\856097\101474\70753\135737"
ou, se você é adepto de rabiscos, isso
𘑥򎑡𡁢𑒁豱󐰢𼝤􈓃𐲂숼𨐢𐨽𘑥𐦅􈐤򏡡𒁃񈰡񐱂𰠱𑃥􈑃򑑁򔓂踾𑃱󐰢񀰡񔢣𐣃𐲂𓂡􈒑󈡩𠐣𘰢𼝤􈓂숼𨐢𐡁򑐡衣𐢢쑡𡁡𙘽򉡁𙐡􉉅𘑇򎱢𑑡𒂡衂򎑂񤝃𐣃𐲄􈱤􈓃􊡡𙑃񌟂숼𨐡𐱡𡈽𑃢쑁򔓂豁򔢥􈑃𑃢쑢𑡡ꡃ񈰢񄟅􈐤𐦃貱󩐡𐡑󠠰𘡤𠐡𴝣裱󑀡𘱢𑑡𡈹

Notas adicionais

  • Usando http://mothereff.in/byte-counter , as listagens de diretórios e edTesto tamanho dos testes são consistentes, mas ainda diferem do tamanho indicado na pergunta.
  • O teste nº 10 contém alguns EM DASHes ( ) com os quais substituí, -pois estão fora do 0-7f gama.
  • Uma compactação adicional pode ser obtida usando o quarto bit restante, enquanto achatar, por exemplo, 00caso base, 01repetir tudo, 10repetir exceto por último,11 repete exceto os dois últimos.
  • Os arquivos de teste e o código estão todos disponíveis aqui https://github.com/gxtaillon/codegolf/tree/master/Kolmogorov
gxtaillon
fonte
Olá, obrigado por esta resposta! :) Eu não entendi o que acontece no binário quando você converte abcdefghijklm...para 𘑥򎑡𡁢𑒁豱󐰢𼝤..., poderia explicar um pouco mais, por favor? Além disso, corrigi as contagens de caracteres e converti os hífens no número 10, na pergunta. Minhas contagens de caracteres ainda são diferentes das suas. Não sei porque, usei a ferramenta mothereff.in.
xem
@xem Os detalhes intrincados foram revelados.
Gxtaillon
Minha mente é (figurativamente) literalmente soprada pela idéia de que os números 0 e 2-127 podem ser codificados em 5 bits. Você encontrou isso sozinho ou foi algo conhecido? Pergunta de bônus: quantos bits você precisa para armazenar apenas os caracteres ascii imprimíveis, ou seja, 95 caracteres diferentes?
xem
@xem Os números não são codificados em 5 bits, cada um de seus fatores. Eu ficaria muito feliz se tivesse encontrado uma maneira de codificar 7 bits em apenas 5. Quanto aos caracteres ascii, usando esse método, eles ainda precisariam de 5 bits cada.
Gxtaillon
1
Como no intervalo especificado, existem no máximo 6 fatores por número, o comprimento usa 3 de um "bloco" de 5 bits. Em seguida, os índices são codificados em 5 bits, sim. Nesta implementação, um dos 2 bits não utilizados no bloco de comprimento é usado para obter compactação adicional.
Gxtaillon
4

C ++ (C ++ 11), 2741 pontos

Esta resposta usa UTF-32 como a codificação para o texto compactado.

#include <cstdio>
#include <iostream>
#include <locale>
#include <string>
#define L locale
using namespace std;long b,n,i,l;void c(){string d;char x;while((x=cin.get())!=EOF)d+=x;b=(d.size()*7)%20;n=5;wcout.imbue(L());for(char y:d){b=b<<7|y&127;n+=7;if(n>=20)wcout.put(b>>(n-=20)&0xFFFFF);}if(n)wcout.put(b<<20-n&0xFFFFF);}void d(){wstring d;wchar_t w;wcin.imbue(L());while((w=wcin.get())!=EOF)d+=w;l=-1;for(wchar_t y:d){b=b<<20|y;n+=20;if(l<0)l=b>>15&31,n-=5;while(n>=7&(i<d.size()-1|n>20-l))cout.put(b>>(n-=7)&127);++i;}}int main(int t,char**a){L::global(L("en_US.utf8"));**++a<'d'?c():d();}

Contagens e pontuação de caracteres

Código: 593 chars (a nova linha à direita é removida)

Textos compactados (caracteres unicode) : 654 + 145 + 82 + 38 + 51 + 104 + 73 + 423 + 506 = 2148 (contados com wc -mo número de caracteres unicode em vez de bytes, a contagem de bytes é igual à resposta de @ gxtaillon , superior aos originais, 8413 bytes no total, contados comwc -c ).

Taxa de compactação (ASCII para unicode) : 35,01% (usando os 6135 bytes da pergunta (o mesmo quewc -c ))

Cuidado:

Muitos shells não conseguem lidar com os caracteres unicode que este programa produz. Portanto, a descompactação pode levar o texto a ser cortado em algum lugar quando o shell não puder manipular um caractere, pois a entrada é obtida viastdin do shell.

Compilando

Ele deve ser compilado com clang++e g++ -std=c++11, mas mostrará alguns avisos sobre a precedência do operador, pois uma expressão como b<<20-n&0xFFFFFnão será tratada como ((b << 20) - n) & 0xFFFFF, como seria de esperar, mas sim como(b << (20 - n)) & 0xFFFFF .

Uso

  • Compile o programa em um executável, por exemplo ./compress .
  • Execute o programa ./compress cpara compactar ou ./compress ddescompactar. (Cuidado, deixar de fora a opção fornece SEGFAULT (a verificação de erros é tão cara quanto os caracteres ...) e outras opções (como usar em Dvez ded ) podem gerar resultados inesperados
  • A entrada é lida stdine a saída gravada emstdout

Como funciona

Ungolfed

#include <cstdio>
#include <iostream>
#include <locale>
#include <string>

using namespace std;

long b, n, i, l;

// Compress
void c() {
    string d;
    char x;
    // Read from STDIN until EOF
    while((x = cin.get()) != EOF)
        d += x;
    // Calculate the number of bits used from the last unicode character
    // (maximum 19) and store it into the first 5 bits
    b = (d.size() * 7) % 20;
    n = 5;
    // Set the output locale to allow unicode
    wcout.imbue(locale());
    // For each character in the input...
    for (char y : d) {
        // Add its bit representation (7 bits) to the right of the buffer
        // by shifting the buffer left and ORing with the character code
        b = (b << 7) | (y & 127);
        // Add 7 to the bit counter
        n += 7;
        // If enough data is present (20 bits per output character),
        // calculate the output character by shifting the buffer right,
        // so that the last 20 bits are the left 20 bits of the buffer.
        // Also decrement the bit counter by 20, as 20 bits are removed.
        if (n >= 20)
            wcout.put((b >> (n -= 20)) & 0xFFFFF);
    }
    // If there are still bits in the buffer, write them to the front of
    // another unicode character
    if (n)
        wcout.put((b << (20 - n)) & 0xFFFFF);
}

// Decompress
void d() {
    wstring d;
    wchar_t w;
    // Set STDIN to UNICODE
    wcin.imbue(locale());
    // Read wide characters from STDIN (std::wcin) until EOF
    while ((w = wcin.get()) != EOF)
        d += w;
    // `l' represents the number of bits used in the last unicode character.
    // It will be set later
    l = -1;
    // For each input character...
    for (wchar_t y : d) {
        // Add it to the buffer and add 20 to the bit counter
        b = (b << 20) | y;
        n += 20;
        // If the number of bits in the last unicode character has not been
        // set yet, read the first 5 buffer bits into `l'. This is
        // necessary because the last character may contain more than 7
        // (one entire uncompressed character) unused bits which may
        // otherwise be interpreted as garbage.
        if (l < 0) {
            l = (b >> 15) & 31;
            n -= 5;
        }
        // As long as there is data to turn into output characters
        // (at least 7 bits in the buffer and either not the last
        // unicode character or before the unused bits)
        while (n >= 7 && ((i < d.size() - 1) || (n > (20 - l)))
            cout.put((b >> (n -= 7)) & 127); // Output the left 7 bits in the buffer as an ASCII character
        ++i; // Increment the character index, so that we know when we reach the last input character
    }
}
int main(int t, char**a) {
    // Set the default locale to en_US.utf8 (with unicode)
    locale::global(locale("en_US.utf8"));
    // Decide whether to compress or decompress.
    // This is just fancy pointer stuff for a[1][0] < 'd' ? c() : d()
    (**(++a) < 'd') ? c() : d();
}

Explicação

Como todos os caracteres unicode de U+0000a U+10FFFFsão permitidos, podemos usar 20 bits por caractere unicode:U+FFFFF usa 20 bits e ainda está incluído no intervalo permitido. Assim, apenas tentamos agrupar todos os bits de caracteres ASCII individuais nos caracteres unicode para armazenar vários caracteres ASCII em um caractere unicode. No entanto, também precisamos armazenar o número de bits usados ​​no último caractere unicode, pois os bits de lixo não utilizados podem ser interpretados como caracteres ASCII compactados adequados. Como o número máximo de bits usados ​​no último caractere unicode é 20, precisaremos de 5 bits, que são colocados no início dos dados compactados.

Saída de exemplo

Esta é a saída, por exemplo, no 4 (conforme fornecido por less):

<U+4E1C5><U+8F265><U+CD9F4><U+69D5A><U+F66DD><U+DBF87><U+1E5CF><U+A75ED>
<U+DFC79><U+F42B8><U+F7CBC><U+BA79E><U+BA77F>쏏𦛏<U+A356B><U+D9EBC><U+63ED8>
<U+B76D1><U+5C3CE><U+6CF8F><U+96CC3><U+BF2F5><U+D3934><U+74DDC><U+F8EAD>
<U+7E316><U+DEFDB><U+D0AF5><U+E7C77><U+EDD7A><U+73E5C><U+786FD><U+DB766>
<U+BD5A7><U+467CD><U+97263><U+C5840>

( 쏏𦛏<U+C3CF><U+266CF>como códigos de caracteres, mas eu posso ter entendido errado)

hlt
fonte
2

Python 3, 289 + 818 = 1107 pontos

Apenas levemente golfe.

import zlib as Z
def p(s):
 z=int.from_bytes(Z.compress(s),'big');o=''
 while z:
  z,d=divmod(z,1<<20)
  if d>0xd000:d+=1<<16
  o+=chr(d)
 return o[::-1]
def u(s):
 i=0
 for c in s:
  d=ord(c)
  if d>0xe000:d-=1<<16
  i=(i<<20)+d
 return Z.decompress(i.to_bytes(i.bit_length()//8+1,'big'))

O tamanho total do código é 289 bytes e codifica os 6135 bytes em 818 caracteres Unicode - a contagem total de bytes de saída é de 3201 bytes, significativamente menor que as entradas originais.

Codifica usando zlib e, secundariamente, usando codificação unicode. Alguma lógica extra foi necessária para evitar substitutos (que o Python realmente odeia).

Exemplo de saída do # 4, como visto por less(37 caracteres Unicode):

x<U+AC0DC><U+BB701><U+D0200><U+D00B0><U+AD2F4><U+EEFC5>𤆺<U+F4F34>멍<U+3C63A><U+2F62C><U+BA5B6><U+4E70A><U+F7D88><U+FF138><U+40CAE>
<U+CB43E><U+C30F5><U+6FFEF>𥠝<U+698BE><U+9D73A><U+95199><U+BD941><U+10B55E><U+88889><U+75A1F><U+4C4BB><U+5C67A><U+1089A3><U+C75A7>
<U+38AC1><U+4B6BB><U+592F0>ᚋ<U+F2C9B>

Programa de driver para teste:

if __name__ == '__main__':
    import os
    total = 0
    for i in range(1,10+1):
        out = p(open('data/%d.txt'%i,'rb').read())
        total += len(out)
        open('out/%d.bin'%i,'w',encoding='utf8').write(out)
    print(total)
    for i in range(1,10+1):
        out = u(open('out/%d.bin'%i,'r',encoding='utf8').read())
        open('data2/%d.txt'%i,'wb').write(out)

Contagem de bytes de saída:

 607 out/1.bin
 128 out/2.bin
 101 out/3.bin
 143 out/4.bin
 177 out/5.bin
 145 out/6.bin
 186 out/7.bin
 222 out/8.bin
 389 out/9.bin
1103 out/10.bin
3201 total
nneonneo
fonte
1
Não é verdade que isso está usando uma biblioteca de compactação enganando um pouco?
Decay Beta
@BetaDecay: Isso não restringe a questão, então achei que era um jogo justo.
Nneonneo 1/11
Além disso, você precisa incluir um descompactador.
Beta Decay
@BetaDecay: pé o empacotador, ué o desempacotador.
Neyonneo 04/11
1

Python 2-1141 pontos

from zlib import *;v=256
def e(b):
 x=0
 for c in compress(b,9):x=(x*v)+ord(c)
 b=bin(x)[2:]
 return "".join(unichr(int("1"+b[a:a+19],2))for a in range(0,len(b),19))
def d(s):
 y=int("".join(bin(ord(a))[3:]for a in s),2);x=""
 while y:y,d=(y/v,chr(y%v));x=d+x
 return decompress(x)

O tamanho do código é 281bytes e codifica os 6135bytes em 860caracteres unicode.

Como funciona:

Para codificar:

  1. Comprima a sequência a ser codificada.
  2. Interprete a sequência compactada como um número 256 base.
  3. Converta o número em binário.
  4. Divida o binário em grupos de 19bits, adicione um 1pouco ao início de cada um deles e converta em caracteres Unicode.

Decodificação é o inverso.

Observe que algumas versões do python podem lidar apenas com caracteres unicode até e 0xFFFF, portanto, esse código aumentará a ValueError.

pppery
fonte