Antecedentes

En este sitio, ocasionalmente tenemos preguntas que requieren que los programas sean "endurecidos por radiación"; Esto significa que el programa debe poder sobrevivir a la eliminación de uno o más bytes, sin importar qué bytes se eliminen.

Como es común para las tareas que con frecuencia se establecen en los desafíos de programación, es natural querer crear un lenguaje que sea particularmente bueno para estos desafíos. Dado que la forma natural de hacer esto es agregar algunos metadatos que permitan revertir la corrupción, en realidad no es realmente un lenguaje que deba diseñarse, sino una codificación; La idea es transformar cada entrada en una secuencia de bytes, de tal manera que incluso si la secuencia está ligeramente irradiada, es posible extraer la entrada original.

La tarea

Escriba dos programas o funciones, E (un codificador) y D (un decodificador), de modo que:

• E toma dos argumentos, una secuencia de octetos (que llamaremos " entrada " en esta especificación) y un entero no negativo " radiación ", y genera una secuencia de octetos " codificación ";
• D toma un argumento, una secuencia de octetos (" encdng "), y genera una secuencia de octetos " reconstrucción ";
• Si ejecuta E y D (con encdng , la entrada a D, elegida al eliminar no más que elementos de radiación de la codificación (no necesariamente contiguamente)), la reconstrucción será igual a la entrada sin importar qué caracteres se eliminaron para formar encdng .

Aclaraciones

• Si envía funciones, no tiene que llamarlas Ey D; Puede elegir el nombre que sea más adecuado para su idioma.
• Un "octeto" es básicamente un entero de 0 a 255 inclusive, que puede codificar como un entero, un carácter o lo que sea apropiado para su idioma.
• E y D deben ser completamente deterministas (es decir, darles las mismas entradas siempre producirá la misma salida, donde "entradas" se define como entrada y radiación para E, o encdng para D). En particular, E no puede comunicar información a D a través de un canal lateral.
• Las eliminaciones se realizan eliminando un elemento de la secuencia; piense en abrir la secuencia en un editor, colocando el cursor en un punto arbitrario y presionando Retroceso. Si un elemento aparece varias veces, es posible que solo se elimine una copia del elemento (es decir, otras instancias del mismo octeto no se verán afectadas).
• Aunque el puntaje solo se calcula sobre la base de una entrada bastante corta , su programa debe funcionar en teoría para cualquier entrada y radiación . En particular, debe funcionar sin importar qué octetos aparezcan en la entrada . (Lo sentimos, las personas que deseen la posibilidad de utilizar caracteres no imprimibles que saben que no aparecerán en la entrada, pero necesito asegurarme de que la entrada sea incompresible para que el desafío sea el endurecimiento de la radiación en lugar de la compresión).
• Puede enviar un archivo que defina dos funciones; dos archivos que definen una función o que son programas completos; o tres archivos, dos de los cuales implementan D y E respectivamente (ya sea mediante programas completos o mediante la definición de una función), y el tercero, que es un archivo de encabezado o biblioteca común a D y E. Independientemente de la forma de envío que utilice , la implementación de su lenguaje de programación debe ser capaz de comprender ambos programas sin más argumentos como ubicaciones de archivos (o de lo contrario debe pagar una penalización de byte por invocar su implementación de una manera inusual, según nuestras reglas estándar).

Condición de victoria

Para cada longitud y radiación , sea f ( longitud , radiación ) las longitudes totales de las codificaciones que corresponden a todas las entradas con longitud de longitud y la radiación dada . (Es decir, f ( longitud , radiación ) = la suma de _{entrada tiene longitud longitud} longitud (E ( entrada , radiación )).) Luego, deje que g ( longitud , radiación ) sea igual a f ( longitud ,radiación ) ÷ 256 de ^longitud . En otras palabras, g es la longitud promedio de la salida codificada, para una longitud de entrada dada y un requisito de endurecimiento de radiación dado. (En teoría, podría calcular esto por la fuerza bruta, pero probablemente tomaría un tiempo inverosímil calcular su puntaje de esa manera. Espero que la mayoría de los envíos puedan hacer un argumento matemático sobre cuál es su puntaje. Si usted '' no está seguro, publique un puntaje aproximado y usted u otra persona pueden calcularlo con mayor profundidad si otra entrada publica un puntaje similar).

