Ini terinspirasi oleh pertanyaan CS.SE yang sekarang dihapus .
Tugas
Diberikan dua string input A dan B yang tidak kosong, menampilkan jarak terkecil dari A ke palindrom yang berisi B sebagai substring. Jarak didefinisikan oleh jumlah penggantian karakter ( jarak Hamming ).
Batasan
- Input yang masuk akal: ada palindrome. Ini berarti | A | ≥ | B |.
- A dan B hanya berisi karakter ASCII yang lebih rendah, huruf kecil dan huruf besar berbeda (seperti semua karakter lainnya).
- Jika bahasa Anda tidak dapat berurusan dengan karakter ASCII, Anda dapat menggunakan integer (atau tipe data wajar lainnya) juga, dan Anda dapat memilih untuk membatasi rentang hingga 128 elemen.
- Anda dapat mengambil input dari stdin, argumen fungsi, argumen baris perintah, dll.
- Anda dapat memberikan hasilnya pada stdout, nilai pengembalian, dll.
- Anda tidak perlu memberikan palindrom yang berfungsi, jarak terkecil ke satu sudah cukup.
Contohnya
A B Output
thilloaoyreot hello 4 (thelloaolleht)
benjonson stack 9 (stackcats)
neversaynever! odd 9 (neveroddoreven)
ppcggcpp gg 0 (ppcggcpp)
stars tat 1 (stats)
Mencetak gol
Ini adalah kode golf, kode terpendek dalam byte yang menang.
code-golf
string
palindrome
Komunitas
sumber
sumber
Pyth, 45 byte
Cobalah online. Suite uji.
Saya masih belum benar-benar puas dengan bagaimana ini terjadi. Tapi setidaknya itu cukup sulit untuk dipahami tanpa penjelasan sekarang. (Sukses, kurasa?)
Penjelasan
Q
dan B sebagaiz
.m
..._BQ
Hitung yang berikut untuk A dan kebalikannya sebagaid
:m
…h-ldlz
Hitung yang berikut untuk semuak
dari 0 hinggalen(A) - len(B)
inklusif:+Bklz
Dapatkan pasangank, k + len(B)
.cd
Berpisahd
di indeks-indeks itu.X
…1z
Ganti bagian kedua (tengah) dengan B.Ks
Gabungkan potongan dan simpanK
. B sekarang dimasukkan pada posisik
di A atau kebalikannya.hc2
Pisahkan string yang dihasilkan menjadi dua dan simpan bagian pertama. Ini memberikan setengah dari string dengan karakter tengah yang mungkin.hc2PK
Hapus karakter terakhir dan lakukan split yang sama, menjaga potongan pertama. Ini memberikan setengah dari string tanpa karakter tengah yang memungkinkan.+
..._
Tambahkan kebalikan dari bagian yang lebih pendek ke bagian yang lebih panjang. Kami sekarang memiliki palindrome.s
Menggabungkan hasil untuk A dan kebalikannya.f}zT
Hapus semua string yang tidak mengandung B.m
Hitung yang berikut untuk semua string yang dihasilkand
:nVQd
Dapatkan ketidaksetaraan berpasangan dengan A. Ini memberi True untuk pasangan yang perlu diubah.s
Jumlahkan daftar. Ini memberi jarak Hamming.hS
Ambil hasil minimum.sumber
JavaScript (Firefox 30+),
152146 bytePendekatan brute force: menghasilkan setiap kemungkinan tumpang tindih A dan B, membuat masing-masing menjadi palindrom, menghitung jarak Hamming dari A, dan mengambil jarak terkecil yang dihasilkan.
Mungkin bisa bermain golf sedikit lebih ...
Cuplikan tes
Tampilkan cuplikan kode
sumber