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 Code-Herausforderung . 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

var QUESTION_ID=152856,OVERRIDE_USER=21034;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:380px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Score</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

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.

/// , 2 * 1 + 1020874 = 1020876

Druckt ein Leerzeichen.

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

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!

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)

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.

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.

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

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

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

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.

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.

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

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.

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

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

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.

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