Su puntaje es igual a la suma de g ( longitud , radiación ) para toda la radiación en el rango de 0 a 9 inclusive, y toda la longitud en el rango de 0 a 99 inclusive, más (principalmente para evitar la codificación rígida o para mantener la competencia si alguien descubre una codificación matemáticamente perfecta; de lo contrario, es probable que sea un factor mínimo) el número total de bytes en su envío al desafío (más las penalizaciones estándar para cosas como requerir banderas de intérprete inusuales o nombres de archivo específicos). El ganador es la entrada con la puntuación más baja (quebrada por la primera entrada que se envía)

CJam, puntaje ≤ 286,516 + 54 + 36 = 286,606

Codificador

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

Pruébalo en línea!

Descifrador

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

Pruébalo en línea!

Ambos toman y devuelven una lista de enteros. Los enlaces TIO incluyen conversión de / a cadenas para mayor comodidad. Tenga en cuenta que estos son increíblemente ineficientes para cadenas más largas. Si desea probar algunos caracteres más, le recomiendo usar caracteres con códigos de caracteres pequeños.

La idea básica para crear una codificación endurecida por radiación implica dos pasos:

1. Encuentre una codificación que nunca contenga dos octetos idénticos consecutivos.
2. Repita cada octeto en la cadena codificada r + 1 veces, donde r es el nivel de radiación.

De esta manera, la radiación no puede eliminar por completo una serie de caracteres idénticos, por lo que podemos decodificar la cadena tomando un carácter de cada serie y luego decodificando el paso 1.

Entonces, la única parte interesante es encontrar una codificación que nunca produzca octetos repetidos. La idea básica es usar algo como A043096 como un sistema de números. Es decir, para codificar un entero N , simplemente contamos en alguna base b , omitiendo todos los números con octetos repetidos. Creo que la cantidad de números que se pueden representar de esta manera con hasta d dígitos es la misma que la cantidad de números que se pueden representar en la base biyectiva b-1 (ya que, cuando desea escribir dicho número, puede elija entre b-1 dígito para cada posición sin violar la restricción).

Por supuesto, para obtener la compresión máxima usaremos b = 256 . Para convertir la entrada en un entero, también podemos usar la conversión de base. Si no fuera vago, usaría una base biyectiva para la entrada, pero por ahora solo estoy anteponiendo a 1(para asegurarme de que no haya ceros a la izquierda) y luego uso la base más pequeña posible para que todos los octetos en el La entrada es menor que la base.

Esta base se antepone a la codificación (para que el decodificador sepa qué base usar) y se separa del número restante por un octeto 0 (esto funciona porque el número restante nunca comenzará con un cero). Como una optimización menor, la cadena vacía sigue siendo una cadena vacía.

La razón por la que no he calculado un puntaje exacto arriba es porque solo estoy calculando un límite superior para cuánto tiempo cada entrada se basará en su longitud y su octeto máximo. Sin embargo, para estos dos parámetros, a menudo habrá dos longitudes de salida diferentes, y aún no me he molestado en averiguar dónde se produce el punto de inflexión entre ellos. También he usado la longitud de la base 255 habitual en lugar de la base 255 biyectiva para estimar esa longitud, que de nuevo es un poco más grande de lo necesario. El código exacto de Mathematica que utilicé para el cálculo es el siguiente:

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]debería dar el número de cadenas de longitud lcon el octeto máximo b-1(a excepción de b == 1, donde lo he codificado 0porque siempre estoy usando al menos base 2).

bash + GNU utilidades, puntaje 294506 283468

Edición 1: corrige un problema que @Leo notó, ¡gracias!

