Berikut adalah file teks ASCII 1.2Mb yang berisi teks Moby-Dick Herman Melville ; atau, Paus . Tugas Anda adalah menulis program atau fungsi (atau kelas, dll. - lihat di bawah) yang akan diberikan file ini satu karakter pada satu waktu, dan pada setiap langkah harus menebak karakter berikutnya.

Ini adalah tantangan kode . Skor Anda akan

2*L + E

di mana Lukuran pengiriman Anda dalam byte, dan Ejumlah karakter yang ditebaknya salah. Skor terendah menang.

Keterangan lebih lanjut

Kiriman Anda akan berupa program atau fungsi (dll.) Yang akan dipanggil atau dipanggil atau dikirim data beberapa kali. (1215235 kali tepatnya.) Ketika itu disebut untuk n ^th waktu itu akan diberi n ^th karakter whale.txtatau whale2.txtdan harus keluaran menebak-nya untuk ( n + 1 ) ^th karakter. The Ekomponen skor yang akan menjadi jumlah karakter yang menebak benar.

Sebagian besar pengiriman harus menyimpan beberapa keadaan di antara doa, sehingga mereka dapat melacak berapa kali mereka dipanggil dan apa input sebelumnya. Anda dapat melakukan ini dengan menulis ke file eksternal, dengan menggunakan staticatau variabel global, dengan mengirimkan kelas daripada fungsi, menggunakan negara monad, atau apa pun yang berfungsi untuk bahasa Anda. Kiriman Anda harus menyertakan kode apa pun yang diperlukan untuk menginisialisasi keadaannya sebelum permohonan pertama.

Program Anda harus berjalan secara deterministik, sehingga selalu membuat tebakan yang sama dengan input yang sama (dan karenanya selalu mendapat skor yang sama).

Jawaban Anda harus mencakup tidak hanya kiriman Anda, tetapi juga kode yang Anda gunakan untuk menghitung Ebagian dari skornya. Ini tidak perlu ditulis dalam bahasa yang sama dengan kiriman Anda, dan tidak akan dihitung terhadap jumlah byte-nya. Anda didorong untuk membuatnya mudah dibaca.

Mengenai antarmuka antara kiriman Anda dan program penghitungan skor ini, semuanya baik-baik saja, asalkan program Anda selalu memberikan satu byte output sebelum menerima byte input berikutnya. (Jadi, misalnya, Anda tidak bisa hanya meneruskannya sebuah string yang berisi semua input dan mendapatkan kembali string yang berisi semua output.)

Anda benar-benar harus menjalankan program pengujian dan menghitung / memverifikasi skor Anda sebelum mengirimkan entri Anda. Jika kiriman Anda berjalan terlalu lambat untuk Anda memverifikasi skornya maka tidak memenuhi syarat untuk bersaing, bahkan jika Anda tahu berapa skornya pada prinsipnya.

The Lkomponen skor Anda akan dihitung sesuai dengan aturan biasa untuk tantangan kode golf. Jika kiriman Anda akan berisi banyak file, harap perhatikan aturan penilaian dan struktur direktori dalam kasus itu. Data apa pun yang digunakan kode Anda harus dimasukkan dalam Lskor Anda .

Anda dapat mengimpor perpustakaan yang ada tetapi tidak dapat memuat file eksternal lainnya, dan kode Anda mungkin tidak mengakses whale.txtatauwhale2.txtfile dengan cara apa pun selain yang dijelaskan di atas. Anda tidak boleh memuat jaringan saraf pra-terlatih atau sumber data statistik lainnya. (Tidak apa-apa menggunakan jaringan saraf, tetapi Anda harus memasukkan data bobot dalam kiriman Anda dan menghitungnya terhadap jumlah byte Anda.) Jika karena alasan tertentu bahasa atau perpustakaan Anda menyertakan fitur yang menyediakan beberapa atau semua teks Moby Dick , Anda tidak boleh menggunakan fitur itu. Selain itu, Anda dapat menggunakan fitur perpustakaan atau built-in apa saja yang Anda suka, termasuk yang berkaitan dengan pemrosesan teks, prediksi atau kompresi, asalkan itu bagian dari bahasa Anda atau perpustakaan standarnya. Untuk rutinitas khusus yang lebih eksotis dan khusus yang menyertakan sumber data statistik, Anda harus menerapkannya sendiri dan memasukkannya dalam jumlah byte Anda.

Kemungkinan beberapa pengiriman akan mencakup komponen yang dihasilkan sendiri oleh kode. Jika demikian, harap sertakan dalam jawaban Anda kode yang digunakan untuk membuatnya, dan jelaskan cara kerjanya . (Selama kode ini tidak diperlukan untuk menjalankan kiriman Anda, kode itu tidak akan dimasukkan dalam jumlah byte Anda.)

Untuk alasan historis, ada dua versi file, dan Anda dapat menggunakan salah satu dari mereka dalam sebuah jawaban. Dalam whale2.txt(ditautkan di atas) teks tidak dibungkus, sehingga baris baru hanya muncul di akhir paragraf. Dalam whale.txtteks asli , teks dibungkus dengan lebar 74 karakter, jadi Anda harus memprediksi akhir setiap baris serta memprediksi teks. Hal ini membuat tantangan lebih fiddly, jadi whale2.txtdirekomendasikan untuk jawaban baru. Kedua file berukuran sama, 1215236 byte.

Untuk meringkas, semua jawaban harus mencakup hal-hal berikut:

• Kiriman Anda sendiri. (Kode, plus file data apa pun yang digunakan - ini bisa berupa tautan jika besar.)
• Penjelasan tentang cara kerja kode Anda. Tolong jelaskan metode I / O serta bagaimana ia memprediksi karakter berikutnya. Penjelasan tentang algoritma Anda adalah penting, dan penjelasan yang baik akan menghasilkan hadiah dari saya.
• Kode yang Anda gunakan untuk mengevaluasi skor Anda. (Jika ini identik dengan jawaban sebelumnya, Anda dapat menautkannya.)
• Kode apa pun yang Anda gunakan untuk menghasilkan kiriman Anda, bersama dengan penjelasan kode itu. Ini termasuk kode yang Anda gunakan untuk mengoptimalkan parameter, menghasilkan file data dll. (Ini tidak dihitung terhadap jumlah byte Anda tetapi harus dimasukkan dalam jawaban Anda.)

