Schreiben Sie ungefähr Moby Dick

297

Hier ist eine 1,2-MB-ASCII-Textdatei, die den Text von Herman Melvilles Moby-Dick enthält. oder der Wal . Ihre Aufgabe ist es, ein Programm oder eine Funktion (oder eine Klasse usw. - siehe unten) zu schreiben, die diese Datei jeweils zeichenweise erhält und bei jedem Schritt das nächste Zeichen erraten muss.

Das ist eine . Ihre Punktzahl wird sein

2*L + E

Wo List die Größe Ihrer Einreichung in Bytes und Ewie viele Zeichen werden falsch erraten? Die niedrigste Punktzahl gewinnt.

Weitere Angaben

Ihre Einreichung wird ein Programm oder eine Funktion (usw.) sein, die mehrmals aufgerufen oder aufgerufen oder Daten gesendet werden. (1215235-mal um genau zu sein.) Wenn es zum n- ten Mal aufgerufen wird, erhält es das n- te Zeichen von whale.txtoder whale2.txtund muss seine Schätzung für das ( n + 1 ) -te Zeichen ausgeben . Die EKomponente seiner Punktzahl ist die Gesamtzahl der Zeichen, die er falsch erraten hat.

Die meisten Übermittlungen müssen zwischen den Aufrufen einen bestimmten Status speichern, damit sie nachverfolgen können, wie oft sie aufgerufen wurden und wie die vorherigen Eingaben waren. Sie können dies tun, indem Sie in eine externe Datei schreiben, staticoder globale Variablen verwenden, eine Klasse anstelle einer Funktion übergeben, eine Statusmonade verwenden oder was auch immer für Ihre Sprache sonst noch funktioniert. Ihre Einreichung muss den Code enthalten, der zum Initialisieren des Status vor dem ersten Aufruf erforderlich ist.

Ihr Programm sollte deterministisch ablaufen, damit es bei gleicher Eingabe immer die gleichen Vermutungen anstellt (und daher immer die gleiche Punktzahl erhält).

Ihre Antwort muss nicht nur Ihren Beitrag enthalten, sondern auch den Code, den Sie zur Berechnung des ETeils der Punktzahl verwendet haben. Dies muss nicht in derselben Sprache wie Ihre Einreichung verfasst sein und wird nicht auf die Anzahl der Bytes angerechnet. Sie werden ermutigt, es lesbar zu machen.

In Bezug auf die Schnittstelle zwischen Ihrer Einreichung und diesem Score-Berechnungsprogramm ist alles in Ordnung, solange Ihr Programm immer ein Byte ausgibt, bevor es das nächste Byte an Eingaben erhält. (So ​​können Sie beispielsweise nicht einfach eine Zeichenfolge übergeben, die die gesamte Eingabe enthält, und eine Zeichenfolge zurückerhalten, die die gesamte Ausgabe enthält.)

Sie müssen Ihr Testprogramm ausführen und Ihre Punktzahl berechnen / verifizieren, bevor Sie Ihren Beitrag einreichen. Wenn Ihr Beitrag zu langsam ist, um die Punktzahl zu überprüfen, ist er nicht für den Wettbewerb qualifiziert, auch wenn Sie wissen, wie hoch die Punktzahl im Prinzip sein würde.

Die LKomponente Ihrer Punktzahl wird nach den üblichen Regeln für Code-Golf-Herausforderungen berechnet. Wenn Ihre Einreichung mehrere Dateien enthält, beachten Sie in diesem Fall die Regeln zur Bewertung und Verzeichnisstruktur . Alle Daten, die Ihr Code verwendet, müssen in Ihrer LPartitur enthalten sein.

Sie können vorhandene Bibliotheken importieren, aber möglicherweise keine anderen externen Dateien laden, und Ihr Code greift möglicherweise nicht auf whale.txtoder zuwhale2.txtDatei auf eine andere Weise als oben beschrieben. Sie dürfen keine vorab trainierten neuronalen Netze oder andere Quellen statistischer Daten laden. (Es ist in Ordnung, neuronale Netze zu verwenden, aber Sie müssen die Gewichtsdaten in Ihre Übermittlung einbeziehen und diese auf Ihre Byteanzahl angerechnet.) Wenn Ihre Sprache oder Bibliotheken aus irgendeinem Grund eine Funktion enthalten, die den gesamten oder einen Teil des Texts von Moby Dick enthält können Sie diese Funktion nicht verwenden. Abgesehen davon können Sie alle anderen eingebauten oder Bibliotheksfunktionen verwenden, die Sie mögen, einschließlich derer, die sich auf Textverarbeitung, Vorhersage oder Komprimierung beziehen, sofern sie Teil Ihrer Sprache oder ihrer Standardbibliotheken sind. Exotischere, speziellere Routinen, die statistische Datenquellen enthalten, müssen Sie selbst implementieren und in Ihre Byteanzahl einbeziehen.

Es ist wahrscheinlich, dass einige Übermittlungen Komponenten enthalten, die selbst durch Code generiert werden. In diesem Fall geben Sie bitte in Ihrer Antwort den Code an, mit dem sie erstellt wurden, und erläutern Sie die Funktionsweise . (Solange dieser Code nicht zum Ausführen Ihrer Übermittlung benötigt wird, wird er nicht in Ihre Byteanzahl aufgenommen.)

Aus historischen Gründen gibt es zwei Versionen der Datei, und Sie können beide in einer Antwort verwenden. In whale2.txt(oben verlinkt) wird der Text nicht umbrochen, so dass Zeilenumbrüche nur am Ende von Absätzen erscheinen. Im Original wird whale.txtder Text mit einer Breite von 74 Zeichen umgebrochen, sodass Sie das Ende jeder Zeile sowie den Text vorhersagen müssen. Dies macht die Herausforderung kniffliger und whale2.txtwird für neue Antworten empfohlen. Beide Dateien haben dieselbe Größe (1215236 Byte).


Zusammenfassend sollten alle Antworten die folgenden Punkte enthalten:

  • Ihre Einreichung selbst. (Der Code sowie alle verwendeten Datendateien - dies können Links sein, wenn sie groß sind.)
  • Eine Erklärung, wie Ihr Code funktioniert. Bitte erläutern Sie die E / A-Methode sowie die Vorhersage des nächsten Zeichens. Die Erklärung Ihres Algorithmus ist wichtig und gute Erklärungen bringen mir Kopfgeld.
  • Der Code, mit dem Sie Ihre Punktzahl bewertet haben. (Wenn dies mit einer vorherigen Antwort identisch ist, können Sie einfach darauf verlinken.)
  • Jeglicher Code, den Sie zum Erstellen Ihrer Einreichung verwendet haben, zusammen mit einer Erläuterung dieses Codes. Dies schließt Code ein, den Sie zur Optimierung von Parametern, zum Generieren von Datendateien usw. verwendet haben. (Dies wird nicht für Ihre Byteanzahl gezählt, sollte aber in Ihrer Antwort enthalten sein.)

Bestenliste

Kopfgelder

Von Zeit zu Zeit biete ich Kopfgelder an, um verschiedene Ansätze zu fördern.

Der erste, 50 Punkte, wurde an A. Rex für die beste Antwort seiner Zeit vergeben.

Die zweite, 100 Punkte, wurde ebenfalls an A. Rex für die gleiche Antwort vergeben, weil sie ihre bestehende Antwort mit einer sehr guten Erklärung versehen haben.

Die nächste Prämie, 200 Punkte , wird an beide vergeben

  • Eine wettbewerbsfähige Antwort, die eine neue Technik verwendet. (Dies wird auf meiner subjektiven Beurteilung basieren, da es mein Repräsentant ist, der die Belohnung erhält, aber Sie können mir vertrauen, dass ich fair bin. Beachten Sie, dass Ihre Antwort eine ausreichende Erklärung enthalten muss, damit ich verstehe, wie es funktioniert!) Eine solche Antwort ist nicht erforderlich Die Bestnote wird nicht erreicht, sie muss im Vergleich zu den vorhandenen Antworten nur einigermaßen gut abschneiden. Ich bin besonders an Lösungen interessiert, die auf wiederkehrenden neuronalen Netzen basieren, aber ich werde die Prämie für alles vergeben, was sich von den Markov-Modellen, die die aktuellen Top-Scores dominieren, zu unterscheiden scheint.

Oder:

  • Jeder andere, der mit einer beliebigen Methode die Bestnote von A. Rex (derzeit 444444) übertrifft.

Sobald die 200-Punkte-Prämie beansprucht wird, werde ich höchstwahrscheinlich eine 400-Punkte-Prämie anbieten und die Anforderungen entsprechend aktualisieren.

Nathaniel
quelle
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Dennis
9
xkcd.com/1960 scheint ein Hinweis auf diese Herausforderung zu sein!
A. Rex
Ich dachte , das zu komprimieren ... aber es ist ein bisschen zu lang , dass mein Computer abgestürzt Achselzucken
Naruyoko

Antworten:

135

/// , 2 * 1 + 1020874 = 1020876

 