Edición 2: se mejoró el método de codificación para el parámetro de radiación, para una mejor puntuación.

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 el codificador: secuencia de octeto pasada como caracteres en stdin, el parámetro de radiación r pasado como argumento.

Para el decodificador: la entrada se pasa como caracteres en stdin.

Para ambos: Salida en stdout.

El codificador antepone a los datos de entrada los dígitos de r, con un carácter 'a' insertado entre cada par de dígitos idénticos consecutivos, seguido de una nueva línea nueva. Luego copia toda la entrada (comenzando con los caracteres antepuestos), reemplazando cada carácter por r + 1 copias de ese carácter.

El decodificador deshace esto, pasando por cada uno de los caracteres restantes x en su entrada, saltando hasta r copias idénticas consecutivas de x después de x e imprimiendo lo que queda. Los datos antepuestos no tienen caracteres repetidos, por lo que pueden decodificarse antes de que se conozca r. En ese punto, se conoce r, y ese valor es necesario para decodificar el resto de los datos correctamente.

Puede comprobar que esto funciona incluso si la entrada original tiene caracteres idénticos repetidos.

Cálculo del puntaje:

Suponga que la entrada tiene una longitud L y el parámetro de radiación es r (que es como máximo 9 para el cálculo de puntuación, por lo que cabe en un dígito y, por lo tanto, no tiene caracteres repetidos consecutivos). Los datos antepuestos son 2 bytes (dígito, nueva línea), por lo que la salida es (r + 1) (L + 2) bytes para la secuencia codificada.

Entonces g (L, r) = (r + 1) (L + 2).

De ello se deduce que la puntuación total se puede calcular como

Perl + Math :: {ModInt, Polynomial, Prime :: Util}, puntaje ≤ 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/^␁//;$_}

Las imágenes de control se utilizan para representar el carácter de control correspondiente (por ejemplo, ␀es un carácter NUL literal). No te preocupes mucho por tratar de leer el código; Hay una versión más legible a continuación.

Corre con -Mbigint -MMath::ModInt=mod -MMath::Polynomial -MNtheory=:all. -MMath::Bigint=lib,GMPno es necesario (y, por lo tanto, no está incluido en el puntaje), pero si lo agrega antes que las otras bibliotecas, el programa se ejecutará un poco más rápido.

Cálculo de puntaje

El algoritmo aquí es algo mejorable, pero sería bastante más difícil de escribir (debido a que Perl no tiene las bibliotecas apropiadas). Debido a esto, hice un par de compensaciones de tamaño / eficiencia en el código, sobre la base de que dado que los bytes se pueden guardar en la codificación, no tiene sentido tratar de reducir cada punto del golf.

El programa consta de 600 bytes de código, más 78 bytes de penalizaciones para las opciones de línea de comandos, lo que da una penalización de 678 puntos. El resto de la puntuación se calculó ejecutando el programa en la cadena del mejor y el peor de los casos (en términos de longitud de salida) para cada longitud de 0 a 99 y cada nivel de radiación de 0 a 9; el caso promedio está en algún punto intermedio, y esto da límites en el puntaje. (No vale la pena intentar calcular el valor exacto a menos que entre otra entrada con una puntuación similar).

Por lo tanto, esto significa que la puntuación de la eficiencia de codificación está en el rango de 91100 a 92141 inclusive, por lo que la puntuación final es:

91100 + 600 + 78 = 91778 ≤ puntaje ≤ 92819 = 92141 + 600 + 78

Versión menos golfista, con comentarios y código de prueba

Este es el programa original + nuevas líneas, sangría y comentarios. (En realidad, la versión de golf se produjo al eliminar las nuevas líneas / sangría / comentarios de esta versión).

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 el problema