Papan peringkat

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>

Bounties

Dari waktu ke waktu saya akan menawarkan hadiah untuk mendorong pendekatan yang berbeda.

Yang pertama, 50 poin, diberikan kepada A. Rex untuk jawaban skor terbaik saat itu.

Yang kedua, 100 poin, juga diberikan kepada A. Rex, untuk jawaban yang sama, karena mereka menambahkan penjelasan yang sangat bagus untuk jawaban yang ada.

Hadiah berikutnya, 200 poin , akan diberikan kepada keduanya

• Jawaban kompetitif yang menggunakan teknik baru. (Ini akan didasarkan pada penilaian subyektif saya karena perwakilan saya yang masuk ke dalam karunia, tetapi Anda dapat mempercayai saya untuk bersikap adil. Perhatikan bahwa jawaban Anda perlu berisi penjelasan yang cukup bagi saya untuk memahami cara kerjanya!) Jawaban seperti itu perlu dapat mengambil skor teratas, itu hanya perlu dilakukan dengan cukup baik dibandingkan dengan jawaban yang ada. Saya sangat tertarik untuk melihat solusi berdasarkan jaringan saraf berulang, tapi saya akan menghadiahkan hadiah untuk apa pun yang tampaknya cukup berbeda dari model Markov yang mendominasi skor teratas saat ini.

Atau:

• Siapa pun yang mengalahkan skor tertinggi A. Rex (saat ini 444444), menggunakan metode apa pun.

Setelah nilai 200 poin diklaim saya kemungkinan besar akan menawarkan 400 poin satu, memperbarui persyaratan yang sesuai.

/// , 2 * 1 + 1020874 = 1020876

Mencetak spasi.

Node.js, 2 * 224 + 524279 = 524727

Silakan merujuk ke log perubahan di akhir posting ini untuk pembaruan skor.

Fungsi mengambil dan mengembalikan byte.

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

Ini terdiri dari model PPM sederhana yang melihat 8 karakter terakhir untuk memprediksi yang berikutnya.

Kami memercayai pola panjang L ketika kami menjumpainya setidaknya T [L] kali, di mana T adalah array ambang arbitrer: [1,1,2,1,2,3,5,2] . Selain itu, kami selalu mempercayai pola yang cocok dengan karakter pertamanya [A-Z '"(].

Kami memilih pola tepercaya terpanjang dan mengembalikan prediksi dengan skor tertinggi yang terkait dengan pola ini pada saat panggilan.

Catatan

• Ini jelas tidak dioptimalkan untuk kecepatan, tetapi beroperasi dalam waktu sekitar 15 detik di laptop saya.

• Jika kami diizinkan untuk mengulangi proses beberapa kali berturut-turut tanpa mengatur ulang model, jumlah kesalahan akan konvergen ke ~ 268000 setelah 5 iterasi.

• Tingkat keberhasilan fungsi prediksi saat ini adalah ~ 56,8%. Seperti yang diperhatikan oleh @immibis dalam komentar, jika tebakan yang salah dan benar tercampur menjadi satu, hasilnya bahkan tidak bisa dibaca.

  Misalnya, cuplikan ini di dekat akhir buku:

  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.
  

  menjadi:

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

  Dengan mengganti tebakan buruk dengan garis bawah, kami memiliki gagasan yang lebih baik tentang fungsi yang benar:

  _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 : Contoh di atas dibuat dengan versi kode sebelumnya, bekerja pada versi pertama dari file input.}

Kode uji

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

Ubah log

• 524727 - menyelamatkan 19644 poin dengan beralih ke whale2.txt (pembaruan tantangan)
• 544371 - menyelamatkan 327 poin dengan memaksa pola yang dimulai dengan huruf kapital, kutipan, kutipan ganda atau tanda kurung pembuka untuk selalu dipercaya
• 544698 - menyelamatkan 2119 poin dengan memaksa pola yang dimulai dengan spasi agar selalu dipercaya
• 546817 - menyelamatkan 47 poin dengan menyesuaikan ambang batas dan memainkan fungsi prediksi
• 546864 - menyelamatkan 1496 poin dengan memperluas panjang pola maksimum hingga 8 karakter
• 548360 - menyelamatkan 6239 poin dengan memperkenalkan gagasan pola tepercaya, dengan ambang batas bergantung pada panjangnya
• 554599 - menyelamatkan 1030 poin dengan meningkatkan prediksi umpan baris
• 555629 - menyelamatkan 22 poin dengan memainkan fungsi prediksi
• 555651 - menghemat 40 poin dengan memainkan fungsi prediksi
• 555691 - skor awal

Perl, 2 · 70525 + 326508 = 467558

Prediktor

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

Untuk menjalankan program ini, Anda perlu file ini di sini , yang harus dinamai B. (Anda dapat mengubah nama file ini pada karakter karakter kedua di Batas.) Lihat di bawah untuk cara membuat file ini.

Program ini menggunakan kombinasi model Markov pada dasarnya seperti dalam jawaban ini oleh user2699 , tetapi dengan beberapa modifikasi kecil. Ini menghasilkan distribusi untuk karakter selanjutnya. Kami menggunakan teori informasi untuk memutuskan apakah akan menerima kesalahan atau menghabiskan sedikit penyimpanan dalam Bpetunjuk penyandian (dan jika demikian, bagaimana). Kami menggunakan kode aritmatika untuk menyimpan bit fraksional secara optimal dari model.

Program ini panjangnya 582 byte (termasuk baris akhir yang tidak perlu) dan panjang file biner Badalah 6.9942 byte, jadi berdasarkan aturan untuk mencetak banyak file , kami mendapat skor L582 + 69942 + 1 = 70525.

