Escribe Moby Dick, aproximadamente

297

Aquí hay un archivo de texto ASCII de 1.2Mb que contiene el texto de Moby-Dick de Herman Melville ; o la ballena . Su tarea es escribir un programa o función (o clase, etc. - ver más abajo) que se le dará a este archivo un carácter a la vez, y en cada paso debe adivinar el siguiente carácter.

Este es . Tu puntaje será

2*L + E

donde Les el tamaño de su envío en bytes y Ees el número de caracteres que adivina incorrectamente. El puntaje más bajo gana.

Otros detalles

Su envío será un programa o función (etc.) que será invocado o invocado o enviado datos varias veces. (1215235 veces para ser exactos). Cuando se llama a la n º tiempo que se le dará el n º carácter de whale.txto whale2.txty debe adivinar su salida para el ( n + 1 ) ésimo carácter. El Ecomponente de su puntuación será el número total de caracteres que adivina incorrectamente.

La mayoría de las presentaciones necesitarán almacenar algún estado entre invocaciones, para que puedan rastrear cuántas veces se han llamado y cuáles fueron las entradas anteriores. Puede hacerlo escribiendo en un archivo externo, utilizando staticvariables globales o, enviando una clase en lugar de una función, utilizando una mónada de estado o cualquier otra cosa que funcione para su idioma. Su envío debe incluir cualquier código requerido para inicializar su estado antes de la primera invocación.

Su programa debe ejecutarse de manera determinista, de modo que siempre haga las mismas conjeturas con la misma entrada (y, por lo tanto, siempre obtenga la misma puntuación).

Su respuesta debe incluir no solo su envío, sino también el código que utilizó para calcular la Eparte de su puntaje. No es necesario que esté escrito en el mismo idioma que su envío y no se contará para su recuento de bytes. Se le recomienda que sea legible.

Con respecto a la interfaz entre su envío y este programa de cálculo de puntaje, todo está bien, siempre que su programa siempre dé un byte de salida antes de recibir su próximo byte de entrada. (Entonces, por ejemplo, no puede simplemente pasarle una cadena que contenga toda la entrada y recuperar una cadena que contenga toda la salida).

En realidad, debe ejecutar su programa de prueba y calcular / verificar su puntaje antes de enviar su entrada. Si su envío es demasiado lento para que pueda verificar su puntaje, entonces no está calificado para competir, incluso si sabe cuál sería su puntaje en principio.

El Lcomponente de su puntaje se calculará de acuerdo con las reglas habituales para los desafíos de golf de código. Si su envío contendrá varios archivos, tome nota de las reglas sobre puntuación y estructura de directorios en ese caso. Cualquier información que use su código debe incluirse en su Lpuntaje.

Puede importar bibliotecas existentes, pero no puede cargar ningún otro archivo externo, y su código puede no acceder a la whale.txtowhale2.txtarchivo de cualquier otra manera que no sea la descrita anteriormente. No puede cargar ninguna red neuronal previamente entrenada u otras fuentes de datos estadísticos. (Está bien usar redes neuronales, pero debe incluir los datos de peso en su envío y contarlos para su recuento de bytes). Si por alguna razón su idioma o bibliotecas incluyen una función que proporciona parte o la totalidad del texto de Moby Dick , no puede usar esa función. Además de eso, puede usar cualquier otra función incorporada o de biblioteca que desee, incluidas las relacionadas con el procesamiento de texto, la predicción o la compresión, siempre que formen parte de su idioma o de sus bibliotecas estándar. Para rutinas más exóticas y especializadas que incluyen fuentes de datos estadísticos, deberá implementarlas usted mismo e incluirlas en su recuento de bytes.

Es probable que algunas presentaciones incluyan componentes que son generados por el código. Si este es el caso, incluya en su respuesta el código que se utilizó para producirlos y explique cómo funciona . (Mientras este código no sea necesario para ejecutar su envío, no se incluirá en su recuento de bytes).

Por razones históricas, hay dos versiones del archivo, y puede usar cualquiera de ellas en una respuesta. En whale2.txt(vinculado anteriormente) el texto no está ajustado, por lo que las nuevas líneas aparecen solo al final de los párrafos. En el original, whale.txtel texto se ajusta a un ancho de 74 caracteres, por lo que debe predecir el final de cada línea y el texto. Esto hace que el desafío sea más complicado, por lo que whale2.txtse recomienda para nuevas respuestas. Ambos archivos son del mismo tamaño, 1215236 bytes.


Para resumir, todas las respuestas deben incluir lo siguiente:

  • Su presentación en sí. (El código, más cualquier archivo de datos que use; estos pueden ser enlaces si son grandes).
  • Una explicación de cómo funciona su código. Explique el método de E / S y cómo predice el siguiente carácter. La explicación de su algoritmo es importante, y las buenas explicaciones me darán recompensas.
  • El código que usó para evaluar su puntaje. (Si esto es idéntico a una respuesta anterior, simplemente puede vincularla).
  • Cualquier código que utilizó para generar su envío, junto con una explicación de ese código. Esto incluye el código que utilizó para optimizar los parámetros, generar archivos de datos, etc. (Esto no cuenta para el recuento de bytes, pero debe incluirse en su respuesta).

Tabla de clasificación

Recompensas

De vez en cuando ofreceré recompensas para alentar diferentes enfoques.

El primero, 50 puntos, fue otorgado a A. Rex por la respuesta con mejor puntuación en ese momento.

El segundo, 100 puntos, también fue otorgado a A. Rex, por la misma respuesta, porque agregaron una muy buena explicación a su respuesta existente.

La próxima recompensa, 200 puntos , se otorgará a cualquiera

  • Una respuesta competitiva que utiliza una nueva técnica. (Esto se basará en mi juicio subjetivo ya que es mi representante el que entra en la recompensa, pero puedes confiar en mí para ser justo. ¡Ten en cuenta que tu respuesta debe contener una explicación suficiente para que entienda cómo funciona!) No tome el puntaje más alto, solo necesita hacerlo razonablemente bien en comparación con las respuestas existentes. Estoy particularmente interesado en ver soluciones basadas en redes neuronales recurrentes, pero otorgaré la recompensa a cualquier cosa que parezca lo suficientemente diferente de los modelos de Markov que dominan las puntuaciones más altas actuales.

O:

  • Cualquier otra persona que supere la puntuación máxima de A. Rex (actualmente 444444), utilizando cualquier método.

Una vez que se reclame la recompensa de 200 puntos, lo más probable es que ofrezca una de 400 puntos, actualizando los requisitos en consecuencia.

Nathaniel
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Dennis
99
¡xkcd.com/1960 parece ser una referencia a este desafío!
A. Rex
Pensé en comprimir esto ... pero es un poco demasiado largo que mi computadora se encogió de hombros
Naruyoko

Respuestas:

135

/// , 2 * 1 + 1020874 = 1020876

 

Imprime un espacio.

daniero
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Dennis
¡Ese es un hackeo de recompensas extremadamente inteligente! Debe ser un AGI;)
Alex
97

Nodo.js, 2 * 224 + 524279 = 524727

Consulte el registro de cambios al final de esta publicación para obtener actualizaciones de puntaje.

Una función que toma y devuelve un byte.

