É possível compactar alguns tipos de dados, como texto humano ou código fonte, com gramáticas lineares. Você basicamente cria uma gramática cujo idioma possui exatamente uma palavra - os dados não compactados. Nesta tarefa, você precisa escrever um programa que implemente esse método de compaixão de dados.
Entrada
A entrada é uma cadeia de caracteres com comprimento não superior a 65535 bytes. É garantido que a entrada corresponda à expressão regular [!-~]+
(ou seja, pelo menos um caractere ASCII imprimível, excluindo espaços em branco).
Um exemplo de entrada é
abcabcbcbcabcacacabcabab
Resultado
A saída é um conjunto de regras que formam uma gramática que descreve exatamente uma palavra (a entrada). Cada não-terminal é indicado por um número decimal maior que 9. O símbolo inicial é o número dez. Um exemplo de saída correspondente à entrada de exemplo é dado abaixo; sua sintaxe é descrita mais abaixo:
10=11 11 12 12 11 13 13 11 14 14
11=a 12
12=b c
13=a c
14=a b
Cada regra tem o formato <nonterminal>=<symbol> <symbol> ...
com um número arbitrário de símbolos separados por espaços em branco no lado direito. Cada saída que obedece às seguintes restrições e deriva exatamente a sequência de entrada é válida.
Restrições
Para impedir que as pessoas façam coisas estranhas, várias restrições estão ocorrendo:
Cada não-terminal deve aparecer pelo menos duas vezes no lado direito de uma regra. Por exemplo, a seguinte gramática para a entrada
abcabc
é ilegal porque a regra 12 aparece apenas uma vez:10=12 11=a b c 12=11 11
Nenhuma sequência de dois símbolos adjacentes pode aparecer mais de uma vez no lado direito de todas as regras, exceto se elas se sobrepuserem. Por exemplo, a seguinte gramática para a entrada
abcabcbc
é ilegal, pois a sequênciabc
aparece duas vezes:10=11 11 b c 11=a b c
Uma gramática válida seria:
10=11 11 12 11=a 12 12=b c
Seu programa deve terminar em menos de um minuto para cada entrada válida que não exceda 65535 bytes.
Como de costume, você não pode usar nenhum recurso do seu idioma ou qualquer função de biblioteca que torne a solução trivial ou implemente grande parte dela.
Entrada de amostra
Gere entrada de amostra com o seguinte programa C.
#include <stdlib.h>
#include <stdio.h>
int main(int argc, char **argv) {
unsigned int i,j = 0,k;
if (argc != 3
|| 2 != sscanf(argv[1],"%u",&i)
+ sscanf(argv[2],"%u",&k)) {
fprintf(stderr,"Usage: %s seed length\n",argv[0]);
return EXIT_FAILURE;
}
srand(i);
while(j < k) {
i = rand() & 0x7f;
if (i > 34 && i != 127) j++, putchar(i);
}
return EXIT_SUCCESS;
}
A entrada de amostra gerada pelo programa acima geralmente não resultará em bons resultados de compactação. Considere usar texto humano ou código-fonte como exemplo de entrada.
Critérios de vitória
Isso é código de golfe; o programa com o menor código fonte vence. Para crédito extra, escreva um programa que reconstrua a entrada da saída.
fonte
Respostas:
GolfScript,
111108 caracteresEssa é uma abordagem bastante desajeitada usando o GolfScript. A segunda versão tem um desempenho muito melhor que a inicial. É muito mais longo que o código pretendido, mas minha implementação aninhava do-loops e isso causava problemas com o intérprete.
Exemplos:
fonte
Retraído - o algoritmo não pode lidar com todos os casos.
C, 422 (corrigido para remover dups na saída e caracteres eliminados)Implementação inicial, começará a jogar.
Como as regras não exigem que ele realmente comprima essa abordagem ingênua de força bruta, isso servirá ...
Pode processar 65535 de comprimento em 10 segundos
Exemplo de execução:
fonte