Program ini hampir pasti membutuhkan arsitektur 64-bit (little-endian?). Diperlukan waktu sekitar 2,5 menit untuk menjalankan m5.largeinstance di Amazon EC2.

Kode uji

# 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

Test harness menganggap pengajuan ada dalam file submission.pl, tetapi ini dapat dengan mudah diubah di baris kedua.

Perbandingan teks

"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

Sampel ini (dipilih dalam jawaban lain ) muncul agak terlambat dalam teks, sehingga model ini cukup berkembang pada titik ini. Ingat bahwa model ini ditambah oleh 70 kilobyte "petunjuk" yang secara langsung membantunya menebak karakter; itu tidak didorong hanya oleh potongan pendek kode di atas.

Menghasilkan petunjuk

Program berikut menerima kode pengiriman yang tepat di atas (pada input standar) dan menghasilkan Bfile yang tepat di atas (pada output standar):

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

Diperlukan waktu kira-kira untuk berjalan seperti pengiriman, karena melakukan perhitungan yang sama.

Penjelasan

Di bagian ini, kami akan mencoba menjelaskan apa yang dilakukan solusi ini dengan cukup detail sehingga Anda dapat "mencobanya di rumah" sendiri. Teknik utama yang membedakan jawaban ini dari yang lain adalah beberapa bagian di bawah sebagai mekanisme "mundur", tetapi sebelum kita sampai di sana, kita perlu mengatur dasar-dasarnya.

Model

Bahan dasar dari solusi adalah model bahasa. Untuk tujuan kami, model adalah sesuatu yang mengambil sejumlah teks bahasa Inggris dan mengembalikan distribusi probabilitas pada karakter berikutnya. Ketika kami menggunakan model, teks bahasa Inggris akan menjadi beberapa awalan (benar) dari Moby Dick. Harap dicatat bahwa output yang diinginkan adalah distribusi , dan bukan hanya tebakan tunggal untuk karakter yang paling mungkin.

Dalam kasus kami, kami pada dasarnya menggunakan model dalam jawaban ini oleh user2699 . Kami tidak menggunakan model dari jawaban dengan skor tertinggi (selain dari milik kami) oleh Anders Kaseorg justru karena kami tidak dapat mengekstraksi distribusi daripada hanya satu tebakan terbaik. Secara teori, jawaban itu menghitung rata-rata geometris tertimbang, tetapi kami mendapat hasil yang sedikit buruk ketika kami menafsirkannya secara harfiah. Kami "mencuri" model dari jawaban lain karena "saus rahasia" kami bukanlah model melainkan pendekatan keseluruhan. Jika seseorang memiliki model "lebih baik", maka mereka harus bisa mendapatkan hasil yang lebih baik menggunakan sisa teknik kami.

Sebagai komentar, sebagian besar metode kompresi seperti Lempel-Ziv dapat dilihat sebagai "model bahasa" dengan cara ini, meskipun orang mungkin harus sedikit menyipit. (Ini sangat sulit untuk sesuatu yang melakukan transformasi Burrows-Wheeler!) Juga, perhatikan bahwa model oleh user2699 adalah modifikasi dari model Markov; intinya tidak ada lagi yang kompetitif untuk tantangan ini atau bahkan pemodelan teks secara umum.

Arsitektur keseluruhan

Untuk keperluan pemahaman, senang memecah arsitektur keseluruhan menjadi beberapa bagian. Dari perspektif tingkat tertinggi, perlu ada sedikit kode manajemen negara. Ini tidak terlalu menarik, tetapi untuk kelengkapan kami ingin menekankan bahwa pada setiap titik program diminta untuk tebakan berikutnya, itu telah tersedia untuknya awalan yang benar dari Moby Dick. Kami tidak menggunakan tebakan salah kami di masa lalu dengan cara apa pun. Demi efisiensi, model bahasa mungkin dapat menggunakan kembali statusnya dari karakter N pertama untuk menghitung statusnya untuk karakter pertama (N + 1), tetapi pada prinsipnya, ia dapat menghitung ulang hal-hal dari awal setiap kali dipanggil.

Mari kita kesampingkan "driver" dasar program ini dan mengintip bagian dalam yang menebak karakter selanjutnya. Ini membantu secara konseptual untuk memisahkan tiga bagian: model bahasa (dibahas di atas), file "petunjuk", dan "penerjemah". Pada setiap langkah, penerjemah akan meminta model bahasa untuk distribusi untuk karakter berikutnya dan mungkin membaca beberapa informasi dari file petunjuk. Maka akan menggabungkan bagian-bagian ini menjadi tebakan. Tepatnya informasi apa yang ada dalam file petunjuk serta bagaimana penggunaannya akan dijelaskan nanti, tetapi untuk saat ini membantu memisahkan bagian-bagian ini secara mental. Perhatikan bahwa implementasi-bijaksana, file petunjuk secara harfiah file terpisah (biner) tetapi bisa berupa string atau sesuatu yang disimpan di dalam program. Sebagai perkiraan,

Jika seseorang menggunakan metode kompresi standar seperti bzip2 seperti dalam jawaban ini , file "hints" sesuai dengan file yang dikompresi. "Interpreter" sesuai dengan decompressor, sedangkan "model bahasa" agak implisit (seperti yang disebutkan di atas).

Mengapa menggunakan file petunjuk?

Mari kita ambil contoh sederhana untuk dianalisis lebih lanjut. Misalkan teks Npanjang karakter dan didekati dengan baik oleh model di mana setiap karakter (independen) huruf Edengan probabilitas sedikit kurang dari setengah, Tsama dengan probabilitas sedikit kurang dari setengah, dan Adengan probabilitas 1/1000 = 0,1%. Mari kita asumsikan tidak ada karakter lain yang mungkin; dalam kasus apa pun, Aini cukup mirip dengan kasus karakter yang sebelumnya tidak terlihat tiba-tiba.

