Tugas Anda untuk memecahkan masalah SLCSC, yang terdiri dari menemukan kode sesingkat mungkin untuk menyelesaikan masalah Suburensi Umum Terpanjang .
Sebuah solusi yang valid untuk masalah LCS untuk dua atau lebih string S 1 , ... S n adalah string T panjang maksimal sehingga karakter dari T muncul di semua S i , dalam urutan yang sama seperti pada T .
Perhatikan bahwa T tidak harus menjadi sub string dari S i .
Contoh
Senar axbycz
dan xaybzc
memiliki 8 urutan umum panjang 3:
abc abz ayc ayz xbc xbz xyc xyz
Semua ini akan menjadi solusi yang valid untuk masalah LCS.
Detail
Tulis program atau fungsi yang memecahkan masalah LCS, seperti dijelaskan di atas, mematuhi aturan berikut:
Input akan terdiri dari dua string atau lebih yang hanya berisi huruf kecil.
Anda dapat membaca string tersebut sebagai array string atau string tunggal dengan pembatas pilihan Anda.
Kode Anda harus menampilkan salah satu dari solusi yang mungkin untuk masalah, secara opsional diikuti oleh umpan baris atau dikelilingi oleh tanda kutip.
Anda dapat mengasumsikan bahwa string lebih pendek dari 1000 karakter dan paling banyak 20 string.
Dalam batas-batas ini, kode Anda harus berfungsi seperti yang diharapkan dalam teori (diberikan waktu dan memori tidak terbatas).
Kode Anda harus menyelesaikan kasus uji gabungan bagian berikutnya dalam waktu kurang dari satu jam di komputer saya (Intel Core i7-3770, 16 GiB RAM).
Pendekatan yang hanya mengulangi semua kemungkinan berikutnya tidak akan memenuhi batas waktu.
Menggunakan bawaan yang meremehkan tugas ini, seperti
LongestCommonSequence
, tidak diizinkan.
Aturan standar kode-golf berlaku.
Uji kasus
a
ab
Keluaran: a
aaaaxbbbb
bbbbxcccc
ccccxaaaa
Keluaran: x
hxbecqibzpyqhosszypghkdddykjfjcajnwfmtfhqcpavqrtoipocijrmqpgzoufkjkyurczxuhkcpehbhpsuieqgjcepuhbpronmlrcgvipvibhuyqndbjbrrzpqbdegmqgjliclcgahxoouqxqpujsyfwbdthteidvigudsuoznykkzskspjufgkhaxorbrdvgodlb
qnnprxqpnafnhekcxljyysobbpyhynvolgtrntqtjpxpchqwgtkpxxvmwwcohxplsailheuzhkbtayvmxnttycdkbdvryjkfhshulptkuarqwuidrnjsydftsyhuueebnrjvkfvhqmyrclehcwethsqzcyfvyohzskvgttggndmdvdgollryqoswviqurrqhiqrqtyrl
Output: hxbbpyhogntqppcqgkxchpsieuhbncvpuqndbjqmclchqyfttdvgoysuhrrl
atau urutan umum lainnya dengan panjang yang sama
riikscwpvsbxrvkpymvbbpmwclizxlhihiubycxmxwviuajdzoonjpkgiuiulbjdpkztsqznhbjhymwzkutmkkkhirryabricvhb
jnrzutfnbqhbaueicsvltalvqoorafnadevojjcsnlftoskhntashydksoheydbeuwlswdzivxnvcrxbgxmquvdnfairsppodznm
kzimnldhqklxyezcuyjaiasaeslicegmnwfavllanoolkhvqkjdvxrsjapqqwnrplcwqginwinktxnkfcuuvoyntrqwwucarfvjg
Output: icsvllvjnlktywuar
atau urutan umum lainnya dengan panjang yang sama
rblartqkfggrjpiipuzzypkycnyckkcqceeujiyy
yfpnedyjtiwrhyuktripdwyvgkblzodeufkelhub
ywcyboxwqkibwvredkrbdsyudkulpvmhixeqxynh
bnxwahbzhwjxkotnvbxrojkkldtsodtjmvdrmbgr
Output: krkk
atau urutan umum lainnya dengan panjang yang sama
bwfscmotshoczmduwaev
coywaaizdaxjovipsmeh
dobzcpoiedenzlfdjpiu
bbhfeqscvvbwkuoxdoge
drqrzwbcpcsvneodelja
Output: code
atau urutan umum lainnya dengan panjang yang sama
nqrualgoedlf
jgqorzglfnpa
fgttvnogldfx
pgostsulyfug
sgnhoyjlnfvr
wdttgkolfkbt
Output: golf
atau urutan umum lainnya dengan panjang yang sama
epopyfuhgowedpiqpgfj
ddxyestqynpwmytxhozm
ptubgzyqqksieoovuezv
tovotqmnhgzttfpywjgr
aomvytkgaijlgqzkljls
vzvxpaixrnprxvenbbuo
syfuwxlpcyontqlmfvib
arxleuomstkjegpduwcx
xgqrxaopouvkvwgbzewn
yggunddigctgpnuztzai
izroomywwztdymqszsuo
kiawjnxjncdtufhkrjsp
Output: string kosong
sumber
Jawaban:
CJam, 31
Cobalah online
9 byte golf berkat Dennis!
Penjelasan:
Algoritma ini mencoba setiap karakter yang mungkin untuk posisi pertama selanjutnya, mengganti setiap string dengan substring setelah kemunculan pertama karakter itu, dan kemudian menyebut dirinya secara rekursif (dengan memoisasi).
sumber
Python -
665644Tingkat lekukan:
Kode mendefinisikan fungsi
o
, yang mengambil daftar string sebagai argumen dan mengembalikan salah satu LCS untuk string.Kode uji:
Waktu yang diperlukan untuk menjalankan tes di komputer saya:
sumber
(n+1)
, Anda dapat menggantinya dengan-~n
untuk menyimpan 2 byte dalam setiap kasus. Juga, di mana saja Anda menggunakanmap
denganlambda
, pertimbangkan menggunakan pemahaman daftar sebagai gantinya. Misalnya,map(lambda x:x-1,z)
dapat dipersingkat tiga byte dengan mengubahnya menjadi[~-x for x in z]
.r,x=r+(j+1)*x,x*(l[k]+1)
dapat disingkat menjadir+=(j+1)*x;x*=(l[k]+1)
. Juga, Anda tidak perluu=...
karenau
hanya digunakan di satu tempat. Ganti saja kode itu dengan surat ituu
.Pyth,
59585535 bytePotong 20 byte kekalahan berkat @isaacg!
Versi 55 byte:
Potong 3 byte dengan mengubah
.U@bZ
ke@F
(operator lipat).Versi 58 byte:
Potong byte dengan mengubah format kondisional boolean.
Versi 59 byte:
Ini sulit! Python terus melakukan segmentasi! Cukup yakin itu semacam bug, tapi saya tidak bisa mendapatkan test case minimal. Baiklah.
Saya mendasarkan algoritma dari yang satu ini . Yang baik-baik saja, kecuali bahwa yang dirancang hanya untuk dua string. Saya harus men-tweak sedikit untuk membuatnya bekerja lebih banyak. Kemudian, test case terakhir terlalu lama, jadi saya harus menambahkan cek tambahan untuk keluar dari rekursi jika tidak ada karakter yang lebih umum.
Ini cukup lambat, tetapi harus memakan waktu kurang dari satu jam (semoga). Saya sedang menguji Core i3 saya dengan 6 GB RAM, jadi Core i7 16-GB Anda harus menerobos ini. :)
Saya juga memanfaatkan fungsi memo-otomatis Pyth untuk membuatnya sedikit lebih cepat.
EDIT : @Dennis bilang sudah lewat!
Untuk mengujinya, tambahkan baris berikut:
dan berikan daftar string melalui input standar (misalnya
['a', 'ab']
).Penjelasan untuk versi 35 byte:
WIP.
Penjelasan untuk versi 55 byte:
sumber
C,
618564 byteDan di sini terurai, untuk "keterbacaan":
Hadirin sekalian, saya telah melakukan kesalahan yang mengerikan. Itu digunakan untuk menjadi cantik ... Dan goto-kurang ... Setidaknya sekarang itu cepat .
Kami mendefinisikan fungsi rekursif
L
yang mengambil input arrays
array karakter dan jumlahn
string. Fungsi mengeluarkan string yang dihasilkan ke stdout, dan secara tidak sengaja mengembalikan ukuran karakter string itu.Pendekatan
Meskipun kodenya berbelit-belit, strategi di sini tidak terlalu rumit. Kita mulai dengan algoritma rekursif yang agak naif, yang akan saya uraikan dengan pseudocode:
Sekarang, algoritma ini sendiri cukup mengerikan (tapi bisa muat sekitar ~ 230 byte, saya temukan). Ini bukan bagaimana seseorang mendapatkan hasil yang cepat. Algoritma ini berskala sangat buruk dengan panjang string. Algoritma ini , bagaimanapun, skala cukup baik dengan jumlah string yang lebih besar. Kasing terakhir akan dipecahkan secara instan, karena tidak ada string yang
s
memiliki karakter yangc
sama. Ada dua trik utama yang saya terapkan di atas yang menghasilkan peningkatan kecepatan luar biasa:Di setiap panggilan
L
, periksa apakah kami telah diberi input yang sama sebelumnya. Karena dalam praktiknya informasi diteruskan melalui pointer ke set string yang sama, kita tidak benar - benar harus membandingkan string, hanya lokasi, yang bagus. Jika kami menemukan bahwa kami telah mendapatkan informasi ini sebelumnya, tidak perlu menjalankan perhitungan (sebagian besar waktu, tetapi mendapatkan output membuat ini sedikit lebih rumit) dan kami bisa lolos hanya dengan mengembalikan panjangnya. Jika kami tidak menemukan kecocokan, simpan rangkaian input / output ini untuk dibandingkan dengan panggilan berikutnya. Dalam kode C,for
loop kedua mencoba menemukan kecocokan dengan input. Pointer input yang diketahui disimpanR
, dan nilai output karakter dan panjang yang sesuai disimpanA
. Paket ini memiliki efek drastis pada runtime, terutama dengan string yang lebih panjang.Setiap kali kita menemukan lokasi dari
c
dalams
, ada kesempatan kita tahu langsung dari kelelawar bahwa apa yang kita temukan adalah tidak optimal. Jika setiap lokasic
muncul setelah beberapa lokasi diketahui dari surat lain, kami secara otomatis tahu bahwa inic
tidak mengarah ke substring yang optimal, karena Anda dapat memasukkan satu huruf lagi di dalamnya. Ini berarti bahwa untuk biaya yang kecil, kami berpotensi menghapus beberapa ratus panggilanL
untuk string besar. Dalam kode C di atas,y
adalah set bendera jika kita secara otomatis tahu bahwa karakter ini mengarah ke string suboptimal, danz
merupakan set bendera jika kita menemukan karakter yang secara eksklusif memiliki penampilan lebih awal daripada karakter lain yang dikenal. Penampilan karakter paling awal saat ini disimpan dix
. Implementasi saat ini dari ide ini agak berantakan, tetapi kinerja hampir dua kali lipat dalam banyak hal.Dengan dua ide ini, apa yang tidak selesai dalam satu jam sekarang membutuhkan waktu sekitar 0,015 detik.
Mungkin ada banyak trik kecil yang dapat mempercepat kinerja, tetapi pada titik ini saya mulai khawatir tentang kemampuan saya untuk bermain golf semuanya. Saya masih belum puas dengan golf, jadi saya akan kembali lagi nanti!
Pengaturan waktu
Inilah beberapa kode pengujian, yang saya undang untuk Anda coba secara online :
Saya menjalankan test case OP pada laptop yang dilengkapi dengan chip Intel Core i7 1,7 GHz, dengan pengaturan optimalisasi
-Ofast
. Simulasi melaporkan puncak 712KB diperlukan. Berikut ini contoh proses dari setiap kasus uji, dengan timing:Dalam bermain golf, saya mencapai performa yang cukup signifikan, dan karena orang-orang sepertinya menyukai kecepatan kasar (0,013624 detik untuk menyelesaikan semua test case digabungkan) dari solusi 618-byte saya sebelumnya, saya akan meninggalkannya di sini untuk referensi:
Algoritme itu sendiri tidak berubah, tetapi kode baru bergantung pada divisi dan beberapa operasi bitwise rumit yang akhirnya memperlambat semuanya.
sumber
best_found
? Itu hanya disebutkan dua kali, satu kali ketika digunakan dalam kondisi, dan yang lainnya ketika diatur ulang.best_found
diatur kebest_length + current_depth
. Anda mungkin harus menyebutkan itu dalam penjelasannya!best_found
adalah bilangan bulat global yang menjelaskan panjang substring umum terpanjang yang ditemukan pada titik tertentu dalam eksekusi. Saya akan menjelaskannya!Python 2, 285
Kode:
Pemakaian:
Penjelasan:
Ini adalah fungsi rekursif.
s
adalah karakter yang kami cari.a
berisi daftar string yang diiris setelahnyas
.b
mengandung daftar string yang belum pernah ditemukan.f
mengembalikan string umum terpanjang.Kondisi pertama memeriksa apakah kami sudah selesai melewati semua string. jika demikian, artinya
s
adalah karakter yang umum, dan ia kembalis
dan mencari karakter yang lebih umum.Kondisi kedua memeriksa jika kita tidak mulai melalui string apa pun, artinya kita bahkan tidak memiliki karakter (
a==[]
sama dengans==''
). jika demikian kita periksa setiap karakter dari string pertama dib
.Baris terakhir memindahkan string pertama
b
kea
, dengan menemukan setiap kemunculans
di string ini.Pada panggilan pertama,
s
harus string kosong.a
harus daftar kosong danb
harus berisi semua string.sumber
f(b,s='',a=[])
.