Seolah tantangan ini bisa jadi lebih Pythonesque in spirit ... Tidak ada pengetahuan sebelumnya tentang rantai Markov atau teknik enkripsi yang diperlukan.
Anda adalah mata-mata yang perlu mendapatkan beberapa informasi penting dari M1S layanan keamanan Inggris. Agen M1S sangat menyadari bahwa sinyal Wi-Fi mereka dapat dicegat, kerentanan keamanan Android / iOS dll., Sehingga semuanya menggunakan Nokia 3310 untuk mengirimkan informasi teks yang diketik menggunakan pelengkapan otomatis T9 .
Anda sebelumnya telah meretas ponsel untuk dikirim ke agen intelijen dan telah menginstal keyloggers di bawah keyboard plastik mereka yang mulia, jadi sekarang Anda menerima urutan nomor yang sesuai dengan huruf yang mereka ketik, sehingga " elang telah meninggalkan sarangnya waspada agen " menjadi
84303245304270533808430637802537808430243687
Tapi tunggu! Beberapa urutan T9 bersifat ambigu ("6263" dapat berupa "nama", "surai" atau "oboe"; semakin kabur, semakin mencurigakan!), Jadi apa yang Anda lakukan? Anda tahu bahwa satu-satunya ujian masuk yang digunakan M1S adalah meringkas karya agung Marcel Proust "Remembrance of Things Past" dalam 15 detik, jadi Anda ingin memilih kata yang muncul setelah yang sebelumnya menurut distribusi frekuensinya di seluruh chef-d ' uuu Proust!
Bisakah Anda memecahkan kode dan mendapatkan pesan asli?
Prinsip T9
Mekanisme penyelesaian otomatis T9 dapat dijelaskan sebagai berikut. Ini memetakan karakter alfabet ke angka seperti yang ditunjukkan pada gambar di atas.
abc -> 2
def -> 3
ghi -> 4
jkl -> 5
mno -> 6
pqrs -> 7
tuv -> 8
wxyz -> 9
<space> -> 0
<other> -> <is deleted>
Decryptor T9 menerima urutan angka dan mencoba menebak kata yang dapat diketik dengan penekanan tombol itu. Mungkin menggunakan tabel frekuensi standar, tetapi kita akan selangkah lebih maju dan memprediksi kata berikutnya menggunakan rantai Markov!
Sampel pembelajaran
Corpus adalah versi Proust yang berjudul "Remembrance of Things Past" ( s/-/ /g
, s/['’]s //g
dan s/[^a-zA-Z ]//g
- hilang posesif yang membingungkan 's
!) Yang awalnya diterbitkan di situs web University of Adelaide (teks dari karya ini ada di Public Domain di Australia).
Seluruh teks harus dianalisis sebagai satu string, sebagai satu kalimat panjang, sebagai satu vektor panjang kata (mana yang lebih nyaman untuk bahasa Anda), dilucuti dari linebreak , dan dipecah menjadi kata-kata di spasi . (Saya tidak menyediakan file paragraf tunggal karena hal itu mungkin disukai oleh alat github.)
Bagaimana cara membaca seluruh teks sebagai satu string / kalimat? Contoh dalam R :
p_raw <- read.table("proust.txt", sep="\t") # Because there are no tabs
p_vec <- as.character(p_raw$V1) # Conversion to character vector
p_str <- paste(p_vec, collapse=" ") # One long string with spaces
p_spl <- strsplit(p_str, split=" ")[[1]] # Vector of 1360883 words
proust <- p_spl[p_spl!=""] # Remove empty entries — 1360797
Tugas
Diberikan urutan digit sebagai angka, kembalikan string teks yang mungkin dapat diketik menggunakan kunci T9 yang sesuai menggunakan rantai probabilitas untuk memprediksi kata X berikutnya berdasarkan teks pelatihan ini yang diperlakukan sebagai satu kalimat panjang.
Jika X adalah kata T9 pertama dari teks dan ada beberapa tebakan, pilih satu secara acak, atau pilih satu-satunya yang mungkin.
Untuk semua T9-kata X berikutnya (i) didahului dengan kata yang sudah diuraikan w (i-1) :
- Jika T9-kata X dapat dikonversi menjadi kata normal x dengan satu cara yang unik, lakukanlah.
- Jika ada beberapa opsi konversi yang tersedia untuk X , katakanlah x1, x2, ... , cari kata yang sebelumnya ditebak w .
- Jika w tidak pernah diikuti oleh apa pun yang memetakan ke X dalam karya asli Proust, pilih salah satu dari x1, x2, ... yang mungkin secara acak.
- Jika w X selalu sesuai dengan w x1 di aslinya dan tidak ada xi konkuren yang dapat dipetakan ke X , pilih x1 .
- Jika w X dapat dikonversi ke w x1 , w x2 , ... yang dapat ditemukan di corpus, maka hitung semua kemungkinan xi yang mengikuti w dan petakan ke X di corpus dan pilih xi dengan probabilitas xi / (x1 + x2 + ...) .
Contoh 2a. Jika pesannya 76630489
, di mana 489
bisa guy
atau ivy
(mereka muncul dalam korpus setidaknya sekali), 7663
dapat diuraikan sebagai some
(kata pertama yang sangat mungkin). Jika some
tidak pernah diikuti oleh apa pun yang dipetakan ke 489
dalam corpus, maka pilih guy
atau ivy
secara acak dengan probabilitas 0,5.
Contoh 2b. Jika pesannya 766302277437
, di mana 2277437
bisa barrier
atau carrier
, 7663
bisa diuraikan sebagai some
. Jika Proust selalu digunakan some carrier
dan tidak pernah some barrier
, pilihlah some carrier
.
Contoh 2c. Misalkan Anda ingin menguraikan urutannya 536307663
. 5363
diperkirakan sebagai lend
. 7663
bisa menjadi salah satu dari ini: pond
, roof
dan some
. Anda menghitung kemunculan kata berikut lend
dalam korpus sampel. Misalkan Anda mendapatkan sesuatu seperti ini (hanya untuk menggambarkan):
T9 Word following lend Occurrences
7663 some 7
7663 pond 2
7663 roof 1
Jadi jika 7663
didahului oleh lend
, ada 7/(7+2+1)=70%
probabilitas yang 7663
berarti some
, 20% pond
dan 10% roof
. Algoritme Anda harus menghasilkan lend some
dalam 70% kasus, lend pond
dalam 20% kasus dll.
Anda dapat dengan aman berasumsi bahwa agen hanya menggunakan huruf dan spasi az (tidak ada tanda baca, tidak posesif 's
, dan tidak ada angka).
Anda juga dapat berasumsi bahwa agen M1S tidak pernah menggunakan kata apa pun di luar lingkup “Remembrance of Things Past” (yang merupakan kosakata kekalahan 29.237 kata!).
Fuctionality T9 diimplementasikan dalam tantangan ini , jadi Anda mungkin melihatnya.
Jika Anda memerlukan bantuan, rantai probabilitas dimenangkan dengan gemilang dalam hal ini , itu dan tantangan - tantangan berikut , tetapi Anda bahkan tidak perlu mengetahui prinsip rantai tersebut: semuanya dinyatakan dalam tugas.
Uji kasus
--Inputs--
20784250276960369
20784250276960369
84303245304270533808430637802537808430243687
94280343084306289072908608430262780482737
94280343084306289072908608430262780482737
--Possible outputs--
c quick brown fox
a stick crown fox
the eagle gas left the nest blest vie agents
what did the navy pay to the coast guards
what did the navy raz un the coast guards
Aturan:
- Celah standar berlaku.
- Anda tidak tahu pesan aslinya, semua yang Anda dapatkan adalah urutan digit dan file proust.txt yang Anda hanya perlu memuat di memori / ruang kerja / apa pun. Tidak perlu memiliki apa pun yang mandiri; anggap
proust.txt
selalu dapat diakses. - Algoritme Anda harus dapat menghasilkan keluaran yang berbeda dengan probabilitas masing-masing jika lebih dari satu opsi dekripsi kemungkinan sesuai dengan corpus (lihat Contoh 2c).
Anda harus tetap diam-diam, sehingga kode terpendek menang!
PS Manfaat nyata dari algoritma probabilistik ini adalah kenyataan bahwa probabilitas Anda akan mendapatkan string asli yang sebenarnya untuk string yang diuraikan secara ambigu cenderung menjadi satu - tunggu saja ...
PPS Lihat juga Prediksi oleh Pencocokan Sebagian .
sumber
Jawaban:
Solusi R, ilustrasi yang tidak bersaing tentang apa yang dapat dilakukan
Pertama, kami memuat urutan kata ke dalam memori:
Kedua, kita membutuhkan fungsi yang membuat teks T9-ifies:
Kemudian, kami T9-ify Proust:
Persiapan akhir: kami membagi string input pada nol menggunakan fungsi yang kami sebut
prep
):Dan sekarang saya mengusulkan fungsi yang mengambil string input angka,
prep
s dan menguraikan kata-kata satu per satu:Dan sekarang apa yang sebenarnya dilakukannya:
Contoh kedua:
Tolong jangan berkomentar bahwa ini bisa golf. Tampaknya hanya sedikit orang yang tertarik dengan tantangan ini karena kata-kata mengerikan saya, jadi saya memposting jawaban ini untuk menunjukkan seperti apa program yang mungkin terlihat. Anda tidak perlu mengungguli / menurunkan jawaban ini.
sumber
Python 3, 316 byte
sumber