Jika kita beroperasi dalam rezim L 0 (seperti kebanyakan, tetapi tidak semua, dari jawaban lain untuk pertanyaan ini), tidak ada strategi yang lebih baik untuk penerjemah daripada memilih salah satu dari Edan T. Rata-rata, itu akan mendapatkan sekitar setengah dari karakter yang benar. Jadi E ≈ N / 2 dan skor ≈ N / 2 juga. Namun, jika kita menggunakan strategi kompresi, maka kita dapat memampatkan sedikit lebih dari satu bit per karakter. Karena L dihitung dalam byte, kita mendapatkan L ≈ N / 8 dan dengan demikian skor ≈ N / 4, dua kali lebih baik dari strategi sebelumnya.

Mencapai tingkat ini sedikit lebih dari satu bit per karakter untuk model ini sedikit nontrivial, tetapi satu metode adalah pengkodean aritmatika.

Pengkodean aritmatika

Seperti yang umum diketahui, pengkodean adalah cara mewakili beberapa data menggunakan bit / byte. Sebagai contoh, ASCII adalah pengkodean 7 bit / karakter teks bahasa Inggris dan karakter terkait, dan itu adalah pengkodean file Moby Dick asli yang sedang dipertimbangkan. Jika beberapa huruf lebih umum daripada yang lain, maka penyandian lebar-tetap seperti ASCII tidak optimal. Dalam situasi seperti itu, banyak orang meraih kode Huffman . Ini optimal jika Anda menginginkan kode tetap (bebas awalan) dengan jumlah bit integer per karakter.

Namun, pengkodean aritmatika bahkan lebih baik. Secara kasar, ia dapat menggunakan bit "fraksional" untuk menyandikan informasi. Ada banyak panduan untuk coding aritmatika yang tersedia online. Kami akan melewatkan detailnya di sini (terutama dari implementasi praktis, yang bisa sedikit rumit dari perspektif pemrograman) karena sumber daya lain yang tersedia secara online, tetapi jika seseorang mengeluh, mungkin bagian ini dapat diperlihatkan lebih lanjut.

Jika seseorang memiliki teks yang sebenarnya dihasilkan oleh model bahasa yang dikenal, maka pengkodean aritmatika memberikan pengkodean teks yang pada dasarnya optimal dari model itu. Dalam beberapa hal, ini "memecahkan" masalah kompresi untuk model itu. (Dengan demikian dalam praktiknya, masalah utama adalah bahwa model tidak diketahui, dan beberapa model lebih baik daripada yang lain dalam pemodelan teks manusia.) Jika tidak diizinkan untuk membuat kesalahan dalam kontes ini, maka dalam bahasa bagian sebelumnya , salah satu cara untuk menghasilkan solusi untuk tantangan ini adalah dengan menggunakan encoder aritmatika untuk menghasilkan file "petunjuk" dari model bahasa dan kemudian menggunakan dekoder aritmatika sebagai "penerjemah".

Dalam pengkodean yang pada dasarnya-optimal ini, kita akhirnya menghabiskan -log_2 (p) bit untuk karakter dengan probabilitas p, dan laju bit keseluruhan dari pengkodean adalah entropi Shannon . Ini berarti bahwa karakter dengan probabilitas dekat 1/2 membutuhkan waktu sekitar satu bit untuk mengkodekan, sedangkan karakter dengan probabilitas 1/1000 membutuhkan sekitar 10 bit (karena 2 ^ 10 kira-kira 1000).

Tetapi metrik penilaian untuk tantangan ini dipilih dengan baik untuk menghindari kompresi sebagai strategi optimal. Kita harus mencari cara untuk membuat beberapa kesalahan sebagai tradeoff untuk mendapatkan file petunjuk yang lebih pendek. Sebagai contoh, salah satu strategi yang mungkin dicoba adalah strategi percabangan sederhana: kami biasanya mencoba menggunakan pengkodean aritmatika ketika kami bisa, tetapi jika distribusi probabilitas dari model itu "buruk" dalam beberapa cara kami hanya menebak karakter yang paling mungkin dan tidak t coba menyandikannya.

Mengapa melakukan kesalahan?

Mari kita menganalisis contoh dari sebelumnya untuk memotivasi mengapa kita mungkin ingin membuat kesalahan "dengan sengaja". Jika kita menggunakan pengkodean aritmatika untuk menyandikan karakter yang benar, kita akan menghabiskan kira-kira satu bit dalam kasus Eatau T, tetapi sekitar sepuluh bit dalam kasus suatu A.

Secara keseluruhan, ini adalah pengkodean yang cukup bagus, menghabiskan sedikit lebih sedikit per karakter meskipun ada tiga kemungkinan; pada dasarnya, Aini sangat tidak mungkin dan kami tidak menghabiskan sepuluh bit yang sesuai terlalu sering. Namun, bukankah lebih baik jika kita bisa membuat kesalahan sebagai gantinya A? Bagaimanapun, metrik untuk masalah ini menganggap 1 byte = 8 bit panjangnya setara dengan 2 kesalahan; jadi sepertinya orang harus lebih memilih kesalahan daripada menghabiskan lebih dari 8/2 = 4 bit pada sebuah karakter. Menghabiskan lebih dari satu byte untuk menyimpan satu kesalahan pasti terdengar kurang optimal!

Mekanisme "mundur"

Bagian ini menjelaskan aspek pintar utama dari solusi ini, yang merupakan cara untuk menangani tebakan yang salah tanpa biaya panjang.

Untuk contoh sederhana yang telah kami analisis, mekanisme mundur sangat mudah. Juru bahasa membaca sedikit dari file petunjuk. Jika 0, itu menebak E. Jika itu adalah 1, ia menebak T. Kali berikutnya dipanggil, ia melihat apa karakter yang benar. Jika file petunjuk diatur dengan baik, kami dapat memastikan bahwa dalam kasus seorang Eatau T, penerjemah menebak dengan benar. Tapi bagaimana dengan itu A? Gagasan mekanisme mundur adalah tidak kode Asama sekali . Lebih tepatnya, jika penerjemah kemudian mengetahui bahwa karakter yang benar adalah A, maka secara metaforis " memutar ulang kaset": ia mengembalikan bit yang dibacanya sebelumnya. Bit yang dibaca memang bermaksud untuk kode EatauT, tapi tidak sekarang; itu akan digunakan nanti. Dalam contoh sederhana ini, ini pada dasarnya berarti bahwa ia terus menebak karakter yang sama ( Eatau T) sampai benar; kemudian membaca sedikit lagi dan terus berjalan.

