Tulis Moby Dick, kira-kira


297

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

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.


Komentar bukan untuk diskusi panjang; percakapan ini telah dipindahkan ke obrolan .
Dennis

9
xkcd.com/1960 tampaknya menjadi referensi untuk tantangan ini!
A. Rex

Saya berpikir untuk mengompresi ini ... tapi agak terlalu lama komputer saya mengalami crash bahu
Naruyoko

Jawaban:



97

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

44
Bagi yang penasaran, tidak, ini tidak menghasilkan apa-apa seperti Moby Dick. Ini banyak sekali sidg tlanses,oeth to, shuld hottut tild aoersors Ch, th! Sa, yr! Sheu arinning whales aut ihe e sl he traaty of rrsf tg homn Bho dla tiasot a shab sor ty, af etoors tnd hocket sh bts ait mtubb tiddin tis aeewnrs, dnhost maundy cnd sner aiwt d boelh cheugh -aaieiyns aasiyns taaeiins! th, tla. Terkadang berhasil mendapatkan beberapa kata lengkap. Seperti whales.
immibis

23
@immibis Judul tantangan dipilih dengan bijak. Ini Moby Dick, kira-kira . :-)
Arnauld

3
@Nathaniel Ada banyak pembaruan, sehingga hampir tidak dapat dibaca dan tidak terlalu informatif. Saya telah menambahkan log perubahan sebagai gantinya dengan penjelasan singkat tentang perbaikan.
Arnauld

45
Saya pikir program Anda benar-benar melakukan terjemahan yang sempurna ke bahasa Gaelic.
Beska

1
@ Draco18s Sulit untuk mengetahui apakah koma ini merupakan tebakan yang baik atau buruk. Jika itu adalah dugaan yang buruk, fungsi prediksi mungkin secara sah mencoba untuk menempatkan huruf setelah apa pun-surat-lain-yang-sebenarnya-ada-di sana-bukan-dari-koma setelah menerimanya.
Arnauld

91

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!


8
Wow, jawaban yang mengesankan. Saya berasumsi ada kode tambahan yang diperlukan untuk menghasilkan Bfile? Jika demikian, dapatkah Anda memasukkannya dalam jawaban Anda?
Nathaniel

8
Luar biasa! Jawaban pertama (dan sejauh ini satu-satunya) untuk menembus penghalang skor 500k.
ShreevatsaR

5
"tersed the shite whale" omg I'm crying
Phill

5
Karena tidak ada jawaban baru yang diposting selama periode hadiah, saya menghadiahkannya untuk jawaban Anda, sebagai penilaian terbaik dan pendekatan paling canggih. Jika Anda punya waktu, saya akan sangat menghargai penjelasan yang lebih mendalam tentang cara kerja jawaban ini, yaitu apa sebenarnya algoritme itu?
Nathaniel

2
@Nathaniel: Saya menambahkan penjelasan untuk posting ini. Beri tahu saya jika menurut Anda cukup detail untuk mereproduksi solusinya sendiri.
A. Rex

77

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)

2
Alat yang tepat untuk pekerjaan itu. Skor bagus. Bagus
agtoever

1
Klarifikasi yang mungkin: b"\0\3\6\r\34'&-20'\22!P\n[\26"adalah representasi bobot ascii, di mana nilai-nilai kecil yang tidak dapat dicetak lolos dalam oktal.
C?ur

Saya telah memperbarui pertanyaan dengan versi file di mana teks tidak dibungkus - Anda dapat mencoba menjalankan kembali kode Anda pada hal itu (mungkin sedikit lebih baik)
Nathaniel

3
Terima kasih atas penjelasan itu - jika Anda dapat mengedit sinopsis ke dalam pertanyaan, itu akan bagus. (Pengalaman dengan tantangan saya sebelumnya Paint Starry Night adalah bahwa prosedur pengoptimalan ini adalah bagian paling menarik dari jawaban, jadi jauh lebih baik jika jawaban menyertakan kode yang digunakan untuk melakukan itu, dan penjelasannya. Saya memasukkan aturan di keduanya tantangan mengatakan bahwa mereka harus.)
Nathaniel