a=[...l='14210100'],m={},s={},b={}
f=c=>a.some((t,n)=>x=s[y=l.slice(n)]>t|/^[A-Z '"(]/.test(y)&&b[y],l+=String.fromCharCode(c),a.map((_,n)=>(m[x=l.slice(n)]=-~m[x])<s[y=l.slice(n,8)]||(s[y]=m[x],b[y]=c)),l=l.slice(1))&&x||32

Consiste en un modelo PPM simple que mira los últimos 8 caracteres para predecir el siguiente.

Confiamos en un patrón de longitud L cuando lo hemos encontrado al menos T [L] veces, donde T es una matriz de umbrales arbitrarios: [1,1,2,1,2,3,5,2] . Además, siempre confiamos en un patrón cuyo primer carácter coincida [A-Z '"(].

Seleccionamos el patrón de confianza más largo y devolvemos la predicción con la puntuación más alta asociada a este patrón en el momento de la llamada.

Notas

  • Obviamente, esto no está optimizado para la velocidad, pero se ejecuta en aproximadamente 15 segundos en mi computadora portátil.

  • Si se nos permitiera repetir el proceso varias veces seguidas sin restablecer el modelo, el número de errores convergería a ~ 268000 después de 5 iteraciones.

  • La tasa de éxito actual de la función de predicción es ~ 56.8%. Como notó @immibis en los comentarios, si las conjeturas incorrectas y correctas se mezclan, el resultado ni siquiera es legible.

    Por ejemplo, este fragmento cerca del final del libro:

    Here be it said, that this pertinacious pursuit of one particular whale,[LF]
    continued through day into night, and through night into day, is a thing[LF]
    by no means unprecedented in the South sea fishery.
    

    se convierte en:

    "e e be it said, that thes woacangtyous sarsuet of tie oort cular thale[LF][LF]
     orsinued toeough tir on e togh   and sheough toght an o ters af t shin[LF][LF]
    be to means insrocedented tn hhe sputh Sevsaonh ry,
    

    Al reemplazar las conjeturas erróneas con guiones bajos, tenemos una mejor idea de lo que funcionó correctamente:

    _e_e be it said, that th_s _____n___ous __rsu_t of __e __rt_cular _hale_[LF]
    _o__inued t__ough ___ _n__ __gh__ and _h_ough __ght _n_o ____ __ _ _hin_[LF]
    b_ _o means _n_r_cedented _n _he __uth _e_____h_ry_
    

    NB : El ejemplo anterior se creó con una versión anterior del código, trabajando en la primera versión del archivo de entrada.

Código de prueba

/**
  The prediction function f() and its variables.
*/
a=[...l='14210100'],m={},s={},b={}
f=c=>a.some((t,n)=>x=s[y=l.slice(n)]>t|/^[A-Z '"(]/.test(y)&&b[y],l+=String.fromCharCode(c),a.map((_,n)=>(m[x=l.slice(n)]=-~m[x])<s[y=l.slice(n,8)]||(s[y]=m[x],b[y]=c)),l=l.slice(1))&&x||32

/**
  A closure containing the test code and computing E.
  It takes f as input.
  (f can't see any of the variables defined in this scope.)
*/
;
(f => {
  const fs = require('fs');

  let data = fs.readFileSync('whale2.txt'),
      len = data.length,
      err = 0;

  console.time('ElapsedTime');

  data.forEach((c, i) => {
    i % 100000 || console.log((i * 100 / len).toFixed(1) + '%');

    if(i < len - 1 && f(c) != data[i + 1]) {
      err++;
    }
  })

  console.log('E = ' + err);
  console.timeEnd('ElapsedTime');
})(f)

Cambiar registro

  • 524727 : ahorró 19644 puntos al cambiar a whale2.txt (actualización de desafío)
  • 544371 : ahorró 327 puntos al forzar patrones que comienzan con una letra mayúscula, una comilla, una comilla doble o un paréntesis de apertura para que siempre se confíe
  • 544698 : ahorró 2119 puntos al forzar patrones que comienzan con un espacio en el que siempre se puede confiar
  • 546817 : ahorró 47 puntos ajustando los umbrales y jugando golf a la función de predicción
  • 546864 : ahorró 1496 puntos al extender la longitud máxima del patrón a 8 caracteres
  • 548360 : ahorró 6239 puntos al introducir la noción de patrones confiables, con umbrales que dependen de su longitud
  • 554599 : ahorró 1030 puntos al mejorar la predicción de avance de línea
  • 555629 : ahorró 22 puntos jugando al golf en la función de predicción
  • 555651 : ahorró 40 puntos jugando al golf con la función de predicción
  • 555691 - puntaje inicial
Arnauld
fuente
44
Para los curiosos, no, esto no produce nada como Moby Dick. Es mucho sidg tlanses,oeth to, shuld hottut tild aoersors Ch, th! Sa, yr! Sheu arinning whales aut ihe e sl he traaty of rrsf tg homn Bho dla tiasot a shab sor ty, af etoors tnd hocket sh bts ait mtubb tiddin tis aeewnrs, dnhost maundy cnd sner aiwt d boelh cheugh -aaieiyns aasiyns taaeiins! th, tla. Se las arregla para obtener algunas palabras completas a veces. Al igual whales.
immibis
23
@immibis El título del desafío fue elegido sabiamente. Este es Moby Dick, aproximadamente . :-)
Arnauld
3
@Nathaniel Ha habido muchas actualizaciones, por lo que sería apenas legible y no realmente informativo. En su lugar, agregué un registro de cambios con explicaciones breves sobre las mejoras.
Arnauld
45
Creo que su programa está haciendo una traducción perfecta al gaélico.
Beska
1
@ Draco18s Es difícil saber si esta coma fue una buena o mala suposición. Si fue una mala suposición, la función de predicción puede haber intentado legítimamente poner una letra después de cualquier otra letra que estaba realmente allí en lugar de la coma una vez que la recibió.
Arnauld
91

Perl, 2 · 70525 + 326508 = 467558

Vaticinador

$m=($u=1<<32)-1;open B,B;@e=unpack"C*",join"",<B>;$e=2903392593;sub u{int($_[0]+($_[1]-$_[0])*pop)}sub o{$m&(pop()<<8)+pop}sub g{($h,%m,@b,$s,$E)=@_;if($d eq$h){($l,$u)=(u($l,$u,$L),u($l,$u,$U));$u=o(256,$u-1),$l=o($l),$e=o(shift@e,$e)until($l^($u-1))>>24}$M{"@c"}{$h}++-++$C{"@c"}-pop@c for@p=($h,@c=@p);@p=@p[0..19]if@p>20;@c=@p;for(@p,$L=0){$c="@c";last if" "ne pop@c and@c<2 and$E>99;$m{$_}+=$M{$c}{$_}/$C{$c}for sort keys%{$M{$c}};$E+=$C{$c}}$s>5.393*$m{$_}or($s+=$m{$_},push@b,$_)for sort{$m{$b}<=>$m{$a}}sort keys%m;$e>=u($l,$u,$U=$L+$m{$_}/$s)?$L=$U:return$d=$_ for sort@b}

Para ejecutar este programa, necesita este archivo aquí , que debe nombrarse B. (Puede cambiar este nombre de archivo en la segunda instancia del carácter Banterior). Consulte a continuación cómo generar este archivo.

El programa utiliza una combinación de modelos de Markov esencialmente como en esta respuesta del usuario 2699 , pero con algunas pequeñas modificaciones. Esto produce una distribución para el siguiente personaje. Utilizamos la teoría de la información para decidir si aceptar un error o gastar bits de almacenamiento en Bsugerencias de codificación (y si es así, cómo). Usamos codificación aritmética para almacenar de manera óptima bits fraccionales del modelo.

El programa tiene una longitud de 582 bytes (incluida una nueva línea final innecesaria) y el archivo binario Btiene una longitud de 69942 bytes, por lo que, según las reglas para la puntuación de varios archivos , calificamosL como 582 + 69942 + 1 = 70525.

El programa casi seguramente requiere una arquitectura de 64 bits (little-endian?). Se tarda aproximadamente 2,5 minutos en ejecutarse en una m5.largeinstancia en Amazon EC2.

Código de prueba

# Golfed submission
require "submission.pl";

use strict; use warnings; use autodie;

# Scoring length of multiple files adds 1 penalty
my $length = (-s "submission.pl") + (-s "B") + 1;

# Read input
open my $IN, "<", "whale2.txt";
my $input = do { local $/; <$IN> };

# Run test harness
my $errors = 0;
for my $i ( 0 .. length($input)-2 ) {
    my $current = substr $input, $i, 1;
    my $decoded = g( $current );

    my $correct = substr $input, $i+1, 1;
    my $error_here = 0 + ($correct ne $decoded);
    $errors += $error_here;
}

# Output score
my $score = 2 * $length + $errors;
print <<EOF;
length $length
errors $errors
score  $score
EOF

El arnés de prueba asume que el envío está en el archivo submission.pl , pero esto se puede cambiar fácilmente en la segunda línea.

Comparación de texto

"And did none of ye see it before?" cried Ahab, hailing the perched men all around him.\\"I saw him almost that same instant, sir, that Captain 
"And wid note of te fee bt seaore   cried Ahab, aasling the turshed aen inl atound him. \"' daw him wsoost thot some instant, wer, that Saptain 
"And _id no_e of _e _ee _t _e_ore__ cried Ahab, _a_ling the __r_hed _en __l a_ound him._\"_ _aw him ___ost th_t s_me instant, __r, that _aptain 

Ahab did, and I cried out," said Tashtego.\\"Not the same instant; not the same--no, the doubloon is mine, Fate reserved the doubloon for me. I 
Ahab aid  ind I woued tut,  said tashtego, \"No, the same instant, tot the same -tow nhe woubloon ws mane. alte ieserved the seubloon ior te, I 
Ahab _id_ _nd I ___ed _ut,_ said _ashtego__\"No_ the same instant_ _ot the same_-_o_ _he _oubloon _s m_ne_ __te _eserved the __ubloon _or _e_ I 

only; none of ye could have raised the White Whale first. There she blows!--there she blows!--there she blows! There again!--there again!" he cr
gnly  towe of ye sould have tersed the shite Whale aisst  Ihere ihe blows! -there she blows! -there she blows! Ahere arains -mhere again!  ce cr
_nly_ _o_e of ye _ould have ___sed the _hite Whale _i_st_ _here _he blows!_-there she blows!_-there she blows! _here a_ain__-_here again!_ _e cr

Esta muestra (elegida en otra respuesta ) aparece bastante tarde en el texto, por lo que el modelo está bastante desarrollado en este punto. Recuerde que el modelo está aumentado por 70 kilobytes de "pistas" que lo ayudan directamente a adivinar los caracteres; no está impulsado simplemente por el breve fragmento de código anterior.

Generando pistas

El siguiente programa acepta el código de envío exacto anterior (en la entrada estándar) y genera el Barchivo exacto anterior (en la salida estándar):

@S=split"",join"",<>;eval join"",@S[0..15,64..122],'open W,"whale2.txt";($n,@W)=split"",join"",<W>;for$X(0..@W){($h,$n,%m,@b,$s,$E)=($n,$W[$X]);',@S[256..338],'U=0)',@S[343..522],'for(sort@b){$U=($L=$U)+$m{$_}/$s;if($_ eq$n)',@S[160..195],'X<128||print(pack C,$l>>24),',@S[195..217,235..255],'}}'

Se tarda aproximadamente el tiempo de ejecución que el envío, ya que realiza cálculos similares.

Explicación

En esta sección, intentaremos describir lo que hace esta solución con suficiente detalle para que usted pueda "probarla en casa". La técnica principal que diferencia esta respuesta de las otras es algunas secciones más abajo como mecanismo de "rebobinado", pero antes de llegar allí, necesitamos establecer los conceptos básicos.

Modelo

El ingrediente básico de la solución es un modelo de lenguaje. Para nuestros propósitos, un modelo es algo que toma una cantidad de texto en inglés y devuelve una distribución de probabilidad en el siguiente carácter. Cuando usamos el modelo, el texto en inglés será un prefijo (correcto) de Moby Dick. Tenga en cuenta que el resultado deseado es una distribución , y no solo una suposición para el personaje más probable.

En nuestro caso, esencialmente utilizamos el modelo en esta respuesta por user2699 . No utilizamos el modelo de la respuesta con la puntuación más alta (que no sea la nuestra) de Anders Kaseorg precisamente porque no pudimos extraer una distribución en lugar de una sola conjetura. En teoría, esa respuesta calcula una media geométrica ponderada, pero obtuvimos resultados algo pobres cuando lo interpretamos demasiado literalmente. "Robamos" un modelo de otra respuesta porque nuestra "salsa secreta" no es el modelo sino el enfoque general. Si alguien tiene un modelo "mejor", entonces debería poder obtener mejores resultados utilizando el resto de nuestras técnicas.

Como comentario, la mayoría de los métodos de compresión como Lempel-Ziv pueden verse como un "modelo de lenguaje" de esta manera, aunque uno podría tener que entrecerrar los ojos un poco. (¡Es particularmente complicado para algo que hace una transformación de Burrows-Wheeler!) Además, tenga en cuenta que el modelo por user2699 es una modificación de un modelo de Markov; esencialmente nada más es competitivo para este desafío o tal vez incluso modelar texto en general.

Arquitectura general

A los efectos de la comprensión, es bueno dividir la arquitectura general en varias piezas. Desde la perspectiva de más alto nivel, debe haber un poco de código de administración de estado. Esto no es particularmente interesante, pero para completar, queremos enfatizar que en cada punto al programa se le pide la siguiente suposición, tiene disponible un prefijo correcto de Moby Dick. No utilizamos nuestras conjeturas incorrectas pasadas de ninguna manera. En aras de la eficiencia, el modelo de lenguaje probablemente puede reutilizar su estado de los primeros N caracteres para calcular su estado para los primeros (N + 1) caracteres, pero en principio, podría volver a calcular las cosas desde cero cada vez que se invoca.

Dejemos a un lado este "controlador" básico del programa y echemos un vistazo dentro de la parte que adivina el siguiente personaje. Ayuda conceptualmente a separar tres partes: el modelo de lenguaje (discutido anteriormente), un archivo de "pistas" y un "intérprete". En cada paso, el intérprete le pedirá al modelo de lenguaje una distribución para el siguiente carácter y posiblemente leerá alguna información del archivo de sugerencias. Luego combinará estas partes en una suposición. Más adelante se explicará con precisión qué información está en el archivo de sugerencias y cómo se usa, pero por ahora ayuda a mantener estas partes separadas mentalmente. Tenga en cuenta que, en cuanto a la implementación, el archivo de sugerencias es literalmente un archivo separado (binario), pero podría haber sido una cadena o algo almacenado dentro del programa. Como una aproximación,

Si se está utilizando un método de compresión estándar como bzip2 como en esta respuesta , el archivo de "sugerencias" corresponde al archivo comprimido. El "intérprete" corresponde al descompresor, mientras que el "modelo de lenguaje" es un poco implícito (como se mencionó anteriormente).

¿Por qué usar un archivo de pistas?

Elija un ejemplo simple para analizar más a fondo. Suponga que el texto tiene Ncaracteres largos y bien aproximados por un modelo en el que cada carácter es (independientemente) la letra Econ probabilidad ligeramente inferior a la mitad, de Tmanera similar con probabilidad ligeramente inferior a la mitad y Acon probabilidad 1/1000 = 0.1%. Supongamos que no hay otros personajes posibles; en cualquier caso, el Aes bastante similar al caso de un personaje nunca antes visto de la nada.

Si operamos en el régimen L 0 (como lo hacen la mayoría, pero no todas, las otras respuestas a esta pregunta), no hay mejor estrategia para el intérprete que elegir una de Ey T. En promedio, obtendrá aproximadamente la mitad de los caracteres correctos. Entonces E ≈ N / 2 y el puntaje ≈ N / 2 también. Sin embargo, si usamos una estrategia de compresión, podemos comprimir a un poco más de un bit por carácter. Como L se cuenta en bytes, obtenemos L ≈ N / 8 y, por lo tanto, puntaje ≈ N / 4, el doble de bueno que la estrategia anterior.

Lograr esta tasa de un poco más de un bit por carácter para este modelo es ligeramente no trivial, pero un método es la codificación aritmética.

Codificación aritmética

Como es comúnmente conocido, una codificación es una forma de representar algunos datos usando bits / bytes. Por ejemplo, ASCII es una codificación de 7 bits / caracteres de texto en inglés y caracteres relacionados, y es la codificación del archivo Moby Dick original en consideración. Si algunas letras son más comunes que otras, entonces una codificación de ancho fijo como ASCII no es óptima. En tal situación, muchas personas buscan la codificación de Huffman . Esto es óptimo si desea un código fijo (sin prefijo) con un número entero de bits por carácter.

Sin embargo, la codificación aritmética es aún mejor. En términos generales, es capaz de usar bits "fraccionales" para codificar información. Hay muchas guías de codificación aritmética disponibles en línea. Omitiremos los detalles aquí (especialmente de la implementación práctica, que puede ser un poco complicada desde una perspectiva de programación) debido a los otros recursos disponibles en línea, pero si alguien se queja, tal vez esta sección se pueda desarrollar más.

Si uno tiene texto realmente generado por un modelo de lenguaje conocido, entonces la codificación aritmética proporciona una codificación esencialmente óptima del texto de ese modelo. En cierto sentido, esto "resuelve" el problema de compresión para ese modelo. (Por lo tanto, en la práctica, el problema principal es que el modelo no se conoce, y algunos modelos son mejores que otros para modelar texto humano). Si no se permitió cometer errores en este concurso, entonces en el lenguaje de la sección anterior , una forma de producir una solución a este desafío habría sido usar un codificador aritmético para generar un archivo de "sugerencias" a partir del modelo de lenguaje y luego usar un decodificador aritmético como "intérprete".

En esta codificación esencialmente óptima, terminamos gastando -log_2 (p) bits para un personaje con probabilidad p, y la tasa de bits general de la codificación es la entropía de Shannon . Esto significa que un carácter con probabilidad cercana a 1/2 toma aproximadamente un bit para codificar, mientras que uno con probabilidad 1/1000 toma aproximadamente 10 bits (porque 2 ^ 10 es aproximadamente 1000).

Pero la métrica de puntuación para este desafío fue bien elegida para evitar la compresión como la estrategia óptima. Tendremos que encontrar alguna forma de cometer algunos errores como compensación para obtener un archivo de sugerencias más corto. Por ejemplo, una estrategia que podría probarse es una estrategia de ramificación simple: generalmente intentamos usar la codificación aritmética cuando podemos, pero si la distribución de probabilidad del modelo es "mala" de alguna manera, simplemente adivinamos el carácter más probable y no lo hacemos ' Intenta codificarlo.

¿Por qué cometer errores?

Analicemos el ejemplo anterior para motivar por qué podríamos querer cometer errores "intencionalmente". Si usamos codificación aritmética para codificar el carácter correcto, gastaremos aproximadamente un bit en el caso de un Eo T, pero unos diez bits en el caso de un A.

En general, esta es una codificación bastante buena, gastando un poco más de un bit por personaje, aunque hay tres posibilidades; básicamente, Aes bastante improbable y no terminamos gastando sus diez bits correspondientes con demasiada frecuencia. Sin embargo, ¿no sería bueno si pudiéramos cometer un error en el caso de un A? Después de todo, la métrica para el problema considera que 1 byte = 8 bits de longitud son equivalentes a 2 errores; Por lo tanto, parece que uno debería preferir un error en lugar de gastar más de 8/2 = 4 bits en un personaje. ¡Gastar más de un byte para guardar un error definitivamente suena subóptimo!

El mecanismo de "rebobinado"

Esta sección describe el principal aspecto inteligente de esta solución, que es una forma de manejar conjeturas incorrectas sin costo alguno.

Por el simple ejemplo que hemos estado analizando, el mecanismo de rebobinado es particularmente sencillo. El intérprete lee un bit del archivo de sugerencias. Si es un 0, adivina E. Si es un 1, adivina T. La próxima vez que se llame, verá cuál es el carácter correcto. Si el archivo de sugerencias está bien configurado, podemos asegurarnos de que en el caso de una Eo T, el intérprete adivine correctamente. ¿Pero que pasa A? La idea del mecanismo de rebobinado es simplemente no codificar Aen absoluto . Más precisamente, si el intérprete luego se entera de que el carácter correcto era un A, metafóricamente " rebobina la cinta": devuelve el bit que leyó anteriormente. El bit que lee tiene la intención de codificar EoT, Pero no ahora; Se usará más tarde. En este simple ejemplo, esto básicamente significa que sigue adivinando el mismo personaje ( Eo T) hasta que lo haga bien; luego lee otro bit y continúa.

La codificación para este archivo de sugerencias es muy simple: convierta todos los Es en 0 bits Tys en 1 bits, todo mientras ignora los As por completo. Mediante el análisis al final de la sección anterior, este esquema comete algunos errores pero reduce el puntaje general al no codificar ninguno de los As. Como efecto más pequeño, también ahorra en la longitud del archivo de sugerencias, porque terminamos usando exactamente un bit para cada uno Ey T, en lugar de un poco más de un bit.

Un pequeño teorema

¿Cómo decidimos cuándo cometer un error? Supongamos que nuestro modelo nos da una distribución de probabilidad P para el siguiente carácter. Vamos a separar los posibles personajes en dos clases: codificados y no codificados . Si el carácter correcto no está codificado, terminaremos usando el mecanismo de "rebobinado" para aceptar un error sin costo alguno. Si se codifica el carácter correcto, usaremos alguna otra distribución Q para codificarlo mediante codificación aritmética.

Pero, ¿qué distribución Q deberíamos elegir? No es demasiado difícil ver que los caracteres codificados deberían tener una probabilidad más alta (en P) que los caracteres no codificados. Además, la distribución Q solo debe incluir los caracteres codificados; después de todo, no estamos codificando los otros, por lo que no deberíamos estar "gastando" entropía en ellos. Es un poco más complicado ver que la distribución de probabilidad Q debería ser proporcional a P en los caracteres codificados. Poner estas observaciones juntas significa que debemos codificar los caracteres más probables pero posiblemente no los caracteres menos probables, y que Q es simplemente P reescalado en los caracteres codificados.

Además, resulta que hay un teorema genial sobre qué "corte" se debe elegir para los caracteres de codificación: debe codificar un carácter siempre que sea al menos 1 / 5.393 tan probable como los otros caracteres codificados combinados. Esto "explica" la aparición de la constante aparentemente aleatoria 5.393más cerca del final del programa anterior. El número 1 / 5.393 ≈ 0.18542 es la solución a la ecuación -p log (16) - p log p + (1 + p) log (1 + p) = 0 .

Quizás sea una idea razonable escribir este procedimiento en código. Este fragmento está en C ++:

// Assume the model is computed elsewhere.
unordered_map<char, double> model;

// Transform p to q
unordered_map<char, double> code;
priority_queue<pair<double,char>> pq;
for( char c : CHARS )
    pq.push( make_pair(model[c], c) );
double s = 0, p;
while( 1 ) {
    char c = pq.top().second;
    pq.pop();
    p = model[c];
    if( s > 5.393*p )
        break;
    code[c] = p;
    s += p;
}
for( auto& kv : code ) {
    char c = kv.first;
    code[c] /= s;
}

Poniendolo todo junto

Desafortunadamente, la sección anterior es un poco técnica, pero si juntamos todas las otras piezas, la estructura es la siguiente. Cada vez que se le pide al programa que prediga el siguiente carácter después de un carácter correcto dado:

  1. Agregue el carácter correcto al prefijo correcto conocido de Moby Dick.
  2. Actualice el modelo (Markov) del texto.
  3. La salsa secreta : si la suposición anterior era incorrecta, rebobine el estado del decodificador aritmético a su estado antes de la suposición anterior.
  4. Pídale al modelo de Markov que prediga una distribución de probabilidad P para el siguiente carácter.
  5. Transforme P a Q utilizando la subrutina de la sección anterior.
  6. Solicite al decodificador aritmético que decodifique un carácter del resto del archivo de sugerencias, de acuerdo con la distribución Q.
  7. Adivina el personaje resultante.

La codificación del archivo de sugerencias funciona de manera similar. En ese caso, el programa sabe cuál es el siguiente carácter correcto. Si es un carácter que debe codificarse, entonces, por supuesto, uno debe usar el codificador aritmético en él; pero si es un carácter no codificado, simplemente no actualiza el estado del codificador aritmético.

Si comprende los antecedentes teóricos de la información, como las distribuciones de probabilidad, la entropía, la compresión y la codificación aritmética, pero intentó y no entendió esta publicación (excepto por qué el teorema es verdadero), háganoslo saber y podemos intentar aclarar las cosas. ¡Gracias por leer!

A. Rex
fuente
8
Wow, impresionante respuesta. ¿Supongo que se necesita código adicional para generar el Barchivo? Si es así, ¿puede incluir eso en su respuesta?
Nathaniel
8
¡Excelente! La primera (y hasta ahora la única) respuesta para romper la barrera del puntaje de 500k.
ShreevatsaR
55
"Tersed the shite whale" Dios mío, estoy llorando
Phill
55
Dado que no se publicaron nuevas respuestas durante el período de recompensa, lo otorgo a su respuesta, como el mejor puntaje y el enfoque más sofisticado. Si alguna vez tiene tiempo, realmente agradecería una explicación más profunda de cómo funciona esta respuesta, es decir, ¿qué es exactamente el algoritmo?
Nathaniel
2
@Nathaniel: Agregué una explicación a esta publicación. Avíseme si cree que es lo suficientemente detallado como para reproducir la solución usted mismo.
A. Rex
77

Python 3, 2 · 267 + 510193 = 510727

Vaticinador

def p():
 d={};s=b''
 while 1:
  p={0:1};r=range(len(s)+1)
  for i in r:
   for c,n in d.setdefault(s[:i],{}).items():p[c]=p.get(c,1)*n**b'\1\6\f\36AcWuvY_v`\270~\333~'[i]
  c=yield max(sorted(p),key=p.get)
  for i in r:e=d[s[:i]];e[c]=e.get(c,1)+1
  s=b'%c'%c+s[:15]

Utiliza una combinación bayesiana ponderada del orden 0,…, 16 modelos de Markov, con pesos [1, 6, 12, 30, 65, 99, 87, 117, 118, 89, 95, 118, 96, 184, 126, 219, 126].

El resultado no es muy sensible a la selección de estos pesos, pero los optimicé porque pude, utilizando el mismo algoritmo de escalada de aceptación tardía que utilicé en mi respuesta a "Formar una mayoría del Senado" , donde cada mutación candidata es solo un incremento de ± 1 a un solo peso.

Código de prueba

with open('whale2.txt', 'rb') as f:
    g = p()
    wrong = 0
    a = next(g)
    for b in f.read():
        wrong += a != b
        a = g.send(b)
    print(wrong)
Anders Kaseorg
fuente
2
La herramienta adecuada para el trabajo. Gran puntaje. Buena esa.
agtoever
1
Posible aclaración: b"\0\3\6\r\34'&-20'\22!P\n[\26"es la representación ascii de los pesos, donde se escapan pequeños valores no imprimibles en octal.
Coeur
He actualizado la pregunta con una versión del archivo donde el texto no está envuelto; puede intentar volver a ejecutar su código en eso (podría hacerlo un poco mejor)
Nathaniel
3
Gracias por esa explicación: si pudieras editar una sinopsis de la pregunta, sería genial. (La experiencia con mi desafío anterior Paint Starry Night es que estos procedimientos de optimización son la parte más interesante de las respuestas, por lo que es mucho mejor si las respuestas incluyen el código utilizado para hacer eso y una explicación. Incluí una regla en ambas desafía a decir que deberían.)
Nathaniel
1
@ Christoph La combinación de mi modelo en realidad es una media geométrica ponderada. Pero el promedio de PAQ en el dominio logístico es ligeramente diferente: tendré que ver si eso es mejor.
Anders Kaseorg
55

Python 3 , 2 * 279 + 592920 = 593478 2 * 250 + 592467 = 592967 2 * 271 + 592084 = 592626 2 * 278 + 592059 = 592615 2 * 285 + 586660 = 587230 2 * 320 + 585161 = 585801 2 * 339 + 585050 = 585728

d=m={}
s=1
w,v='',0
def f(c):
 global w,m,v,s,d
 if w not in m:m[w]={}
 u=m[w];u[c]=c in u and 1+u[c]or 1;v+=1;q=n=' ';w=w*s+c;s=c!=n
 if w in m:_,n=max((m[w][k],k)for k in m[w])
 elif s-1:n=d in'nedtfo'and't'or'a'
 elif'-'==c:n=c
 elif"'"==c:n='s'
 elif'/'<c<':':n='.'
 if v>4*(n!=q)+66:n='\n'
 if s:d=c
 if c<q:w=w[:-1]+q;v=s=0
 return n

Pruébalo en línea!

Una función que usa variables globales. A medida que avanza, construye un modelo a nivel de palabra: dado lo que se ha visto hasta ahora en esta palabra , ¿cuál es el siguiente carácter más común? A medida que entra más información, aprende palabras comunes del texto bastante bien, y también aprende el carácter más común para comenzar la siguiente palabra.

Por ejemplo:

  • Si lo que se ha visto hasta ahora es 'Captai', predice una "n"
  • Si es "Capitán" predice un espacio
  • Si es el comienzo de una palabra, y la última palabra fue "Capitán", predice una 'A'
  • Si la palabra hasta ahora es 'A', predice una 'h' (y luego 'a' y 'b'; de manera similar para 'C').

Al principio no funciona muy bien, pero al final salen grandes partes de palabras reales. La opción de reserva es un espacio, y después de un solo espacio es una "a", a menos que la letra anterior sea una de "nedtfo", un dígito o un guión o apóstrofe. También predice agresivamente los saltos de línea después de 71 caracteres, o si se esperaba un espacio después de 66. Ambos se ajustaron a los datos ("t" es mucho más común después de un espacio, pero ya se ha predicho más a menudo, así que " un "es una mejor suposición fuera de esos seis casos especiales).

Aprender qué pares de palabras se unieron y presentar el mapeo resultó no valer la pena.


Termina con un texto como este:

nl tneund his    I woi tis tnlost ahet toie tn tant  wod, ihet taptain Ahab ses
 snd t
oeed Sft   aoid thshtego    Io, fhe soie tn tant  tot the soie      ahe sewbtoon
swn tagd  aoths eatmved fhe sewbtoon wor ta  I sfey  aote of totsonld nive betse
d ahe
hate Whale iorst  Ihe e ioi beaos! -there soi beaos! -there soi beaos!

que corresponde a esta parte de la entrada:

todo a su alrededor.

"Lo vi casi en ese mismo instante, señor, que el Capitán Ahab lo hizo, y grité", dijo Tashtego.

"No es el mismo instante; no es lo mismo, no, el doblón es mío, Fate me reservó el doblón. Yo solo; ninguno de ustedes podría haber criado a la Ballena Blanca primero. ¡Allí ella sopla! ¡Allí sopla!" -¡Allí ella sopla!

Puedes ver dónde los sustantivos propios en particular salen bastante bien, pero los extremos de las palabras también son en su mayoría correctos. Cuando se ve "dou" espera "duda", pero una vez que aparece la "l" se pone "doblón".

Si lo ejecuta por segunda vez con el mismo modelo que acaba de construir, inmediatamente obtiene otros 92k correctos (51.7% -> 59.3%), pero siempre es inferior al 60% desde la segunda iteración.


El código de medición está en el enlace TIO, o aquí hay una versión un poco mejor:

total = 0
right = 0
with open('whale.txt') as fp:
    with open('guess.txt', 'w') as dest:
        for l in fp.readlines():
            for c in l:
                last = c
                if p == c: right += 1
                n = f(c)
                p = n
                total += 1
                dest.write(n)
                if total % 10000 == 0:
                    print('{} / {} E={}\r'.format(right, total, total-right), end='')
print('{} / {}: E={}'.format(right, total, total - right))

guess.txt tiene la salida adivinada al final.

Michael Homer
fuente
3
Este es un excelente enfoque!
Skyler
2
demasiado <s> </s>;)
FantaC
1
+1 porque este enfoque me recordó el algoritmo de compresión LZW.
Marcos
25

C ++, puntaje: 2 * 132 + 865821 = 866085

¡Gracias a @Quentin por guardar 217 bytes!

int f(int c){return c-10?"t \n 2  sS \n  -  08........       huaoRooe oioaoheu thpih eEA \n   neo    enueee neue hteht e"[c-32]:10;}

Una solución muy simple que, dado un carácter, solo genera el carácter que aparece con más frecuencia después del carácter de entrada.

Verifique el puntaje con:

#include <iostream>
#include <fstream>

int f(int c);

int main()
{
    std::ifstream file;
    file.open("whale2.txt");

    if (!file.is_open())
        return 1;

    char p_ch, ch;
    file >> std::noskipws >> p_ch;
    int incorrect = 0;
    while (file >> std::noskipws >> ch)
    {
        if (f(p_ch) != ch)
            ++incorrect;
        p_ch = ch;
    }

    file.close();

    std::cout << incorrect;
}

Editar: el uso whale2.txtda una mejor puntuación.

Steadybox
fuente
55
Puede traducir esta matriz a un literal de cadena e insertarla directamente en lugar de Lguardar un montón de caracteres :)
Quentin
@Quentin Gracias! Ahora me pregunto por qué no pensé en eso en primer lugar ...
Steadybox
20

Python, 2 * 516 + 521122 = 522154

Algoritmo:

Otra presentación de Python, este algoritmo calcula la próxima letra más probable mirando secuencias de longitud 1, ..., l. Se usa la suma de probabilidades, y hay algunos trucos para obtener mejores resultados.

from collections import Counter as C, defaultdict as D
R,l=range,10
s,n='',[D(C) for _ in R(l+1)]
def A(c):
 global s;s+=c;
 if len(s)<=l:return ' '
 P=D(lambda:0)
 for L in R(1,l+1):
  w=''.join(s[-L-1:-1]);n[L][w].update([c]);w=''.join(s[-L:])
  try:
   q,z=n[L][w].most_common(1)[0];x=sum(list(n[L][w].values()))
  except IndexError:continue
  p=z/x
  if x<3:p*=1/(3-x)
  P[q]+=p
 if not P:return ' '
 return max(P.items(),key=lambda i:i[1])[0]
import this, codecs as d
[A(c) for c in d.decode(this.s, 'rot-13')]

Resultados:

Principalmente galimatías, aunque puede ver que se repite en la frase ocasional, como "Padre Mapple".

errors: 521122
TRAINING:
result:  tetlsnowleof the won -opes  aIther Mapple,woneltnsinkeap hsd   lnd the  thth a shoey,aeidorsbine ao
actual: ntal knobs of the man-ropes, Father Mapple cast a look upwards, and then with a truly sailor-like bu
FINAL:
result: mnd wnd round  ahe   ind tveryaonsracting th ards the sol ens-ike aeock tolblescn the sgis of thet t
actual: und and round, then, and ever contracting towards the button-like black bubble at the axis of that s

Código de prueba:

Bastante simple, muestra algunos ejemplos del texto en diferentes puntos. Utiliza whale2.txt, ya que esto evita cierta lógica adicional para calcular nuevas líneas.

from minified import A

def score(predict, text):
    errors = 0
    newtext = []
    for i, (actual, current) in  enumerate(zip(text[1:], text[:-1])):
        next = predict(current)
        errors += (actual != next)
        newtext.append(next)
        if (i % (len(text) // 100) == 0):
            print ('.', end='', flush=True)
    return errors, ''.join(newtext)

t = open('whale2.txt')
text = t.read()
err2, text2 = score(A, text)
print('errors:', err2)
print("TRAINING:")
print(text2[100000:100100].replace('\n', '\\n'))
print(text1[100001:100101].replace('\n', '\\n'))
print("FINAL:")
print(text2[121400:1215500].replace('\n', '\\n'))
print(text[121401:1215501].replace('\n', '\\n'))
usuario2699
fuente
3
Bienvenido al sitio! Esta es una fantástica primera presentación. :)
DJMcMayhem
@DJMcMayhem, gracias por la bienvenida. He disfrutado viendo por un tiempo ahora, este es el primer concurso en llamar mi atención para una entrada.
user2699
19

C (gcc) , 679787 652892

84 76 bytes, 679619 652740 conjeturas incorrectas

p[128][128][128][128];a,b,c,d;g(h){p[a][b][c][d]=h;h=p[a=b][b=c][c=d][d=h];}

Pruébalo en línea!

Actualización: ~ 27000 puntos con archivo actualizado, 16 puntos (8 bytes) con una función mejor desarrollada.

Explicación

La forma en que esto funciona es que a medida que el código se ejecuta a través del texto, memoriza el último carácter que finalizó cualquier secuencia de 4 caracteres y devuelve ese valor. Algo similar al enfoque de Arnauld anterior, pero se basa en la probabilidad inherente de que dos secuencias de 4 caracteres dadas terminen de la misma manera.

De-golf:

p[128][128][128][128];
a,b,c,d;
g(h){
    p[a][b][c][d]=h; // Memorize the last character.
    h=p[a=b][b=c][c=d][d=h]; // Read the guess. We save several
                             // bytes with the assignments inside indices.
}

fuente
... El enlace TIO es inútil. Entonces, ¿la función devuelve el valor de la última asignación?
user202729
Permítanme editar la respuesta con una explicación, luego :)
1
@Rogem He agregado una versión de golf (que hice porque tampoco podía seguirla). Espero que esto no te moleste, pero por favor retrocede si lo deseas.
Adam Davis
@AdamDavis en la mayoría de las implementaciones de C, todas las variables globales comienzan en cero. Es un comportamiento indefinido, por lo que solo se usa en code-golf.
NieDzejkob
1
@NieDzejkob Ah, tienes razón, ¡gracias! "ANSI-C requiere que todas las variables estáticas / globales no inicializadas se inicialicen con 0".
Adam Davis
16

sh + bzip2, 2 * 364106 = 728212

2 * 381249 + 0 = 762498

dd if=$0 bs=1 skip=49|bunzip2&exec cat>/dev/null

seguido por el archivo bzip2-comprimido whale2.txt con el primer byte perdido

Ignora su entrada; da como resultado la respuesta correcta. Esto proporciona una línea de base en un extremo; daniero proporciona una línea de base en el otro extremo.

Script de constructor:

#!/bin/sh
if [ $# -ne 3 ]
then
    echo "Usage $0 gen.sh datafile output.sh"
    exit 1
fi

cat $1 > $3
dd ibs=1 if=$2 skip=1 | bzip2 -9 >> $3
chmod +x $3

Arnés de prueba de E / S (tcc; corte la primera línea para gcc). Cualquiera puede utilizar este arnés de prueba en una plataforma adecuada que envíe un programa completo que espere lectura / escritura de E / S. Utiliza la E / S byte-at-a-time para evitar trampas. El programa secundario debe vaciar la salida después de cada byte para evitar el bloqueo.

#!/usr/bin/tcc -run
#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <unistd.h>
#include <errno.h>

int main(int argc, char **argv)
{
    volatile int result;
    int readfd[2];
    int writefd[2];
    int cppid;
    int bytecount;
    char c1, c2, c3;
    if (argc != 2) {
        printf("write X approximately -- service host\n");
        printf("Usage: %s serviceprocessbinary < source.txt\n", argv[0]);
        return 1;
    }
    /* Start service process */
    if (pipe(readfd)) {
        perror("pipe()");
        return 3;
    }
    if (pipe(writefd)) {
        perror("pipe()");
        return 3;
    }
    result = 0;
    if (!(cppid = vfork())) {
        char *argtable[3];
        argtable[0] = argv[1];
        argtable[1] = NULL;
        dup2(readfd[0], 0);
        dup2(writefd[1], 1);
        close(readfd[1]);
        close(writefd[0]);
        close(readfd[0]);
        close(writefd[1]);
        execvp(argv[1], argtable);
        if (errno == ENOEXEC) {
            argtable[0] = "/bin/sh";
            argtable[1] = argv[1];
            argtable[2] = NULL;
            /* old standard -- what isn't an executable
             * can be exec'd as a /bin/sh script */
            execvp("/bin/sh", argtable);
            result = ENOEXEC;
        } else {
            result = errno;
        }
        _exit(3);
    } else if (cppid < 0) {
        perror("vfork()");
        return 3;
    }
    if (result) {
        errno = result;
        perror("execvp()");
        return 3;
    }
    close(readfd[0]);
    close(writefd[1]);
    /* check results */
    read(0, &c2, 1);
    bytecount = 1;
    errno = 0;
    while (read(0, &c1, 1) > 0) {
        write(readfd[1], &c2, 1);
        if (read(writefd[0], &c3, 1) <= 0) {
            printf("%d errors (%d bytes)\n", result, bytecount);
            if (errno == 0)
                fprintf(stderr, "pipe: unexpected EOF\n");
            else
                perror("pipe");
            return 3;
        }
        if (c3 != c1)
            ++result;
        c2 = c1;
        ++bytecount;
    }
    printf("%d errors (%d bytes)\n", result, bytecount);
    return 0;
}
Joshua
fuente
66
Creo que lo que está preguntando es: ¿cómo no viola la but may not load any other external files, and your code may not access the whale.txt file in any way other than described above.cláusula?
8
@Rogem Los datos comprimidos se colocan después de lo que se muestra aquí, y el código accede a sí mismo.
user202729
44
La pregunta dice: "Su envío será un programa o función (etc.) que se invocará o invocará varias veces. Cuando se llama por el nthtiempo, se le dará el enésimo carácter de whale.txto whale2.txty debe generar su conjetura para el (n+1)thpersonaje." - ¿Cómo se cumple este requisito? El código muestra el texto completo de whale.txtcada vez que se ejecuta.
axiac
1
@axiac "todo está bien, siempre que su programa siempre dé un byte de salida antes de recibir su próximo byte de entrada".
user202729
55
@axiac dado el arnés de prueba, estoy feliz de considerar enviar el programa un byte desde STDIN como "llamarlo o invocarlo". Lo importante es que el programa devuelve un byte de salida después de cada byte de entrada, que este realmente hace, cuando se ejecuta a través del arnés de prueba. Como dice la pregunta, "todo está bien, siempre y cuando su programa siempre dé un byte de salida antes de recibir su próximo byte de entrada".
Nathaniel
13

Python 3 , 879766

F=[[0]*123for _ in range(123)]
P=32
def f(C):global P;C=ord(C);F[P][C]+=1;P=C;return chr(max(enumerate(F[C]),key=lambda x:x[1])[0])

Pruébalo en línea!


... Los /// respuesta que imprime un espacio obtiene 10 votos a favor, mientras que mi código solo puede obtener 3 ...

Explicación:

Para cada personaje, el programa:

  • incrementar frequency[prev][char]
  • Encuentra el personaje que aparece más veces en frequency[char]
  • y sacarlo.

  • Código no protegido en el enlace TIO, comentado.
  • El código es de 131 bytes.
  • El código que se ejecuta en mi máquina informa:
879504 / 1215235
Time: 62.01348257784468

que tienen la puntuación total

2*131 + 879504 = 879766

Como no hay forma de cargar un archivo grande en TIO (excepto preguntarle a Dennis), el ejemplo que se ejecuta en el enlace TIO solo ejecuta el programa para una pequeña parte del texto.

En comparación con la respuesta anterior, esta tiene 362 caracteres incorrectos más, pero el código es más corto en 255 bytes. El multiplicador hace que mi presentación tenga una puntuación más baja.

usuario202729
fuente
13

C #, 378 * 2 + 569279 = 570035

using System.Collections.Generic;using System.Linq;class P{Dictionary<string,Dictionary<char,int>>m=new
Dictionary<string,Dictionary<char,int>>();string b="";public char N(char
c){if(!m.ContainsKey(b))m[b]=new Dictionary<char,int>();if(!m[b].ContainsKey(c))m[b][c]=0;m[b][c]++;b+=c;if(b.Length>4)b=b.Remove(0,1);return
m.ContainsKey(b)?m[b].OrderBy(k=>k.Value).Last().Key:' ';}}

Este enfoque utiliza una tabla de búsqueda para aprender el carácter más común que sigue a una cadena dada. Las teclas de la tabla de búsqueda tienen un máximo de 4 caracteres, por lo que la función primero actualiza la tabla de búsqueda con el carácter actual y luego simplemente verifica qué carácter es más probable que suceda después de los 4 anteriores, incluido el actual. . Si esos 4 caracteres no se encuentran en la tabla de búsqueda, imprime un espacio.

Esta versión utiliza el whale2.txtarchivo, ya que mejora en gran medida el número de conjeturas exitosas.

El siguiente es el código utilizado para probar la clase:

using System;
using System.IO;
using System.Text;

public class Program
{
    public static void Main(string[] args)
    {
        var contents = File.OpenText("whale2.txt").ReadToEnd();
        var predictor = new P();

        var errors = 0;
        var generated = new StringBuilder();
        var guessed = new StringBuilder();
        for (var i = 0; i < contents.Length - 1; i++)
        {
            var predicted = predictor.N(contents[i]);
            generated.Append(predicted);
            if (contents[i + 1] == predicted)
                guessed.Append(predicted);
            else
            {
                guessed.Append('_');
                errors++;
            }
        }

        Console.WriteLine("Errors/total: {0}/{1}", errors, contents.Length);
        File.WriteAllText("predicted-whale.txt", generated.ToString());
        File.WriteAllText("guessed-whale.txt", guessed.ToString());

        Console.ReadKey();
    }
}

El código se ejecuta en apenas 2 segundos. Solo para el registro, esto es lo que obtengo cuando modifico el tamaño de las claves de la tabla de búsqueda (incluye los resultados de una segunda ejecución sin restablecer el modelo):

Size   Errors   Errors(2)
-------------------------
1      866162   865850
2      734762   731533
3      621019   604613
4      569279   515744
5      579446   454052
6      629829   396855
7      696912   335034
8      765346   271275
9      826821   210552
10     876471   158263

Sería interesante saber por qué un tamaño de clave de 4 caracteres es la mejor opción en este algoritmo.

Comparación de texto

Original:

"And did none of ye see it before?" cried Ahab, hailing the perched men all around him.

"I saw him almost that same instant, sir, that Captain Ahab did, and I cried out," said Tashtego.

"Not the same instant; not the same--no, the doubloon is mine, Fate reserved the doubloon for me. I only; none of ye could have raised the White Whale first. There she blows!--there she blows!--there she blows! There again!--there again!"

Recreado:

"Tnd tes note of to seamtn we ore  
sried thab  wedleng the srriead te  a l tneund tes  
"T day tim t lost shet toie tn tand  aor, ahet taptain thab sid  tnd t waued tnt   said teshtego  
"To, ahe shme tn tand  aot the shme whot nhe sewbteodsan tagd  althsteatnved the sewbteodsaor te, I hncy  aote of to sanld bave beised the shate Whale iorst  Bhe e ati boaos  -the   ati boaos  -the   ati boaos  the e anains -ahe   anains 

Suposiciones:

"_nd ___ no_e of __ se____ _e_ore____ried _hab_ ___l_ng the __r___d _e_ a_l ___und _____
"_ _a_ _im ___ost _h_t ___e _n_tan__ __r, _h_t _aptain _hab _id_ _nd _ ___ed __t__ said __shtego__
"_o_ _he s_me _n_tan__ _ot the s_me___o_ _he ___b__o____ _____ __t___e___ved the ___b__o___or _e_ I _n_y_ _o_e of __ ___ld _ave __ised the _h_te Whale __rst_ _he_e ___ b___s__-the__ ___ b___s__-the__ ___ b___s_ _he_e a_ain__-_he__ a_ain__

Cambiar registro

  • 569279 : se modificó whale2.txty, por lo tanto, se eliminó la optimización.
  • 577366 : optimizado con código que intentó adivinar cuándo devolver un avance de línea.
  • 590354 - versión original.
Charlie
fuente
44
¡Gracias por mostrar la variación a medida que cambia el tamaño de la clave y el umbral de la columna!
Jeremy Weirich
He actualizado la pregunta con una versión del archivo donde el texto no está envuelto. Probablemente pueda guardar algunos puntos al usarlo
Nathaniel
@Nathaniel lo hace de hecho. He actualizado la respuesta.
Charlie
Puede guardar algunos bytes usando var en lugar de declarar los tipos.
Ed T
1
A medida que el tamaño de la clave aumenta, el número de aciertos versus errores se reducirá y, por lo tanto, se generarán más espacios cuando una tecla más corta podría haber adivinado el carácter correcto. A medida que el tamaño de la clave se reduce, las suposiciones individuales son menos precisas para los segmentos que coinciden. Sospecho que es por eso que una longitud de cuatro es óptima. Si mantuvo claves de múltiples longitudes y usó coincidencias más cortas cuando no hay disponibles más largas, entonces espero que la tasa de aciertos (y, por lo tanto, la puntuación) se mejore enormemente en longitudes de clave más largas.
Jeffrey L Whitledge
11

Java 7, 1995 caracteres, (1995 * 2 + 525158) 529148

Java es una mierda para programas pequeños. De todos modos, probé varios enfoques extremadamente complejos y complicados que produjeron resultados sorprendentemente malos. Posteriormente volví y simplemente hice un enfoque simple, que resultó en un tamaño de programa más pequeño y mejores resultados.

Este enfoque es realmente extremadamente simple. Alimenta ciegamente los caracteres x anteriores (además de todas las subcadenas de esos caracteres) en una tabla hash, asignada al carácter actual. Luego realiza un seguimiento de qué patrones predicen con mayor precisión el carácter actual. Si los patrones que preceden a ciertos personajes se encuentran varias veces, tienen éxito en predecir el personaje. Da prioridad a las cadenas más largas y da prioridad a cualquier carácter que siga con mayor frecuencia una cadena dada. Este algoritmo no sabe nada sobre el tipo de documento o el idioma inglés.

Me decidí a usar 9 caracteres e intentar unir palabras enteras con esos 9 caracteres anteriores cuando sea posible. Cuando no intenta hacer una coincidencia de palabras dentro de las cadenas, la longitud óptima es de 6 caracteres, produciendo varios miles de predicciones más.

Una observación interesante fue que el uso de 20 caracteres resultó en malas predicciones la primera vez, pero con una precisión del 99.9 por ciento en los pases posteriores. El algoritmo fue básicamente capaz de memorizar el libro en trozos superpuestos de 20 bytes, y esto fue lo suficientemente distinto como para permitirle recordar todo el libro de un personaje a la vez.

  • (1950 * 2 + 532919) 536819
  • (2406 * 2 + 526233) 531045 comprobando la puntuación para hacer mejores conjeturas
  • (1995 * 2 + 525158) 529148 más retoques, jugaron un poco de palabrería

package mobydick; import java.util.HashMap; public class BlindRankedPatternMatcher { String previousChars = ""; int FRAGLENGTH = 9; HashMap > patternPredictor = new HashMap<>(); void addWordInfo(String key, String prediction) { HashMap predictions = patternPredictor.get(key); if (predictions == null) { predictions = new HashMap(); patternPredictor.put(key, predictions); } WordInfo info = predictions.get(prediction); if (info == null) { info = new WordInfo(prediction); predictions.put(prediction, info); } info.freq++; } String getTopGuess (String pattern) { if (patternPredictor.get(pattern) != null) { java.util.List predictions = new java.util.ArrayList<>(); predictions.addAll(patternPredictor.get(pattern).values()); java.util.Collections.sort(predictions); return predictions.get(0).word; } return null; 
} String mainGuess() { 
if (trimGuess(",") != null) return trimGuess(","); if (trimGuess(";") != null) return trimGuess(";"); 
if (trimGuess(":") != null) return trimGuess(":"); 
if (trimGuess(".") != null) return trimGuess("."); if (trimGuess("!") != null) return trimGuess("!"); if (trimGuess("?") != null) return trimGuess("?"); if (trimGuess(" ") != null) return trimGuess(" "); for (int x = 0;x< previousChars.length();x++) { String tg = getTopGuess(previousChars.substring(x)); if (tg != null) { return tg; } } return "\n"; } String trimGuess(String c) { if (previousChars.contains(c)) { 
String test = previousChars.substring(previousChars.indexOf(c)); return getTopGuess(test); } return null; } public String predictNext(String newChar) { if (previousChars.length() < FRAGLENGTH) { previousChars+= newChar; } else { for (int x = 0; x addWordInfo(previousChars.substring(x), newChar); } previousChars = previousChars.substring(1) + newChar; } return mainGuess(); 
} class WordInfo implements Comparable { public WordInfo (String text) { this.word = text; } 
String word; int freq = 0; @Override public int compareTo(WordInfo arg0) { return Integer.compare(arg0.freq, this.freq); }
Jim W
fuente
Esa es una puntuación bastante buena para un lenguaje tan detallado.
DJMcMayhem
1
Pensé que valía la pena intentarlo ya que el tamaño del archivo da mucho margen de mejora en comparación con el tamaño del programa.
Jim W
3
Esto no es compilable bajo Java 7 (o cualquier versión de Java, por lo que vale). ¿Podrías arreglar tu código? Una vez hecho esto, con mucho gusto jugaré golf para que su puntaje mejore.
Olivier Grégoire
No probado, pero este debería ser exactamente el mismo código ligeramente golfizado: 950 bytes . Sin embargo, su código actual contenía bastantes errores, por lo que no estoy seguro de si completé todo correctamente. Nuevamente, no probado, así que solo compara las versiones para ver qué he cambiado / renombrado, y mira si todo sigue funcionando igual que tu código original. Sin embargo, definitivamente se puede jugar un poco más.
Kevin Cruijssen
Mierda, hice esto mientras estaba aburrido en mi antiguo trabajo y no me llevé el código. Tendré que echarle un vistazo para ver dónde está el error tipográfico.
Jim W
10

Python 3, 2 × 497 + 619608 = 620602 2 × 496 + 619608 = 620600

import operator as o
l=''
w=''
d={}
p={}
s=0
def z(x,y):
 return sorted([(k,v) for k,v in x.items() if k.startswith(y)],key=o.itemgetter(1))
def f(c):
 global l,w,d,p,s
 r=' '
 if c in' \n':
  s+=1
  if w in d:d[w]+=1
  else:d[w]=1
  if w:
   if l:
    t=l+' '+w
    if t in p:p[t]+=1
    else:p[t]=1
   n=z(p,w+' ')
   if n:g=n[-1];l=w;w='';r=g[0][len(l)+1]
   else:l=w;w='';r='t'
 else:
  w=w+c;m=z(p,w)
  if m:
   g=m[-1]
   if g[0]==w:
    if s>12:s=0;r='\n'
   else:r=g[0][len(w)]
 return r

Intenté esto de forma independiente, pero terminé con lo que efectivamente es una versión inferior de la respuesta de Michael Homer. Espero que eso no vuelva mi respuesta completamente obsoleta.

Esto construye con el tiempo un diccionario de palabras (definido crudamente como cadenas terminadas por o \n, distingue entre mayúsculas y minúsculas e incluye puntuación). Luego busca en este diccionario palabras que comiencen con lo que hasta ahora conoce de la palabra actual, ordena la lista resultante por frecuencia de ocurrencia (lentamente) y adivina que el siguiente carácter es el siguiente en la palabra coincidente más común. Si ya tenemos la palabra coincidente más común, o ya no existe una palabra coincidente, devuelve .

También crea un diccionario repugnantemente ineficiente de pares de palabras. Al llegar al límite de una palabra, adivina que el siguiente carácter es la primera letra de la segunda palabra en el par de palabras coincidentes más comunes, o tsi no hay una coincidencia. Sin embargo, no es muy inteligente. A continuación Moby, el programa adivina correctamente que el siguiente personaje esD , pero luego olvida todo sobre el contexto y generalmente termina llamando a la ballena "Pato Moby" (porque la palabra "holandés" parece ser más frecuente en la primera mitad del texto). ) Sería fácil solucionar esto priorizando los pares de palabras sobre las palabras individuales, pero espero que la ganancia sea marginal (ya que generalmente es correcta desde el tercer carácter en adelante, y los pares de palabras no son tan útiles en primer lugar).

Podría ajustar esto para que coincida mejor con el texto proporcionado, pero no creo que el ajuste manual del algoritmo basado en el conocimiento previo de la entrada esté realmente en el espíritu del juego, aparte de elegir t como el personaje alternativo después de un espacio ( y probablemente tampoco debería haber hecho eso), lo evité. Ignoré la longitud de línea conocida del archivo de entrada y en su lugar inserté\n después de cada 13 espacios; esto es casi seguro una coincidencia muy pobre, la intención principal era mantener la longitud de línea razonable en lugar de coincidir con la entrada.

El código no es exactamente rápido (~ 2 horas en mi máquina), pero en general obtiene la mitad de los caracteres correctos (49%). Espero que el puntaje sea marginalmente mejor si se ejecuta whale2.txt, pero no lo he hecho.

El inicio de la salida se ve así:

T t t t t t t t t L t t t tsher t t t ty t to t t te t t t t t tem t t t d b ta tnL te t tv tath a to tr t tl t l toe g to tf ahe gi te we th austitam ofd laammars, tn te to t tis nf tim oic t t th tn cindkth ae tf t d bh ao toe tr ai tat tnLiat tn to ay to tn hf to tex tfr toe tn toe kex te tia t l t l ti toe ke tf hhe kirl tou tu the tiach an taw th t t Wh tc t d t te the tnd tn tate tl te tf teu tl tn oan. HeAL. tn nn tf r t-H ta t WhALE.... S tn nort ts tlom rhe ka tnd Dr t t tALL th teuli th tis t-H taCTIONARY " t r t o t a t A t . t eALT t I t HLW t I t e t w t AO t t t AOLE, I T t t t ALE t w t t R t EK t T t R tSupplied by wnLw t t iit ty cce thet whe to tal ty tnd

pero al final, se parece un poco más a ... algo. Mi pasaje favorito casi al final del libro,

y como ninguno puede ser mío, déjame remolcar en pedazos, mientras te persigo, aunque atado a ti, ¡maldita ballena! ¡ASÍ, renuncio a la lanza! "

sale como

I dhrnery oyay ooom the woc Ihal iiw chshtego -tit my ti ddohe bidmer Hh, ho sheee opdeprendera toetis of tygd ahesgapdo tnep tnd tf y arosl tinl ahesgaorsltoak, and tidlhty ai p, cnd telas taep toip syst ho she tachlhe tnd tith ut ay Rnet hor bf toom the wist tord oaeve of ty nsst toip recked,hontain th, tingly toadh af tingly tike 'h, tot a hoet ty oh ost sreat ess iik in ty oh ost sremf Hew hiw"aoom tnl tou oolthert tyand . taoneoo sot an ao syad tytlows of ty oii e oor hoi tike and th ohes if oaped uoueid tf ty ooadh Ih ards the t houle lhesganl p tyt tpdomsuera tiile ah the wist t hrenelidtith the Ioom ti p s di dd o hoinbtn the Ior tid toie o hoetefy oist tyoakh on the Opr tnl toufin and tnl ti dd .mh tf ooueon gaor tnd todce tovther lon by tygd ait my the th aih tapce ciice toill moaneng she thesgh thmd th the thesgaoy d jiile YhE t hrve tpothe woerk "

Eso habría hecho que The Wrath of Khan fuera mucho más confuso. Y "solitario" → "hormigueo" es una sustitución particularmente satisfactoria.

Editar: guardado un byte eliminando un espacio extraño

Puntuación

#! /usr/bin/env python3
import sys
import os
import mobydick as moby


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)

total = 0
right = 0
real_char = ''
guess_char = 'T'
print('T',end='')
with open("whale.txt") as whale:
    while True:
        if real_char == guess_char:
            right += 1
        real_char = whale.read(1)
        if not real_char:
            eprint(str(right) + " / " + str(total) + " (" +
                str(right/total*100) + "%)")
            size = os.path.getsize("mobydick.py")
            eprint("Source size: " + str(size) + "B")
            eprint("Score: " + str(2*size + total - right))
            sys.exit(0)
        guess_char = moby.f(real_char)
        print(guess_char,end='')
        total += 1

Esto ejecuta el programa para el texto de Moby Dick y genera el texto "predicho" en stdout, y abusa de stderr para escribir la partitura. Recomiendo redirigir la salida a un archivo.

georgewatson
fuente
2
Bienvenido a PPCG!
Martin Ender
1
¿No lambda i:i[1]sería más barato que tratar con operator?
Draconis
@Draconis Casi seguro.
georgewatson el
9

C ++, 2 · 62829 + 318786 = 444444

Para ejecutar este programa, necesita este archivo aquí , que debe nombrarse C.

El programa usa la misma combinación de modelos de Markov que en nuestra respuesta anterior . Como antes, esta combinación es esencialmente el modelo de esta respuesta del usuario 2699 , pero con algunas pequeñas modificaciones.

Al ver cómo esta respuesta usa exactamente el mismo modelo que antes, la mejora es un mejor mecanismo teórico de información que el mecanismo de "rebobinado" descrito anteriormente. Esto le permite cometer menos errores y al mismo tiempo tener una longitud combinada más pequeña. El programa en sí no se juega mucho al golf porque no es el principal contribuyente a la puntuación.

El programa tiene una longitud de 2167 bytes (incluidas todas las pestañas para la sangría y muchos otros caracteres innecesarios, pero antes del código de prueba), y el archivo binario Ctiene una longitud de 60661 bytes, por lo que, según las reglas para calificar múltiples archivos , calificamos Lcomo 2167 + 60661 + 1 = 62829.

El programa tarda aproximadamente 8 minutos en ejecutarse en una m5.4xlargeinstancia en Amazon EC2 y utiliza un poco más de 16 GB de memoria. (Este uso excesivo de memoria no es necesario, simplemente tampoco lo optimizamos).

#include <map>
#include <queue>
#include <vector>
using namespace std;

FILE *in;
unsigned int a, b = -1, c, d;
string s, t;
double l, h = 1, x[128][129], y[129], m[128];
map<string, int> N;
map<string, double[128]> M;
int G, S;

int f(int C)
{
    int i, j;
    for (i = 0; i <= 20 && i <= S; i++) {
        t = s.substr(S - i);
        N[t]++;
        M[t][C]++;
    }
    s += C;
    S++;

    for (i = 0; i < 128; i++)
        m[i] = 0;

    int E = 0;
    for (i = 20; i >= 0; i--) {
        if (i > S)
            continue;
        t = s.substr(S - i);
        if (i <= 2 && E >= 100 && (i == 0 || t[0] != ' '))
            break;
        if (M.find(t) == M.end())
            continue;
        for (j = 0; j < 128; j++) {
            m[j] += M[t][j] / N[t];
        }
        E += N[t];
    }

    double r = 0;
    for (i = 0; i < 128; i++)
        r += m[i];
    for (i = 0; i < 128; i++)
        m[i] = m[i] / r;

    if (!in) {
        in = fopen("C", "r");
        for (i = 0; i < 4; i++)
            c = c << 8 | getc(in);
    } else {
        l = x[C][G]
            + (l - y[G]) * (x[C][G + 1] - x[C][G]) / (y[G + 1] - y[G]);
        h = x[C][G]
            + (h - y[G]) * (x[C][G + 1] - x[C][G]) / (y[G + 1] - y[G]);
    }

    priority_queue<pair<double, int>> q;
    for (i = 0; i < 128; i++) {
        q.push(make_pair(m[i], i));
    }

    int n = 0;
    double s = 0;
    while (q.size()) {
        i = q.top().second;
        q.pop();
        if (m[i] < s / (n + 15))
            break;
        s += m[i];
        n++;
    }

    r = 0;
    for (i = 0; i < 128; i++) {
        y[i + 1] = m[i] - s / (n + 15);
        if (y[i + 1] < 0)
            y[i + 1] = 0;
        r += y[i + 1];
    }
    for (i = 0; i < 128; i++)
        y[i + 1] /= r;

    for (i = 0; i < 128; i++) {
        r = 0;
        for (j = 0; j < 128; j++) {
            x[i][j + 1] = y[j + 1];
            if (i == j)
                x[i][j + 1] *= 16;
            r += x[i][j + 1];
        }
        for (j = 0; j < 128; j++)
            x[i][j + 1] /= r;
        x[i][0] = 0;
        for (j = 0; j < 128; j++)
            x[i][j + 1] += x[i][j];
    }

    y[0] = 0;
    for (i = 0; i < 128; i++)
        y[i + 1] += y[i];

    for (G = 0; G < 128; G++) {
        if (y[G + 1] <= l)
            continue;
        if (y[G + 1] < h) {
            d = a + (b - a) * ((h - y[G + 1]) / (h - l));
            if (c <= d) {
                b = d;
                l = y[G + 1];
            } else {
                a = d + 1;
                h = y[G + 1];
            }
            while ((a ^ b) < (1 << 24)) {
                a = a << 8;
                b = b << 8 | 255;
                c = c << 8 | getc(in);
            }
        }
        if (h <= y[G + 1])
            return G;
    }
}
// End submission here.  Test code follows.
int main()
{
    FILE *moby = fopen("whale2.txt", "r");

    int E = 0;
    int c = getc(moby);
    while (c != EOF) {
        int guess = f(c);
        c = getc(moby);
        if (c != guess)
            E++;
    }

    printf("E=\t%d\n", E);

    return 0;
}
A. Rex
fuente
7

Python 3, 526640

274 bytes, errores 526092 (usando whale2.txt). Esto definitivamente es capaz de mejorar aún más, pero ha alcanzado la etapa de "lo suficientemente bueno para publicar".

from collections import*
D=defaultdict
M=[D(lambda:D(int))for i in range(10)]
X=""
def f(c):
 global X;G=D(int)
 for L in range(10):
  M[L][X[:L]][c]+=1;N=M[L][(c+X)[:L]]
  if N:g=max(N,key=lambda k:(N[k],k));G[g]+=N[g]*L**8
 X=(c+X)[:10]
 return max(G,key=lambda k:(G[k],k))

La idea es almacenar las frecuencias de todas las ejecuciones de 2, 3, 4, ..., 10 caracteres. Para cada una de estas longitudes L, verificamos si los caracteres L-1 más recientes coinciden con un patrón almacenado; si es así, nuestra suposición g L es el siguiente carácter más frecuente que sigue ese patrón. Recopilamos hasta nueve conjeturas de esta manera. Para decidir qué suposición usar, ponderamos la frecuencia de cada patrón por su longitud hasta la octava potencia. Se elige la suposición con la mayor suma de frecuencias ponderadas. Si no hay patrones que coincidan, adivinamos el espacio.

(La longitud máxima del patrón y el exponente de ponderación se eligieron por prueba y error para dar la menor cantidad de conjeturas incorrectas).

Aquí está mi versión sin trabajo de trabajo en progreso:

from collections import defaultdict

PATTERN_MAX_LEN = 10
prev_chars = ""
patterns = [defaultdict(lambda:defaultdict(int))
            for i in range(PATTERN_MAX_LEN)]
# A pattern dictionary has entries like {" wh": {"i": 5, "a": 9}}

def next_char(c):
    global prev_chars
    guesses = defaultdict(int)
    for pattern_len in range(PATTERN_MAX_LEN):
        # Update patterns dictionary based on pattern and c
        pattern = prev_chars[:pattern_len]
        patterns[pattern_len][pattern][c] += 1
        # Make a guess at the next letter based on pattern (including c)
        pattern = (c + prev_chars)[:pattern_len]
        if pattern in patterns[pattern_len]:
            potential_next_chars = patterns[pattern_len][pattern]
            guess = max(potential_next_chars,
                        key=lambda k:(potential_next_chars[k], k))
            frequency = potential_next_chars[guess]
            # Exact formula TBD--long patterns need to be heavily
            # advantaged, but not too heavily
            weight = frequency * pattern_len ** 8
            guesses[guess] += weight
    # Update prev_chars with the current character
    prev_chars = (c + prev_chars)[:PATTERN_MAX_LEN]
    # Return the highest-weighted guess
    return max(guesses, key=lambda k:(guesses[k], k))

Y el arnés de prueba:

from textPredictorGolfed import f as next_char
# OR:
# from textPredictor import next_char

total = 0
correct = 0
incorrect = 0

with open("whale2.txt") as file:
    character = file.read(1)
    while character != "":
        guess = next_char(character)
        character = file.read(1)
        if guess == character:
            correct += 1
        else:
            incorrect += 1
        total += 1

print("Errors:", incorrect, "({:.2f}%)".format(100 * incorrect / total))

Aquí hay algunos resultados de muestra desde cerca del comienzo del texto. Ya empezamos a ver la posibilidad de terminar las palabras comunes después de ver su primera carta ( in, to, and, by, también, al parecer,school ).

 you take in hand to school others, and to teach them by what name a whale-fish
xU wshhlnrwn cindkgo dooool)tfhe -; wnd bo so rhoaoe ioy aienisotmhwnqiatl t n 

Cerca del final, todavía hay muchos errores, pero también muchas secuencias muy buenas ( shmage seashawkspor ejemplo).

savage sea-hawks sailed with sheathed beaks. On the second day, a sail drew near
shmage seashawks wtidod oith tua dh   tyfr.  Tn the shaond tay, wnltiloloaa niar

Es interesante observar algunos de los errores y adivinar qué palabra "esperaba" el algoritmo. Por ejemplo, después sail, el programa dos veces predice o--para sailor, supongo. O de nuevo, después de , alo nesperado, posiblemente debido a la ocurrencia común de, and .


Registro de cambios:

  • 274 * 2 + 526092 = 526640 Golfed el algoritmo, a costa de algunos errores adicionales
  • 306 * 2 + 526089 = 526701 Versión original
DLosc
fuente
6

Python 2, puntaje: 2 * (407 + 56574) + 562262 = 676224

Las búsquedas de palabras que coinciden con los caracteres anteriores a partir de una lista de  todas las  mayoría de las palabras utilizadas en el texto, ordenados por el número de sus apariciones.

Código:

import zlib
f=open("d","rb")
l=zlib.decompress(f.read()).split()
w=""
def f(c):
 global w
 if c.isalpha():
  w+=c
  try:n=next(x for x in l if x.startswith(w))
  except StopIteration:return" "
  if len(n)>len(w):
   return list(n)[len(w)]
  return" "
 w="";
 n=ord(c)
 if n>31:
  return list("t \n 2  sS \n  -  08........       huaoRooe oioaoheu thpih eEA \n   neo    enueee neue hteht e")[n-32]
 return"\n"

Datos: https://www.dropbox.com/s/etmzi6i26lso8xj/d?dl=0

Banco de pruebas:

incorrect = 0

with open("whale2.txt") as file:
    p_ch = ch = file.read(1)
    while True:
        ch = file.read(1)
        if not ch:
            break
        f_ch = f(p_ch)
        if f_ch != ch:
            incorrect += 1
        p_ch = ch

print incorrect

Editar: el uso whale2.txtda una mejor puntuación.

Steadybox
fuente
5

C ++ (CCG), 725 × 2 + 527076 = 528526

Otra presentación de frecuencia de prefijo. Sigue corriendo whale2.txty obtén un puntaje similar (ligeramente peor) que otros.

#import<bits/stdc++.h>
char*T="\n !\"$&'()*,-.0123456789:;?ABCDEFGHIJKLMNOPQRSTUVWXYZ[]_abcdefghijklmnopqrstuvwxyz";
int I[124];std::string P(7,0);struct D{int V=0;std::array<int,81>X{{0}};};std::vector<D>L(1);D
init(){for(int i=81;i--;)I[T[i]]=i;}int
f(int c){P=P.substr(1)+(char)I[c];for(int i=7;i--;){int D=0;for(char
c:P.substr(i)){if(!L[D].X[c]){L[D].X[c]=L.size();L.push_back({});}D=L[D].X[c];}++L[D].V;}std::vector<int>C(81);for(int
i=81;i--;)C[i]=i;for(int
i=0;i<7;++i){int D=0;for(char c:P.substr(i)){D=L[D].X[c];if(!D)break;}if(!D)continue;int M=0;for(int
x:C)M=std::max(M,L[L[D].X[x]].V);C.erase(std::remove_if(C.begin(),C.end(),[&](int
x){return L[L[D].X[x]].V!=M;}),C.end());if(C.size()<2)break;}return T[C[0]];}

Este busca con avidez la cadena más larga que comienza con un sufijo de la historia, y si hay múltiples candidatos, desempate con cadenas más cortas.

Por ejemplo: si los últimos 7 caracteres son abcdefgh, y la cadena abcdefghiy abcdefghjaparece con la frecuencia más grande en todas las cadenas de la forma abcdefgh*, la salida será io j, desempate con sufijos más cortos ( bcdefgh,cdefgh , ...).

Por razones desconocidas, nada más que 7 y mi computadora no tiene suficiente RAM para ejecutarlo. Incluso con 7, necesito cerrar todos los navegadores web para ejecutarlo.


Código de prueba:

int main() {
    init(); 

    std::cout << "Start ---\n";
    std::time_t start = std::clock();

    std::ifstream file {"whale2.txt"};
    // std::ofstream file_guess {"whale_guess.txt"};
    std::ofstream file_diff {"whale_diff.txt"};
    if (!file.is_open()) {
        std::cout << "File doesn't exist\n";
        return 0;
    }

    char p_ch, ch;
    file >> std::noskipws >> p_ch;
    int incorrect = 0, total = 0;
    // file_diff << p_ch;

    int constexpr line_len = 80;
    std::string correct, guess_diff;
    correct += p_ch;
    guess_diff += '~';

    while (file >> ch) {
        char guess = f(p_ch);

        // file_guess << guess;
/*        if (guess != ch) {
            if (ch == '\n') {
                file_diff << "$";
            } else if (ch == ' ') {
                file_diff << '_';
            } else {
                file_diff << '~';
            }
        } else {
            file_diff << ch;
        }*/
        incorrect += (guess != ch);
        total += 1;
        p_ch = ch;

        if (guess == '\n') guess = '/';
        if (ch == '\n') ch = '/';
        correct += ch; guess_diff += (ch == guess ? ch == ' ' ? ' ' : '~' : guess);
        if (correct.length() == line_len) {
            file_diff << guess_diff << '\n' << correct << "\n\n";
            guess_diff.clear();
            correct.clear();
        }
    }

    file_diff << guess_diff << '\n' << correct << "\n\n";

    file.close();
    file_diff.close();

    std::cout << (std::clock() - start) 
    / double(CLOCKS_PER_SEC) << " seconds, "
    "score = " << incorrect << " / " << total << '\n';
}

Sin golf:

size_t constexpr N = 7;

int constexpr NCHAR = 81;

std::array<int, NCHAR> const charset = {{
'\n', ' ', '!', '"', '$', '&', '\'', '(', ')', '*', ',', '-', '.', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', ':', ';', '?', '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', '[', ']', '_', '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'
}}; // this actually contains a lot of information, may want to golf it
// (may take the idea of using AndersKaseorg's algorithm, late acceptance hill climbing)

std::array<int, 'z' + 1> const char_index = [](){
    std::array<int, 'z' + 1> char_index;
    for (size_t i = NCHAR; i --> 0;) 
        char_index[charset[i]] = i;
    return char_index;
}(); // IIFE ?

std::string past (N, 0); 
// modifying this may improve the score by a few units

struct node {
    int value = 0;
    std::array<size_t, NCHAR> child_index {{0}};
};
std::vector<node> node_pool (1); // root

int f(int c) {
    past = past.substr(1) + (char) char_index[c];

    for (size_t i = 0; i < N; ++i) {
        // add past.substr(i) to the string
        size_t node = 0;
        for (char c : past.substr(i)) {
            if (node_pool[node].child_index[c] == 0) {
                node_pool[node].child_index[c] = node_pool.size();
                node_pool.emplace_back();
            }
            node = node_pool[node].child_index[c];
        }
        assert(node != 0); // the substring is non-empty
        ++node_pool[node].value;
    }

    std::vector<size_t> candidates (NCHAR);
    std::iota(candidates.begin(), candidates.end(), 0);
    for (size_t i = 0; i < N; ++i) {
        size_t node = 0;
        for (char c : past.substr(i)) {
            node = node_pool[node].child_index[c];
            if (node == 0) break;
        }
        if (node == 0) continue;

        assert(node_pool[0].value == 0);
        int max_value = 0;
        for (size_t x : candidates)
            max_value = std::max(max_value, node_pool[node_pool[node].child_index[x]].value);

        candidates.erase(
            std::remove_if(candidates.begin(), candidates.end(), [&](size_t x){
                return node_pool[node_pool[node].child_index[x]].value != max_value;
            }), candidates.end()
        );

        if (candidates.size() == 1) 
            break;
    }

    return charset[candidates[0]];
}

Salida de ejemplo:

~ ~s  ta~ hard ts tt~~~~~~~ ~doam ~~ ar~ ~ i~~~ ~~~ ~he~~~~,a~ t~~~~ t~ ho~si~  
n--as his wont at intervals--stepped forth from the scuttle in which he leaned, 

~~~ thr~ ~~ t~~ crp~~~~~~~~ a~ wap~~~~~ a~eo~~ h~~ o~~ s~~~ or~~y~ ~  boog~e~~ t
and went to his pivot-hole, he suddenly thrust out his face fiercely, snuffing u

~ a~~ ~h~ ~n~ onitn~oi~~~~~~ ~~a~ ~ cewsoat~  a~ tae~~~~ ~e~~t~~ te~~ ouc~s~i~~ 
p the sea air as a sagacious ship's dog will, in drawing nigh to some barbarous 

ct as I~ iisk~~~~ ~~e~ tls~~~~ i~~~ ~~ soe~e Ae ~ ~~e~ tar~~~~~ trd~  ot ~ h~~~ 
isle. He declared that a whale must be near. Soon that peculiar odor, sometimes 

Este está cerca del final del texto. La mayoría de las palabras largas se predicen con bastante precisión ( intervals, pivot-hole, distance)

 au t  tf weu~i~ aor~ mre~g~~~ m~t~~ ~~~  ~"NC~X~t~ti~  ~~n~ SNsh A FNECnSERTR O
 on as it rolled five thousand years ago./////Epilogue//"AND I ONLY AM ESCAPED A

NL~~,S~ ~HR~ yO~ -/s~n "~A~~ laeu~ta Vew~, S~e s~~  s~ ~ ain~ t~d ~t~ oirept~~ ~
LONE TO TELL THEE" Job.//The drama's done. Why then here does any one step forth

Las mayúsculas no parecen buenas.

usuario202729
fuente
Trie parece ser más memoria consume mucho de lo que esperaba ...
user202729
... y también más difícil de implementar.
user202729
4

Python 2, 756837

Usa algo que podría ser cadenas de Markov?

import zlib
a=eval(zlib.decompress('x\x9cM\x9cis\xda\xcc\xd2\x86\xff\x8a2\xf5\xd4\x81\xb8,\x977l\'\xf9\x90\x12 \x02f\x11G\x02c||*%@,a\x11a1\xe0S\xef\x7f\x7fC\x13\xf75\xdf\xda\xaaa4\xd3\xcb\xddw\xf7\x8c\xfc\xbf\xcc\x8f\xd7E\xe6\xab\x93if\xce\x9d\xcc\x8f\xefG\xd1\x11\xf1\x1b\xa2At\x8e\xa2\'\xe2\xc5Q\xfc,\xa2{\x14+"\x9e3\xf63b\x87\x9f\xb5\x8fb$b\xeb(\x96E\x8c\x18\x1b2\xb6{\x14/D\xfcq\x14\x03\x11}\xc6zG\xb1.b\xc0\xd3\x06\xcb\xa9\xf1\xb3\xcaQl\x88X>\x8a-\x11\xb7G1\x11q\x85\x98\x1c\xc5\x95\x88\xf1Q\xec\x89\x98\x1e\xc5\x81\x88\xa2\xb3X\xc4\x19\xe2\xe4(\xbe\x898\xd6\xc9F\xa8\xe4E\x16\x19\x8a\xc8r^|U\xc9\x8b\xc7\xd8\xfcQ\xf4\x8f\xe2\xbf\x1c\x06\xbc\xa8v6\xef\xba\xb2\x17V\xf6\x92\xe8r6\x07\x9d\xcc\x95EN\xe4\xe9FW\xb6\xd9\xea6M\xa2K\xdf\xact\x86\xf9\xc976Gy\xf2\xce\xef\x96G1\x15q\xf1\xf1\xd4\xcc3\xe6\x8f\xb8\x96\xdf}\xd27\xcf\x1d\x9da\x8e\x1f\xcd\xc5c\\\x11Q\xcf\xfc\x02Q\x9c\xe7\\\xd6\xbe;\x8acY\xe5\x8c\x17\xcfu9F\xc4\x83\xfc\x0c\x076\x0b\x1d;\xc7\x97\xe7_U\x9c\xacT\xfc\xc2\x1a\xbe\xb0\x06\x83\r7b\xd9\x85<\x9d\xe8\x86\xbe|Q\xff\xfc\xf2\xa0\xe2d\xa7?\xfbr\xc5\xbc\x97\x8c\xbd\xd1\xbd}\xb9f@\x8e\x01\xb7\x88\xf7\x88w*\xce\x13v1\xc1ZCv\x1c\xebz\xe7=]\xce\x1c\x9d\xcdg\xe8,U/\x98/\x18`\xed\xf8\x8d\xa7\xe21\'\x1bo\xd4,sk\x80\xb8\xc6L\xc45Oq\xa9M\xac\x9e8\xc7?k\xb8\x9fY\xe9\x80\x9a\x8c\x9d\x8a\x98\xea\xde\x8c\xcc\xbb\x94\xa7\x13\x06\xc8\xca\xfa"\x1e\x98\xa1\xa4\xe1R\xfb\xa1\xb1W+\xf2b\xc0\xa4\x96W\xac\xa8\x15\x10=\x8d\xd3ZC#\xb2F \xd7j\xccP\xd78\xadU\x8fbWD"\xbd\xd6Q\xb7\xaf\xb5\x98\x0cH\xac\x85\xfc\x0cH\xac5\x15(k\xdd\x8f\xa7\xa6&\xf1v\xfa\x19\x00Q\xc3\x7fkxuM\xe2\xad(\xa2D\xd6\xabX\xb6&\xfeyy\x14\x1d\xdc\xa4v\x8azY\xdbU\xa4P\xf9\xc4\xcc?\x0fj\x8d\x9f\x135\xf8O\xde\xf7\xd3Q?Ym\xf4\xe9\n\xefY\xe12\xab\x9d:\xc7\n`Y\xfd>\x8a[\x11\xf1\x88\xd5\x9a\xc9\xf6\xcc\x80#\xad\xde\xd5+W\x03\x9e\x12/\xab!\xf3\x8e\x98\x81xY\xf5\x18\xd0g2\xe2e5g\xb2\x05+\x13\x07\x9d\x8b8fCD\xd1j\xca\xcf,X]\x81X+\xb0i\xa5\x88\xf5\'\x1c\x14VW`\xe9\n\x84]\x19u\xaa\x15\x16X\x81\xb0+\x0c\xb7"\'\xbf.N\xab0\xa7?n\xd5\x13^\x179\xb5\xf9\xebB<\xe4\xe1$_[c\x04\xc3\x06\'\x99W\xbd.\xb2\x1ap\xaf\x8b\xb3\x8fy\xcc\x9fW\x19\xe6t\xacE\x18\x1d\xffoR\xf1\xeb\xa2k\xc9/\x96\xfc\x1fk\xfa\x96Z\xe7u\xd1VLx]<\xa9Q^\x17\x1dkL\xd3\x9a\xe7\xdfj\xe4\xd7Eh\x8d\x8fT\xc3\xaf\x8b\x9a5\xben\xc9\ru\xd2\xd7E\xa0\xf6}]\x94\xad1\x15k\x8b\x8f\xd6\xf8\xaa\xf5\xae\xa25\xde\xb7\xe6)Y\xe3\x7fX\xb2g\x8d\xc9[\xeb/(:\xfc[\xd4P9=>X?}\xb7\xe4\x8d\xa5\x92\xad5\xe5\x9b\xb5\x9c\x9d5Fbru\x92\x7f[\xaf]Y\xe3\xd7\x96\xdaf\xd6\x16\xe7\x1a\t\xaf\x8b\x85\xb5\x06\t\x96\xe1I\x1e[\xf3L\xac\xf5\xfc\xb2~;\xb5\x9e\x0f\xac\xf1\x12\xd7\xfb\x93<\xb4\xe6\x1fYk\x8e\xad\xdf\xf6\xac\xdf\xf6u\xfc\x80\x00\x19\x10A\x03\xdcz\xa0ac\x06\x84\xe3\x00>3 2\x07D\xe6\x80\xd8\x1e\x10\xdb\x03\xd8\xc8\xc0\x02\x82\x01\xb9w \xea\xd9\x89\x08\xee\x0c\xe6\xaa\xd8\x01\xba\x19L\xf9\x19\x9a\x1c\xa0\xc8\x01\x807\x00\xf0\x06hq\x00\xd9\x1d\xf4\xd0\x89\xa5\x9e\x985\x80\xb4\x837\xd6\x00\x82\x0f\xf0\xae\x01\x19y\x80\xaf\x0c@\xf0\xc1\xf2cCf\x87Vw\xe8o\x87Vw\x98h\x87]vXk\x07a\xdc\xa1\xf6\x1d\xba\xdea\x81K\x012aR\x977\x88\x97\no\x97W<\x85u]\n\x17;e\xceK(\xda%\xc4\xed\x12\x16x\t7\xdcYV\xbe\x94-I\xba\xbcd\xa3\x97\xec\xee\xf2\\W\xb1\xc3r;l\xb4\xc3r\xbb\xbe\xea}\xd7C\x14s\x9dt\t\xb5\xdb-\xd0\x04>\xb5#)\xed\xe0\xb5;\x12\xd8\x0e\x84\xd8Q8\xec0\xe2\x8e\xe4\xbc[2\x00?\xb9\xc4#\nl\xb3\x80\xe5\n\xa2\x12![\x05\x81G!\x1e\x05AP)\xed\n\x02\xac\x02\xfa\x85\x80\xa75\xc5\xba\x02t\xad  )\xc5l\x01jW\xe8"\x86\xbcB\xd0RrR\xa1\xc5+\x08\x9d\xc2X\xd5W \xbd\x17f\xba\xcd\x82\xa8Z\xd2N!Q\xf5\x15\xdeU}\x85\x83\xc6@a\xa5\x01U\x10\xa5\x9e\xd8\xee@\x9fN 4\x06,3#\xd5\xaf\x01\xc9\x0c$\xc5\x10\xa8\x13\xe0y\xb2\xd4\x1dO0\x96I\xd5\x16\x93\xadnh\x82\x85\xcc/f \x1f\x18\x06L\xc6\xba\x9c\t\xc8c\xc8\x17\x13j\x8c\xc9L}}\x92\xea\xd2\'\xe2\x88#\x11\xd9\xd0\x04\xaa5\xe9\xf1\xb3D]\xd9\x90\xce&#\xc6\x0e\xd9[\x11\x9d\xf9\xe8\x97dj\xc8\xa5\xc6\xd3\x080dRSP\xbb\x99\x1ac\xeb<%\xf3\x9b\x00\x9d\x91\xf7\ri\xdf<2/I\xdf\xc0Y\x0c\x94\xc5<1\x03\x84\xc5\xc0W\x0ct\xc5\x84,\x07\xb2b\xe0KO\xb2\xb7\x9ah\x07\xf43\xaf\x19uv\x039\x7f\x12MI\x1d\xf3$k/\xc8\x80\x0b\xc5.s\x06\xe6=\xc9\x9e\xa58\x99\xb8\xea\xd7\x13"yr\x81\xed\x01\xb7\x89\xbcN\xb2\xd9\xc4\xe8l\x7f\xcah\x85|\xc3:\x9fp\x89\'0\xefi\xa2\xa29\x81\xe9\xdf\x15\xa5j\xc7\xc9\xe9\xb9\xbc&Gc)\x87\xeb\xe6@\xe4\x1c8\x9d\xcb)\xde\xe6\xc0\xf4\x1cew\x8e\x04\x90#-\xe4.u\xc99RHN\x12\x8b$\xa1\x1cj\xc9\x01{9\xf8w\x19L*\xd3\xf2*S\xf5\x95\x9fxJ\xff\xac\xdcb\x00uc\xb9\x82\xd8`\x00Uj\xb9\xce\x0c@d\x19\x88,\x1f\xd4ve\xca\xb4\xf2\x04\x11RR\x8e\xd5\x1ce*\xab\xb2m\x992&-\x7fV\xfd\x94/\xac\x11(\xa8\xec\xaac\x95\xb5\x92\xfd\x13VZ\xdf\xfeG\xb4\xd2\x16Q;d&\xf3\xcd\xe8l\xaf\x19\xcb\xb52\xce\x87k\x99\x8c{\x14]\x11\xcf\xcd\xc7\x0b\x17$8\x8br.\x00\xbf\x05yqA\xb6\xb4\xe8\xec\x02\xb6v"\xb3\x12\x86\'\xaey\x12\xa1R\'\xa6y\x1aKM\xba@s\'\xea*\x00qb\xae\xa7\xa7{\x9e\x92N\x17$\x97/\x04\x96E\xd2-\x8enQ\xf4\x05I`AA\xbe \tX\xf4\x7f\xa1t\xcedv\xe6o\xf8\x98\xcc\x9b\xf9;\xc0d\xb6\xe6\xef6Mf\xf3\xa1T\x93Y#\xae\x18\xfb\xdb\xfc]\x8e\xc9,\x8d\xce{`\xc0\x88\xa7C\xf3Wg&\x93\x98\xbf+3\x7fx\xb6\xce\xdb?\x8a3\x11{\xcc\x1b36\xe5\xe9\xe2\x8fh2\xe6(\xce\x99a\xc6\x0c\x13\xf3\xd7\xf2&3f9\x1dv\xfc\xc4\xd3\x16O#\xdc\x08&\xba\xb8\xc0-\x9bFm\x01\x81]\x00\x88\x0b\xc3\xd8\xae\xbe\xe2T!\x9f\x94\xea\x1f\xc5\xbd\x88E\xb4S@\xcc\xb3M\xcf\xa8{~g\xde\x80\xf56\xf8Y\xfdc\xac\xc9\xd4\xcc_\xe72\x99\n\xda)\x7f\x8c\xcd|eo_\x1du\xb9\xaf\xf4\x1a\xbeZ\xe1\xfe\'Gj\xac\xd6\x8f\x1b\x15\xbdg\xea\x8e\xe6\x9c:\xd3\xd5\t\xfc:\xc8X\x07%\xea\xf0\xf7\xfa\xe9%\x1d\x91\xe9l\xd7\xc9\x12u\x89>\xe9\x82\xd7\x01\xab:\xb5G}\xc3\xc4+D"\xaa\x0e\x08\xd6i\xf6\xd5\x0b\x9a\x0e\xeb4\x06\xeb\x02\xa3\xc2\x1e\xeb5\x05\xad:8[o(\xce\xd6+\xec\xbe\xcd\xcf\x9a\ne\xf5\x88\xe5\x90\x0c\xce_9[X[\x95\xc3\x1aD]S\xca\xac\xd1\xd59f:G\xdb\xe7g\x0c \xf9\x9c\xd3\xeeYgu\x99k\xcc\xb1f\x865\xf6ZS\xf1\xae\xf1\xe7\xb5z\xb9Yg48\xce\x1f\xf4\x15\xdfu2\xf3\x9d\x01\xdfA\xec\xccwG\xcd\xbc\xc62k@kM\x07y\r\xc0\xad\xa98\xd6t\xdd\xd7\x18\x7f\r\xd6\xad\xa1\xab\xeb_\x8a\xcdk\xe0\x7f\r\xb5]\xc3\xf6\xd7\x00\xfd\x1a\xf8_\x93\x14\xd6}\x85\xdeu\x8f\xa7\xb4\xb9\xd7#\xd6\x0b\xd0\xaf\x81\xff55@H\xb9\x15&\xba\x86P&\x93f[\xc8\xca\xc2\xb1\xbe-\x94]\x08\xa7\x0e\xe1\x07!\xdd\xa0\xf0\tQ\xb8\x84\x90\xa3\xb0\xa9\x8e\x1dBAB(H\x88[\x86\xf4\xccC\x02&\xfc\xa1\x8e\x1dz\x1a0a^}<\xa49\x15R\xb0\x85\xb0\x91P\x02F\x90#\xa4\xb8\x0b\xe9\x99\x87\xd4\x84!\xce\x1e\x12\x02!\xbd\xd2\x10\x18\n\xc5\xa3\xaeD\xc4\x81C\xf1\xc4\xbc\x888{\x08\xf6\x84\xa7\x88\x93pH(e\x12J\x99$Us&\xd4\xd4\t\x0c5\xa1\r\x93L\x15\x91\x12|.I\xd4\xc8\t| !\xf3\'\x94\x7f\tT+\xe9+\x16$\x90\x8b\x84pI\xf6\x0c\xe0\xb0.\x81\xcd%DC\xb2C$\xf3\'\x84VB\x01\x99\x10\x86\tgf\xc9\xcf\xa3(\\7\x01,\x12t\x9d\xa0\xe0\x84\xfeY\x02\xedO\x80\x90\x84\x92$!\xc5$\xd8;\x01\xfd\x12L\x7fA\xa1\x92\x9c\x0c\'S\xec\xa1w\xfb\x89jjO3dO\t\xbf\'\xa8\xf7\xf0\xb4}\xac\x10\xb2O4\xf8\xf6\xa2\xebO"\x82<{\x94\xb6\xa7E\xb2\xdf\xaa\xc7\\\xd1\x1d\xdd\xa3\x93=\x9a\xda\x8b\xfe$\x87\xedE\x11R\xaf\xecU=f\x8f\xd2\xf6\xec~om\xf9\xeaR\xadqE=rE\xa3\xeb\x8a:\xe7\x8a:\xe7J\xea\x9c{\x11\xa9s\xae\xa8\x94\xae\x04\xc5\xafE$\xbf\\\xd1l\xbb\xa2_u\xc5\xe6\x8a\x12\xca\x82\xe7\xc5\x9a\xc6z\xb1\xae\xb8P$\xc0\x8b`H\xb1\xa8\x10Q\xf4\x15N\x8ad\xe5"\x80T\xa4<*\xb6\x15\xc7\x8a\x1c\xa0\x15#\x85\x93"\xed\x87\xe2D-[\x84P\x14c\x05\xd0"\xa7\x87\xc5\xad\x1a\xaeH\xfe)\x9e\xd4.(S\xb4\xb6\xac\xf64\xc5\x8cr\xb2"\x14\xa8\x88\xbb\x17\xf1\xe6\x8e\xaf\x88\xd4\xa1r\xefp\x9b\xa1C=\xd7\x81rt\xd0_\x87\xf6X\x87\xc2\xb7#\xbb\xff&"-\xafN\x131Q\x07\xed\xd01\xec\x80n\x1d\x1a\x82\x1d\x02\xaa\xa3\x8a0\x1d\xd0\xb6\xe3\xb02\xee\x85t\xb8\x17\xd2\xb1N\x1d;\xec~\xcb\x81\xdf/p\xeaZ\xbc2\'O\'\x1a\x1a\xbf\x12\xb5\xdc/Y\xb0T>\xbfR5\xd7\x1d\xfc\xe6\x8e\xe0\xba\xc3Dw\x04\xc9\x1d\xa5\xfc\x1dArG\xe8\xdc\x11$w9\x8d\x81;\t\x129\x0e\xbb\x93EJ\x82\xb9\xa3\x9dp\xf7E\xc3\xa1\xc5\xed\x8a;\xab\x81F\xeb\xbeb\xc5o\x05\x9dT@\xbd\n\xc0ZaG\x15vT\xc1\xa7*\n\xa1\xa6\x92\xf9(r2\x95g\xf4^\xe1\xeeH\xa5\xc9\xefH\xf7\x95\x10\xb1\xad\xc1S\xc1\xa9*O\xea>\x95\x8a\xee\xb9R\xd7\xf0\xabp\xdf\xa6\x12\xa8\x87V\xc4\x85\x7f\x88\xc8\x8d\x9dJ\x81\xc9\xf2\xea(\x15\xc8E\xa5\xc8\x80\x1f\xac\xa1\xc4S*\xe4\n9\xaaB\xa3\xb5B\xc2\xab\x08\xceK\xbb\xadB2\xaf\x88\xf7\x08\xa2WH\xe6\x15\x12Ae\xa4\xc8Q\xa1\xd7\x98\xa5\xb0\xce\xaeu\rY\x8a\xf0,\r\xd1,\xb6\xf7\xb0a\x16\x92\x90\x85\x82f9O\xce\x92\xad\xb2\x9c\xa8e\xa1$Y\xc8f\x96s\x80,\xa1\x9c\x85E\\\x8b\x01\xe4\xf8?\x0b\xad\xcc\x82\x0b\xd9H\x8d\x95m\xf26i;\n^g\xe9@e\xf1\x87lU\xed\x96-3\x96.h\x96r(+\xfe \x80\x9e\xad\xf1b\n\xaa,\x9d\xd8l\x81\x9fy\n\xb6\xd9\x92:W\x96\xcb\x1c\xd9"/\xf6\xd9\x85\xc4\xf71\xb1\x99\xe3!\xb3\xc6@jUT\x0b\xfbv\x13\xa7*\x9eL\xf8$\xa3\x89\xb4\x94PL1c\n\xb1I\xc9\xd1)Q\x99\xd2\x01H\x89\xeb\x94hO\xc9\xe7\xdf\xa8\xae\xbei\xae5\xdf\xa8\x98\xbeQ\xcb}\xb3\x96#\x9e"\x97`R|8\xc5SR\xf1\x1fa0)EP\xfa\x0b\x11\x0fL\xc7\x1a\x10)\xa7\x85)\xae\x9f\xd2\x92O!\xafi\x9f5\xd0\xbeOi\x87y\xa1z`\n7M\x0f\xea\xb8\xe9\x9e\xc9\xe0\xa6\xdf\xacb8%\x1b\xa7\xc4u\xca-\xa3\x14r\x9a\xc2\xc9R\x98Z\x83}6\xe8f6h&4\x92\x8f\xa7\xa6Erk\xf0\xe2\x06i\xb7\x81\xef7\xa08\r*\x9b\x06\xd7\x85\x1a\xa4\xf3\x06d\xa6Am\xd4\xa0\xbaj\xf8\xfc\xec\x07O\x9f\x11\xe1@\r\x9a\t\r\x88O\x03Do\xb4\x18@\x0f\xa2\x01\x8c7:\xec\xc2J\xd1\r\\\xbcA\xc9\xd4\xb0\xda\xb7\x0b\x92m\x03\x8e\xd3\x80\xb36,\x05\xe2\xee\x0bk\xe2\x93me\xff16\x88\x01\xdf\x18W\x8aa+1n\x17\xe3\xa2\xf1P\x8d\x14c\xe6x\xccX\\?\xc6\xf5c\xc2$&-\xc4\x80o\xbc\xd0\xe0\x89q\xaax\xc9\xdb\xc8<\xf1\x8a\xb1\xb0\x99\x18g\x8d9(\x8f\xa9\xbabJ\xb8\x983\xc0\x980\xb9\x82\xac,\x80\x8b\x05Zm\x9dTy#\xbf\x03|b(A\x0c:\xc5\x90\xf7\x98c\x9c\x18\xc3\xc4\xa0^\xcc;b\xe0+\xb6\x88\x8b\xebk`\xbb\x9c\xc0\xb9\x9c\xb5\xb9\x82\xda\x92O\\\xf1}I\x85.G\xb6n\x9e\xb1u\xc4\x1a?\xe3\xac\xcd%\xa6\\\xb2\x8c[\xe6gD\xa5\xfb\xc8+\xda\xea\x11.\'p.gm.w\x86\\\xce\xda\xdc&\xf3r\xd6\xe6\x86\xfa\xd4!\xc5\xba\x9c\xc09\xdc>q)\xf5]2\x8ck\r\xa0#\xe4\x12\x03.g\xba.\xa5\xbeK\xa9\xba\xd9\xf1\x94\xbb4.Wl\\b`\x83\x83\xba\xdc\xa3q9\xecp\xc5W\x85\x1a\xb9\x90\x95\r5\xb2\x8b\xaf\xba\xc4\x80\x0bww\xd7h\x12\xf6\xb5\xe1\xfe\xc2\x86\x1do\xe8vm8\xe1s9~\xdap\x14\xecr\xd8\xe1\xda\xa7K\x1b+s;\xd6\xd5f\x1a\xe0\xaev\xd33\x1bBf\x83;\xbbV\xf7\xd1u1.a\xe0f\x99\x98\x88\xd80`\xe3\xa2,x\xc0\x86H\xdb\x90\xd07\xf0\x80\r\x01\xea\xa0\xee\x11\x17\\G4\x17#\x16\x1c\xb1\x8d\x88P\x8ch]E\x16:G\xb24\xc92\x11\x0b\x8e\xe4\xcdB\x1a"\xbd\xc8o"\x80::\xe9\xb5$\xf2A\x8d\x13a\xf4\x88l\x1a\x01f\x11\x1d\xd7h\xc3\xd8\xa9*0\xa2=\x16QKF)K#\xcfG@r\x84\x0fF\x84D$\x81"\x146J\x18\x10)4DT\xb9Q\x07Q@@\xca\xeb\x88\xcb\xb7\x11\x17u#\x92{TV\x18\x89\xe8JF\xa0OTg\x00\xd9?\x82\xb7Fy\xe6\xf5\x18Ku3\xc4\x9eC\xac<\x14\xd3\xca\x9d\xcc!.3\xc4e\x86\xda\x1e3C<mH6\x1eb\xef!$q\x88\x07\x8f\xf0\x9e\xa1\x15GC\x02w\x08b\x0c\xe9h\r\xe9h\ri\xb6\x0fi\x97\x0ci\x9a\r\xb1\xcb\x10\xee8\x04\x94\x86\xdc\xe4\x1f\x02kC\xcd\xbbf\xc4\xe6\x1c\xa9\xb4\xa5\xfe>\xb0\xcf\x03\x9b;\xb0\xe5\x03\xfb<\xa0\xb4\x03\xaa<\xa0\xbf\x03\xaf8`\x81\x03v9\xa0\xa9\x11o\xbb\xa63p\xcd\xd5\xafk\xdag\x07K\xab\xd7\\\xfb\xbf&\x8b_\xd3r\xb8\xa6\xe5pM\x1b\xe1\x9a\x0e\xdc\xb5\xac]: \xd7\xec\xf3\xda\xda\'Z=PU\x1e\xe6\xfa\xb3\x03\x08y\xa0\xbds\xe0`\xe3@\xf7\xeb\x00\xf8\x1e\xc8<\x07\x0e+\x0e\xc0\xf7\x81\xabI\x07\xa0\xfe\xb0d\x06\xfc\xe8@\xff\xec\x00\xe8\x1d(\x93}\x0bz|\xd0\xcbg\xcb\xbe\x85o\xbe\xc2\x9e\xf1\x81/\x1f\x8b\xfb\xdc\x88\xf7Aa\x1f\x83\xfaX\xdc\xa7\x7f\xe1\x13\xcb~\xa0p\xe1K\xdcK\xe9\xea\x83\x11~Y\xd1\xc0\x87u\xf8\x12\xe1/"B\xea}>_\xf2\xa9b}j\x01\xbf\xc0\x0cy\x96\x0e\xd5\xf7\xa5\x00\x10\x92\xed\xbf\xf0bN{\xfc\x0e?\x83\xdf\xfb\x94\xf0>=\x1f\x9f\n\xc1\xa7\xe7\xe3\xd3"\xf1q\x19\x9f\xfbZ>\xc7L>W\xe3|\xf1\x08a\xbd\xbex\x84d.\x9fF\x84Oq\xe8\xe3S\xfe\x9e\xb7Au}\x9af>\xd0\xe3C@|r\x91\xbfd\x91\xe2i\xbfE\xa47\xf3|\xf2)1\xe73\x01\xf3\x8co<\x8b9\x9fE\xa4_\xf5La\xf6\x0c\xbd}~V\x13\xfd#\x88$\x14\xfa\x1f.\xc5?\x8b1\xa4)\xf1\x0c\xb3\x99Zh0\xe5lc\x8a\xafN9?\x9d\x02ISh\xfa\x94\xb5O\xc1\xa1)\xa11\xc5\x99\xa7\xc0\xd7\x14o\xbfg\x86{\x1a\xf6\xf7\xf4Y\xef\xef\xf4m\xf79]\xef=Pw\x0fN\xdd\x83^\xf7|\xe0t\x0f\xd2\xdd\x0bzIk\xf4\x1eL\x9bb\xfb)\x1f\xd5Ma\x86\xd3\xa1b\xc4\x14\xc0\x99\x02oS\xe0mJG\x7f\n\xeb\x9d\x92J\xa6P\x87)04\xe5\xb6\xea\x14\xef\x99\xc2d\xa6$\xb9)e\xd9c\xa0\x0e\xf1\xe8+L=J\xf8J[\xf3\x99\xf3\xd5GV\xf6(K\x17\xa2\xf2\x88C<ri\xf4\x11k>b\xa1,*1\x0c\xf8\xafM\x80?c\xf0\xcf\x18\xfc3\xa3?\xe3\x1c\x9f/x\xca\x8d\xa1\xcf\xa0\xe2\x92\x88Y\xa2\xaa%Lo\x89~\x96\x1bDBu\x89\xaa\x96\\D^\xd2\x96\xfcl/~I\xd5\xb4D-K\xd8\xe2\x12;/\xb1\xfe\x92\x84\xb5D\xc7K>\xbf\\b\xfd\x1b\xf2\xe7\xd2\x8a\xbf%j[\x12\x1cK\xd8\xc1\x92\xfe\xc5\x92P\\\xc2:\x96\x98i\x89\x8a\x97(\xfe\x86\xa7\x01c\x03W!\'\xb0\x06h\x88\x9b\x80,\x16\x80\x0c\x01\x9d\x95\xe0\xb4\r\xf1\xb6\x806_@\x9a\x0fh\xf3\x05c\x8d\xe6\x00\xfa\x15\xd0Y\t\xf8\x10"\xe0\x849\x80\xd6\x05 n@\xfb+ u\x07DR@\xc6\x0f$P\xaa"rn\x15\xd4\x11\xb9\x04\x10Ty\xca\xf5\xc5\xa0\xac0\x1cH\xd2\x14\n\x1d\x94\x18\xcb\xd7\xb2\x01\x07\x04A\x01M\xf1\xe1l\xe0\xf1TR\xa9\xa4\x82\xa0\xc3+\xc8\x94\x01\xb7\xc1\x03:\xdc\x01UE\x10\xaaO\x05Z`\x98\x1en\xd2\xe3\x10\xbb\x87\r{\xd8\xbb\x87\x9b\xf4\xf0\x8d\x1e\xde\xd5\x83\xfd\xf7\xbe2\x16\xaf\xed\xbd\x02v\xbd\x81Z\xa0\x07\\\xf6F\x0c\x80\x8f\xf7z\x0c\x00\x18{TZ=\x82\xab\x97j\x18\xf5\xc6LF \xf6h\x9f\xf56\n\x97=\xdc\xa4\xf7\xc6\xcap\xa9\x1e\x05F\x8f\xa6m\x0f\xe8\xb8\xb0Ab{\xfaC\xc0\xd3\xa13ra5)\xb7\x84\xf0\x05J\xbe@\xc9[\x14wA$]X7E/2\x1c\rl\xad\x1f2\xdd\x96\x8b}[\x8e\xd5\xb6\xd8w\x0b\xa6n\x7f\xf2\xbe\xba:\xcbE\x11\xd1G,!\xfe\x97=]p\'\xec\xa2\xa3\xe2\x16%m\x856\t\xff\xd9\nmz\x17\x91\x8b\x9c[\xda\x8d[\x94\xbf\xc5$\x17\t\xf3\x02\xf7[\x92\xc0\x16\x1e\xb8\x05S\xb6|c\xbe\xa5\'\xba\xe5\x90xK\x83uK\xf9\xb7\xa5\xed\xb5\xe5\xde\xfeVPI\x9aV\xdbX]hK\xf1\xb1\xed)\xae\xb5\x0e\xba\x9c\x16m/\xcf\xeaA\xb6V\xaa\x93{\x0b\xed[\xb4\x17Zd\x94\x16I\xb9ES\xb9\x05]\xf5\x08\xe3\x960\xedc\xef\xdbx\x1c\xc3\xb4\xba\x8a\t-\xb1\x91\x90\xf9\x96\x80\x86\xd4\x0b-\x81\x12\xa9\x17<q*\xb9l\xdd\x82t{\xe2T\xc2*[\xfc\xb3\x82\x16\xa7\x04-N\xc8Z\x94\x19\xad\no\xa3\xa0hq\x87\xbf\x05qm\t\xf4\xc9)\x96WPP\xf6\xf2\xac\xc1\xfa\x19q\xe2q\x19\xc3\x13\x0f\x15\xa6\xe3Uto\x1e\xb7\r<\xaa\x1e\x0f\x84\xf7X\xba\xc7\xb1c\xcb*\xde\xbc\xa6\xc6\xa2\x17\xb1`\xce\x19<\xa0\xd8\xa3\xc0\xf1:<}\xd2\xdd{\x94H\xde3O_P\x8f\xa3\x9e\xdf"j\xbd\xbeb\xa3\x07/\xf5\x06\n}\xde\x08\x91\xa3\x05\x0f\x14\xf4\xe8cyP\x97\x16\xf7\xe8<\xd0\xd5\xe3h\xc1#v<J\x19\x8f\xa3c\x8f\x98\xf4V,\x92\xf3\x04\x8f\x00\xf7 f\x1e\x9f\xe3y\xf4R=>\xfc\x1c1\xd6\xa1\x976\x82\xef\x8e\xacf$k\x18\x81\x0b\x0e\xa1\xec\xf0\xbd\xbeC#\xd9\xa1\xbd\xecp\x99\xd2Ag\x0e\xd9\xcb\xa1m=\x02\xdd\x1c(\xdc\x88\xb3\x9d\xd1P\xb53"\xd3\x8d\xe8D8\xb0\x15\x87\x96\xc2\x88;\x98\x0e-n\xc7R\t\xc7\xed#\x8c\xe5\xf0\xa5\xd1\x88\xa5\x8f\xc6\xea\x04\x0e\x07\xd5\x0e\x9f\x0c9\x1cn8|t\xe4p\x10\xe2p<\xe2\xf0\xb9\xaf\xc3\xd7\xc1\x0e\xdf\t9|S\xe4p\xce\xe1\xf0\xfd\x91\xc3\x99\x88\xc3\xb7J\x0e\xe7\'\x0e\xdf\t9\x9c]8|S\xe4p\xce\xe1p\xfa\xe1p&\xe2pR\xe2\xf0\xad\x92\xf3\xc2+\x9e\x99\x8c\xd3\x8f\x11\xe1\xe4H>\x94v\x80c\x14+\x1c>\xffv\xfe\xf5!\x1a\'ct\xb2\x7f\x8eO\xa5\xdf\xe7\xc8\x89\xb7\x90=\'\x8b\xc8\xb5\xbf\x11\xd5\x8fC\xfev\xa4B\x95km\x0eu\xab\xc3\xb7\xec\x8e\x94\xbbR\x04\x8f(\x84\x1c)w\x856;R\x04Ki<\x82\xaa9R\xcd~\x11\x91\nc\x04\x81\x1bY\xe9\xe7\x1d\xa2\xf5N\xbd\xf2N&z\xc7\xbb\xde\xb9d\xf8\x0e\x1f\x7f\x87\xa5\xbf\x13#\xef\xef\x1a\xb2\xef\x94`74\x9b\x1cB\xf6f\xa0;z\x87\xd3\xbc\xbb\xbc\xcd\xda\xdcZ\r\xf7\x0ef\xbe\x83\x99m\x0e|\x1c\xf0\xea\x86\n\xff\x06]\xdf\xd0#\xb8\xa1\xefyC\x8f\xe0\x86/\xacnh\x9d\xde\xd0P\xbd\xa1\xf7pC+\xe4\x86\xf5>nu\x17\x0eHZ\x12\xbf\x17\xe4/\xd1\xe5/\xd1\xfb/q\x03\xa9D7\xbeTR\xff,q\xd7\xa8D]R\xa23X\xe2\xba\x7f\tU\x97\xb0E\x89{\x0f%\x0c[\xe2\xf3\x84\x12Ek\x89\xa3\xe6\x92u ^\x82\xaf\x96\xc4\x02R\x14\x948\xed)\xb9\xcc\xc6\x8d\xbb.\xed\xc9.]\xcd\xae,X\x9a\x80]z\x16]v\xdf\xa5\x90\xea\xc2R\xba\xa2\xbfS\xce\xee\xd28\xee\xe2\xa0].\x83t\xed\xcfA\xce!K)\xd0|N\xa4u\t\x99\xae\xab\xf6\xe8\xe2\xa2]\x8b/t\xf5\x03a\xd3\xa5L\xeeBZ\xba\x14\x02c\x9e\xce\xa8|g\xe4\x92\x19\xb7\x07f\xe4\x92\x19]\x8bY_w:\xa3\xee\x98Q\x1f\xcd\xb8:2\x9b1\xc3\\\x83c\xcd\xe6f\x84\xf8\x0cE\xccH\xc53\x92\xf9\x0c\x7f\x9e\xe1V3R\xf1\x8c+\xd93:\xa63\x90\xe1\x9c/\xd8g\x00\x91\x99Q\xa2\xce0\xc1\x8c\xae\xc7\x8c\x18\x9f\x11_3\xac1\x03Zg\xd6\xe6P\xfb\x0c\x18\x9ea\x81\x07&{`\xb2\x07y\xb1$\x93\x87\x07\x9erq\xf2\xe1Zq\xfa\xe1F\x01\xf7\x81\xcd=\\\xf1\x14\xecx\x00Q\x1e\x04;$\x83<\x08\xa2H/\xb2\xea|\xc4\xb8\xa9\xe2GUb\xaaj9]\x95\x05W\xd9Q\xf5\xa4V\x89\xaaj\xacJ\xa9R\xefT\xb1x\x15\x86X%\xca\xab\x90\x8e*uK\xd5\xd7x\xaf\x12\xc3\xd5\x9a\x06n\x95\xb8\xac\x86\x8aUU\xae\xe5U\xb9\xb1Y\x85\x13\x9f\x91\xc4\xcf:\xfa\xe2\xb3\xa6\xae\xec\x0c\x1ap\x161\x00\xd2q\xc6\xbf$;\xcb\xeb\x80\xefv\xad~\x86{\x9cQ\r\x9f\xd9C.\xf1\x95\xdfh\xb6\x85\xf8\x9b\xff\xfe\xd2\xa4Q\xd0\xdc \xc2T\x9b\x07u\xdd&`\xd4\x14#\xc8\x19@\x13\xf6\xd9\x9c\xa8\xb75Sf\x00\x80\x9b\xdc\x82lF\xaa\xcd\xa6hH0\xbe\xd9A$\xa34\xf9\xf8\xb6\xd9U\xfcmr\xa2\xd3\xa4\xbejr7\xb2)\x8a\x95z\xb0I\x1ai\xd2\x15kr\x81\xac\xe9\xf06"\xa9\x89\xce\x9a\x94LM\xeb\xf8\xac\xcf\xc7\xab\xfd\x89j\xb5\xcfU\xa8>t\xa4\x0fI\xe9S\x15\xf4\xa9\xc9\xfb\x16HR\xe6\xf4\xb9\x98\xd1\x07\x7f\xfa`U\x1f\x04\xeb\x93\x9c\xfb\xd8\xb0\xbfa26\xd7\'\xab\xf5\xd9g\x1f|\xeaS\x9c\xf7\t\xcb>\xf0\xd3\xc7\xd1\xfaV\x8b\xe0\x8d\x1d\xbd\xd1s~#X\xdf\xf8\x94\xfc\x8d\xb5\xbf\xb1\xe07\xdd\xa7y\xcb\x18\xfd\x19k\xcfc\xf0<\xdfB\xe5\xa9\xb8\xf3T\xc6\xf9@a$O\xb8\xe7\xdb\xcc\x00\x8d\xc9\x13\xf9y\x02;O\xea\xcd\xd3\xe7\xcb\xe3\xd7y6\x94\xe7\x7ft\xe5\xe9\xd2\xe5\xe9\xe0\xe6\xb1\xe1F\x9b&&\x0fH\xe692\xcbc\x97\xbc\x85\x97yL\xd0fD\x1b\xf5\xb4\x15}3#,\xd7\xde\xe8z\\\x98q\x9b\xfbDm\xc9\xab\xc2\xfd\xda3\x1d\xdb\x06D7\xd6\xcf\xba\n\xa2m)S\xe4\x18\xb6M7\xb7\xcd1M\x9bo\xdf\xda(\xb8\r\x18\xb4\xeb\x1a\xa9m1\x9c\xb0\xc7\xb6\x18NZ\x1am\xba\x1bmxb\x9b\xeb\x9b\xed\xa2\x86r\xfb\x87"@\xdbS#\xb7i\xcc\xb4\xf3\x1a\xcac4\xf9\x89\x1c\xfd\xc9\xba\xaf4\xe6\x9e\xd3\'\x98\xd6\'2\xf3\'\xeb\xbf6|\x02\x9c\xc7\xf0\xe81\x86\x19c\xae\xb15\x96W\x8f9\x14\x19C%>\xd9\xf0>\xb6\x0fY\x80\xe41~5\x06\xd4\xc7\xc0\xc4\x98\x92b\x0cL\x8c\xe1Gc\xf8\xd1\x98o#\xc7\xf4\xa5\xc7\xb0\xea1\x1cm\x0c]\x1ds\x9bjLwaL\x95:\x86\xad\x8f\xb9\xc60\x16\xca(g\xdd\xe3\x01\x1b\x02\r7P\xc6[J\xa0[\xa11\xc2<n\xa1&\xb7P\x93[\xbe\xbc\xbd\xcd\xa99n\xf9\xc7\x11\xb7\x14Q\xb7\xfc\x93\x89[\x8a\xa8[Lw\xcbY\xee\x85e\xf2[<~\x04t\x8e\xfeZ\xf4\xff\xfe\x1f\xfa\xddI\x97'))
global t
t=' '
def f(k):
 global t
 r=a[t+k]if t+k in a else'e';t=k
 return r
Skyler
fuente
1
Explicación rápida: se zlib.decompress('...')evalúa {'G?':' ', 'G;':' ','G"':' ',.......}y aes un diccionario que asigna de 2 caracteres a 1 carácter. Básicamente, variante de 2 caracteres de la respuesta de Steadybox .
user202729
1
Como puedo ver, el literal es 17780 bytes. Puede reducirlo a 11619 caracteres eliminando espacios en blanco en el contenido descomprimido, lo que ahorra 12322 bytes. (si conté correctamente) También ... convertir códigos de escape hexadecimales en caracteres sin procesar reales puede ahorrar aún más bytes.
user202729
¿Cómo publico algo aquí si son bytes sin procesar?
Skyler
1
xxd, hexdump, uuencode, O similares
Peter Taylor
@ user202729 Solo tenga en cuenta que el código Python no puede contener bytes NUL sin procesar reales.
mbomb007
4

Haskell, (1904 + 1621 + 208548 + 25646) * 2 + 371705 = 847143

{-# LANGUAGE FlexibleInstances, DeriveGeneric #-}

import Control.Arrow
import Control.Monad
import Control.Monad.Trans.State
import Data.List

import System.IO
import Data.ByteString (ByteString)
import qualified Data.ByteString as BS
import qualified Data.ByteString.Lazy as BSL
import qualified Data.ByteString.Char8 as BC8
import Data.Ord
import Data.Char
import Data.Monoid
import Data.Maybe (fromJust, catMaybes)
import Data.Function
import qualified Data.Map as Map

import Codec.Compression.Lzma

import Data.Flat

import GHC.Word

maxWordLen :: Integral n => n
maxWordLen = 20

wordSeqDictSize :: Integral n => n
wordSeqDictSize = 255

predict :: [Trie] -> Char -> State ([Either Char Int], String) Char
predict statDict c = do
   (nextChar:future, begunWord) <- get
   case nextChar of
     Left p -> do
       put (future, [])
       return p
     Right lw -> do
       let wpre = begunWord++[c]
       put (future, wpre)
       return $ trieLook (tail wpre) (case drop lw statDict of{(t:_)->t;_->Trie[]})

newtype Trie = Trie [(Char,Trie)] deriving (Show, Generic)
instance Flat Trie

trieLook :: String -> Trie -> Char
trieLook [] (Trie ((p,_):_)) = p
trieLook (c:cs) (Trie m)
 | Just t' <- lookup c m  = trieLook cs t'
trieLook _ _ = ' '

moby :: IO (String -> String)
moby = do
    approxWSeq <- BSL.unpack . decompress <$> BSL.readFile "wordsseq"
    Right fallbackTries <- unflat <$> BS.readFile "dicttries"
    seqWords <- read <$> readFile "seqwords"
    let rdict = Map.fromList $ zip [maxWordLen..wordSeqDictSize] seqWords
    return $ \orig ->
      let reconstructed = approxWSeq >>= \i
             -> if i<maxWordLen then let l = fromIntegral i+1
                                     in replicate l $ Right l
                                else Left <$> rdict Map.! i
      in (`evalState`(reconstructed, ""))
              $ mapM (predict fallbackTries) (' ':orig)

Ejemplo:

Call me Ishmael. Some years ago--never mind how long precisely--having
 ap  me ,nhmael.  Hme ?ears |ce--never  usd how long .aacesely--|ubing
little or no money in my purse, and nothing particular to interest me on
little or no ?ivey in my ?efse, and ,uwhing .hrticular to Bdaenest me on
shore, I thought I would sail about a little and see the watery part of
?neae, I thought I would  cfl about a little and see the |rkers part of
the world. It is a way I have of driving off the spleen and regulating
the world. It is a way I have of ,uiving off the |kli   and .ia       
the circulation. Whenever I find myself growing grim about the mouth;
the Ca         . B        I  rtd |yself ,haoing  eom about the ?ivlh;
whenever it is a damp, drizzly November in my soul; whenever I find
Baieever it is a  'mp, ,uiv    Bar      in my  cfl; Baieever I  rtd

Utiliza tres archivos auxiliares precalculados:

  • seqwords contiene las 236 palabras más comunes.
  • wordsseq contiene una secuencia comprimida de LZMA de estas palabras, y para todas las palabras que no están entre las 236 más comunes, la longitud.
  • dicttriescontiene, para cada longitud de palabra, un árbol de decisión que contiene todas las palabras restantes. De estos intentos, las entradas se seleccionan a medida que avanzamos.

De esta manera, logramos una tasa de error significativamente menor que todos los otros esquemas con pérdidas; Desafortunadamente, elwordsseq archivo sigue siendo demasiado grande para ser competitivo.

Aquí hay una versión completa que crea los archivos y realiza el análisis:

depunct :: String -> [String]
depunct (p:l) = (p:take lm1 wordr) : depunct (drop lm1 wordr ++ srcr)
 where lm1 = maxWordLen-1
       (wordr, srcr) = (`span`l) $ if isAlpha p
                 then \c -> isLetter c || c=='\''
                 else not . isAlpha
depunct []=[]

mhead :: Monoid a => [a] -> a
mhead (h:_) = h
mhead [] = mempty

limit :: [Int] -> [Int]
limit = go 0
 where go z (n:l) | z<100 = n : go (z+n) l
       go _ l = take 1 l

packStr :: String -> Integer
packStr = go 0
 where go n [] = n
       go n (c:cs)
        | c>='a' && c<='z'  = go (28*n + fromIntegral
                                   (1 + fromEnum c - fromEnum 'a')) cs
        | otherwise         = go (28*n) cs


mkTrie :: [String] -> Trie
mkTrie [] = Trie []
mkTrie strs = Trie [ (c, mkTrie . filter (not . null) $ tail<$>l)
                   | l@((c:_):_) <- sortBy (comparing length)
                                  . groupBy ((==)`on`head)
                                  $ sortBy (comparing head) strs ]

mkTries :: [String] -> [Trie]
mkTries rsrc = [ mkTrie $ filter ((==l) . length) rsrc
               | l <- [0..maximum (length<$>rsrc)] ]

main :: IO ()
main = do
    orig <- readFile "whale.txt"
    let wordchopped = depunct orig
        dictRes
          = take 5000
          . map mhead
          . sortBy (comparing $ negate . length)
          . group . sort
          $ wordchopped
        dict = Map.fromList $ zip dictRes [maxWordLen..wordSeqDictSize]
        rdict = Map.fromList $ zip [maxWordLen..wordSeqDictSize] dictRes
        approxWSeq = [ case Map.lookup w dict of
                        Just i -> i
                        Nothing -> fromIntegral (length w - 1) :: Word8
                     | w <- wordchopped ]
        fallbackTries = mkTries . drop (wordSeqDictSize-maxWordLen) $ dictRes
        reconstructed = approxWSeq >>= \i
             -> if i<maxWordLen then let l = fromIntegral i+1
                                     in replicate l $ Right l
                                else Left <$> rdict Map.! i
        predicted = (`evalState`(reconstructed, ""))
              $ mapM (predict fallbackTries) (' ':orig)
        incorrects = length . filter id $ zipWith (/=) orig predicted
    putStrLn $ "longest word: "++show(maximum $ length<$>wordchopped)
    putStrLn $ show incorrects++" errors / "++show (length orig)++" chars"
    BSL.writeFile "wordsseq" . compress $ BSL.pack approxWSeq
    BS.writeFile "dicttries" $ flat fallbackTries
    writeFile "seqwords" . show $ take (256-maxWordLen) dictRes
    writeFile "whale-approx.txt" . unlines $ coLines orig predicted

coLines :: String -> String -> [String]
coLines [] _ = [[],[]]
coLines ('\n':l) (_:m) = []:[]:coLines l m
coLines l ('\n':m) = coLines l ('|':m)
coLines (c:l) (d:m) = case coLines l m of
   (lt:mt:r) -> (c:lt):(d:mt):r
dejó de girar en sentido antihorario
fuente
3

C ++ (WIP), 1923 * 2 + 1017344 = 1021190

#include <map>
#include <random>
#include <string>
#include <type_traits>
#include <vector>

using namespace std;

constexpr minstd_rand::result_type seed = 10087702;

template<typename T>
class discrete_mapped_distribution {
private:
    discrete_distribution<size_t> distr;
    vector<T> values;

public:
    discrete_mapped_distribution() :
            distr(), values() {
    }
    template<typename I, typename = typename enable_if<is_arithmetic<I>::value,
            I>::type>
    discrete_mapped_distribution(map<T, I> distribution) :
            values() {
        vector<I> counts;

        values.reserve(distribution.size());
        counts.reserve(distribution.size());

        for (typename map<T, I>::const_reference count : distribution) {
            values.push_back(count.first);
            counts.push_back(count.second);
        }

        distr = discrete_distribution<size_t>(counts.cbegin(), counts.cend());
    }

    discrete_mapped_distribution(const discrete_mapped_distribution&) = default;
    discrete_mapped_distribution& operator=(const discrete_mapped_distribution&) = default;

    template<typename URNG>
    T operator()(URNG& urng) {
        return values.at(distr(urng));
    }
};

class generator2 {
private:
    static map<char, discrete_mapped_distribution<char>> letters;

    minstd_rand rng;

public:
    static void initDistribution(const string& text) {
        map<char, map<char, uint64_t>> letterDistribution;

        string::const_iterator it = text.cbegin();
        char oldLetter = *it++;

        for (; it != text.cend();) {
            ++(letterDistribution[oldLetter][*it]);
            oldLetter = *it++;
        }

        generator2::letters = map<char, discrete_mapped_distribution<char>>();

        for (map<char, map<char, uint64_t>>::const_reference letter : letterDistribution) {
            generator2::letters[letter.first] = discrete_mapped_distribution<char>(letter.second);
        }
    }

    generator2() :
            rng(seed) {
    }

    char getNextChar(char in) {
        return letters.at(in)(rng);
    }
};

map<char, discrete_mapped_distribution<char>> generator2::letters;

Tal como están las cosas, esta solución es WIP y, por lo tanto, no tiene golf. También teniendo en cuenta que el tamaño real del código apenas tiene ningún impacto en la puntuación, pensé que publicaría mi respuesta primero antes de comenzar a optimizarlo.
(Código completo disponible aquí: https://github.com/BrainStone/MobyDickRNG - Incluye programa completo y búsqueda de semillas)

Esta solución se basa en un RNG. Primero analizo el texto. Creo un mapa que cuenta las ocurrencias de dos caracteres consecutivos. Luego creo un mapa de distribución. Todo esto se hace estáticamente, por lo que debe estar de acuerdo con las reglas.

Luego, mientras intento imprimir el texto, busco y extraigo un carácter aleatorio de los posibles. Si bien esto generalmente produce peores resultados que simplemente generar la siguiente letra más común, es probable que haya semillas de Dios que produzcan mejores resultados. Es por eso que la semilla está codificada. Actualmente estoy buscando la mejor semilla. Y actualizaré esta respuesta una vez que encuentre mejores semillas. ¡Así que mantente informado!

Si alguien quiere buscar semillas por sí mismo o usar diferentes RNG, no dude en bifurcar el repositorio.

Método utilizado para calcular la puntuación: https://github.com/BrainStone/MobyDickRNG/blob/master/src/search.cpp#L15

Tenga en cuenta que aunque la puntuación total es la peor en este momento, supera el recuento de errores de solo generar espacios. Y hay muchas posibilidades de que el puntaje disminuya, al verificar más semillas.

Registro de cambios

  • 24/01/2018 : Respuesta inicial publicada.
    Semillas marcadas: 0-50000. Puntuación: 2305 * 2 + 1017754 = 1022364
  • 24/01/2018 : Hicimos un mínimo de golf. Enlace agregado al método de cálculo de puntaje.
    Semillas marcadas: 0-80000. Puntuación: 1920 * 2 + 1017754 = 1021594 (-770)
  • 02/02/2018 : Nueva semilla (10087702) (no encontró el tiempo para arreglar el envío)
    Semillas marcadas: 0-32000000. Puntuación: 1923 * 2 + 1017344 = 1021190 (-404)
BrainStone
fuente
¿Podría incluir un arnés de prueba en su respuesta que evalúe el puntaje?
Nathaniel
@Nathaniel He vinculado el código de puntuación directamente. Además del repositorio, ¿considerarías esto lo suficiente?
BrainStone
Al revisar las reglas, me di cuenta de que violé algunas de ellas. Naturalmente, actualizaré mi respuesta una vez que solucione los problemas
BrainStone
Luego terminarás codificando el texto en la semilla aleatoria. Vea el lenguaje de programación esotérico Seed , y es posible que desee aplicar ingeniería inversa al programa MT19937 y superar esta respuesta (si puede).
user202729
Buena idea, pero no ayudará a obtener una buena puntuación. +1 de todos modos.
user202729
3

Rubí, 1164418 (ay)

Solo quería ver qué tan bien podría hacerlo sin verificar ninguna otra respuesta.
No estoy seguro de si esto está permitido porque incluye un literal que generé al analizar el archivo, pero incluso si no fuera así, no es como si estuviera en peligro de vencer a alguien.

x="\"ect,htabsdd,in,\\nodniwlrfydbulkm;f?ckgwvi0,.*pr;\\\"uz17klI\\n-c'WSpA\\nTwqu8.77!-BeWO5.4.CoP\\n\\\"UHEFu2.?-9.jo6.NI3.MaLYDOGoOAR'QUECziJoxp(\\nYa:\\nVI);K\\nUS*IZEX\\n&\\n$\\n_y[S\""
f=->n{(x.include? n)? x[x.index(n)+1] : ' '}

Como genere x

Primero, generé a.txtcon lo siguiente:

grep -o ".." whale2.txt | sort | uniq -c|sort -bn>a.txt

Entonces generé a.csv:

cat a.txt | awk '{ print $1","$2 }'|sort -n|tac>a.csv

Luego lo analicé xcon el siguiente script de Ruby:

f={}
File.open('./a.csv').each{|l|x=l.partition(',')
f[x.last[0..1]]=x.first}
n={}
r={}
f.each{|k,v|if((r.include? k[0]and v>n[k[0]])or not r.include? k[0])and not k[1].nil?
r[k[0]]=k[1]
n[k[0]]=v
end}
s=''
r.each{|k,v|s+=k+v}
puts s.inspect

Cómo anoté

w=File.read('whale2.txt')
x="ect,htabsdd,in,\nodniwlrfydbulkm;f?ckgwvi0,.*pr;\"uz17klI\n-c'WSpA\nTwqu8.77!-BeWO5.4.CoP\n\"UHEFu2.?-9.jo6.NI3.MaLYDOGoOAR'QUECziJoxp(\nYa:\nVI);K\nUS*IZEX\n&\n$\n_y[S"
f=->n{(x.include? n)? x[x.index(n)+1] : ' '}

score = 235
w.each_line{|l|v=l[0];l[0..-3].each_char{|n|v+=f[n]};v.split(//).each_with_index{|c,i|if l[i]==c
print c
else
print '_'
score+=1

end}}

puts "FINAL SCORE: #{score}"
NO_BOOT_DEVICE
fuente
Estoy seguro de que está permitido; Si se analizaron los archivos, buen trabajo! Solo si el programa lo hace, esto no es válido.
Erik the Outgolfer
@EriktheOutgolfer> _> (desliza silenciosamente un "(no competidor)" en el título)
NO_BOOT_DEVICE
¿Por qué? Si esto es válido, está compitiendo, aunque no gane mucho. Si no es válido (es decir, su solución lee el archivo y no solo contiene un literal), debe eliminarse.
Erik the Outgolfer
Hmmm Pensé que querías decir si algún programa analizaba el archivo, y no solo la solución.
NO_BOOT_DEVICE
1
No puedo leer Ruby, pero creo que esto es válido. Tener el literal dentro del programa está completamente bien, no hay problema en absoluto.
Nathaniel el
2

Python 3 , (146 * 2 + 879757) 880049 bytes

def f(c):return"\n                     t \n 2  sS \n  -  08........       huaoRooe oioaohue thpih eEA \n   neo    enueee neue hteht e"[ord(c)-10]

Pruébalo en línea!

Tabla de frecuencias bastante sencilla. Cada posición en la cadena corresponde al código ascii del carácter actual (menos 10 = 0x0a = '\ n', el carácter más bajo en el archivo), y el carácter en cada índice es el siguiente carácter más frecuente. Suponiendo que calculé las frecuencias correctamente ...

Probado con el código de la prueba de user202729

Kevin
fuente
¿Puedes guardar algunos bytes usando def f(c):return(" ">c)*c or"t ... e"[ord(c)-32]?
Neil
0

[Python 3] (644449 * 2 + 0) 1288898 puntos

Precisión perfecta en solo 644449 bytes

import zlib,base64 as s
t=enumerate(zlib.decompress(s.b64decode(b'###')).decode());a=lambda c:next(t)[1]

El código completo no puede caber en una respuesta, así que lo puse aquí y reemplacé el literal de cadena binaria grande con b '###' en el texto de respuesta.

Esto se genera con el siguiente código, donde "modified.py" es el archivo generado y "cheatsheet.txt" es el archivo whale2.txt que comienza en el segundo carácter.

import zlib, base64
with open("modified.py","w") as writer:
    writer.write("import zlib,base64 as s\nt=enumerate(zlib.decompress(s.b64decode(")
    with open("cheatsheet.txt","rb") as source:
        text = source.read()
        writer.write(str(base64.b64encode(zlib.compress(text,9))))
    writer.write(')).decode());a=lambda c:next(t)[1]')

El código se puede ejecutar agregando lo siguiente al final de "modified.py". "whale2.txt" debe estar en el mismo directorio que "modified.py", y la salida se escribirá en "out.txt".

with open("out.txt","w") as writer:
    with open("whale2.txt","r") as reader:
        text = reader.read()
        for b in text:
            c = a(b)
            writer.write(c)

Esta respuesta no accede directamente a whale.txt o whale2.txt. Hace uso de las bibliotecas de compresión estándar existentes según lo permitido explícitamente en las reglas.

Legorhin
fuente
podría haber un "\ r \ n" allí del que no podía deshacerme en Windows cuando los estaba contando
Legorhin
2
Sí, eso fue un error tipográfico que se propagó
Legorhin