Pengkodean untuk file petunjuk ini sangat sederhana: ubah semua Es menjadi 0 bit dan Ts menjadi 1 bit, semuanya mengabaikan Asepenuhnya s. Dengan analisis di akhir bagian sebelumnya, skema ini membuat beberapa kesalahan tetapi mengurangi skor secara keseluruhan dengan tidak menyandikan salah satu dari As. Sebagai efek yang lebih kecil, itu sebenarnya menghemat panjang file petunjuk juga, karena kita akhirnya menggunakan tepat satu bit untuk masing-masing Edan T, alih-alih sedikit lebih dari sedikit.

Teorema kecil

Bagaimana kita memutuskan kapan harus membuat kesalahan? Misalkan model kita memberi kita distribusi probabilitas P untuk karakter berikutnya. Kami akan memisahkan karakter yang mungkin menjadi dua kelas: kode dan bukan kode . Jika karakter yang benar tidak dikodekan, maka kita akan berakhir menggunakan mekanisme "mundur" untuk menerima kesalahan tanpa biaya panjang. Jika karakter yang benar dikodekan, maka kita akan menggunakan beberapa distribusi Q lainnya untuk menyandikannya menggunakan pengkodean aritmatika.

Tetapi distribusi Q apa ​​yang harus kita pilih? Tidak terlalu sulit untuk melihat bahwa karakter yang dikode semuanya harus memiliki probabilitas yang lebih tinggi (dalam P) daripada karakter yang tidak diberi kode. Juga, distribusi Q seharusnya hanya menyertakan karakter kode; lagipula, kita tidak mengkode yang lain, jadi kita seharusnya tidak "menghabiskan" entropi untuk mereka. Agak sulit untuk melihat bahwa distribusi probabilitas Q harus proporsional dengan P pada karakter kode. Menyatukan pengamatan ini berarti bahwa kita harus mengkode karakter yang paling mungkin tetapi mungkin bukan karakter yang kurang mungkin, dan bahwa Q hanya P yang ditulis ulang pada karakter yang dikode.

Lebih jauh lagi ternyata ada teorema keren tentang "cutoff" mana yang harus dipilih untuk karakter pengkodean: Anda harus mengkode karakter selama paling tidak 1/5, 393 lebih besar dari kemungkinan kombinasi karakter berkode lainnya. Ini "menjelaskan" penampilan konstanta yang tampaknya acak 5.393mendekati akhir program di atas. Angka 1 / 5.393 ≈ 0,18542 adalah solusi untuk persamaan -p log (16) - p log p + (1 + p) log (1 + p) = 0 .

Mungkin ide yang masuk akal untuk menuliskan prosedur ini dalam kode. Cuplikan ini ada di 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;
}

Menyatukan semuanya

Bagian sebelumnya sayangnya sedikit teknis, tetapi jika kita menyatukan semua bagian lainnya, strukturnya adalah sebagai berikut. Setiap kali program diminta untuk memprediksi karakter berikutnya setelah karakter yang diberikan benar:

1. Tambahkan karakter yang benar ke awalan Moby Dick yang diketahui benar.
2. Perbarui model (Markov) teks.
3. The saus rahasia : Jika menebak sebelumnya tidak benar, mundur keadaan decoder aritmatika ke keadaan sebelum menebak sebelumnya!
4. Minta model Markov untuk memprediksi distribusi probabilitas P untuk karakter selanjutnya.
5. Ubah P menjadi Q menggunakan subrutin dari bagian sebelumnya.
6. Minta decoder aritmatika untuk mendekode karakter dari sisa file petunjuk, sesuai dengan distribusi Q.
7. Tebak karakter yang dihasilkan.

Pengkodean file petunjuk beroperasi dengan cara yang sama. Dalam hal ini, program tahu apa karakter selanjutnya yang benar. Jika itu adalah karakter yang harus dikodekan, maka tentu saja orang harus menggunakan encoder aritmatika di atasnya; tetapi jika itu bukan karakter kode, itu hanya tidak memperbarui keadaan aritmatika encoder.

Jika Anda memahami latar belakang teori-informasi seperti distribusi probabilitas, entropi, kompresi, dan pengkodean aritmatika tetapi mencoba dan gagal memahami posting ini (kecuali mengapa teorema itu benar), beri tahu kami dan kami dapat mencoba untuk menyelesaikannya. Terima kasih sudah membaca!

Python 3, 2 · 267 + 510193 = 510727

Prediktor

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]

Ini menggunakan kombinasi Bayesian tertimbang dari urutan 0,…, 16 model Markov, dengan bobot [1, 6, 12, 30, 65, 99, 87, 117, 118, 89, 95, 118, 96, 184, 126, 219, 126].

Hasilnya tidak terlalu peka terhadap pemilihan bobot ini, tetapi saya mengoptimalkannya karena saya bisa, menggunakan algoritme pendakian bukit penerimaan terlambat yang sama yang saya gunakan dalam jawaban saya untuk "Menyatukan mayoritas Senat" , di mana setiap kandidat mutasi adalah hanya kenaikan ± 1 untuk satu berat.

Kode uji

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

Cobalah online!

Fungsi menggunakan variabel global. Belajar sambil jalan, membangun model di tingkat kata: mengingat apa yang terlihat sejauh ini dalam kata ini , apa karakter berikutnya yang paling umum? Semakin banyak input yang masuk, ia belajar kata-kata umum dari teks dengan cukup baik, dan juga mempelajari karakter yang paling umum untuk memulai kata berikutnya .