1
@Christoph Kombinasi model saya sebenarnya adalah rata-rata geometris tertimbang. Tetapi rata-rata PAQ dalam domain logistik sedikit berbeda — saya harus melihat apakah itu lebih baik.
Anders Kaseorg

55

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

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

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.


3
Ini adalah pendekatan yang sangat bagus!
Skyler

2
terlalu banyak <s> </s>;)
FantaC

1
+1 karena pendekatan ini mengingatkan saya pada algoritma kompresi LZW.
Marcos

25

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.


5
Anda dapat menerjemahkan array ini ke dalam string literal dan langsung memasangnya di tempat Luntuk menyimpan banyak karakter :)
Quentin

@ Quentin Terima kasih! Sekarang saya bertanya-tanya mengapa saya tidak memikirkan hal itu sejak awal ...
Steadybox

20

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

3
Selamat datang di situs ini! Ini adalah pengiriman pertama yang fantastis. :)
DJMcMayhem

@DJMcMayhem, Terima kasih atas sambutannya. Saya menikmati menonton untuk sementara waktu sekarang, ini adalah kontes pertama yang menarik perhatian saya untuk entri.
user2699

19

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

... TIO link tidak berguna. Jadi fungsi mengembalikan nilai tugas terakhir?
user202729

Biarkan saya mengedit jawaban dengan penjelasan, lalu :)

1
@Rogem Saya telah menambahkan versi de-golfed (yang saya lakukan karena saya juga tidak bisa mengikutinya) - semoga ini tidak mengganggu Anda, tetapi silakan putar kembali jika diinginkan.
Adam Davis

@AdamDavis pada sebagian besar implementasi C, semua variabel global mulai dari nol. Itu perilaku yang tidak terdefinisi, jadi itu hanya digunakan dalam kode-golf.
NieDzejkob

1
@NieDzejkob Ah, Anda benar, terima kasih! "ANSI-C mengharuskan semua variabel statis / global yang tidak diinisialisasi harus diinisialisasi dengan 0."
Adam Davis

16

sh + bzip2, 2 * 364106 = 728212

2 * 381249 + 0 = 762498

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

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

6
Saya pikir yang dia tanyakan adalah: bagaimana hal ini tidak melanggar but may not load any other external files, and your code may not access the whale.txt file in any way other than described above.klausa?

8
@Rogem Data yang dikompresi diletakkan setelah apa yang ditampilkan di sini, dan kode mengaksesnya sendiri.
user202729

4
Pertanyaannya mengatakan: "Kiriman Anda akan menjadi program atau fungsi (dll) yang akan dipanggil atau dipanggil beberapa kali. Ketika dipanggil untuk nthwaktu itu akan diberikan karakter ke-n whale.txtatau whale2.txtdan ia harus menampilkan tebakannya untuk (n+1)thkarakter." - Bagaimana persyaratan ini dipenuhi? Kode menampilkan seluruh teks whale.txtsetiap kali dieksekusi.
Aksioma

1
@axiac "semuanya baik-baik saja, asalkan program Anda selalu memberikan satu byte output sebelum menerima byte input berikutnya."
user202729

5
@axiac diberi test harness, saya senang menganggap mengirim program satu byte dari STDIN sebagai "memanggil atau memanggil" itu. Yang penting adalah bahwa program mengembalikan satu byte output setelah setiap byte input, yang sebenarnya dilakukan, ketika dijalankan melalui test harness. Seperti kata pertanyaan, "semuanya baik-baik saja, selama program Anda selalu memberikan satu byte output sebelum menerima byte input berikutnya."
Nathaniel

13

Python 3 , 879766

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

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.


13

C #, 378 * 2 + 569279 = 570035

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

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.

4
Terima kasih telah menunjukkan varians saat Anda mengubah ukuran kunci dan ambang kolom!
Jeremy Weirich

Saya telah memperbarui pertanyaan dengan versi file di mana teks tidak dibungkus - Anda mungkin dapat menyimpan beberapa poin dengan menggunakan itu
Nathaniel

@Nathaniel memang. Saya telah memperbarui jawabannya.
Charlie

Anda dapat menyimpan beberapa byte menggunakan var daripada mendeklarasikan jenisnya.
Ed T

