fundo

Neste site, ocasionalmente temos perguntas que exigem que os programas sejam "reforçados por radiação"; isso significa que o programa precisa sobreviver à exclusão de um ou mais bytes, independentemente de quais bytes sejam excluídos.

Como é comum em tarefas que frequentemente são definidas em desafios de programação, é natural querer criar uma linguagem que seja particularmente boa nesses desafios. Dado que a maneira natural de fazer isso é adicionar alguns metadados que possibilitam reverter a corrupção, na verdade não é realmente uma linguagem que precise ser projetada, mas uma codificação; a idéia é transformar cada entrada em uma sequência de bytes, de maneira que, mesmo que a sequência seja ligeiramente irradiada, é possível extrair a entrada original.

A tarefa

Escreva dois programas ou funções, E (um codificador) e D (um decodificador), de modo que:

• E pega dois argumentos, uma sequência de octetos (que chamaremos de " entrada " nesta especificação) e um número inteiro não negativo " radiação " e gera uma sequência de octetos " codificando ";
• D pega um argumento, uma sequência de octetos (" encdng ") e gera uma reconstrução de uma sequência de octetos " ";
• Se você executar E e D (com encdng , a entrada para D, escolhida pela exclusão de não mais do que elementos de radiação da codificação (não necessariamente contíguo)), a reconstrução será igual à entrada, independentemente de quais caracteres foram excluídos para formar a encdng .

Esclarecimentos

• Se você enviar funções, não precisará chamá-las EeD ; você pode escolher o nome mais adequado ao seu idioma.
• Um "octeto" é basicamente um número inteiro de 0 a 255, inclusive, que você pode codificar como um número inteiro, um caractere ou o que for apropriado para o seu idioma.
• E e D devem ser inteiramente determinísticos (ou seja, fornecer as mesmas entradas sempre produzirá a mesma saída, onde "entradas" é definida como entrada e radiação para E, ou codificação para D). Em particular, E pode não comunicar informações a D através de um canal lateral.
• As exclusões são realizadas excluindo um elemento da sequência; pense em abrir a sua sequência em um editor, colocando o cursor em um ponto arbitrário e pressionando Backspace. Se um elemento aparecer várias vezes, é possível que apenas uma cópia do elemento seja excluída (ou seja, outras instâncias do mesmo octeto não serão afetadas).
• Embora a pontuação é calculada apenas com base em relativamente curto de entrada , seu programa deve funcionar na teoria para qualquer entrada e radiação . Em particular, ele deve funcionar, independentemente de quais octetos apareçam na entrada . (Desculpe, as pessoas que gostariam de usar caracteres não imprimíveis que eles conhecem não aparecerão na entrada, mas preciso garantir que a entrada seja incompressível para que o desafio seja o fortalecimento da radiação e não a compactação.)
• Você pode enviar um arquivo que define duas funções; dois arquivos que definem uma função ou que são programas completos; ou três arquivos, dois dos quais implementam D e E, respectivamente (por serem programas completos ou pela definição de uma função) e o terceiro é um arquivo de cabeçalho ou biblioteca comum a D e E. Independentemente de qual forma de envio você usar , sua implementação da linguagem de programação deve ser capaz de entender os dois programas sem argumentos adicionais, como localizações de arquivo (ou você deve pagar uma multa de bytes por invocar sua implementação de maneira incomum, conforme nossas regras padrão).

Condição de vitória

Para cada comprimento e radiação , seja f ( comprimento , radiação ) os comprimentos totais das s de codificação que correspondem a todas as entradas com comprimento de comprimento e a radiação fornecida . (Ou seja, f ( comprimento , radiação ) = soma _{entrada tem comprimento comprimento} comprimento (E ( entrada , radiação )).) Então deixe g ( comprimento , radiação ) igual f ( radiação comprimento , ) ÷ 256 ^comprimento . Em outras palavras, g é o comprimento médio da saída codificada, para um determinado comprimento de entrada e um determinado requisito de proteção contra radiação. (Em teoria, você pode calcular isso por força bruta, mas provavelmente levaria um tempo implausível para calcular sua pontuação dessa maneira. Espero que a maioria dos envios seja capaz de fazer um argumento matemático sobre qual é a pontuação deles. não tenha certeza, publique uma pontuação aproximada e você ou outra pessoa poderá calculá-la com mais profundidade se outra entrada postar uma pontuação semelhante.)