Sebagai contoh:

• Jika apa yang dilihatnya sejauh ini adalah 'Captai', ia memprediksi sebuah "n"
• Jika itu "Kapten", ia memprediksi sebuah ruang
• Jika ini adalah awal dari sebuah kata, dan kata terakhir adalah "Kapten" itu memprediksi 'A'
• Jika kata sejauh ini adalah 'A', ia memprediksi 'h' (dan kemudian 'a' dan 'b'; demikian pula untuk 'C').

Pada awalnya tidak terlalu baik, tetapi pada akhirnya ada sebagian besar kata-kata yang sebenarnya keluar. Opsi mundur adalah spasi, dan setelah satu spasi itu adalah "a", kecuali huruf sebelumnya adalah salah satu dari "nedtfo", digit, atau tanda hubung atau tanda kutip. Itu juga secara agresif memprediksi jeda baris setelah 71 karakter, atau jika spasi diharapkan setelah 66. Keduanya hanya disetel ke data ("t" jauh lebih umum setelah spasi, tetapi lebih sering sudah diprediksi, jadi " a "adalah tebakan yang lebih baik di luar enam kasus khusus).

Mempelajari pasangan kata apa yang berjalan bersama dan melakukan preseeding pemetaan ternyata tidak bermanfaat.

Itu berakhir dengan teks seperti ini:

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!

yang sesuai dengan bagian input ini:

di sekelilingnya.

"Saya melihatnya hampir seketika itu juga, Sir, seperti yang dilakukan Kapten Ahab, dan saya berteriak," kata Tashtego.

"Tidak instan yang sama; tidak sama - tidak, doubloon itu milikku, Takdir mencadangkan doubloon untukku. Aku hanya; tidak seorang pun dari kalian yang bisa mengangkat Paus Putih terlebih dahulu. Di sana dia berhembus! - di sana dia meledak! - -ada dia pukulan!

Anda dapat melihat di mana kata benda yang tepat keluar dengan cukup baik, tetapi ujung-ujung kata sebagian besar benar juga. Ketika itu terlihat "dou" itu mengharapkan "keraguan", tetapi begitu "l" muncul itu mendapat "doubloon".

Jika Anda menjalankannya untuk kedua kalinya dengan model yang sama dengan yang baru dibangun, ia akan segera mendapatkan 92k yang benar (51,7% -> 59,3%), tetapi selalu di bawah 60% sejak iterasi kedua aktif.

Kode pengukuran ada di tautan TIO, atau ini versi yang sedikit lebih baik:

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 memiliki hasil tebakan pada akhirnya.

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

Terima kasih kepada @ Quentin karena telah menghemat 217 byte!

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

Solusi yang sangat sederhana yang, diberikan karakter, hanya menampilkan karakter yang paling sering muncul setelah karakter input.

Verifikasi skor dengan:

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

Sunting: Menggunakan whale2.txtmemberi skor yang lebih baik.

Python, 2 * 516 + 521122 = 522154

Algoritma:

Namun pengajuan python lain, algoritma ini menghitung huruf berikutnya yang paling mungkin melihat urutan panjang 1, ..., l. Jumlah probabilitas digunakan, dan ada beberapa trik untuk mendapatkan hasil yang lebih baik.

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

Hasil:

Sebagian besar omong kosong, meskipun Anda dapat melihatnya mengambil frasa sesekali, seperti "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

Kode uji:

Cukup sederhana, menampilkan beberapa contoh teks pada titik yang berbeda. Gunakan whale2.txt, karena ini menghindari beberapa logika tambahan untuk menghitung baris baru.

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 byte, 679619 652740 tebakan salah

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

Cobalah online!

Pembaruan: ~ 27.000 poin dengan file yang diperbarui, 16 poin (8 byte) dengan fungsi yang lebih baik.

Penjelasan

Cara kerjanya adalah saat kode dijalankan melalui teks, kode tersebut menghafal karakter terakhir yang mengakhiri urutan 4 karakter yang diberikan, dan mengembalikan nilai tersebut. Agak mirip dengan pendekatan Arnauld di atas, tetapi bergantung pada kemungkinan inheren dari dua urutan 4-karakter yang diberikan mengakhiri dengan cara yang sama.

De-golf:

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

sh + bzip2, 2 * 364106 = 728212

2 * 381249 + 0 = 762498

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

diikuti oleh whale2.txt bzip2-terkompresi dengan byte pertama hilang

Abaikan inputnya; menghasilkan jawaban yang benar. Ini memberikan garis dasar pada satu ujung; daniero memberikan garis dasar di ujung lainnya.

Skrip pembuat:

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

I / O test harness (tcc; potong baris pertama untuk gcc). Rangkaian uji ini dapat digunakan oleh siapa saja pada platform yang sesuai yang mengirimkan program lengkap yang mengharapkan baca / tulis I / O. Menggunakan byte / at-a-time I / O untuk menghindari kecurangan. Program anak harus flush output setelah setiap byte untuk menghindari pemblokiran.

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

Cobalah online!

... ///Jawaban yang mencetak spasi mendapat 10 upvotes, sedangkan kode saya hanya bisa mendapatkan 3 ...

Penjelasan:

Untuk setiap karakter, program:

• meningkatkan frequency[prev][char]
• Temukan karakter yang paling sering muncul di frequency[char]
• dan output itu.

• Kode yang tidak digabungkan dalam tautan TIO, dikomentari.
• Kode ini 131 byte.
• Kode yang dijalankan di mesin saya melaporkan:

879504 / 1215235
Time: 62.01348257784468

yang memiliki skor total

2*131 + 879504 = 879766

Karena tidak ada cara untuk mengunggah file besar ke TIO (kecuali meminta Dennis), contoh dijalankan di tautan TIO hanya menjalankan program untuk sebagian kecil teks.

Dibandingkan dengan jawaban yang lebih lama, yang ini memiliki 362 karakter yang lebih salah, tetapi kode ini lebih pendek sebesar 255 byte. Pengganda membuat kiriman saya memiliki skor lebih rendah.

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

