Dalam semangat Patch Gambar , inilah tantangan yang sama tetapi dengan teks.
Tantangan
Bit busuk telah mempengaruhi teks berharga Anda! Diberi paragraf yang terdiri dari karakter ASCII, dengan lubang persegi panjang di suatu tempat di dalamnya, program Anda harus mencoba mengisi lubang dengan teks yang sesuai, sehingga paragraf berpadu sebaik mungkin.
Definisi lebih lanjut
- Lubang akan selalu berbentuk persegi panjang, dan dapat menjangkau beberapa garis.
- Hanya akan ada satu lubang.
- Perhatikan bahwa lubang tidak harus jatuh pada batas kata (pada kenyataannya, biasanya tidak akan).
- Lubang tersebut paling banyak 25% dari paragraf input, tetapi mungkin tumpang tindih atau melampaui "akhir" dari teks "normal" (lihat contoh Euclid atau Badger di bawah).
- Karena menemukan lubang bukanlah titik utama dari tantangan ini, itu hanya akan terdiri dari tanda pagar
#
untuk memudahkan identifikasi. - Tidak ada lokasi lain di paragraf masukan yang akan memiliki tanda pagar.
- Kode Anda tidak dapat menggunakan teks "normal" dalam contoh di bawah ini - ia hanya akan menerima dan memproses teks dengan lubang di dalamnya.
- Input dapat berupa string multi-baris tunggal, sebagai array string (satu elemen per baris), sebagai file, dll. - pilihan Anda tentang apa yang paling nyaman untuk bahasa Anda.
- Jika diinginkan, input tambahan opsional yang merinci koordinat lubang dapat diambil (misalnya, tupel koordinat atau sejenisnya).
- Tolong jelaskan algoritma Anda dalam kiriman Anda.
Pemungutan suara
Para pemilih diminta untuk menilai entri berdasarkan seberapa baik algoritma mengisi lubang teks. Beberapa saran termasuk yang berikut:
- Apakah area yang diisi sesuai dengan perkiraan ruang dan tanda baca sebagai sisa paragraf?
- Apakah area yang diisi memperkenalkan sintaksis yang salah? (misalnya, dua spasi berturut-turut, periode diikuti oleh tanda tanya, urutan yang keliru seperti
, ,
, dll.) - Jika Anda menyipitkan mata (sehingga Anda tidak benar-benar membaca teks), dapatkah Anda melihat di mana lubang itu dulu?
- Jika tidak ada kata CamelCase di luar lubang, apakah lubang itu mengandung kata-kata? Jika tidak ada Huruf Kapital di luar lubang, apakah lubang itu berisi? Jika Ada Banyak Huruf Kapital Di Luar Lubang, apakah lubang itu mengandung jumlah yang proporsional?
Kriteria Validitas
Agar kiriman dianggap sah, ia tidak boleh mengubah teks paragraf di luar lubang (termasuk spasi tambahan). Satu baris tambahan di bagian paling akhir adalah opsional.
Uji Kasus
Format adalah paragraf asli dalam blok kode, diikuti oleh paragraf yang sama dengan sebuah lubang. Paragraf dengan lubang akan digunakan untuk input.
1 (Menambal Gambar)
In a popular image editing software there is a feature, that patches (The term
used in image processing is inpainting as @minxomat pointed out.) a selected
area of an image, based on the information outside of that patch. And it does a
quite good job, considering it is just a program. As a human, you can sometimes
see that something is wrong, but if you squeeze your eyes or just take a short
glance, the patch seems to fill in the gap quite well.
In a popular image editing software there is a feature, that patches (The term
used in image processing is inpainting as @minxomat pointed out.) a selected
area of an image, #############information outside of that patch. And it does a
quite good job, co#############is just a program. As a human, you can sometimes
see that something#############t if you squeeze your eyes or just take a short
glance, the patch seems to fill in the gap quite well.
2 (Alamat Gettysburg)
But, in a larger sense, we can not dedicate, we can not consecrate, we can not
hallow this ground. The brave men, living and dead, who struggled here, have
consecrated it, far above our poor power to add or detract. The world will
little note, nor long remember what we say here, but it can never forget what
they did here. It is for us the living, rather, to be dedicated here to the
unfinished work which they who fought here have thus far so nobly advanced. It
is rather for us to be here dedicated to the great task remaining before us-
that from these honored dead we take increased devotion to that cause for which
they gave the last full measure of devotion-that we here highly resolve that
these dead shall not have died in vain-that this nation, under God, shall have
a new birth of freedom-and that government of the people, by the people, for
the people, shall not perish from the earth.
But, in a larger sense, we can not dedicate, we can not consecrate, we can not
hallow this ground. The brave men, living and dead, who struggled here, have
consecrated it, far above our poor power to add or detract. The world will
little note, nor long remember what we say here, but it can never forget what
they did here. It is for us the living, rather, to be dedicated here to the
unfinished work which they who fought here h######################advanced. It
is rather for us to be here dedicated to the######################before us-
that from these honored dead we take increas######################use for which
they gave the last full measure of devotion-######################solve that
these dead shall not have died in vain-that ######################, shall have
a new birth of freedom-and that government of the people, by the people, for
the people, shall not perish from the earth.
3 (Lorem Ipsum)
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do
eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim
ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut
aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit
in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur
sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt
mollit anim id est laborum.
Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do
eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim
ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut
aliquip ex ea commodo conse################irure dolor in reprehenderit
in voluptate velit esse cil################giat nulla pariatur. Excepteur
sint occaecat cupidatat non################in culpa qui officia deserunt
mollit anim id est laborum.
4 (Jabberwocky)
'Twas brillig, and the slithy toves
Did gyre and gimble in the wabe;
All mimsy were the borogoves,
And the mome raths outgrabe.
'Twas brillig, and the slithy toves
Did gyre a######### in the wabe;
All mimsy #########borogoves,
And the mome raths outgrabe.
5 (bukti Euclid tentang Teorema Pythagoras)
1.Let ACB be a right-angled triangle with right angle CAB.
2.On each of the sides BC, AB, and CA, squares are drawn,
CBDE, BAGF, and ACIH, in that order. The construction of
squares requires the immediately preceding theorems in Euclid,
and depends upon the parallel postulate. [footnote 14]
3.From A, draw a line parallel to BD and CE. It will
perpendicularly intersect BC and DE at K and L, respectively.
4.Join CF and AD, to form the triangles BCF and BDA.
5.Angles CAB and BAG are both right angles; therefore C, A,
and G are collinear. Similarly for B, A, and H.
6.Angles CBD and FBA are both right angles; therefore angle ABD
equals angle FBC, since both are the sum of a right angle and angle ABC.
7.Since AB is equal to FB and BD is equal to BC, triangle ABD
must be congruent to triangle FBC.
8.Since A-K-L is a straight line, parallel to BD, then rectangle
BDLK has twice the area of triangle ABD because they share the base
BD and have the same altitude BK, i.e., a line normal to their common
base, connecting the parallel lines BD and AL. (lemma 2)
9.Since C is collinear with A and G, square BAGF must be twice in area
to triangle FBC.
10.Therefore, rectangle BDLK must have the same area as square BAGF = AB^2.
11.Similarly, it can be shown that rectangle CKLE must have the same
area as square ACIH = AC^2.
12.Adding these two results, AB^2 + AC^2 = BD × BK + KL × KC
13.Since BD = KL, BD × BK + KL × KC = BD(BK + KC) = BD × BC
14.Therefore, AB^2 + AC^2 = BC^2, since CBDE is a square.
1.Let ACB be a right-angled triangle with right angle CAB.
2.On each of the sides BC, AB, and CA, squares are drawn,
CBDE, BAGF, and ACIH, in that order. The construction of
squares requires the immediately preceding theorems in Euclid,
and depends upon the parallel postulate. [footnote 14]
3.From A, draw a line parallel to BD and CE. It will
perpendicularly intersect BC and DE at K and L, respectively.
4.Join CF and AD, to form the triangles BCF and BDA.
5.Angles CAB and BAG are both right angles; therefore C, A,
and G are #############milarly for B, A, and H.
6.Angles C#############e both right angles; therefore angle ABD
equals ang############# both are the sum of a right angle and angle ABC.
7.Since AB#############FB and BD is equal to BC, triangle ABD
must be co#############iangle FBC.
8.Since A-#############ight line, parallel to BD, then rectangle
BDLK has t############# of triangle ABD because they share the base
BD and hav#############titude BK, i.e., a line normal to their common
base, conn#############rallel lines BD and AL. (lemma 2)
9.Since C #############with A and G, square BAGF must be twice in area
to triangl#############
10.Therefo############# BDLK must have the same area as square BAGF = AB^2.
11.Similar############# shown that rectangle CKLE must have the same
area as square ACIH = AC^2.
12.Adding these two results, AB^2 + AC^2 = BD × BK + KL × KC
13.Since BD = KL, BD × BK + KL × KC = BD(BK + KC) = BD × BC
14.Therefore, AB^2 + AC^2 = BC^2, since CBDE is a square.
6 (Badger, Badger, Badger oleh weebl)
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a-
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a-
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mush-mushroom, a
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Argh! Snake, a snake!
Snaaake! A snaaaake, oooh its a snake!
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Mushroom, mushroom, a-
Badger##################badger, badger,
badger##################badger, badger
Mushro##################
Badger##################badger, badger,
badger##################badger, badger
Mush-mushroom, a
Badger, badger, badger, badger, badger,
badger, badger, badger, badger, badger
Argh! Snake, a snake!
Snaaake! A snaaaake, oooh its a snake!
sumber
Jawaban:
Python 2
Saya tahu bahwa @atlasologist sudah memposting solusi di Python 2, tetapi cara kerja saya agak berbeda. Ini bekerja dengan menelusuri semua lubang, dari atas ke bawah, kiri ke kanan, melihat 5 karakter ke belakang dan pada karakter di atas, dan menemukan karakter tempat yang cocok. Jika beberapa karakter ditemukan, itu memilih yang paling umum. Jika tidak ada karakter yang ditemukan, ini akan menghilangkan batasan karakter di atas. Jika masih tidak ada karakter yang ditemukan, ini mengurangi jumlah karakter yang terlihat kembali, dan berulang.
Inilah hasil Badger, Badger, Badger:
Inilah hasil dari buktinya:
Dan hasil dari Jabberwocky:
sumber
Python 2
Ini adalah solusi yang sangat mudah. Ini menciptakan string sampel yang terdiri dari kata-kata yang berada di antara panjang kata rata-rata
A
- (A
/ 2) danA
+ (A
/ 2), kemudian menerapkan potongan spasi terpimpin dan tertinggal dari sampel ke area tambalan. Itu tidak menangani kapitalisasi, dan saya yakin ada test case curveball di luar sana yang akan mematahkannya, tetapi tidak apa-apa pada contoh. Lihat tautan di bawah untuk menjalankan semua tes.Saya juga memasukkan patch ke kode untuk mengukur baik.
Lorem Ipsum, asli kemudian ditambal:
Cobalah
sumber
mushroger
...#
karakter lain dalam kode.@
, tidak ada yang menarik.Java Shakespeare
Siapa yang butuh pemahaman tentang konvensi bahasa Inggris standar? Buat saja sendiri! Persis seperti Bard diizinkan untuk membuat kata-katanya sendiri. Bot ini tidak terlalu khawatir mengoreksi kata-kata yang terpotong, ia benar-benar hanya memasukkan kata-kata acak. Hasilnya adalah beberapa puisi yang indah. Sebagai fitur bonus, Bard memiliki kaliber lebih tinggi dan dapat menangani beberapa lubang asalkan ukurannya sama!
Input Sampel
Output yang indah
Baris pasangan terakhir sangat puitis jika saya mengatakannya sendiri. Ini bekerja dengan sangat baik pada alamat gettysburg juga.
Mari kita lihat apa yang membuat Shakespeare tergerak. Ini kodenya. Intinya dia berusaha membangun basis kosakata dari input. Dia kemudian menggunakan kata-kata ini dan secara acak menempatkannya di dalam lubang (memastikan bahwa itu cocok dengan baik). Dia deterministik karena dia menggunakan benih tetap untuk keacakan.
Sebagian besar puisi Shakespeare adalah ranah publik.
sumber
Python 2.7
Solusi Python lain dengan pendekatan berbeda. Program saya melihat teks sebagai rantai Markov , di mana setiap huruf diikuti oleh huruf lain dengan probabilitas tertentu. Jadi langkah pertama adalah membangun tabel probabilitas. Langkah selanjutnya adalah menerapkan probabilitas itu ke tambalan.
Kode lengkap, termasuk satu contoh teks di bawah ini. Karena satu contoh menggunakan karakter unicode, saya menyertakan codepage eksplisit (utf-8) untuk kompatibilitas dengan contoh itu.
Contoh keluaran untuk Lorem Ipsum:
Garis puitis ekstra di Jabberwocky:
sumber
C # 5 masif seperti biasa
Saya melemparkan ini bersama-sama, ini agak berantakan, tetapi beberapa kali menghasilkan hasil yang OK. Ini sebagian besar algoritma deterministik, tetapi dengan beberapa (tetap-seed) keacakan ditambahkan untuk menghindarinya menghasilkan string yang sama untuk kesenjangan yang sama. Perlu beberapa upaya untuk mencoba menghindari hanya memiliki kolom ruang di kedua sisi celah.
Ini bekerja dengan tokenizing input ke dalam kata-kata dan tanda baca (tanda baca berasal dari daftar yang dimasukkan secara manual, karena saya tidak dapat diganggu untuk bekerja jika Unicode dapat melakukan ini untuk saya), sehingga dapat menempatkan spasi sebelum kata-kata, dan tidak sebelum tanda baca, karena ini cukup khas. Itu terbagi pada ruang putih khas. Dalam jalur rantai markov (saya pikir), ini menghitung seberapa sering setiap token mengikuti satu sama lain, dan kemudian tidak menghitung probabilitas untuk ini (saya pikir karena dokumen sangat kecil, kami akan lebih baik untuk bias terhadap hal-hal kita melihat banyak di mana kita bisa). Kemudian kami melakukan pencarian luas pertama, mengisi ruang yang ditinggalkan oleh hash dan kata-kata 'parsial' di kedua sisi, dengan biaya yang dihitung sebagai
-fabness(last, cur) * len(cur_with_space)
, di manafabness
pengembalian berapa kalicur
diikutilast
untuk setiap token yang ditambahkan dalam string yang dihasilkan. Secara alami, kami berusaha meminimalkan biaya. Karena kita tidak selalu dapat mengisi celah dengan kata-kata dan tanda baca yang ditemukan dalam dokumen, itu juga mempertimbangkan sejumlah token 'khusus' dari negara tertentu, termasuk string parsial di kedua sisi, yang kami bias terhadap dengan kenaikan biaya sewenang-wenang.Jika BFS gagal menemukan solusi, maka kami secara naif mencoba untuk memilih kata keterangan acak, atau hanya memasukkan spasi untuk mengisi ruang.
Hasil
Semua 6 dapat ditemukan di sini: https://gist.github.com/anonymous/5277db726d3f9bdd950b173b19fec82a
Kasus uji Euclid tidak berjalan dengan baik ...
Menambal Gambar
Jabberwocky
Luak
_Saya senang dengan bagaimana yang satu ini ternyata ... itu meramalkan bahwa "luak, luak," cocok, atau yang ini tidak akan melakukannya dengan baik
Kode
Jalankan dengan
Ada cukup banyak. Satu-satunya yang menarik adalah
Fill
metode. Saya menyertakan implementasi heap, karena .NET tidak memilikinya (MENGAPA MS MENGAPA ?!).sumber