La idea básica es reducir este problema de "codificación de eliminación" (que no es ampliamente explorado) en un problema de codificación de borrado (un área matemática ampliamente explorada). La idea detrás de la codificación de borrado es que está preparando datos para enviarlos a través de un "canal de borrado", un canal que a veces reemplaza los caracteres que envía con un carácter "distorsionado" que indica una posición conocida de un error. (En otras palabras, siempre está claro dónde se ha producido la corrupción, aunque aún se desconoce el carácter original). La idea detrás de esto es bastante simple: dividimos la entrada en bloques de longitud ( radiación+ 1), y use siete de los ocho bits en cada bloque para datos, mientras que el bit restante (en esta construcción, el MSB) alterna entre configurarse para un bloque completo, borrar para todo el siguiente bloque, establecer para el bloque después de eso, y así sucesivamente. Debido a que los bloques son más largos que el parámetro de radiación, al menos un carácter de cada bloque sobrevive en la salida; entonces, al tomar series de caracteres con el mismo MSB, podemos determinar a qué bloque pertenecía cada personaje. El número de bloques también es siempre mayor que el parámetro de radiación, por lo que siempre tenemos al menos un bloque no dañado en el encdng; Por lo tanto, sabemos que todos los bloques que son más largos o que están atados por más tiempo no están dañados, lo que nos permite tratar los bloques más cortos como dañados (por lo tanto, una balble) También podemos deducir el parámetro de radiación como este ('

Codificación de borrado

En cuanto a la parte de codificación de borrado del problema, se utiliza un caso especial simple de la construcción Reed-Solomon. Esta es una construcción sistemática: la salida (del algoritmo de codificación de borrado) es igual a la entrada más una cantidad de bloques adicionales, igual al parámetro de radiación. Podemos calcular los valores necesarios para estos bloques de una manera simple (¡y de golf!), Tratándolos como confusos, luego ejecutando el algoritmo de decodificación para "reconstruir" su valor.

La idea real detrás de la construcción también es muy simple: ajustamos un polinomio, del grado mínimo posible, a todos los bloques en la codificación (con garbles interpolados de los otros elementos); si el polinomio es f , el primer bloque es f (0), el segundo es f (1), y así sucesivamente. Está claro que el grado del polinomio será igual al número de bloques de entrada menos 1 (porque ajustamos un polinomio a esos primero, luego lo usamos para construir los bloques de "verificación" adicionales); y porque d +1 puntos definen de forma única un polinomio de grado d, si se confunde cualquier número de bloques (hasta el parámetro de radiación), dejará una cantidad de bloques no dañados igual a la entrada original, que es suficiente información para reconstruir el mismo polinomio. (Entonces solo tenemos que evaluar el polinomio para anular el bloqueo de un bloque).

Conversión base

La consideración final que queda aquí tiene que ver con los valores reales tomados por los bloques; Si hacemos una interpolación polinómica en los enteros, los resultados pueden ser números racionales (en lugar de enteros), mucho más grandes que los valores de entrada, o indeseables. Como tal, en lugar de usar los enteros, usamos un campo finito; en este programa, el campo finito utilizado es el campo de números enteros módulo p , donde p es el primo más grande de menos de 128 ^{radiaciones +1}(es decir, el primo más grande para el que podemos ajustar un número de valores distintos iguales a ese primo en la parte de datos de un bloque). La gran ventaja de los campos finitos es que la división (excepto por 0) está definida de manera única y siempre producirá un valor dentro de ese campo; por lo tanto, los valores interpolados de los polinomios encajarán en un bloque de la misma manera que lo hacen los valores de entrada.

Para convertir la entrada en una serie de datos de bloque, entonces, necesitamos hacer una conversión de base: convertir la entrada de la base 256 en un número, luego convertirla en la base p (por ejemplo, para un parámetro de radiación de 1, tenemos p= 16381). Esto se debió principalmente a la falta de rutinas de conversión de bases de Perl (Math :: Prime :: Util tiene algunas, pero no funcionan para bases bignum, y algunos de los primos con los que trabajamos aquí son increíblemente grandes). Como ya estamos usando Math :: Polynomial para la interpolación polinomial, pude reutilizarlo como una función "convertir de secuencia de dígitos" (al ver los dígitos como los coeficientes de un polinomio y evaluarlo), y esto funciona para bignums muy bien Sin embargo, en el otro sentido, tuve que escribir la función yo mismo. Afortunadamente, no es demasiado difícil (o detallado) escribir. Desafortunadamente, esta conversión de base significa que la entrada normalmente se vuelve ilegible. También hay un problema con los ceros a la izquierda;

Cabe señalar que no podemos tener más de p bloques en la salida (de lo contrario, los índices de dos bloques serían iguales, y posiblemente tendrían que producir diferentes salidas del polinomio). Esto solo sucede cuando la entrada es extremadamente grande. Este programa resuelve el problema de una manera muy simple: aumentando la radiación (lo que hace que los bloques sean más grandes y p mucho más grandes, lo que significa que podemos incluir muchos más datos y que claramente conduce a un resultado correcto).

Otro punto que vale la pena destacar es que codificamos la cadena nula para sí misma, porque el programa tal como está escrito se bloquearía de lo contrario. También es claramente la mejor codificación posible, y funciona sin importar cuál sea el parámetro de radiación.

Posibles mejoras

La principal ineficiencia asintótica en este programa tiene que ver con el uso de modulo-prime como los campos finitos en cuestión. Existen campos finitos de tamaño 2 ⁿ (que es exactamente lo que queremos aquí, porque los tamaños de carga útil de los bloques son, naturalmente, una potencia de 128). Desafortunadamente, son bastante más complejos que una simple construcción de módulo, lo que significa que Math :: ModInt no lo cortaría (y no pude encontrar ninguna biblioteca en CPAN para manejar campos finitos de tamaños no primos); Tendría que escribir una clase completa con aritmética sobrecargada para Math :: Polynomial para poder manejarlo, y en ese momento el costo del byte podría sobrepasar la pérdida (muy pequeña) del uso, por ejemplo, 16381 en lugar de 16384.

Otra ventaja de usar tamaños de potencia de 2 es que la conversión de la base sería mucho más fácil. Sin embargo, en cualquier caso, un mejor método para representar la longitud de la entrada sería útil; El método "anteponer un 1 en casos ambiguos" es simple pero derrochador. La conversión de base biyectiva es un enfoque plausible aquí (la idea es que tenga la base como un dígito y 0 como no un dígito, de modo que cada número corresponda a una sola cadena).

Aunque el rendimiento asintótico de esta codificación es muy bueno (por ejemplo, para una entrada de longitud 99 y un parámetro de radiación de 3, la codificación siempre tiene 128 bytes de longitud, en lugar de los ~ 400 bytes que obtendrían los enfoques basados ​​en la repetición), su rendimiento es menos bueno en entradas cortas; la longitud de la codificación siempre es al menos el cuadrado del (parámetro de radiación + 1). Entonces, para entradas muy cortas (longitud 1 a 8) en la radiación 9, la longitud de la salida es de todos modos 100. (En la longitud 9, la longitud de la salida es a veces 100 y a veces 110.) Los enfoques basados ​​en la repetición claramente superan esta eliminación enfoque basado en codificación en entradas muy pequeñas; Puede valer la pena cambiar entre múltiples algoritmos basados ​​en el tamaño de la entrada.

Finalmente, en realidad no aparece en la puntuación, pero con parámetros de radiación muy altos, usar un bit de cada byte (⅛ del tamaño de salida) para delimitar bloques es un desperdicio; sería más barato usar delimitadores entre los bloques en su lugar. Reconstruir los bloques a partir de delimitadores es bastante más difícil que con el enfoque de MSB alternativo, pero creo que es posible, al menos si los datos son lo suficientemente largos (con datos cortos, puede ser difícil deducir el parámetro de radiación de la salida) . Eso sería algo a tener en cuenta si se busca un enfoque asintóticamente ideal, independientemente de los parámetros.

(Y, por supuesto, ¡podría haber un algoritmo completamente diferente que produzca mejores resultados que este!)