Pendekatan ini menggunakan tabel pencarian untuk mempelajari karakter paling umum yang mengikuti string yang diberikan. Kunci dari tabel pencarian memiliki maksimal 4 karakter, jadi fungsi pertama memperbarui tabel pencarian dengan karakter saat ini dan kemudian hanya memeriksa karakter mana yang paling mungkin terjadi setelah 4 yang sebelumnya termasuk yang saat ini . Jika 4 karakter itu tidak ditemukan dalam tabel pencarian, itu mencetak spasi.

Versi ini menggunakan whale2.txtfile, karena sangat meningkatkan jumlah tebakan yang berhasil.

Berikut ini adalah kode yang digunakan untuk menguji kelas:

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

Kode berjalan hanya dalam 2 detik. Sebagai catatan, inilah yang saya dapatkan ketika saya memodifikasi ukuran tombol dari tabel pencarian (termasuk hasil dari putaran kedua tanpa mengatur ulang model):

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

Akan menarik untuk mengetahui mengapa ukuran kunci 4 karakter adalah pilihan terbaik dalam algoritma ini.

Perbandingan teks

Asli:

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

Rekreasi:

"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 

Tebak:

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

Ubah log

• 569279 - berubah menjadi whale2.txtdan dengan demikian menghapus optimasi.
• 577366 - dioptimalkan dengan kode yang mencoba menebak kapan harus mengembalikan umpan baris.
• 590354 - versi asli.

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

Java menyebalkan untuk ukuran program kecil. Lagi pula, saya mencoba beberapa pendekatan yang sangat rumit dan rumit yang menghasilkan hasil omong kosong yang mengejutkan. Saya kemudian kembali dan hanya melakukan pendekatan sederhana, yang menghasilkan ukuran program yang lebih kecil dan hasil yang lebih baik.

Pendekatan ini sebenarnya sangat sederhana. Itu membabi buta memberi makan karakter x sebelumnya (di samping semua substring dari karakter tersebut) ke dalam hashtable, dipetakan ke karakter saat ini. Kemudian melacak pola mana yang paling akurat memprediksi karakter saat ini. Jika pola yang mendahului karakter tertentu ditemui berulang kali, mereka berhasil memprediksi karakter. Ini memberi prioritas pada string yang lebih panjang dan memberikan prioritas pada karakter apa pun yang paling sering mengikuti string yang diberikan. Algoritma ini tidak tahu apa-apa tentang jenis dokumen atau bahasa Inggris.

Saya memutuskan untuk menggunakan 9 karakter dan berusaha mencocokkan seluruh kata dalam 9 karakter sebelumnya jika memungkinkan. Ketika Anda tidak mencoba melakukan pencocokan kata dalam string, panjang optimal adalah 6 karakter, menghasilkan beberapa ribu kesalahan prediksi.

Satu pengamatan yang menarik adalah bahwa menggunakan 20 karakter menghasilkan prediksi buruk pertama kali melalui tetapi akurasi 99,9 persen pada lintasan berikutnya. Algoritma ini pada dasarnya mampu menghafal buku dalam tumpang tindih potongan 20 byte, dan ini cukup berbeda untuk memungkinkannya mengingat seluruh buku karakter dalam satu waktu.

• (1950 * 2 + 532919) 536819
• (2406 * 2 + 526233) 531045 memeriksa tanda baca untuk membuat tebakan yang lebih baik
• (1995 * 2 + 525158) 529148 lebih mengutak-atik, menyingkirkan beberapa kata

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

Saya mencoba ini secara independen, tetapi berakhir dengan apa yang secara efektif merupakan versi yang lebih rendah dari jawaban Michael Homer. Saya harap itu tidak membuat jawaban saya sepenuhnya usang.

Ini membangun kamus kata-kata (didefinisikan secara kasar sebagai string yang diakhiri oleh atau \n, case-sensitive dan termasuk tanda baca). Kemudian mencari kamus ini untuk kata-kata yang dimulai dengan apa yang sejauh ini diketahui dari kata saat ini, mengurutkan daftar yang dihasilkan berdasarkan frekuensi kemunculannya (perlahan-lahan), dan menebak bahwa karakter berikutnya adalah karakter berikutnya dalam kata yang paling umum yang cocok. Jika kami sudah memiliki kata yang cocok paling umum, atau tidak ada lagi kata yang cocok, itu kembali .

Ini juga membangun kamus pasangan kata yang menjijikkan dan tidak efisien. Setelah mencapai batas kata, ia menebak bahwa karakter berikutnya adalah huruf pertama dari kata kedua dalam pasangan kata yang paling umum cocok, atau tjika tidak ada yang cocok. Tapi itu tidak terlalu pintar. Mengikuti Moby, program dengan benar menebak bahwa karakter berikutnya adalah D, tetapi kemudian ia melupakan semua konteksnya dan biasanya berakhir dengan memanggil paus "Moby Duck" (karena kata "Belanda" tampaknya lebih sering terjadi pada paruh pertama teks ). Akan mudah untuk memperbaikinya dengan memprioritaskan pasangan kata daripada kata-kata individual, tetapi saya berharap kenaikannya menjadi marginal (karena biasanya benar dari karakter ketiga aktif, dan pasangan kata tidak begitu membantu di tempat pertama).

Saya bisa menyetel ini agar lebih cocok dengan teks yang disediakan, tapi saya tidak berpikir secara manual menyetel algoritma berdasarkan pengetahuan sebelumnya dari input benar-benar dalam semangat permainan jadi, selain memilih t sebagai karakter mundur setelah spasi ( dan saya mungkin juga seharusnya tidak melakukan itu), saya menghindarinya. Saya mengabaikan panjang baris yang diketahui dari file input, dan alih-alih dimasukkan \nsetelah setiap 13 spasi — ini hampir pasti kecocokan yang sangat buruk, maksud utamanya adalah menjaga panjang garis masuk akal daripada untuk mencocokkan input.

