pengantar
Dalam tantangan ini, tugas Anda adalah menemukan string yang disamaratakan secara umum. Selanjutnya tidak selalu berdekatan, dan mereka juga dapat "membungkus" string, melewati ujungnya dan mulai lagi dari awal. Anda akan ingin meminimalkan jumlah wraps.
Lebih formal, biarkan u
dan v
menjadi dua string, dan k ≥ 0
bilangan bulat. Kami mengatakan bahwa u
ini adalah proses k
pembatalan awal v
, jika ada indeks yang berbeda sehingga , dan sebagian besar indeks memuaskan . Ini berarti bahwa dapat ditemukan di dalam dengan pergi dari kiri ke kanan, memilih beberapa karakter di jalan, dan membungkus sekitar waktu paling banyak (sama, melakukan paling banyak menyapu ). Perhatikan bahwa tidak ada karakter yang dapat dipilih lebih dari sekali, bahkan setelah selesai, dan bahwa -menggulung tulisan adalah persis biasa yang kita semua kenal.i1, i2, ..., ilen(u)
u == v[i1] v[i2] ... v[ilen(u)]
k
ij
ij > ij+1
u
v
k
k+1
v
0
Tugas
Input Anda adalah dua string alfanumerik yang tidak kosong u
dan v
, dan output Anda adalah bilangan bulat terkecil k
sehingga u
merupakan akhir proses k
pembungkus v
. Jika tidak k
ada, output akan menjadi -1
.
Contoh
Pertimbangkan input u := xyzyxzzxyx
dan v := yxzzazzyxxxyz
. Jika kita mulai mencari karakter u
dalam v
dengan cara serakah, kita akan membungkus sekitar 3 kali:
yxzzazzyxxxyz
>─x─────y────z┐
┌─────────────┘
└y───────x────┐
┌─────────────┘
└──zz─────x─y─┐
┌─────────────┘
└──────────x──>
Jadi output yang benar adalah paling banyak 3. Perhatikan bagaimana karakter paling kiri x
dipilih sekali, dan kemudian diabaikan pada sapuan kedua, karena tidak dapat digunakan kembali. Namun, ada metode yang lebih pendek dengan hanya 2 bungkus:
yxzzazzyxxxyz
>──────────xyz┐
┌─────────────┘
└yxzz────x────┐
┌─────────────┘
└───────y─x───>
Ternyata satu bungkus-sekitar (yaitu, dua sapuan) tidak cukup, jadi output yang benar adalah 2
.
Aturan dan Bonus
Anda dapat menulis fungsi atau program lengkap, dan Anda juga dapat mengubah urutan input jika diperlukan. Hitungan byte terendah menang, dan celah standar tidak diizinkan.
Ada bonus -10% untuk menghitung semua kasus uji dalam waktu kurang dari 10 detik. Saya akan menguji kasus yang tidak jelas pada mesin saya; implementasi referensi saya di Python membutuhkan waktu sekitar 0,6 detik. Saya memiliki laptop 7 tahun dengan CPU dual core 1,86 GHz, yang mungkin perlu Anda pertimbangkan.
Uji Kasus
"me" "moe" -> 0
"meet" "metro" -> -1
"ababa" "abaab" -> 1
"abaab" "baabaa" -> 1
"1c1C1C2B" "1111CCCcB2" -> 3
"reverse" "reserved" -> 2
"abcdefg" "gfedcba" -> 6
"xyzyxzzxyx" "yxzzazzyxxxyz" -> 2
"aasdffdaasdf" "asdfddasdfsdaafsds" -> 2
sumber
x
digunakan dalam tiga sapuan berbeda. Ini hanya bisa digunakan sekali.Jawaban:
Pyth, 34 byte
Ini mendefinisikan fungsi
g
, yang mengambil dua string sebagai parameter. Cobalah secara online: Pyth Compiler / ExecutorKode ini sangat tidak efisien. Ini memiliki kompleksitas waktu dan memori
len(v)!/(len(v)-len(u))!
. Itu tidak dapat menyelesaikan kasus uji yang lebih lama dalam waktu kurang dari 10 detik. (Ini juga akan crash sangat mungkin, karena akan kehabisan memori.)sumber
Haskell, 160 * 0,9 = 144 byte
Waktu untuk semua kasus uji (catatan: argumen dibalik):
Cara kerjanya (versi pendek): brute force sederhana yang mengambil minimum menggunakan karakter yang cocok dan melewatkannya. Saya menghentikan pencarian ketika selesai (mengembalikan jumlah siklus) atau ketika bersepeda lebih dari minimum sejauh ini (mengembalikan -1).
Menyimpan banyak byte dibandingkan dengan versi pertama saya, terutama karena saya beralih dari program lengkap ke fungsi.
Dengan beberapa komentar dan jarak yang tepat, golf Haskell cukup mudah dibaca:
Untuk referensi: versi lama, program lengkap, 187 byte
sumber
JavaScript (ES6) 174 (193 - 10%)
Pencarian rekursif, seperti jawaban @ nimi, menjaga min wraps. Ruang solusi besar (di atas semua untuk contoh terakhir) tetapi memotong pencarian di min saat ini ditemukan membuat waktu tetap rendah. Sunting 1 Tambahkan test case yang hilang, disingkat sedikit. Edit 2 Tidak perlu melewati parameter, itu diperbaiki
Tidak disatukan
Uji di Firefox / konsol FireBug
Output (baris terakhir adalah waktu eksekusi dalam ms)
sumber