Sua pontuação é igual à soma de g ( comprimento , radiação ) para toda a radiação no intervalo de 0 a 9 inclusive, e todo o comprimento no intervalo de 0 a 99 inclusive, mais (principalmente para evitar codificação incorreta ou para manter a concorrência se alguém descobre uma codificação matematicamente perfeita; isso provavelmente será um fator mínimo, caso contrário) o número total de bytes em sua submissão ao desafio (além das penalidades padrão para coisas como exigir sinalizadores de intérpretes incomuns ou nomes de arquivos específicos). O vencedor é a entrada com a menor pontuação (empatada pela primeira entrada a enviar).

CJam, escore ≤ 286.516 + 54 + 36 = 286.606

Codificador

{_{1\+_:e>)_0a+@@b0\{{)_256b_,\e`,-}g}*256b+\)e*}{*}?}

Experimente online!

Decodificador

{_{e`1f=(\256b{256b_,\e`,=},,\b1>}&}

Experimente online!

Ambos pegam e retornam números inteiros de uma lista. Os links TIO incluem a conversão de / para seqüências de caracteres por conveniência. Observe que eles são incrivelmente ineficientes para cadeias mais longas. Se você quiser tentar mais alguns caracteres, recomendo usar caracteres com códigos de caracteres pequenos.

A idéia básica para criar uma codificação reforçada por radiação envolve duas etapas:

1. Encontre uma codificação que nunca contenha dois octetos idênticos consecutivos.
2. Repita cada octeto na sequência codificada r + 1 vezes, em que r é o nível de radiação.

Dessa forma, a radiação não pode excluir completamente uma execução de caracteres idênticos, para que possamos decodificar a sequência, pegando um caractere de cada execução e decodificando a etapa 1.

Portanto, a única parte interessante é encontrar uma codificação que nunca produz octetos repetidos. A idéia básica é usar algo como A043096 como um sistema numérico. Ou seja, para codificar um número N , simplesmente contamos em alguma base b , pulando todos os números com octetos repetidos. Acredito que a quantidade de números que podem ser representados dessa maneira com até d dígitos é igual à quantidade de números que podem ser representados na base bijetiva b-1 (já que, quando você deseja escrever esse número, pode escolha entre b-1 dígito para cada posição sem violar a restrição).

Obviamente, para obter a compressão máxima, usaremos b = 256 . Para transformar a entrada em um número inteiro, também podemos usar a conversão de base. Se eu não fosse preguiçoso, usaria uma base bijetiva para a entrada, mas por enquanto estou apenas acrescentando a 1(para garantir que não haja zeros à esquerda) e, em seguida, use a menor base possível, de modo que todos os octetos no entrada é menor que a base.

Essa base é então anexada à codificação (para que o decodificador saiba qual base usar) e separada do número restante por um octeto 0 (isso funciona porque o número restante nunca começará com zero). Como uma otimização menor, a cadeia vazia permanece uma cadeia vazia.

A razão pela qual não calculei uma pontuação exata acima é que estou computando apenas um limite superior por quanto tempo cada entrada será baseada em seu comprimento e seu octeto máximo. No entanto, para esses dois parâmetros, geralmente haverá dois comprimentos de saída diferentes, e ainda não me incomodei em descobrir onde ocorre o ponto de inflexão entre eles. Eu também usei o comprimento da base usual 255 em vez da base bijetiva 255 para estimar esse comprimento, que é novamente um pouco maior do que precisa. O código exato do Mathematica que usei para o cálculo é o seguinte:

num[l_, 1] = 0;
num[l_, base_] := num[l, base] = base^l - Sum[num[l, b], {b, base - 1}]
Sum[
  num[l, b]*(r + 1)*(2 + IntegerLength[2*b^l - 1, 255])/256^l, 
  {r, 0, 9}, {l, 1, 99}, {b, 2, 256}
]
N@%

num[l, b]deve fornecer o número de cadeias de comprimento lcom octeto máximo b-1(exceto b == 1onde eu o codifiquei 0porque estou sempre usando pelo menos a base 2).

utilitários bash + GNU, pontuação 294506 283468

Edit 1: Corrige um problema que o @Leo notou - obrigado!

Edit 2: Melhorado o método de codificação para o parâmetro de radiação, para uma melhor pontuação.

Codificador (97 bytes):

for((j=0;j<$1;j++)){ p+=p\;;}
(sed 's/\(.\)\1/\1a\1a/g'<<<$1;cat)|xxd -p -c1|sed ${p-;}|xxd -r -p

Decodificador (121 bytes):

read n
n=`sed 's/\(.\)\1*/\1/g'<<<$n`
sed -r "s/( ..)\1{0,${n//a}}/\1/g"<<<' 0a '`xxd -p -c1`|sed 's/^ [^ ]*//'|xxd -r -p

Para o codificador: sequência de octetos passada como caracteres em stdin, o parâmetro de radiação r passou como argumento.

Para o decodificador: Entrada passada como caracteres em stdin.

Para ambos: Saída em stdout.

O codificador anexa aos dados de entrada os dígitos de r, com um caractere 'a' inserido entre cada par de dígitos idênticos consecutivos, seguido por uma única nova linha. Em seguida, copia toda a entrada (começando pelos caracteres anexados), substituindo cada caractere por r + 1 cópias desse caractere.

O decodificador desfaz isso, passando por cada um dos caracteres restantes x em sua entrada, pulando até r cópias idênticas consecutivas de x após x e imprimindo o que resta. Os dados anexados não possuem caracteres repetidos, portanto, podem ser decodificados antes que r seja conhecido. Nesse ponto, r é conhecido e esse valor é necessário para decodificar o restante dos dados corretamente.

Você pode verificar se isso funciona mesmo que a entrada original tenha repetido caracteres idênticos.

Cálculo da pontuação:

Suponha que a entrada tenha comprimento L e o parâmetro de radiação seja r (que é no máximo 9 para o cálculo da pontuação, portanto cabe em um dígito e, portanto, não possui caracteres repetidos consecutivos). Os dados anexados são 2 bytes (dígito, nova linha); portanto, a saída é (r + 1) (L + 2) bytes para o fluxo codificado.

Então g (L, r) = (r + 1) (L + 2).

Daqui resulta que a pontuação total pode ser calculada como

Perl + Math :: {ModInt, Polinomial, Prime :: Util}, pontuação ≤ 92819

$m=Math::Polynomial;sub l{($n,$b,$d)=@_;$n||$d||return;$n%$b,l($n/$b,$b,$d&&$d-1)}sub g{$p=$m->interpolate([grep ref$_[$_],0..$map{$p->evaluate($_)}0..$}sub p{prev_prime(128**$s)}sub e{($_,$r)=@_;length||return'';$s=$r+1;s/^[␀␁]/␁$&/;@l=map{mod($_,p$s)}l(Math::BigInt->from_bytes($_),p$s);$@l+$r>p($s)&&return e($_,$s);$a=0;join'',map{map{chr$_+$a}l($_->residue,128,$s,($a^=128))}g(@l)}sub d{@l=split/([␀-␡]+)/,$_[0];@l||return'';$s=vecmax map length,@l;@l=g map{length==$s&&mod($m->new(map{ord()%128}split//)->evaluate(128),p$s)}@l;$$_=$m->new(map{$_->residue}@l)->evaluate(p$s)->to_bytes;s/^␁//;$_}

As imagens de controle são usadas para representar o caractere de controle correspondente (por exemplo, ␀ é um caractere NUL literal). Não se preocupe muito em tentar ler o código; há uma versão mais legível abaixo.

Corra com -Mbigint -MMath::ModInt=mod -MMath::Polynomial -MNtheory=:all.-MMath::Bigint=lib,GMPnão é necessário (e, portanto, não está incluído na pontuação), mas se você o adicionar antes das outras bibliotecas, o programa será executado um pouco mais rápido.

Cálculo de pontuação

O algoritmo aqui é um pouco improvável, mas seria mais difícil de escrever (devido ao Perl não possuir as bibliotecas apropriadas). Por isso, fiz algumas trocas de tamanho / eficiência no código, com base no fato de que, como os bytes podem ser salvos na codificação, não há sentido em tentar eliminar todos os pontos do golfe.

O programa consiste em 600 bytes de código, mais 78 bytes de penalidades para opções de linha de comando, dando uma penalidade de 678 pontos. O restante da pontuação foi calculado executando o programa na sequência de melhor e pior caso (em termos de comprimento de saída) para todos os comprimentos de 0 a 99 e todos os níveis de radiação de 0 a 9; o caso médio está em algum lugar no meio, e isso dá limites à pontuação. (Não vale a pena tentar calcular o valor exato, a menos que outra entrada apareça com uma pontuação semelhante.)

Portanto, isso significa que a pontuação da eficiência da codificação está no intervalo de 91100 a 92141, inclusive, portanto, a pontuação final é:

91100 + 600 + 78 = 91778 ≤ pontuação ≤ 92819 = 92141 + 600 + 78

Versão menos golfe, com comentários e código de teste

Este é o programa original + novas linhas, recuo e comentários. (Na verdade, a versão em golfe foi produzida removendo novas linhas / indentação / comentários desta versão.)

use 5.010;                    # -M5.010; free
use Math::BigInt lib=>'GMP';  # not necessary, but makes things much faster
use bigint;                   # -Mbigint
use Math::ModInt 'mod';       # -MMath::ModInt=mod
use Math::Polynomial;         # -MMath::Polynomial
use ntheory ':all';           # -Mntheory=:all
use warnings;                 # for testing; clearly not necessary

### Start of program

$m=Math::Polynomial;          # store the module in a variable for golfiness

sub l{ # express a number $n in base $b with at least $d digits, LSdigit first
    # Note: we can't use a builtin for this because the builtins I'm aware of
    # assume that $b fits into an integer, which is not necessarily the case.
    ($n,$b,$d)=@_;
    $n||$d||return;
    $n%$b,l($n/$b,$b,$d&&$d-1)
}

sub g{ # replaces garbled blocks in the input with their actual values
    # The basic idea here is to interpolate a polynomial through all the blocks,
    # of the lowest possible degree. Unknown blocks then get the value that the
    # polynomial evaluates to. (This is a special case of Reed-Solomon coding.)
    # Clearly, if we have at least as many ungarbled blocks as we did original
    # elements, we'll get the same polynomial, thus we can always reconstruct
    # the input.
    # Note (because it's confusing): @_ is the input, $_ is the current element
    # in a loop, but @_ is written as $_ when using the [ or # operator (e.g.
    # $_[0] is the first element of @_.
    # We waste a few bytes of source for efficiency, storing the polynomial
    # in a variable rather than recalculating it each time.
    $p=$m->interpolate([grep ref$_[$_],0..$#_],[grep ref,@_]);
    # Then we just evaluate the polynomial for each element of the input.
    map{$p->evaluate($_)}0..$#_
}

sub p{ # determines maximum value of a block, given (radiation+1)
    # We split the input up into blocks. Each block has a prime number of
    # possibilities, and is stored using the top 7 bits of (radiation+1)
    # consecutive bytes of the output. Work out the largest possible prime that
    # satisfies this property.
    prev_prime(128**$s)
}

sub e{ # encoder; arguments: input (bytestring), radiation (integer)
    ($_,$r)=@_; # Read the arguments into variables, $_ and $r respectively
    length||return''; # special case for empty string
    $s=$r+1; # Also store radiation+1; we use it a lot
    # Ensure that the input doesn't start with NUL, via prepending SOH to it if
    # it starts with NUL or SOH. This means that it can be converted to a number
    # and back, roundtripping correctly.
    s/^[␀␁]/␁$&/; #/# <- unconfuse Stack Exchange's syntax highlighting
    # Convert the input to a bignum, then to digits in base p$s, to split it
    # into blocks.
    @l=map{mod($_,p$s)}l(Math::BigInt->from_bytes($_),p$s);
    # Encoding can reuse code from decoding; we append $r "garbled blocks" to
    # the blocks representing the input, and run the decoder, to figure out what
    # values they should have.
    $#l+=$r;
    # Our degarbling algorithm can only handle at most p$s blocks in total. If
    # that isn't the case, try a higher $r (which will cause a huge increase in
    # $b and a reduction in @l).
    @l+$r>p($s)&&return e($_,$s);
    # Convert each block to a sequence of $s digits in base 128, adding 128 to
    # alternating blocks; this way, deleting up to $r (i.e. less than $s) bytes
    # will preserve the boundaries between each block; then convert that to a
    # string
    $a=0; # we must initialize $a to make this function deterministic
    join'',map{map{chr$_+$a}l($_->residue,128,$s,($a^=128))}g(@l)
}

sub d{ # decoder: arguments; encdng (bytestring)
    # Reconstruct the original blocks by looking at their top bits
    @l=split/([␀-␡]+)/,$_[0];
    @l||return''; # special case for empty string
    # The length of the longest block is the radiation parameter plus 1 (i.e.
    # $s). Use that to reconstruct the value of $s.
    $s=vecmax map length,@l;
    # Convert each block to a number, or to undef if it has the wrong length.
    # Then work out the values for the undefs.
    @l=g map{
        # Convert blocks with the wrong length to undef.
        length==$s&&
            # Convert other blocks to numbers, via removing any +128 and then
            # using Math::Polynomial to convert the digit list to a number.
            mod($m->new(map{ord()%128}split// #/# <- fix syntax highlighting
            )->evaluate(128),p$s)
    }@l;
    # Remove the redundant elements at the end; now that they've reconstructed
    # the garbled elements they have no further use.
    $#l-=$s-1;
    # Convert @l to a single number (reversing the conversion into blocks.)
    $_=$m->new(map{$_->residue}@l)->evaluate(p$s)
        # Convert that number into a string.
        ->to_bytes;
    # Delete a leading SOH.
    s/^␁//;  #/# <- unconfuse Stack Exchange's syntax highlighting
    # Finally, return the string.
    $_
}


### Testing code
use Encode qw/encode decode/;

# Express a string using control pictures + IBM437, to make binary strings
# easier for a human to parse
sub format_string {
    ($_)=@_;
    $_ = decode("Latin-1", $_);
    s/[\0-\x1f]/chr (0x2400 + ord $&)/eag;
    s/\x7f/chr 0x2421/eag;
    s/[ -~\x80-\xff]/decode("IBM437",$&)/eag;
    encode("UTF-8","\x{ff62}$_\x{ff63}")
}

sub test {
    my ($string, $radiation, $samples) = @_;
    say "Input: ", format_string($string);
    my $encoding = e($string, $radiation);
    say "Encoding: ", format_string($encoding);
    say "Input length ", length($string), ", encoding length ", length($encoding), ", radiation $radiation";
    my $decoding = d($encoding);
    $decoding eq $string or die "Mistake in output!";
    say "Decoding: ", format_string($decoding), " from ",
        format_string($encoding);

    # Pseudo-randomly generate $samples radiation-damaged versions.
    srand 1;
    for my $i (1..$samples) {
        my $encdng = $encoding;
        for my $r (1..$radiation) {
            substr $encdng, int(rand(length $encdng)), 1, "";
        }
        my $newdecoding = d($encdng);
        say "Decoding: ", format_string($newdecoding), " from ",
            format_string($encdng);
        $newdecoding eq $string or die "Mistake in output!";
    }

    say "";
    length $encoding;
}

test "abcdefghijklm", 1, 10;
test "abcdefghijklm", 2, 10;
test "abcdefghijklm", 5, 10;
test "abcdefghijklm", 10, 10;
test "\0\0\0\0\0", 1, 10;
test "\5\4\3\2\1", 2, 10;
test "a", 10, 10;

my %minlength = ();
my %maxlength = ();

for my $length (0..99) {
    my ($min, $max) = ("", "");
    $length and ($min, $max) =
        ("\2" . "\0" x ($length - 1), "\1" . "\377" x ($length - 1));
    for my $radiation (0..9) {
        $minlength{"$length-$radiation"} = test $min, $radiation, 1;
        $maxlength{"$length-$radiation"} = test $max, $radiation, 1;
    }
}

say "Minimum score: ", vecsum values %minlength;
say "Maximum score: ", vecsum values %maxlength;

Algoritmo

Simplificando o problema

A idéia básica é reduzir esse problema de "codificação por exclusão" (que não é amplamente explorado) em um problema de codificação por apagamento (uma área matemática amplamente explorada). A idéia por trás da codificação de apagamento é que você está preparando dados para serem enviados por um "canal de apagamento", um canal que às vezes substitui os caracteres que ele envia por um caractere "indecente" que indica uma posição conhecida de erro. (Em outras palavras, é sempre claro onde a corrupção ocorreu, embora o personagem original ainda seja desconhecido.) A idéia por trás disso é bem simples: dividimos a entrada em blocos de comprimento ( radiação+ 1) e use sete dos oito bits em cada bloco para dados, enquanto o bit restante (nesta construção, o MSB) alterna entre ser definido para um bloco inteiro, limpo para o próximo bloco inteiro, definido para o bloco depois disso e assim por diante. Como os blocos são mais longos que o parâmetro de radiação, pelo menos um caractere de cada bloco sobrevive na saída; portanto, executando séries de caracteres com o mesmo MSB, podemos descobrir em qual bloco cada caractere pertence. O número de blocos também é sempre maior que o parâmetro de radiação; portanto, sempre temos pelo menos um bloco não danificado na encdng; sabemos, portanto, que todos os blocos mais longos ou atados por mais tempo não estão danificados, o que nos permite tratar todos os blocos mais curtos como danificados (portanto, um gargarejo). Também podemos deduzir o parâmetro de radiação como este (é '

Codificação de apagamento

Quanto à parte de codificação do problema do apagamento, isso usa um caso especial simples da construção de Reed-Solomon. Esta é uma construção sistemática: a saída (do algoritmo de codificação de apagamento) é igual à entrada mais um número de blocos extras, igual ao parâmetro de radiação. Podemos calcular os valores necessários para esses blocos de uma maneira simples (e fácil!), Tratando-os como garbles e executando o algoritmo de decodificação neles para "reconstruir" seu valor.

A idéia real por trás da construção também é muito simples: ajustamos um polinômio, no mínimo possível, a todos os blocos da codificação (com gargarejos interpolados dos outros elementos); se o polinômio é f , o primeiro bloco é f (0), o segundo é f (1) e assim por diante. Está claro que o grau do polinômio será igual ao número de blocos de entrada menos 1 (porque ajustamos um polinômio aos primeiros, depois o usamos para construir os blocos "de verificação" extras); e porque d +1 pontos definem exclusivamente um polinômio de grau d, obstruir qualquer número de blocos (até o parâmetro radiação) deixará um número de blocos não danificados igual à entrada original, o que é informação suficiente para reconstruir o mesmo polinômio. (Nós apenas temos que avaliar o polinômio para desmembrar um bloco.)

Conversão base

A consideração final deixada aqui refere-se aos valores reais obtidos pelos blocos; se fizermos interpolação polinomial nos números inteiros, os resultados podem ser números racionais (em vez de números inteiros), muito maiores que os valores de entrada ou indesejáveis. Como tal, em vez de usar números inteiros, usamos um campo finito; Neste programa, o campo finito usado é o campo de números inteiros módulo p , em que p é o maior número primo menor que 128 ^{radiação +1}(ou seja, o maior número primo para o qual podemos ajustar um número de valores distintos iguais a esse número primo na parte de dados de um bloco). A grande vantagem dos campos finitos é que a divisão (exceto por 0) é definida exclusivamente e sempre produzirá um valor nesse campo; portanto, os valores interpolados dos polinômios se encaixam em um bloco da mesma maneira que os valores de entrada.

Para converter a entrada em uma série de dados de bloco, precisamos converter a base: converter a entrada da base 256 em um número e depois converter na base p (por exemplo, para um parâmetro de radiação 1, temos p= 16381). Isso foi sustentado principalmente pela falta de rotinas de conversão de base do Perl (Math :: Prime :: Util possui algumas, mas elas não funcionam para bases de bignum, e algumas das primas com as quais trabalhamos aqui são incrivelmente grandes). Como já usamos o Math :: Polynomial para interpolação polinomial, pude reutilizá-lo como uma função "converter da sequência de dígitos" (visualizando os dígitos como coeficientes de um polinômio e avaliá-lo), e isso funciona para bignums bem. Indo para o outro lado, porém, tive que escrever a função pessoalmente. Felizmente, não é muito difícil (ou detalhado) de escrever. Infelizmente, essa conversão básica significa que a entrada geralmente fica ilegível. Há também um problema com zeros à esquerda;

Deve-se notar que não podemos ter mais do que p blocos na saída (caso contrário, os índices de dois blocos se tornariam iguais e, ainda assim, possivelmente precisaremos produzir saídas diferentes do polinômio). Isso só acontece quando a entrada é extremamente grande. Este programa resolve o problema de uma maneira muito simples: aumentar a radiação (o que torna os blocos maiores ep muito maiores, o que significa que podemos incluir muito mais dados e que claramente leva a um resultado correto).

Um outro ponto que vale a pena destacar é que codificamos a cadeia nula para si mesma, porque o programa, como foi escrito, trava nela de outra forma. Também é claramente a melhor codificação possível e funciona independentemente do parâmetro de radiação.

Potenciais melhorias

A principal ineficiência assintótica neste programa está relacionada ao uso do modulo-prime como campos finitos em questão. Existem campos finitos de tamanho 2 ⁿ (o que é exatamente o que queremos aqui, porque os tamanhos de carga útil dos blocos são naturalmente uma potência de 128). Infelizmente, eles são bem mais complexos do que uma simples construção de módulo, o que significa que o Math :: ModInt não o cortaria (e não consegui encontrar nenhuma biblioteca no CPAN para lidar com campos finitos de tamanhos não primos); Eu precisaria escrever uma classe inteira com aritmética sobrecarregada para Math :: Polynomial para poder lidar com isso, e nesse ponto o custo de bytes poderia potencialmente superar a (muito pequena) perda do uso, por exemplo, 16381 em vez de 16384.

Outra vantagem do uso de tamanhos de potência 2 é que a conversão básica se tornaria muito mais fácil. No entanto, em ambos os casos, seria útil um método melhor para representar o comprimento da entrada; o método "prefixar um 1 em casos ambíguos" é simples, mas desperdício. A conversão de base bijetiva é uma abordagem plausível aqui (a idéia é que você tenha a base como um dígito e 0 como não um dígito, de modo que cada número corresponda a uma única string).

Embora o desempenho assintótico dessa codificação seja muito bom (por exemplo, para uma entrada de comprimento 99 e um parâmetro de radiação de 3, a codificação sempre tem 128 bytes de comprimento, em vez dos ~ 400 bytes que as abordagens baseadas em repetição obteriam), seu desempenho é menos bom em entradas curtas; o comprimento da codificação é sempre pelo menos o quadrado do (parâmetro de radiação + 1). Portanto, para entradas muito curtas (comprimento 1 a 8) na radiação 9, o comprimento da saída é, no entanto, 100. (No comprimento 9, o comprimento da saída é às vezes 100 e às vezes 110.) As abordagens baseadas em repetição superam claramente esse apagamento abordagem baseada em codificação em entradas muito pequenas; pode valer a pena mudar entre vários algoritmos com base no tamanho da entrada.

Finalmente, ele não aparece na pontuação, mas com parâmetros de radiação muito altos, usar um pouco de cada byte (⅛ do tamanho da saída) para delimitar blocos é um desperdício; seria mais barato usar delimitadores entre os blocos. Reconstruir os blocos dos delimitadores é um pouco mais difícil do que com a abordagem de MSB alternado, mas acredito que seja possível, pelo menos se os dados forem suficientemente longos (com dados curtos, pode ser difícil deduzir o parâmetro de radiação da saída) . Isso seria algo a considerar se visássemos uma abordagem assintoticamente ideal, independentemente dos parâmetros.

(E, claro, poderia haver um algoritmo totalmente diferente que produza melhores resultados que este!)