1
Ketika ukuran kunci semakin besar, jumlah ayat yang terlewat akan turun dan dengan demikian lebih banyak ruang akan dihasilkan ketika kunci yang lebih pendek mungkin menebak karakter yang benar. Karena ukuran kunci semakin kecil, tebakan individu kurang akurat untuk segmen yang cocok. Saya menduga inilah sebabnya mengapa panjang empat optimal. Jika Anda mempertahankan kunci dengan panjang lebih dari satu dan menggunakan kecocokan yang lebih pendek ketika yang lebih lama tidak tersedia, maka saya perkirakan tingkat hit (dan karenanya skornya) akan sangat ditingkatkan pada panjang kunci yang lebih panjang.
Jeffrey L Whitledge

11

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

Itu skor yang cukup bagus untuk bahasa yang begitu verbose.
DJMcMayhem

1
Saya pikir itu layak dicoba karena ukuran file memberikan banyak ruang untuk perbaikan dibandingkan dengan ukuran program.
Jim W

3
Ini tidak dapat dikompilasi di bawah Java 7 (atau versi Java apa pun, apa pun nilainya). Bisakah Anda memperbaiki kode Anda? Setelah selesai, saya akan dengan senang hati golf sehingga skor Anda meningkat.
Olivier Grégoire

Belum diuji, tetapi ini harus kode yang sama persis Anda sedikit golf: 950 byte . Kode Anda saat ini mengandung beberapa kesalahan, jadi saya tidak yakin apakah saya sudah mengisi semuanya dengan benar. Sekali lagi, belum diuji, jadi hanya membandingkan versi untuk melihat apa yang telah saya ubah / ubah namanya, dan lihat apakah semuanya masih bekerja sama dengan kode asli Anda. Pasti bisa bermain golf lagi.
Kevin Cruijssen

Sial, saya melakukan ini sambil bosan dengan pekerjaan lama saya dan tidak membawa kode. Saya harus melihatnya untuk melihat di mana kesalahan ketik itu.
Jim W

10

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

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

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.


2
Selamat datang di PPCG!
Martin Ender

1
Bukankah lambda i:i[1]lebih murah daripada berurusan dengan operator?
Draconis

@Draconis Hampir pasti.
georgewatson

9

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

7

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

6

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.


5

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

Contoh output:

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

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

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

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

Yang ini dekat akhir teks. Kebanyakan kata-kata panjang diperkirakan cukup akurat ( intervals, pivot-hole, distance)

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

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

Huruf besar sepertinya tidak baik.


Trie tampaknya lebih memakan banyak memori daripada yang saya harapkan ...
user202729

... dan juga lebih sulit untuk diterapkan.
user202729

4

Python 2, 756837

Menggunakan sesuatu yang mungkin rantai Markov?

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

1
Penjelasan cepat: Yang zlib.decompress('...')dievaluasi menjadi {'G?':' ', 'G;':' ','G"':' ',.......}, dan amerupakan kamus yang memetakan dari 2 karakter ke 1 karakter. Pada dasarnya varian 2-karakter dari jawaban Steadybox .
user202729

1
Seperti yang saya lihat, literalnya adalah 17780 byte. Anda bisa menguranginya menjadi 11619 karakter dengan menghapus spasi putih di konten yang dikompresi, yang menyimpan 12322 byte. (jika saya hitung dengan benar) Juga ... mengonversi kode pelarian hex ke karakter mentah sebenarnya dapat menyimpan lebih banyak byte.
user202729

Bagaimana cara mengirim sesuatu di sini jika byte mentah?
Skyler

1
xxd, hexdump, uuencode, Atau serupa
Peter Taylor

@ user202729 Perhatikan bahwa kode Python tidak dapat berisi byte NUL mentah yang sebenarnya.
mbomb007

4

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