Kode tidak persis cepat (~ 2 jam di mesin saya), tetapi secara keseluruhan mendapat sekitar setengah karakter yang benar (49%). Saya berharap skor akan sedikit lebih baik jika dijalankan whale2.txt, tetapi saya belum melakukannya.

Awal output terlihat seperti ini:

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

tetapi pada akhirnya, itu terlihat sedikit lebih seperti ... sesuatu. Bagian favorit saya dari dekat akhir buku ini,

dan karena tidak ada yang bisa menjadi milikku, biarkan aku menariknya berkeping-keping, sambil masih mengejarmu, meskipun terikat kepadamu, kamu paus sialan! INI, aku menyerahkan tombak! "

keluar sebagai

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 "

Itu akan membuat The Wrath of Khan jauh lebih membingungkan. Dan "kesepian" → "geli" adalah substitusi yang sangat memuaskan.

Sunting: Disimpan satu byte dengan menghapus ruang yang asing

Mencetak gol

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

Ini menjalankan program untuk teks Moby Dick dan mengeluarkan teks "yang diprediksi" ke stdout, dan menyalahgunakan stderr untuk menulis skor. Saya akan merekomendasikan redirect output ke file.

C ++, 2 · 62829 + 318786 = 444444

Untuk menjalankan program ini, Anda perlu file ini di sini , yang harus dinamai C.

Program ini menggunakan kombinasi model Markov yang sama seperti pada jawaban kami sebelumnya . Seperti sebelumnya, kombinasi ini pada dasarnya adalah model dari jawaban ini oleh user2699 , tetapi dengan beberapa modifikasi kecil.

Melihat bagaimana jawaban ini menggunakan model yang sama persis seperti sebelumnya, perbaikan adalah mekanisme informasi-teori yang lebih baik daripada mekanisme "mundur" yang dijelaskan sebelumnya. Ini memungkinkannya untuk membuat lebih sedikit kesalahan sekaligus memiliki panjang gabungan yang lebih kecil. Program itu sendiri tidak banyak bermain golf karena ia bukan penyumbang utama skor.

Program ini panjangnya 2167 byte (termasuk semua tab untuk lekukan dan banyak karakter lain yang tidak perlu, tetapi sebelum kode uji), dan panjang file biner Cadalah 60661 byte, jadi di bawah aturan untuk mencetak banyak file , kami mendapat skor L2167 + 60661 + 1 = 62829.

Program ini memakan waktu sekitar 8 menit untuk dijalankan pada sebuah m5.4xlargeinstance di Amazon EC2 dan menggunakan sedikit lebih dari 16 GB memori. (Penggunaan memori berlebih ini tidak diperlukan - kami hanya tidak mengoptimalkannya juga.)

#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 byte, 526092 kesalahan (menggunakan whale2.txt). Ini jelas mampu meningkatkan lebih lanjut, tetapi telah mencapai tahap "cukup baik untuk dikirim".

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

Idenya adalah untuk menyimpan frekuensi semua menjalankan 2, 3, 4, ..., 10 karakter. Untuk setiap panjang L ini, kami memeriksa apakah karakter L-1 terbaru cocok dengan pola yang disimpan; jika demikian, tebakan kami g _L adalah karakter berikutnya yang paling sering mengikuti pola itu. Kami mengumpulkan hingga sembilan tebakan dengan cara ini. Untuk memutuskan tebakan mana yang akan digunakan, kami menimbang frekuensi dari masing-masing pola berdasarkan panjangnya hingga kekuatan ke-8. Tebakan dengan jumlah frekuensi terbobot terbesar dipilih. Jika tidak ada pola yang cocok, kami menebak ruang.

(Panjang pola maksimum dan eksponen pembobotan dipilih oleh trial-and-error untuk memberikan tebakan salah yang paling sedikit.)

Ini versi work-in-progress ungolfed saya:

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

Dan test harness:

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

Berikut adalah beberapa contoh keluaran dari dekat awal teks. Sudah kita mulai melihat kemampuan untuk menyelesaikan kata-kata umum setelah melihat huruf pertama mereka ( in, to, and, by, juga, tampaknya, 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 

Menjelang akhir, masih ada banyak kesalahan, tetapi juga banyak urutan yang sangat baik ( shmage seashawks, misalnya).

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

Sangat menarik untuk melihat beberapa kesalahan dan menebak kata apa yang "diharapkan" algoritma. Sebagai contoh, setelah itu sail, kedua program memprediksi - okarena sailor, saya kira. Atau lagi, setelah , amengharapkan - nmungkin karena kejadian umum , and.

Changelog:

• 274 * 2 + 526092 = 526640 Memotong algoritma, dengan mengorbankan beberapa kesalahan tambahan
• 306 * 2 + 526089 = 526701 Versi asli

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

Mencari kata-kata yang cocok dengan karakter sebelumnya dari daftar  semua  kata yang paling banyak digunakan dalam teks, diurutkan berdasarkan jumlah kemunculannya.

Kode:

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"

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

Test suite:

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

Sunting: Menggunakan whale2.txtmemberi skor yang lebih baik.

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

Namun pengajuan frekuensi awalan lainnya. Jalankan whale2.txt, dan dapatkan skor serupa (sedikit lebih buruk) dari yang lain.

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

Yang ini dengan rakus menemukan string terpanjang yang dimulai dengan akhiran sejarah, dan jika ada banyak kandidat, tiebreak dengan string yang lebih pendek.

Sebagai contoh: Jika 7 karakter terakhir adalah abcdefgh, dan string abcdefghidan abcdefghjmuncul dengan frekuensi terbesar dalam semua string dari bentuk abcdefgh*, output akan baik iatau j, tiebreak dengan akhiran pendek ( bcdefgh, cdefgh, ...).

Untuk alasan yang tidak diketahui, apapun lebih dari 7 dan komputer saya tidak memiliki cukup RAM untuk menjalankannya. Bahkan dengan 7, saya harus menutup semua browser web untuk menjalankannya.

Kode pengujian:

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

Tidak Terkumpul:

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