The kompleksitas Kolmogorov dari string S adalah panjang dari program terpendek P , ditulis dalam beberapa bahasa pemrograman L , yang output persis S .
(Ya, definisi sebenarnya lebih formal tetapi ini sudah cukup untuk tantangan.)
Tugas Anda dalam tantangan ini adalah untuk menulis sesingkat mungkin "Kolmogorov kompleksitas solver", yaitu sebuah program yang ditulis dalam L sendiri yang mengambil dalam string S dan kembali terpendek P ditulis dalam L yang output S .
Pendekatan naif untuk ini adalah untuk mengulangi semua program 1 panjang, lalu semua program 2 panjang, lalu semua program 3 panjang, dan seterusnya, menjalankan masing-masing dan mengukur output sampai sebuah program yang menghasilkan S ditemukan. Masalah dengan pendekatan ini adalah bahwa beberapa dari program ini mungkin tidak pernah berhenti berjalan, yang berarti bahwa pemecah itu sendiri mungkin tidak pernah berhenti. Dan karena masalah penghentian tidak ada cara pasti untuk menghindari program yang tidak berhenti.
Solusi sederhana, meskipun tidak sempurna adalah dengan menetapkan batas waktu pada waktu eksekusi masing-masing P potensial . Program yang tidak berhenti pada waktunya dapat dilewati, tetapi pemecah pasti akan berhenti (dengan asumsi bahwa suatu program dalam L memang dapat menghasilkan S dalam batas waktu).
Tantangan
Tuliskan solver Anda sebagai program atau fungsi yang mencakup tiga hal:
- String S .
- T bilangan bulat positif yang merupakan batas waktu dalam detik atau rentang waktu yang lebih kecil (misalnya milidetik).
- Sebuah string A dari abjad karakter untuk digunakan untuk potensi P 's.
Dan output terpendek P yang hanya berisi karakter dalam A , berjalan dalam waktu kurang dari T unit waktu, dan output S .
Ini adalah pseudocode umum:
Function KolmogorovComplexitySolver(S, T, A):
Assign N to 0
Loop until function returns:
In any order, iterate over all strings of length N that only contain characters from *A*. Call the current string P:
Execute P, saving the output to O, stopping the execution if it takes longer than time T
If (P did not throw any errors) and (P did not timeout) and (O and S are identical):
Return P
Add 1 to N
Detail
- Anda mungkin berasumsi bahwa akan selalu ada sebuah P terbuat dari karakter dalam A yang berjalan dalam waktu T yang output S .
- Anda dapat mengasumsikan bahwa eksekusi P potensial tidak akan memiliki efek samping yang mencegah solver berjalan atau bekerja dengan benar (seperti mengacaukan memori yang dialokasikan solver).
- Anda tidak boleh berasumsi bahwa potensi P bebas dari kesalahan. Pastikan untuk menyertakan
try
/catch
memblokir atau apa pun yang berlaku di sekitar panggilan eksekusi. - Jika ada beberapa P terpendek , maka semua sudah cukup. "Shortness" diukur dalam karakter bukan byte.
- Output dari P potensial adalah apa yang dicetak ke stdout (atau area output biasa bahasa Anda). String kosong adalah P potensial .
- Idealnya, solver Anda akan memungkinkan A mengandung karakter apa pun. Sebuah keharusan setidaknya untuk bisa mengandung ASCII printable karakter ditambah tab dan baris baru.
- Input dapat berasal dari argumen file / stdin / command line / function. Output menuju stdout atau serupa, atau dapat dikembalikan sebagai string jika Anda menulis suatu fungsi.
Mencetak gol
Kiriman dengan byte paling sedikit menang. Tiebreaker pergi ke kiriman diposting paling awal.
sumber
Jawaban:
Python 3,
240236 byteJangan jalankan ini. Di komputer saya, setidaknya, saya menemukan program sangat sulit untuk berhenti setelah mulai berjalan karena jendela pop-up yang dibuat per proses.
timeout
s hanya ditambahkan kesubprocess.check_output
dalam Python 3, itulah sebabnya kami menggunakan ini daripada Python 2.Berikut ini adalah versi alternatif dengan
time.sleep
yang juga mencetak semua program yang valid yang ditemukan di sepanjang jalan, serta output yang sesuai:Program menggunakan nama file
a
untuk setiap program yangP
akan diuji, jadi jika Anda menjalankan ini pastikan Anda belum memiliki file dengan nama itu. Ganti["py","-3","a"]
dengan perintah yang sesuai untuk pengaturan Anda (misalnya["python","a"]
atau["python3","a"]
).Jangan ragu untuk mengubah
sleep
durasi dengan risiko Anda sendiri :). Sebut sepertif("1\r\n",1,"1()print")
, di manaT
batas waktu dalam detik.Beberapa baris pertama output dari tester dengan panggilan di atas:
(Jika Anda ingin sedikit membantu program ini, Anda dapat mengubahnya
P="".join(P)
keP="print"+"".join(P)
)Karena semua program di atas tidak memiliki output, inilah hasilnya untuk
f("1\r\n",1,["print","(",")","1"])
(token bukan bagian dari tantangan, tapi saya ingin menunjukkan apa yang terjadi):Nilai kembali adalah string
'print(1)'
.Akhirnya, hanya untuk bersenang-senang, inilah yang terjadi jika alfabetnya
string.printable
, yaituTautan pastebin dari semua program 0-2 char Python 3 yang valid
sumber