{-# LANGUAGE FlexibleInstances, DeriveGeneric #-}

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

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

import Codec.Compression.Lzma

import Data.Flat

import GHC.Word

maxWordLen :: Integral n => n
maxWordLen = 20

wordSeqDictSize :: Integral n => n
wordSeqDictSize = 255

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

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

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

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

Contoh:

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

Menggunakan tiga file tambahan yang dihitung sebelumnya:

  • seqwords berisi 236 kata yang paling umum.
  • wordsseq berisi sekuens terkompresi LZMA dari kata-kata ini, dan untuk semua kata yang bukan di antara 236 paling umum, panjangnya.
  • dicttriesberisi, untuk setiap panjang kata, pohon keputusan yang berisi semua kata yang tersisa. Dari percobaan ini, entri dipilih saat kita melanjutkan.

Dengan cara ini, kami mencapai tingkat kesalahan yang jauh lebih rendah daripada semua skema lossy lainnya; Sayangnya, wordsseqfile tersebut masih terlalu besar untuk bisa bersaing.

Berikut ini adalah versi lengkap yang membuat file dan melakukan analisis:

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

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

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

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


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

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

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

coLines :: String -> String -> [String]
coLines [] _ = [[],[]]
coLines ('\n':l) (_:m) = []:[]:coLines l m
coLines l ('\n':m) = coLines l ('|':m)
coLines (c:l) (d:m) = case coLines l m of
   (lt:mt:r) -> (c:lt):(d:mt):r

3

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

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

using namespace std;

constexpr minstd_rand::result_type seed = 10087702;

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

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

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

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

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

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

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

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

    minstd_rand rng;

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

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

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

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

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

    generator2() :
            rng(seed) {
    }

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

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

Saat ini, solusi ini adalah WIP dan karena itu tidak ungolfed. Juga mempertimbangkan bahwa ukuran kode aktual hampir tidak memiliki dampak pada skor saya pikir saya memposting jawaban saya terlebih dahulu sebelum mulai mengoptimalkan mikro itu.
(Kode lengkap tersedia di sini: https://github.com/BrainStone/MobyDickRNG - Termasuk program lengkap dan pencarian unggulan)

Solusi ini didasarkan pada RNG. Pertama saya menganalisis teks. Saya membuat peta yang menghitung kemunculan dua karakter berurutan. Lalu saya membuat peta distribusi. Ini semua dilakukan secara statis sehingga harus sesuai dengan aturan.

Kemudian ketika mencoba untuk mencetak teks saya melakukan pencarian dan menarik karakter acak yang mungkin. Meskipun ini biasanya menghasilkan hasil yang lebih buruk daripada hanya menghasilkan surat berikut yang paling umum, mungkin ada benih dewa yang akan menghasilkan hasil yang lebih baik. Itu sebabnya benih tersebut dikodekan dengan keras. Saat ini saya sedang mencari benih terbaik. Dan saya akan memperbarui jawaban ini setelah saya menemukan benih yang lebih baik. Jadi tetaplah diposting!

Jika ada yang ingin mencari benih sendiri atau menggunakan RNG berbeda jangan ragu untuk membayar repo.

Metode yang digunakan untuk menghitung skor: https://github.com/BrainStone/MobyDickRNG/blob/master/src/search.cpp#L15

Catatan meskipun skor total adalah yang terburuk saat ini, itu mengalahkan hitungan kesalahan hanya menghasilkan ruang. Dan kemungkinan bagus bahwa skor akan turun, dengan memeriksa lebih banyak benih.

Changelog

  • 2018/01/24 : Jawaban inital yang diposting.
    Biji yang diperiksa: 0-50000. Nilai: 2305 * 2 + 1017754 = 1022364
  • 2018/01/24 : Melakukan sedikit golf. Menambahkan tautan ke metode perhitungan skor.
    Benih yang diperiksa: 0-80000. Nilai: 1920 * 2 + 1017754 = 1021594 (-770)
  • 2018/02/02 : Benih baru (10087702) (tidak menemukan waktu untuk memperbaiki pengiriman)
    Benih yang diperiksa: 0-32000000. Nilai: 1923 * 2 + 1017344 = 1021190 (-404)

Bisakah Anda memasukkan test harness dalam jawaban Anda yang mengevaluasi skor?
Nathaniel

@Nathaniel Saya menautkan kode skor secara langsung. Selain itu dengan repositori, apakah Anda akan menganggap ini cukup?
BrainStone

Setelah meninjau aturan saya perhatikan bahwa saya melanggar beberapa dari mereka. Saya secara alami akan memperbarui jawaban saya setelah saya memperbaiki masalah
BrainStone

Anda kemudian akan berakhir menyandikan teks ke dalam seed acak. Lihat Seed bahasa pemrograman esoteris , dan Anda mungkin ingin merekayasa balik program MT19937 dan mengalahkan jawaban ini (jika Anda bisa).
user202729

Ide yang bagus, tetapi tidak akan membantu mendapatkan skor yang bagus. Tetap memberi +1.
user202729

3

Ruby, 1164418 (aduh)

Saya hanya ingin melihat seberapa baik yang bisa saya lakukan tanpa memeriksa jawaban lain.
Saya tidak yakin apakah ini diperbolehkan karena itu termasuk literal yang saya hasilkan dengan menganalisis file, tetapi meskipun tidak, itu tidak seperti itu dalam bahaya mengalahkan siapa pun.

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

Bagaimana saya menghasilkan x

Pertama, saya membuat a.txtdengan yang berikut ini:

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

Lalu saya menghasilkan a.csv:

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

Lalu saya menguraikannya xdengan skrip Ruby berikut:

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

Bagaimana saya mencetak gol

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

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

end}}

