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!
private static final String RICK_ROLL_RETURN = "We're no strangers to love...
Respostas:
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
0
e7f
em 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
108
caracteres e a saída codificada92
,. Seus respectivos tamanhos são, no entanto,108
e364
bytes.Como funciona
Codificação
n
.n
é então convertido em uma lista de seus principais fatoresps
,.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.ps
a codificação agora pode começar.ps
é convertido em seu índice na lista de 32 fatores exclusivos (no código acima, esta lista é identificada comoa
).ps
necessário achatar. Para preservar a integridade dos dados, cada lista é convertida em outra lista de duas partesfs
.fs
podem então ser compactados em caracteres unicode usando deslocamento de bits.Decodificação
1
se encaixa, eu gostaria de lembrá-lo dissoproduct [] == 1
.Testes
Usar essa interface para teste seria doloroso, então usei essa função para fornecer os resultados abaixo.
Amostra
A saída da função de codificação
g
para 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
edTest
o tamanho dos testes são consistentes, mas ainda diferem do tamanho indicado na pergunta.—
) com os quais substituí,-
pois estão fora do0
-7f
gama.00
caso base,01
repetir tudo,10
repetir exceto por último,11
repete exceto os dois últimos.fonte
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.C ++ (C ++ 11), 2741 pontos
Esta resposta usa UTF-32 como a codificação para o texto compactado.
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 -m
o 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 que
wc -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 via
stdin
do shell.Compilando
Ele deve ser compilado com
clang++
eg++ -std=c++11
, mas mostrará alguns avisos sobre a precedência do operador, pois uma expressão comob<<20-n&0xFFFFF
não será tratada como((b << 20) - n) & 0xFFFFF
, como seria de esperar, mas sim como(b << (20 - n)) & 0xFFFFF
.Uso
./compress
../compress c
para compactar ou./compress d
descompactar. (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 emD
vez ded
) podem gerar resultados inesperadosstdin
e a saída gravada emstdout
Como funciona
Ungolfed
Explicação
Como todos os caracteres unicode de
U+0000
aU+10FFFF
sã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
):(
쏏𦛏
dê<U+C3CF><U+266CF>
como códigos de caracteres, mas eu posso ter entendido errado)fonte
Python 3, 289 + 818 = 1107 pontos
Apenas levemente golfe.
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):Programa de driver para teste:
Contagem de bytes de saída:
fonte
p
é o empacotador,u
é o desempacotador.Python 2-1141 pontos
O tamanho do código é
281
bytes e codifica os6135
bytes em860
caracteres unicode.Como funciona:
Para codificar:
19
bits, adicione um1
pouco 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á aValueError
.fonte