Druckt ein Leerzeichen.

daniero
quelle
Kommentare sind nicht für eine längere Diskussion gedacht. Diese Unterhaltung wurde in den Chat verschoben .
Dennis
Das ist ein extrem kluges Belohnungs-Hacking! Sie müssen ein AGI sein;)
Alex
97

Node.js, 2 * 224 + 524279 = 524727

Bitte lesen Sie das Änderungsprotokoll am Ende dieses Beitrags, um die Punktzahl zu aktualisieren.

Eine Funktion, die ein Byte nimmt und zurückgibt.

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

Es besteht aus einem einfachen PPM-Modell , das die letzten 8 Zeichen betrachtet, um das nächste vorherzusagen.

Wir vertrauen einem Muster der Länge L, wenn wir es mindestens T [L] mal angetroffen haben , wobei T ein Array von willkürlichen Schwellenwerten ist: [1,1,2,1,2,3,5,2] . Außerdem vertrauen wir immer einem Muster, dessen erstes Zeichen übereinstimmt [A-Z '"(].

Wir wählen das längste vertrauenswürdige Muster aus und geben die Vorhersage mit der höchsten Punktzahl zurück, die diesem Muster zum Zeitpunkt des Aufrufs zugeordnet ist.

Anmerkungen

  • Dies ist offensichtlich nicht für die Geschwindigkeit optimiert, aber es läuft in etwa 15 Sekunden auf meinem Laptop.

  • Wenn wir den Vorgang mehrmals hintereinander wiederholen könnten, ohne das Modell zurückzusetzen, würde die Anzahl der Fehler nach 5 Iterationen auf ~ 268000 konvergieren.

  • Die aktuelle Erfolgsrate der Vorhersagefunktion beträgt ~ 56,8%. Wie von @immibis in den Kommentaren bemerkt, ist das Ergebnis nicht einmal schwer lesbar, wenn schlechte und richtige Vermutungen miteinander vermischt werden.

    Zum Beispiel dieses Snippet gegen Ende des Buches:

    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.
    

    wird:

    "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,
    

    Indem wir falsche Vermutungen durch Unterstriche ersetzen, haben wir eine bessere Vorstellung davon, was die Funktion richtig gemacht hat:

    _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 : Das obige Beispiel wurde mit einer früheren Version des Codes erstellt, die an der ersten Version der Eingabedatei arbeitete.

Code testen

/**
  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)

Änderungsprotokoll

  • 524727 - 19644 Punkte durch Wechseln zu whale2.txt gespeichert (Challenge-Update)
  • 544371 - 327 Punkte gespart, indem Muster, die mit einem Großbuchstaben, einem Anführungszeichen, einem doppelten Anführungszeichen oder einer öffnenden Klammer beginnen, immer als vertrauenswürdig eingestuft werden
  • 544698 - 2119 Punkte wurden gespeichert, indem Muster erzwungen wurden, die mit einem immer vertrauenswürdigen Leerzeichen beginnen
  • 546817 - 47 Punkte durch Anpassen der Schwellenwerte und Golfspielen der Vorhersagefunktion gespart
  • 546864 - 1496 Punkte wurden gespeichert, indem die maximale Musterlänge auf 8 Zeichen erweitert wurde
  • 548360 - 6239 Punkte wurden durch die Einführung von vertrauenswürdigen Mustern mit Schwellenwerten in Abhängigkeit von ihrer Länge eingespart
  • 554599 - 1030 Punkte durch Verbesserung der Zeilenvorschubvorhersage gespart
  • 555629 - sparte 22 Punkte durch Golfen der Vorhersagefunktion
  • 555651 - 40 Punkte durch Golfen der Vorhersagefunktion gespart
  • 555691 - anfängliche Punktzahl
Arnauld
quelle
44
Für die Neugierigen, nein, das bringt so etwas wie Moby Dick nicht hervor. Es ist eine ganze Menge 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. Es schafft es manchmal, ein paar vollständige Wörter zu bekommen. Wie whales.
immibis
23
@immibis Der Titel der Herausforderung wurde mit Bedacht gewählt. Das ist ungefähr Moby Dick . :-)
Arnauld
3
@ Nathaniel Es gab viele Updates, so dass diese kaum lesbar und nicht wirklich informativ wären. Ich habe stattdessen ein Änderungsprotokoll mit kurzen Erläuterungen zu den Verbesserungen hinzugefügt.
Arnauld
45
Ich denke, Ihr Programm macht tatsächlich eine perfekte Übersetzung ins Gälische.
Beska
1
@ Draco18s Es ist schwer zu sagen, ob dieses Komma eine gute oder eine schlechte Vermutung war. Wenn es sich um eine falsche Vermutung handelte, hat die Vorhersagefunktion möglicherweise zu Recht versucht, einen Buchstaben nach dem anderen Buchstaben zu setzen, der tatsächlich anstelle des Kommas vorhanden war, sobald er empfangen wurde.
Arnauld
91

Perl, 2 · 70525 + 326508 = 467558

Prädiktor

$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}

Um dieses Programm auszuführen, benötigen Sie diese Datei hier , die benannt werden muss B. (Sie können diesen Dateinamen in der zweiten Instanz des Bobigen Zeichens ändern .) Im Folgenden erfahren Sie, wie Sie diese Datei generieren.

Das Programm verwendet eine Kombination von Markov-Modellen im Wesentlichen wie in dieser Antwort von user2699 , jedoch mit einigen kleinen Änderungen. Dies erzeugt eine Verteilung für das nächste Zeichen. Wir verwenden die Informationstheorie, um zu entscheiden, ob ein Fehler akzeptiert oder Speicherplatz für BCodierungshinweise benötigt wird (und wenn ja, wie). Wir verwenden eine arithmetische Codierung , um gebrochene Bits aus dem Modell optimal zu speichern.

Das Programm ist 582 Bytes lang (einschließlich einer unnötigen letzten Zeile) und die Binärdatei Bist 69942 Bytes lang. Nach den Regeln für das Scoring mehrerer Dateien erhalten wir also L582 + 69942 + 1 = 70525.

Das Programm benötigt mit ziemlicher Sicherheit eine 64-Bit-Architektur (Little-Endian?). Die Ausführung einer m5.largeInstanz auf Amazon EC2 dauert ungefähr 2,5 Minuten .

Code testen

# 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

Das Testgeschirr geht davon aus, dass sich die Einreichung in der Datei befindet submission.pl, dies kann jedoch problemlos in der zweiten Zeile geändert werden.

Textvergleich

"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

Dieses Beispiel (in einer anderen Antwort ausgewählt ) kommt ziemlich spät im Text vor, daher ist das Modell zu diesem Zeitpunkt ziemlich entwickelt. Denken Sie daran, dass das Modell um 70 Kilobyte an "Hinweisen" erweitert ist, die es beim Erraten der Zeichen direkt unterstützen. es wird nicht einfach von dem kurzen Code-Snippet oben gesteuert.

Hinweise generieren

Das folgende Programm akzeptiert den oben angegebenen genauen Übermittlungscode (bei Standardeingabe) und generiert die oben angegebene genaue BDatei (bei Standardausgabe):

@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],'}}'

Die Ausführung dauert ungefähr so ​​lange wie die Übermittlung, da ähnliche Berechnungen durchgeführt werden.

Erläuterung

In diesem Abschnitt werden wir versuchen, die Funktionsweise dieser Lösung so detailliert zu beschreiben, dass Sie sie selbst "zu Hause ausprobieren" können. Die Haupttechnik, die diese Antwort von den anderen unterscheidet, ist ein paar Abschnitte weiter unten als "Zurückspulen" -Mechanismus, aber bevor wir dort ankommen, müssen wir die Grundlagen einrichten.

Modell

Der Grundbestandteil der Lösung ist ein Sprachmodell. Für unsere Zwecke ist ein Modell etwas, das etwas englischen Text benötigt und eine Wahrscheinlichkeitsverteilung für das nächste Zeichen zurückgibt . Wenn wir das Modell verwenden, wird der englische Text ein (korrektes) Präfix von Moby Dick sein. Bitte beachten Sie, dass es sich bei der gewünschten Ausgabe um eine Verteilung handelt und nicht nur um eine Vermutung für das wahrscheinlichste Zeichen.

In unserem Fall verwenden wir im Wesentlichen das Modell in dieser Antwort von user2699 . Wir haben nicht das Modell aus der Antwort mit der höchsten Punktzahl (außer unserer eigenen) von Anders Kaseorg verwendet , da wir nicht in der Lage waren, eine Verteilung zu extrahieren, sondern nur eine einzige bestmögliche Vermutung. Theoretisch berechnet diese Antwort einen gewichteten geometrischen Mittelwert, aber wir haben etwas schlechte Ergebnisse erzielt, wenn wir das zu wörtlich interpretiert haben. Wir haben ein Modell aus einer anderen Antwort "gestohlen", weil unsere "geheime Sauce" nicht das Modell ist, sondern der Gesamtansatz. Wenn jemand ein "besseres" Modell hat, sollte er in der Lage sein, mit dem Rest unserer Techniken bessere Ergebnisse zu erzielen.

Bemerkenswert ist, dass die meisten Komprimierungsmethoden wie Lempel-Ziv auf diese Weise als "Sprachmodell" angesehen werden können, obwohl man möglicherweise ein wenig schielen muss. (Es ist besonders schwierig für etwas, das eine Burrows-Wheeler-Transformation ausführt!) Beachten Sie außerdem, dass das Modell von user2699 eine Modifikation eines Markov-Modells ist. Im Grunde genommen ist nichts anderes für diese Herausforderung oder vielleicht sogar für das Modellieren von Text im Allgemeinen wettbewerbsfähig.

Gesamtarchitektur

Zum besseren Verständnis ist es hilfreich, die Gesamtarchitektur in mehrere Teile zu unterteilen. Aus Sicht der obersten Ebene muss ein wenig Code für die Zustandsverwaltung vorhanden sein. Das ist nicht besonders interessant, aber der Vollständigkeit halber möchten wir betonen, dass das Programm an jedem Punkt, an dem es nach der nächsten Vermutung gefragt wird, ein korrektes Präfix von Moby Dick hat. Wir verwenden unsere früheren falschen Vermutungen in keiner Weise. Aus Gründen der Effizienz kann das Sprachmodell wahrscheinlich seinen Zustand aus den ersten N Zeichen wiederverwenden, um seinen Zustand für die ersten (N + 1) Zeichen zu berechnen, aber im Prinzip kann es jedes Mal, wenn es aufgerufen wird, Dinge von Grund auf neu berechnen.

Lassen Sie uns diesen grundlegenden "Treiber" des Programms beiseite legen und einen Blick in den Teil werfen, der das nächste Zeichen errät. Es ist konzeptionell hilfreich, drei Teile zu trennen: das oben beschriebene Sprachmodell, eine "Hinweis" -Datei und einen "Interpreter". Bei jedem Schritt fragt der Interpreter das Sprachmodell nach einer Verteilung für das nächste Zeichen und liest möglicherweise einige Informationen aus der Hinweisdatei. Dann werden diese Teile zu einer Vermutung kombiniert. Welche Informationen genau in der Hinweisdatei enthalten sind und wie sie verwendet werden, wird später erläutert. Derzeit hilft es jedoch, diese Teile mental voneinander zu trennen. Beachten Sie, dass die Hinweisdatei in Bezug auf die Implementierung buchstäblich eine separate (binäre) Datei ist, es sich jedoch auch um eine Zeichenfolge oder eine im Programm gespeicherte Datei handeln könnte. Als eine Annäherung,

Wenn Sie eine Standardkomprimierungsmethode wie bzip2 wie in dieser Antwort verwenden , entspricht die Datei "hints" der komprimierten Datei. Der "Interpreter" entspricht dem Dekomprimierer, während das "Sprachmodell" ein wenig implizit ist (wie oben erwähnt).

Warum eine Hinweisdatei verwenden?

Lassen Sie uns ein einfaches Beispiel auswählen, um es weiter zu analysieren. Angenommen, der Text besteht aus NZeichen, die lang und durch ein Modell gut angenähert sind, bei dem jedes Zeichen (unabhängig) der Buchstabe Emit einer Wahrscheinlichkeit von etwas weniger als einer Hälfte, Tähnlich einer Wahrscheinlichkeit von etwas weniger als einer Hälfte und einer AWahrscheinlichkeit von 1/1000 = 0,1% ist. Nehmen wir an, dass keine anderen Zeichen möglich sind. in jedem Fall ist das Aziemlich ähnlich wie bei einem zuvor unsichtbaren Charakter aus heiterem Himmel.

Wenn wir im L 0 -Regime operieren (wie die meisten, aber nicht alle anderen Antworten auf diese Frage), gibt es keine bessere Strategie für den Dolmetscher als eine von Eund auszuwählen T. Im Durchschnitt wird ungefähr die Hälfte der Zeichen korrekt angezeigt. Also E ≈ N / 2 und die Punktzahl score N / 2 auch. Wenn wir jedoch eine Komprimierungsstrategie verwenden, können wir auf etwas mehr als ein Bit pro Zeichen komprimieren. Da L in Bytes gezählt wird, erhalten wir L ≈ N / 8 und erhalten somit ≈ N / 4, doppelt so gut wie die vorherige Strategie.

Das Erreichen dieser Rate von etwas mehr als einem Bit pro Zeichen für dieses Modell ist etwas nicht trivial, aber eine Methode ist die arithmetische Codierung.

Arithmetische Codierung

Wie allgemein bekannt ist, ist eine Codierung eine Möglichkeit, einige Daten unter Verwendung von Bits / Bytes darzustellen. Beispielsweise ist ASCII eine 7-Bit- / Zeichen-Codierung von englischem Text und verwandten Zeichen und die Codierung der betreffenden Originaldatei von Moby Dick. Wenn einige Buchstaben häufiger vorkommen als andere, ist eine Codierung mit fester Breite wie ASCII nicht optimal. In einer solchen Situation greifen viele Menschen zur Huffman-Codierung . Dies ist optimal, wenn Sie einen festen (vorwahlfreien) Code mit einer ganzzahligen Anzahl von Bits pro Zeichen wünschen.

Die arithmetische Codierung ist jedoch noch besser. Grob gesagt ist es möglich, "gebrochene" Bits zum Codieren von Informationen zu verwenden. Es gibt viele Anleitungen zur arithmetischen Codierung, die online verfügbar sind. Wir werden die Details hier überspringen (insbesondere die praktische Implementierung, die aus Programmiersicht etwas schwierig sein kann), da andere Ressourcen online verfügbar sind. Wenn sich jemand beschwert, kann dieser Abschnitt möglicherweise weiter ausgearbeitet werden.

Wenn Text tatsächlich von einem bekannten Sprachmodell generiert wurde, bietet die arithmetische Codierung eine im Wesentlichen optimale Codierung von Text aus diesem Modell. In gewissem Sinne löst dies das Komprimierungsproblem für dieses Modell. (In der Praxis besteht das Hauptproblem darin, dass das Modell nicht bekannt ist und einige Modelle besser als andere in der Modellierung von menschlichem Text sind.) Wenn es nicht erlaubt war, Fehler in diesem Wettbewerb zu machen, dann in der Sprache des vorherigen Abschnitts Eine Möglichkeit, eine Lösung für diese Herausforderung zu finden, wäre gewesen, einen arithmetischen Codierer zu verwenden, um eine "Hinweis" -Datei aus dem Sprachmodell zu generieren, und dann einen arithmetischen Decodierer als "Interpreter" zu verwenden.

Bei dieser im Wesentlichen optimalen Codierung werden am Ende -log_2 (p) Bits für ein Zeichen mit der Wahrscheinlichkeit p ausgegeben, und die Gesamtbitrate der Codierung ist die Shannon-Entropie . Dies bedeutet, dass ein Zeichen mit einer Wahrscheinlichkeit in der Nähe von 1/2 ungefähr ein Bit zum Codieren benötigt, während eines mit einer Wahrscheinlichkeit von 1/1000 ungefähr 10 Bit benötigt (da 2 ^ 10 ungefähr 1000 ist).

Die Bewertungsmetrik für diese Herausforderung wurde jedoch gut gewählt, um die Komprimierung als optimale Strategie zu vermeiden. Wir müssen einen Weg finden, Fehler zu machen, um eine kürzere Datei mit Hinweisen zu erhalten. Eine Strategie, die man versuchen könnte, ist beispielsweise eine einfache Verzweigungsstrategie: Wir versuchen im Allgemeinen, arithmetische Codierung zu verwenden, wenn wir können, aber wenn die Wahrscheinlichkeitsverteilung aus dem Modell in irgendeiner Weise "schlecht" ist, raten wir nur das wahrscheinlichste Zeichen und geben " nicht versuchen, es zu codieren.

Warum Fehler machen?

Lassen Sie uns das Beispiel von vorhin analysieren, um zu motivieren, warum wir Fehler "absichtlich" machen möchten. Wenn wir arithmetische Codierung verwenden, um das richtige Zeichen zu codieren, geben wir im Fall von Eoder Tungefähr ein Bit aus, im Fall von A.

Insgesamt ist dies eine ziemlich gute Kodierung, die etwas mehr als ein bisschen pro Zeichen ausgibt, obwohl es drei Möglichkeiten gibt. Im Grunde ist das Aziemlich unwahrscheinlich und wir werden die entsprechenden zehn Bits nicht allzu oft ausgeben. Wäre es nicht schön, wenn wir stattdessen einen Fehler machen könnten A? Immerhin betrachtet die Metrik für das Problem 1 Byte = 8 Bits Länge als äquivalent zu 2 Fehlern; daher sollte man einen Fehler vorziehen, anstatt mehr als 8/2 = 4 Bits für ein Zeichen auszugeben. Mehr als ein Byte für die Speicherung eines Fehlers auszugeben, klingt definitiv suboptimal!

Der "Rücklauf" -Mechanismus

In diesem Abschnitt wird der wichtigste clevere Aspekt dieser Lösung beschrieben, mit dem fehlerhafte Vermutungen ohne Kosten für die Länge behoben werden können.

Für das einfache Beispiel, das wir analysiert haben, ist der Rückspulmechanismus besonders einfach. Der Interpreter liest ein Bit aus der Hinweisdatei. Wenn es eine 0 ist, wird es erraten E. Wenn es eine 1 ist, wird es erraten T. Beim nächsten Aufruf wird das richtige Zeichen angezeigt. Wenn die Hinweisdatei gut eingerichtet ist, können wir sicherstellen, dass der Interpreter im Fall eines Eoder Trichtig errät. Aber was ist mit A? Die Idee des rewind Mechanismus ist einfach nicht codiert Aüberhaupt . Genauer gesagt, wenn der Interpreter später erfährt, dass das richtige Zeichen ein war A, " spult er das Band metaphorisch zurück ": Er gibt das zuvor gelesene Bit zurück. Das gelesene Bit soll Eoder codierenT, aber jetzt nicht; es wird später verwendet. In diesem einfachen Beispiel, das bedeutet im Wesentlichen , dass es immer das gleiche Zeichen erraten ( Eoder T) , bis sie macht es richtig; dann liest es noch ein bisschen und geht weiter.

Die Kodierung für diese Hinweisdatei ist sehr einfach: Verwandeln Sie alle Es in 0-Bits und Ts in 1-Bits, während Sie As vollständig ignorieren . Nach der Analyse am Ende des vorherigen Abschnitts macht dieses Schema einige Fehler, reduziert jedoch die Gesamtpunktzahl, indem keines der As codiert wird . Als kleinerer Effekt wird tatsächlich auch die Länge der Hints-Datei gespart, da am Ende genau ein Bit für jedes Eund Tnicht etwas mehr als ein Bit verwendet wird.

Ein kleiner Satz

Wie entscheiden wir, wann wir einen Fehler machen? Angenommen, unser Modell gibt uns eine Wahrscheinlichkeitsverteilung P für das nächste Zeichen. Wir werden die möglichen Zeichen in zwei Klassen unterteilen: codiert und nicht codiert . Wenn das richtige Zeichen nicht codiert ist, verwenden wir am Ende den "Zurückspulen" -Mechanismus, um einen Fehler ohne Kosten in der Länge zu akzeptieren. Wenn das richtige Zeichen codiert ist, verwenden wir eine andere Verteilung Q, um es mit arithmetischer Codierung zu codieren.

Aber welche Verteilung Q sollten wir wählen? Es ist nicht schwer zu erkennen, dass die codierten Zeichen alle eine höhere Wahrscheinlichkeit (in P) haben sollten als die nicht codierten Zeichen. Außerdem sollte die Verteilung Q nur die codierten Zeichen enthalten. Schließlich codieren wir nicht die anderen, also sollten wir keine Entropie für sie "ausgeben". Es ist etwas schwieriger zu erkennen, dass die Wahrscheinlichkeitsverteilung Q für die codierten Zeichen proportional zu P sein sollte. Wenn wir diese Beobachtungen zusammenfassen, bedeutet dies, dass wir die wahrscheinlichsten Zeichen, aber möglicherweise nicht die unwahrscheinlichsten Zeichen codieren sollten und dass Q für die codierten Zeichen einfach P-neu skaliert wird.

Es stellt sich außerdem heraus, dass es einen coolen Satz gibt, welchen "Cutoff" man für die Codierungszeichen auswählen sollte: Sie sollten ein Zeichen codieren, solange es mindestens 1 / 5.393 so wahrscheinlich ist wie die anderen codierten Zeichen zusammen. Dies "erklärt" das Auftreten der scheinbar zufälligen Konstante 5.393am Ende des obigen Programms. Die Zahl 1 / 5.393 ≈ 0.18542 ist die Lösung der Gleichung -p log (16) - p log p + (1 + p) log (1 + p) = 0 .

Vielleicht ist es eine vernünftige Idee, diese Prozedur in Code zu schreiben. Dieses Snippet ist in 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;
}

Alles zusammen

Der vorherige Abschnitt ist leider ein wenig technisch, aber wenn wir alle anderen Teile zusammenfügen, ist die Struktur wie folgt. Wann immer das Programm aufgefordert wird, das nächste Zeichen nach einem bestimmten korrekten Zeichen vorherzusagen:

  1. Fügen Sie dem bekannten korrekten Präfix von Moby Dick das richtige Zeichen hinzu.
  2. Aktualisieren Sie das (Markov-) Modell des Texts.
  3. Die geheime Sauce : Wenn die vorherige Vermutung falsch war, spulen Sie den Zustand des arithmetischen Decoders auf den Zustand vor der vorherigen Vermutung zurück!
  4. Bitten Sie das Markov-Modell, eine Wahrscheinlichkeitsverteilung P für das nächste Zeichen vorherzusagen.
  5. Transformiere P nach Q mit der Subroutine aus dem vorherigen Abschnitt.
  6. Bitten Sie den arithmetischen Decoder, ein Zeichen aus dem Rest der Hinweisdatei gemäß der Verteilung Q zu decodieren.
  7. Errate den resultierenden Charakter.

Die Codierung der Hinweisdatei funktioniert ähnlich. In diesem Fall weiß das Programm, was das richtige nächste Zeichen ist. Wenn es sich um ein Zeichen handelt, das codiert werden soll, sollte natürlich der arithmetische Encoder verwendet werden. Wenn es sich jedoch um ein nicht codiertes Zeichen handelt, wird der Status des arithmetischen Codierers nicht aktualisiert.

Wenn Sie den informationstheoretischen Hintergrund wie Wahrscheinlichkeitsverteilungen, Entropie, Komprimierung und arithmetische Codierung verstehen, diesen Beitrag aber nicht verstanden haben (außer warum der Satz wahr ist), lassen Sie es uns wissen und wir können versuchen, die Dinge aufzuklären. Danke fürs Lesen!

A. Rex
quelle
8
Wow, beeindruckende Antwort. Ich nehme an, es wird zusätzlicher Code benötigt, um die BDatei zu generieren . Wenn ja, können Sie das bitte in Ihre Antwort aufnehmen?
Nathaniel
8
Ausgezeichnet! Die erste (und bislang einzige) Antwort, die die 500-km-Marke durchbricht.
ShreevatsaR
5
Ich weine
Phill
5
Da während des Kopfgeldzeitraums keine neuen Antworten veröffentlicht wurden, vergebe ich sie an Ihre Antwort, die sowohl die beste Bewertung als auch den ausgefeiltesten Ansatz darstellt. Wenn Sie jemals Zeit haben, würde ich wirklich zu schätzen eine genauere Erklärung, wie diese Antwort funktioniert, das heißt , was genau der Algorithmus?
Nathaniel
2
@ Nathaniel: Ich habe diesem Beitrag eine Erklärung hinzugefügt. Lassen Sie mich wissen, wenn Sie der Meinung sind, dass es detailliert genug ist, um die Lösung selbst zu reproduzieren.
A. Rex
77

Python 3, 2 · 267 + 510193 = 510727

Prädiktor

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]

Dies verwendet eine gewichtete Bayes'sche Kombination der Ordnung 0,…, 16 Markov-Modelle mit Gewichten [1, 6, 12, 30, 65, 99, 87, 117, 118, 89, 95, 118, 96, 184, 126, 219, 126].

Das Ergebnis ist nicht sehr empfindlich in Bezug auf die Auswahl dieser Gewichte, aber ich habe sie optimiert, weil ich denselben Algorithmus für die späte Akzeptanz des Bergsteigens verwenden konnte, den ich in meiner Antwort auf die Frage "Stellen Sie eine Senatsmehrheit zusammen" verwendet habe , bei der es sich um jede mögliche Mutation handelt Nur ein ± 1-Inkrement zu einem einzelnen Gewicht.

Code testen

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
quelle
2
Das richtige Werkzeug für den Job. Tolles Ergebnis. Schön.
Geändert
1
Mögliche Klarstellung: b"\0\3\6\r\34'&-20'\22!P\n[\26"Ist die ASCII-Darstellung der Gewichte, bei der kleine nicht druckbare Werte in Oktal maskiert werden.
Cœur
Ich habe die Frage mit einer Version der Datei aktualisiert, in der der Text nicht umbrochen ist - Sie könnten versuchen, Ihren Code darauf erneut auszuführen (es könnte etwas besser sein)
Nathaniel
3
Vielen Dank für diese Erklärung - wenn Sie eine Zusammenfassung in die Frage bearbeiten könnten, wäre es großartig. (Die Erfahrung mit meiner vorherigen Herausforderung Paint Starry Night hat ergeben, dass diese Optimierungsverfahren der interessanteste Teil der Antworten sind. Es ist daher viel besser, wenn die Antworten den dafür verwendeten Code und eine Erklärung enthalten. Ich habe in beiden eine Regel eingefügt Herausforderungen sagen, dass sie sollten.)
Nathaniel
1
@Christoph Meine Modellkombination ist eigentlich ein gewichtetes geometrisches Mittel. Der Durchschnitt der PAQs im Logistikbereich ist jedoch etwas anders - ich muss sehen, ob das besser ist.
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

Probieren Sie es online!

Eine Funktion, die globale Variablen verwendet. Lernt, wie es geht, und baut ein Modell auf Wortebene: Was ist der häufigste nächste Charakter, wenn man bedenkt , was in diesem Wort bisher gesehen wurde ? Je mehr Eingaben eingehen, desto besser lernt es gebräuchliche Wörter aus dem Text und desto häufiger wird das Zeichen zum Starten des nächsten Wortes gelernt .

Zum Beispiel:

  • Wenn das, was es bisher gesehen hat, "Captai" ist, sagt es ein "n" voraus
  • Wenn es sich um "Captain" handelt, wird ein Leerzeichen vorhergesagt
  • Wenn es der Anfang eines Wortes ist und das letzte Wort "Captain" war, sagt es ein "A" voraus.
  • Wenn das Wort bisher "A" ist, sagt es ein "h" voraus (und dann "a" und "b"; ähnlich für "C").

Am Anfang ist es nicht besonders gut, aber am Ende kommen große Teile der tatsächlichen Wörter heraus. Die Fallback-Option ist ein Leerzeichen und nach einem einzelnen Leerzeichen ein "a", es sei denn, der vorangegangene Buchstabe war "nedtfo", eine Ziffer oder ein Bindestrich oder Apostroph. Außerdem werden Zeilenumbrüche nach 71 Zeichen aggressiv vorhergesagt, oder wenn nach 66 ein Leerzeichen erwartet wurde. Beide wurden nur auf die Daten abgestimmt ("t" ist nach einem Leerzeichen weitaus häufiger, wurde jedoch bereits häufiger vorhergesagt, sodass " a "ist eine bessere Vermutung außerhalb dieser sechs Sonderfälle).

Zu lernen, welche Wortpaare zusammengehören, und die Zuordnung vorzubereiten, erwies sich als nicht lohnenswert.


Es endet mit folgendem Text:

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!

Das entspricht diesem Teil der Eingabe:

überall um ihn herum.

"Ich habe ihn fast im selben Moment gesehen, Sir, wie Captain Ahab, und ich habe geschrien", sagte Tashtego.

"Nicht im selben Moment; nicht im selben - nein, der Dublon gehört mir, das Schicksal hat den Dublon für mich reserviert. Ich nur; keiner von euch hätte den Weißen Wal zuerst aufziehen können. Da bläst sie! - Da bläst sie! - -dort bläst sie!

Sie können sehen, wo die Eigennamen besonders gut herauskommen, aber die Wortenden stimmen meistens auch. Wenn es "dou" gesehen wird, erwartet es "Zweifel", aber sobald das "l" erscheint, wird es "doubloon".

Wenn Sie es ein zweites Mal mit demselben Modell ausführen, das es gerade erstellt hat, werden sofort weitere 92.000 korrekt angezeigt (51,7% -> 59,3%), aber ab der zweiten Iteration sind es immer knapp 60%.


Der Messcode befindet sich im TIO-Link oder hier ist eine etwas bessere Version:

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 hat die erratene Ausgabe am Ende.

Michael Homer
quelle
3
Dies ist ein ausgezeichneter Ansatz!
Skyler
2
zu viel <s> </ s>;)
FantaC
1
+1, weil dieser Ansatz mich an den LZW-Komprimierungsalgorithmus erinnerte.
Marcos
25

C ++, Ergebnis: 2 · 132 + 865821 = 866085

Vielen Dank an @Quentin für das Speichern von 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;}

Eine sehr einfache Lösung, bei der für ein bestimmtes Zeichen nur das Zeichen ausgegeben wird, das am häufigsten nach dem eingegebenen Zeichen erscheint.

Überprüfen Sie die Punktzahl mit:

#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;
}

Bearbeiten: Mit erhalten Sie whale2.txteine bessere Punktzahl.

Steadybox
quelle
5
Sie können dieses Array in ein String-Literal umwandeln und direkt in das Array einfügen L, um eine Reihe von Zeichen zu speichern :)
Quentin
@Quentin Danke! Jetzt frage ich mich, warum ich überhaupt nicht daran gedacht habe ...
Steadybox
20

Python, 2 · 516 + 521122 = 522154

Algorithmus:

Bei einer weiteren Python-Übermittlung berechnet dieser Algorithmus den wahrscheinlichsten nächsten Buchstaben, wobei Sequenzen der Länge 1, ..., l betrachtet werden. Die Summe der Wahrscheinlichkeiten wird verwendet, und es gibt einige Tricks, um bessere Ergebnisse zu erzielen.

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')]

Ergebnisse:

Meistens Kauderwelsch, obwohl man sieht, dass es gelegentlich auftaucht, wie zum Beispiel "Father 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

Testcode:

Ziemlich einfach, gibt einige Textbeispiele an verschiedenen Stellen aus. Verwendet whale2.txt, da dadurch zusätzliche Logik zum Berechnen von Zeilenumbrüchen vermieden wird.

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'))
user2699
quelle
3
Willkommen auf der Seite! Dies ist eine fantastische erste Einreichung. :)
DJMcMayhem
@DJMcMayhem, Danke für die Begrüßung. Ich habe es schon eine Weile genossen, mir zuzuschauen. Dies ist der erste Wettbewerb, der meine Aufmerksamkeit auf einen Beitrag lenkt.
user2699
19

C (gcc) , 679787 652892

84 76 Bytes, 679619 652740 falsche Vermutungen

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];}

Probieren Sie es online!

Update: ~ 27000 Punkte bei aktualisierter Datei, 16 Punkte (8 Bytes) bei besserer Golffunktion.

Erläuterung

Dies funktioniert so, dass der Code beim Durchlaufen des Texts das letzte Zeichen speichert, das eine bestimmte 4-stellige Sequenz beendet hat, und diesen Wert zurückgibt. Ähnlich wie Arnauld oben, aber abhängig von der Wahrscheinlichkeit, dass zwei vorgegebene 4-Zeichen-Sequenzen auf die gleiche Weise enden.

Entgolft:

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.
}

quelle
... TIO Link ist nutzlos. Gibt die Funktion also den Wert der letzten Zuweisung zurück?
user202729
Lassen Sie mich die Antwort mit einer Erklärung bearbeiten, dann :)
1
@Rogem Ich habe eine De-Golf-Version hinzugefügt (was ich auch getan habe, weil ich ihr nicht folgen konnte).
Adam Davis
@AdamDavis Bei den meisten Implementierungen von C beginnen alle globalen Variablen bei Null. Es ist undefiniertes Verhalten, daher wird es nur im Code-Golf verwendet.
NieDzejkob
1
@NieDzejkob Ah, du hast recht, danke! "Für ANSI-C müssen alle nicht initialisierten statischen / globalen Variablen mit 0 initialisiert werden."
Adam Davis
16

sh + bzip2, 2 * 364106 = 728212

2 * 381249 + 0 = 762498

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

gefolgt von der bzip2-komprimierten whale2.txt mit dem ersten fehlenden Byte

Ignoriert seine Eingabe; gibt die richtige Antwort aus. Dies liefert eine Basislinie an einem Ende; daniero liefert am anderen ende eine grundlinie.

Builder-Skript:

#!/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

E / A-Testkabelbaum (tcc; erste Zeile für gcc abschneiden). Dieses Testkabel kann von jedermann auf einer geeigneten Plattform verwendet werden, die ein vollständiges Programm einreicht, das Lese- / Schreib-E / A erwartet. Es werden Byte-für-Byte-E / A verwendet, um Betrug zu vermeiden. Das untergeordnete Programm muss die Ausgabe nach jedem Byte leeren, um ein Blockieren zu vermeiden.

#!/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
quelle
6
Ich denke, was er fragt, ist: Wie verstößt dies nicht gegen die 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.Klausel?
8
@Rogem Die komprimierten Daten werden nach den hier gezeigten Daten abgelegt, und der Code greift auf sich selbst zu.
user202729
4
Die Frage lautet: "Ihre Einreichung wird ein Programm oder eine Funktion (usw.) sein, die mehrmals aufgerufen oder aufgerufen wird. Wenn es für die nthZeit aufgerufen wird, erhält es das n-te Zeichen von whale.txtoder whale2.txtund muss seine Vermutung für das ausgeben (n+1)thCharakter." - Wie wird diese Anforderung erfüllt? Der Code zeigt bei whale.txtjeder Ausführung den gesamten Text an .
Axiac
1
@axiac "Alles ist in Ordnung, solange Ihr Programm immer ein Byte ausgibt, bevor es das nächste Byte empfängt."
user202729
5
@axiac Angesichts des Testgeschirrs bin ich froh, das Senden eines Programmbytes von STDIN als "Aufrufen oder Aufrufen" zu betrachten. Das Wichtigste ist, dass das Programm nach jedem Byte der Eingabe ein Byte der Ausgabe zurückgibt, was dieses tatsächlich tut, wenn es durch das Testkabel läuft. Die Frage lautet: "Alles ist in Ordnung, solange Ihr Programm immer ein Byte ausgibt, bevor es das nächste Byte empfängt."
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])

Probieren Sie es online!


... Die ///Antwort, die ein Leerzeichen ausgibt, erhält 10 Upvotes, während mein Code nur 3 bekommen kann ...

Erläuterung:

Für jeden Charakter hat das Programm:

  • erhöhen, ansteigen frequency[prev][char]
  • Suchen Sie den Charakter, der am häufigsten in vorkommt frequency[char]
  • und es ausgeben.

  • Ungolfed-Code im TIO-Link, auskommentiert.
  • Der Code ist 131 Bytes.
  • Der auf meinem Computer ausgeführte Code meldet:
879504 / 1215235
Time: 62.01348257784468

die haben die Gesamtpunktzahl

2*131 + 879504 = 879766

Da es keine Möglichkeit gibt, eine große Datei zu TIO hochzuladen (außer Dennis zu fragen), wird im Beispiel, das über den TIO-Link ausgeführt wird, nur das Programm für einen kleinen Teil des Texts ausgeführt.

Im Vergleich zur älteren Antwort hat diese 362 falschere Zeichen, aber der Code ist um 255 Bytes kürzer. Der Multiplikator bewirkt, dass mein Beitrag eine niedrigere Punktzahl aufweist.

user202729
quelle
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:' ';}}

Bei diesem Ansatz wird eine Nachschlagetabelle verwendet, um das häufigste Zeichen nach einer bestimmten Zeichenfolge zu ermitteln. Die Schlüssel der Nachschlagetabelle haben maximal 4 Zeichen, daher aktualisiert die Funktion zuerst die Nachschlagetabelle mit dem aktuellen Zeichen und prüft dann nur, welches Zeichen nach den 4 vorhergehenden Zeichen, einschließlich des aktuellen Zeichens, am wahrscheinlichsten ist . Wenn diese 4 Zeichen nicht in der Nachschlagetabelle gefunden werden, wird ein Leerzeichen gedruckt.

Diese Version verwendet die whale2.txtDatei, da sie die Anzahl der erfolgreichen Vermutungen erheblich verbessert.

Der folgende Code wird zum Testen der Klasse verwendet:

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();
    }
}

Der Code läuft in knapp 2 Sekunden. Nur zur Veranschaulichung: Dies erhalte ich, wenn ich die Größe der Schlüssel der Nachschlagetabelle ändere (einschließlich der Ergebnisse eines zweiten Durchlaufs ohne Zurücksetzen des Modells):

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

Es wäre interessant zu wissen, warum eine Schlüsselgröße von 4 Zeichen die beste Wahl für diesen Algorithmus ist.

Textvergleich

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!"

Neu erstellt:

"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 

Vermutungen:

"_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__

Änderungsprotokoll

  • 569279 - geändert whale2.txtund damit die Optimierung entfernt.
  • 577366 - optimiert mit Code, der versucht hat, zu erraten, wann ein Zeilenvorschub zurückgegeben werden soll.
  • 590354 - ursprüngliche Version.
Charlie
quelle
4
Vielen Dank, dass Sie die Varianz anzeigen, während Sie die Schlüsselgröße und den Spaltenschwellenwert ändern!
Jeremy Weirich
Ich habe die Frage mit einer Version der Datei aktualisiert, in der der Text nicht umbrochen ist - damit können Sie wahrscheinlich einige Punkte sparen
Nathaniel
@ Nathaniel tut es in der Tat. Ich habe die Antwort aktualisiert.
Charlie
Sie können einige Bytes mit var speichern, anstatt die Typen zu deklarieren.
Ed T
1
Mit zunehmender Tastengröße sinkt die Anzahl der Treffer und Fehler, und es werden mehr Leerzeichen ausgegeben, wenn eine kürzere Taste möglicherweise das richtige Zeichen erraten hat. Wenn die Schlüsselgröße kleiner wird, sind die einzelnen Schätzungen für übereinstimmende Segmente ungenauer. Ich vermute deshalb, dass eine Länge von vier optimal ist. Wenn Sie Schlüssel mit mehreren Längen gepflegt und kürzere Übereinstimmungen verwendet haben, wenn längere nicht verfügbar sind, dann erwarte ich, dass sich die Trefferquote (und damit die Punktzahl) bei längeren Schlüssellängen erheblich verbessert.
Jeffrey L Whitledge
11

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

Java ist zum Kotzen für kleine Programmgrößen. Wie auch immer, ich habe mehrere äußerst komplexe und knifflige Ansätze ausprobiert, die überraschend schlechte Ergebnisse hervorgebracht haben. Anschließend bin ich zurückgegangen und habe nur einen einfachen Ansatz gewählt, der zu einer geringeren Programmgröße und besseren Ergebnissen geführt hat.

Dieser Ansatz ist eigentlich sehr einfach. Die vorherigen x Zeichen (zusätzlich zu allen Teilzeichenfolgen dieser Zeichen) werden blind in eine Hash-Tabelle eingespeist, die dem aktuellen Zeichen zugeordnet ist. Anschließend wird verfolgt, welche Muster das aktuelle Zeichen am genauesten vorhersagen. Wenn Muster, die bestimmten Zeichen vorangehen, mehrmals vorkommen, können sie das Zeichen erfolgreich vorhersagen. Längeren Zeichenfolgen wird Vorrang eingeräumt, und es wird demjenigen Zeichen Vorrang eingeräumt, das am häufigsten auf eine bestimmte Zeichenfolge folgt. Dieser Algorithmus kennt weder die Art des Dokuments noch die englische Sprache.

Ich entschied mich dafür, 9 Zeichen zu verwenden und zu versuchen, möglichst ganze Wörter innerhalb der vorherigen 9 Zeichen zu finden. Wenn Sie nicht versuchen, die Wörter in den Zeichenfolgen abzugleichen, beträgt die optimale Länge 6 Zeichen, was zu mehreren tausend falschen Vorhersagen führt.

Eine interessante Beobachtung war, dass die Verwendung von 20 Zeichen beim ersten Mal zu schlechten Vorhersagen führte, bei nachfolgenden Durchgängen jedoch eine Genauigkeit von 99,9 Prozent. Der Algorithmus war im Grunde in der Lage, das Buch in überlappenden 20-Byte-Blöcken zu speichern, und dies war deutlich genug, um es zu ermöglichen, das gesamte Buch zeichenweise abzurufen.

  • (1950 * 2 + 532919) 536819
  • (2406 * 2 + 526233) 531045 Überprüfung auf Interpunktion, um bessere Vermutungen anzustellen
  • (1995 * 2 + 525158) 529148 mehr Optimierungen, ein wenig Nachdruck weggolfen

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
quelle
Das ist eine ziemlich gute Punktzahl für eine so wörtliche Sprache.
DJMcMayhem
1
Ich dachte, es ist einen Versuch wert, da die Größe der Datei im Vergleich zur Programmgröße viel Raum für Verbesserungen bietet.
Jim W
3
Dies ist unter Java 7 (oder einer Java-Version, für die es sich lohnt) nicht kompilierbar. Würden Sie bitte Ihren Code reparieren? Sobald das erledigt ist, spiele ich gerne Golf, damit sich Ihre Punktzahl verbessert.
Olivier Grégoire
Ungetestet, aber dies sollte genau der gleiche Code sein, mit dem Sie leicht Golf spielen: 950 Bytes . Ihr aktueller Code enthielt jedoch einige Fehler, sodass ich nicht sicher bin, ob ich alles richtig ausgefüllt habe. Nochmals, ungetestet. Vergleichen Sie einfach die Versionen, um zu sehen, was ich geändert / umbenannt habe, und prüfen Sie, ob alles noch genauso funktioniert wie Ihr ursprünglicher Code. Kann aber definitiv noch mehr golfen werden.
Kevin Cruijssen
Mist, ich habe das gemacht, während ich mich in meinem alten Job gelangweilt habe und den Code nicht mitgenommen habe. Ich muss es mir ansehen, um zu sehen, wo der Tippfehler ist.
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

Ich habe es unabhängig versucht, aber am Ende war es eine minderwertige Version von Michael Homers Antwort. Ich hoffe das macht meine Antwort nicht komplett obsolet.

Dadurch wird im Laufe der Zeit ein Wörterbuch mit Wörtern erstellt (grob definiert als Zeichenfolgen, die mit oder abgeschlossen sind \n, wobei die Groß- und Kleinschreibung beachtet wird und Satzzeichen enthalten sind). Anschließend durchsucht es das Wörterbuch nach Wörtern, die mit dem beginnen, was es bisher über das aktuelle Wort wusste, sortiert die resultierende Liste nach der Häufigkeit des Auftretens (langsam) und errät, dass das nächste Zeichen das nächste Zeichen im häufigsten übereinstimmenden Wort ist. Wenn wir bereits das häufigste passende Wort haben oder es kein passendes Wort mehr gibt, wird es zurückgegeben .

Es baut auch ein ekelhaft ineffizientes Wörterbuch von Wortpaaren auf. Wenn Sie auf eine Wortgrenze stoßen, wird vermutet, dass das nächste Zeichen der erste Buchstabe des zweiten Wortes im häufigsten übereinstimmenden Wortpaar ist oder tkeine Übereinstimmung vorliegt. Es ist jedoch nicht sehr klug. Nach Mobyerrät das Programm richtig , dass das nächste Zeichen D, aber dann vergisst sie alles über den Kontext und in der Regel endet den Wal „Moby Duck“ Aufruf (weil das Wort „Dutch“ scheint in der ersten Hälfte des Textes häufiger zu sein ). Es wäre einfach, dies zu beheben, indem man Wortpaare gegenüber einzelnen Wörtern priorisiert, aber ich gehe davon aus, dass der Gewinn marginal ist (da er normalerweise ab dem dritten Zeichen korrekt ist und die Wortpaare überhaupt nicht hilfreich sind).

Ich könnte dies tunen, um es besser mit dem bereitgestellten Text abzustimmen, aber ich denke nicht, dass das manuelle Tunen des Algorithmus basierend auf Vorkenntnissen der Eingabe wirklich im Geiste des Spiels liegt. und das hätte ich wahrscheinlich auch nicht tun sollen), das habe ich vermieden. Ich habe die bekannte Zeilenlänge der Eingabedatei ignoriert und stattdessen \nnach jeweils 13 Leerzeichen eingefügt - dies ist mit ziemlicher Sicherheit eine sehr schlechte Übereinstimmung. Die Hauptabsicht bestand darin, die Zeilenlänge angemessen zu halten, anstatt der Eingabe zu entsprechen.

Der Code ist nicht gerade schnell (~ 2 Stunden auf meinem Computer), aber insgesamt stimmt ungefähr die Hälfte der Zeichen (49%). Ich erwarte, dass die Punktzahl geringfügig besser wäre, wenn sie weiterlaufen würde whale2.txt, aber das habe ich nicht getan.

Der Start der Ausgabe sieht folgendermaßen aus:

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

aber am Ende sieht es ein bisschen mehr nach ... etwas aus. Meine Lieblingspassage vom Ende des Buches,

und da keiner meiner sein kann, lass mich in Stücke ziehen, während du dich immer noch verfolgst, obwohl du an dich gebunden bist, du verdammter Wal! DAHER gebe ich den Speer auf! "

kommt als raus

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 "

Das hätte The Wrath of Khan viel verwirrender gemacht. Und "einsam" → "prickelnd" ist eine besonders befriedigende Substitution.

Bearbeiten: Speichert ein Byte durch Löschen eines nicht benötigten Speicherplatzes

Wertung

#! /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

Dies führt das Programm für den Text von Moby Dick aus und gibt den "vorhergesagten" Text an stdout aus und missbraucht stderr, um die Partitur zu schreiben. Ich würde empfehlen, die Ausgabe in eine Datei umzuleiten.

Georgewatson
quelle
2
Willkommen bei PPCG!
Martin Ender
1
Wäre nicht lambda i:i[1]billiger als der Umgang mit operator?
Draconis
@ Draconis Mit ziemlicher Sicherheit.
Georgewatson
9

C ++, 2 · 62829 + 318786 = 444444

Um dieses Programm auszuführen, benötigen Sie diese Datei hier , die benannt werden muss C.

Das Programm verwendet dieselbe Kombination von Markov-Modellen wie in unserer vorherigen Antwort . Nach wie vor ist diese Kombination im Wesentlichen das Modell aus dieser Antwort von user2699 , jedoch mit ein paar kleinen Änderungen.

Da in dieser Antwort genau dasselbe Modell wie zuvor verwendet wird, ist die Verbesserung ein besserer informationstheoretischer Mechanismus als der zuvor beschriebene "Rückspul" -Mechanismus. Dies ermöglicht es, weniger Fehler zu machen und gleichzeitig eine kleinere kombinierte Länge zu haben. Das Programm selbst spielt nicht viel Golf, weil es nicht den Hauptbeitrag zur Punktzahl leistet.

Das Programm ist 2167 Bytes lang (einschließlich aller Registerkarten für Vertiefung und vielen anderen unnötiger Zeichen, aber vor dem Testcode) und die Binär - Datei Cist 60661 Bytes lang, so dass nach den Regeln für mehrere Dateien Scoring , wir punkten Lals 2.167 + 60661 + 1 = 62829.

Die Ausführung des Programms auf einer m5.4xlargeInstanz unter Amazon EC2 dauert ungefähr 8 Minuten und beansprucht etwas mehr als 16 GB Speicher. (Diese übermäßige Speichernutzung ist nicht erforderlich - wir haben sie auch nicht optimiert.)

#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
quelle
7

Python 3, 526640

274 Bytes, 526092 Fehler (mit whale2.txt). Dies ist definitiv noch verbesserungsfähig, hat aber das Stadium "Gut genug, um zu posten" erreicht.

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))

Die Idee ist, die Häufigkeiten aller Läufe von 2, 3, 4, ..., 10 Zeichen zu speichern. Für jede dieser Längen L prüfen wir, ob die neuesten L-1-Zeichen mit einem gespeicherten Muster übereinstimmen; in diesem Fall ist unsere Schätzung g L das häufigste nächste Zeichen nach diesem Muster. Auf diese Weise sammeln wir bis zu neun Vermutungen. Um zu entscheiden, welche Schätzung verwendet werden soll, gewichten wir die Frequenz jedes Musters durch seine Länge mit der 8. Potenz. Die Schätzung mit der größten Summe gewichteter Frequenzen wird ausgewählt. Wenn es keine übereinstimmenden Muster gibt, schätzen wir den Raum.

(Die maximale Musterlänge und der Gewichtungs-Exponent wurden durch Ausprobieren ausgewählt, um die wenigsten falschen Schätzungen zu erhalten.)

Hier ist meine ungolfed work-in-progress-Version:

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))

Und das Testgeschirr:

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))

Hier ist ein Beispiel für die Ausgabe am Anfang des Textes. Schon beginnen wir die Fähigkeit zu sehen , gemeinsame Worte zu beenden nach ihrem ersten Brief zu sehen ( in, to, and, by, auch anscheinend 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 

Gegen Ende gibt es immer noch viele Fehler, aber auch viele sehr gute Sequenzen ( shmage seashawkszum Beispiel).

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 ist interessant, sich einige der Fehler anzusehen und zu erraten, welches Wort der Algorithmus "erwartet" hat. Zum Beispiel, nachdem saildas Programm beide Male ovorausgesagt hat sailor, nehme ich an. Oder wieder, nachdem , aes erwartet hat - nmöglicherweise wegen des häufigen Auftretens von , and.


Änderungsprotokoll:

  • 274 * 2 + 526092 = 526640 Der Algorithmus wurde auf Kosten einiger zusätzlicher Fehler getestet
  • 306 * 2 + 526089 = 526701 Originalversion
DLosc
quelle
6

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

Sucht nach Wörtern, die mit den vorherigen Zeichen übereinstimmen, aus einer Liste  aller  im Text verwendeten Wörter, sortiert nach der Anzahl ihrer Vorkommen.

Code:

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"

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

Testsuite:

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

Bearbeiten: Mit erhalten Sie whale2.txteine bessere Punktzahl.

Steadybox
quelle
5

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

Noch eine Präfix-Häufigkeitseinreichung. Laufen Sie weiter whale2.txtund erzielen Sie eine ähnliche (etwas schlechtere) Punktzahl als andere.

#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]];}

Dieser findet gierig die längste Zeichenfolge, die mit einem Suffix der Historie beginnt, und wenn es mehrere Kandidaten gibt, Tiebreak mit kürzeren Zeichenfolgen.

Zum Beispiel: Wenn die letzten 7 Zeichen sind abcdefgh, und die Zeichenfolge abcdefghiund abcdefghjerscheinen mit der größten Häufigkeit in allen Saiten der Form abcdefgh*, wird der Ausgang entweder ioder j, Tie - Break mit kürzeren Suffixe ( bcdefgh, cdefgh, ...).

Aus unbekannten Gründen haben mehr als 7 und mein Computer nicht genug RAM, um es auszuführen. Selbst mit 7 muss ich alle Webbrowser schließen, um es auszuführen.


Testcode:

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';
}

Ungolfed:

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]];
}

Beispielausgabe:

~ ~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 

Dieser ist fast am Ende des Textes. Die meisten lange Wörter sind ziemlich genau vorhergesagt ( 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

Großbuchstaben scheinen nicht gut zu sein.

user202729
quelle
Trie scheint speicherintensiver zu sein, als ich erwartet hatte ...
user202729
... und auch schwerer umzusetzen.
user202729
4

Python 2, 756837

Verwendet etwas, das Markov-Ketten sein könnte?

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
quelle
1
Kurze Erklärung: Die zlib.decompress('...')auswertet auf {'G?':' ', 'G;':' ','G"':' ',.......}und aist ein Wörterbuch , das von 2 Zeichen 1 Zeichen abbildet. Grundsätzlich 2-stellige Variante der Antwort von Steadybox .
User202729
1
Wie ich sehen kann, ist das Literal 17780 Bytes. Sie können es auf 11619 Zeichen reduzieren, indem Sie Leerzeichen im dekomprimierten Inhalt entfernen, wodurch 12322 Byte eingespart werden. (wenn ich richtig gezählt habe) Auch ... das Konvertieren von hexadezimalen Escape-Codes in echte Rohzeichen kann noch mehr Bytes einsparen.
user202729
Wie poste ich hier etwas, wenn es rohe Bytes sind?
Skyler
1
xxd, hexdump, uuencode, Oder ähnlich
Peter Taylor
@ user202729 Beachten Sie nur, dass Python-Code keine tatsächlichen unformatierten NUL-Bytes enthalten kann.
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)

Beispiel:

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

Verwendet drei vorberechnete Hilfsdateien:

  • seqwords enthält die 236 häufigsten Wörter.
  • wordsseq enthält eine LZMA-komprimierte Sequenz dieser Wörter und für alle Wörter, die nicht zu den 236 häufigsten gehören, die Länge.
  • dicttriesenthält für jede Wortlänge einen Entscheidungsbaum, der alle verbleibenden Wörter enthält. Aus diesen Versuchen werden Einträge ausgewählt, während wir gehen.

Auf diese Weise erzielen wir eine signifikant niedrigere Fehlerrate als alle anderen verlustbehafteten Schemata. Leider ist die wordsseqDatei immer noch zu groß, um wettbewerbsfähig zu sein.

Hier ist eine fertige Version, die die Dateien erstellt und die Analyse durchführt:

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
hörte auf, sich gegen den Uhrzeigersinn zu drehen
quelle
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;

Gegenwärtig handelt es sich bei dieser Lösung um eine WIP-Lösung, die nicht in die Gewinnzone gelangt. Auch wenn man bedenkt, dass die tatsächliche Codegröße kaum Einfluss auf die Punktzahl hat, dachte ich, ich sende meine Antwort zuerst, bevor ich mit der Mikrooptimierung beginne.
(Vollständiger Code hier verfügbar: https://github.com/BrainStone/MobyDickRNG - Beinhaltet die vollständige Programm- und Samensuche)

Diese Lösung basiert auf einem RNG. Zuerst analysiere ich den Text. Ich erstelle eine Karte, die das Vorkommen von zwei aufeinanderfolgenden Zeichen zählt. Dann erstelle ich eine Verbreitungskarte. Dies erfolgt alles statisch, sollte also in Übereinstimmung mit den Regeln erfolgen.

Während ich dann versuche, den Text auszudrucken, suche ich nach einem zufälligen Zeichen der möglichen. Während dies normalerweise zu schlechteren Ergebnissen führt als nur zur Ausgabe des häufigsten folgenden Buchstabens, könnte es wahrscheinlich Göttersamen geben, die bessere Ergebnisse liefern. Deshalb ist der Samen hart codiert. Ich bin gerade auf der Suche nach dem besten Samen. Und ich werde diese Antwort aktualisieren, sobald ich bessere Samen finde. Also bleibt auf dem Laufenden!

Wenn jemand selbst nach Saatgut suchen oder andere RNGs verwenden möchte, kann er das Repo nach Belieben teilen.

Methode zur Berechnung der Punktzahl: https://github.com/BrainStone/MobyDickRNG/blob/master/src/search.cpp#L15

Beachten Sie, dass die Gesamtpunktzahl im Moment die schlechteste ist, jedoch die Fehleranzahl bei der Ausgabe von Leerzeichen übertrifft. Und die Chancen stehen gut, dass die Punktzahl sinkt, wenn mehr Samen geprüft werden.

Änderungsprotokoll

  • 2018/01/24 : Erste Antwort veröffentlicht.
    Überprüfte Samen: 0-50000. Bewertung: 2305 * 2 + 1017754 = 1022364
  • 24.01.2018 : Minimale Golferfahrung . Link zur Berechnung der Punktzahl hinzugefügt.
    Überprüfte Samen: 0-80000. Ergebnis: 1920 * 2 + 1017754 = 1021594 (-770)
  • 2018/02/02 : Neuer Startwert (10087702) (es wurde keine Zeit gefunden, den Fehler zu beheben.)
    Überprüfte Startwerte: 0-32000000. Bewertung: 1923 * 2 + 1017344 = 1021190 (-404)
BrainStone
quelle
Könnten Sie Ihrer Antwort ein Testgeschirr hinzufügen, das die Punktzahl bewertet?
Nathaniel
@ Nathaniel Ich habe den Score-Code direkt verlinkt. Würden Sie dies zusätzlich zum Repository für ausreichend halten?
BrainStone
Bei der Überprüfung der Regeln habe ich festgestellt, dass ich gegen einige von ihnen verstoße. Ich werde natürlich meine Antwort aktualisieren, sobald ich die Probleme behoben habe
BrainStone
Sie werden dann den Text in den Zufallssamen kodieren. Siehe esoterische Programmiersprache Seed , und Sie können das Programm MT19937 rückentwickeln und diese Antwort unterbieten (wenn Sie können).
user202729
Gute Idee, aber es hilft nichts, ein gutes Ergebnis zu erzielen. +1 sowieso.
user202729
3

Ruby, 1164418 (autsch)

Ich wollte nur sehen, wie gut ich es kann, ohne andere Antworten zu überprüfen.
Ich bin nicht sicher, ob dies zulässig ist, da es ein Literal enthält, das ich durch Analyse der Datei generiert habe, aber auch wenn es nicht so war, besteht nicht die Gefahr, dass jemand geschlagen wird.

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] : ' '}

Wie ich generiert habe x

Zuerst habe ich a.txtmit folgendem generiert :

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

Dann habe ich generiert a.csv:

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

Dann habe ich es xmit dem folgenden Ruby-Skript analysiert :

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

Wie ich getroffen habe

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
quelle
Ich bin sicher, das ist erlaubt. Wenn Sie die Datei analysiert haben, gute Arbeit! Nur wenn das Programm dies tut, ist dies ungültig.
Erik der Outgolfer
@EriktheOutgolfer> _> (schiebt still ein "(nicht konkurrierend)" in den Titel)
NO_BOOT_DEVICE
Warum? Wenn dies gültig ist, konkurriert es, obwohl es nicht viel schlagen kann. Wenn es ungültig ist (dh Ihre Lösung liest aus der Datei und enthält nicht nur ein Literal), sollte es gelöscht werden.
Erik der Outgolfer
Hmmm. Ich dachte du meinst, wenn irgendein Programm die Datei analysiert und nicht nur die Lösung.
NO_BOOT_DEVICE
1
Ich kann Ruby nicht lesen, aber ich denke, das ist gültig. Das Literal im Programm zu haben ist völlig in Ordnung, es ist überhaupt kein Problem.
Nathaniel
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]

Probieren Sie es online!

Ziemlich übersichtliche Häufigkeitstabelle. Jede Position in der Zeichenfolge entspricht dem ASCII-Code des aktuellen Zeichens (minus 10 = 0x0a = '\ n', das niedrigste Zeichen in der Datei), und das Zeichen an jedem Index ist das häufigste nächste Zeichen. Vorausgesetzt, ich habe die Frequenzen richtig berechnet ...

Getestet mit dem Code von user202729's Test

Kevin
quelle
Können Sie mit ein paar Bytes sparen def f(c):return(" ">c)*c or"t ... e"[ord(c)-32]?
Neil
0

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

Perfekte Genauigkeit in nur 644449 Bytes

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

Der vollständige Code kann nicht in eine Antwort passen, daher habe ich ihn hier eingefügt und das große Binärzeichenfolgenliteral im Antworttext durch b '###' ersetzt.

Dies wird mit dem folgenden Code generiert, wobei "modified.py" die generierte Datei und "cheatsheet.txt" die Datei whale2.txt ist, die mit dem zweiten Zeichen beginnt.

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]')

Der Code kann ausgeführt werden, indem am Ende von "modified.py" Folgendes hinzugefügt wird. "whale2.txt" muss sich im selben Verzeichnis wie "modified.py" befinden, und die Ausgabe wird in "out.txt" geschrieben.

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)

Diese Antwort greift nicht direkt auf whale.txt oder whale2.txt zu. Dabei werden vorhandene Standardkomprimierungsbibliotheken verwendet, die in den Regeln ausdrücklich zulässig sind.

Legorhin
quelle
Es könnte ein "\ r \ n" darin geben, das ich in Windows nicht loswerden konnte, als ich sie zählte
Legorhin
2
Ja, das war ein Tippfehler, der sich verbreitete
Legorhin