puts "FINAL SCORE: #{score}"

Saya yakin itu diizinkan; jika Anda menganalisis file, kerja bagus! Hanya jika program melakukannya maka ini tidak valid.
Erik the Outgolfer

@EriktheOutgolfer> _> (diam-diam memasukkan "(tidak bersaing)" ke judul)
NO_BOOT_DEVICE

Mengapa? Jika ini valid, itu bersaing, meskipun mungkin tidak banyak mengalahkan. Jika tidak valid (yaitu, solusi Anda membaca dari file, dan tidak hanya mengandung literal), itu harus dihapus.
Erik the Outgolfer

Hmmm. Saya pikir Anda maksud jika ada program yang menganalisis file, dan bukan hanya solusinya.
NO_BOOT_DEVICE

1
Saya tidak dapat membaca Ruby, tetapi saya pikir ini valid. Memiliki literal di dalam program benar-benar baik, itu tidak masalah sama sekali.
Nathaniel

2

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

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

Cobalah online!

Tabel frekuensi cukup mudah. Setiap posisi dalam string sesuai dengan kode ascii karakter saat ini (minus 10 = 0x0a = '\ n', karakter terendah dalam file), dan karakter pada setiap indeks adalah karakter berikutnya yang paling sering. Dengan asumsi saya menghitung frekuensi dengan benar ...

Diuji dengan kode dari tes user202729


Bisakah Anda menyimpan beberapa byte dengan menggunakan def f(c):return(" ">c)*c or"t ... e"[ord(c)-32]?
Neil

0

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

Akurasi sempurna hanya dalam 644449 byte

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

Kode lengkap tidak dapat ditampung dalam jawaban, jadi saya telah meletakkannya di sini dan mengganti literal string biner besar dengan b '###' dalam teks jawaban.

Ini dihasilkan dengan kode berikut, di mana "modified.py" adalah file yang dihasilkan, dan "cheatsheet.txt" adalah file whale2.txt mulai dari karakter kedua.

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

Kode dapat dieksekusi dengan menambahkan berikut ini di akhir "modified.py". "whale2.txt" harus berada di direktori yang sama dengan "modified.py", dan hasilnya akan ditulis ke "out.txt".

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

Jawaban ini tidak secara langsung mengakses whale.txt atau whale2.txt. Itu menggunakan perpustakaan kompresi standar yang ada secara eksplisit diizinkan dalam aturan.


mungkin ada "\ r \ n" di sana yang saya tidak bisa singkirkan di Windows ketika saya menghitungnya
Legorhin

2
ya itu salah ketik yang diperbanyak
Legorhin
Dengan menggunakan situs kami, Anda mengakui telah membaca dan memahami Kebijakan Cookie dan Kebijakan Privasi kami.
Licensed under cc by-sa 3.0 with attribution required.
Judi bola 体育新闻| 8868体育| 8868体育| 体育新闻>| <蜘蛛词>| <蜘蛛词>| <蜘蛛词>| 8868体育| 8868体育| 8868体育|