Cara pegolf kode mencari perpustakaan

15

Tantangan:

Saya memiliki ribuan lagu dalam koleksi musik saya, dan untungnya bagi saya, pemutar favorit saya memiliki fungsi pencarian. Saya juga memiliki ingatan yang luar biasa — saya dapat mengingat judul setiap lagu dalam koleksi saya. Namun, saya sangat malas dan tidak suka mengetik — setiap keystroke tambahan adalah tugas!

  • Apa string terpendek yang harus saya cari untuk mengisolasi satu lagu? Bantu saya menghafal daftar kunci yang bisa saya gunakan untuk meminimalkan pengetikan saat mencari!

Ini kode-golf , jadi kode terpendek menang.

Aturan:

Diberikan daftar input judul lagu, buat daftar kunci pencarian dengan batasan sebagai berikut:

  1. Setiap judul lagu harus memiliki kunci pencarian.
  2. Jumlah karakter dalam daftar output harus sesedikit mungkin.
  3. Pemutar musik favorit saya adalah foobar2000 :
    • Fungsi pencarian tidak peka huruf besar-kecil. ( applesama dengan aPpLE).
    • Setiap kunci pencarian harus terdiri dari satu atau lebih "kata", dalam urutan apa pun, dipisahkan oleh spasi:
      • Setiap kata harus menjadi substring dari judul lagu yang sesuai.
      • Jika substring yang sama ditentukan beberapa kali, maka harus terjadi beberapa kali dalam judul lagu yang sesuai.
      • Jika substring itu sendiri berisi spasi, maka substring itu harus dikelilingi dengan tanda kutip.

Petunjuk:

  • Seringkali, untuk beberapa judul lagu, ada beberapa kunci pencarian yang memenuhi aturan 2. Dalam kasus seperti itu, salah satu tombol akan berfungsi, tetapi Anda mendapatkan poin brownies untuk mendaftar semuanya.
  • Anda dapat berasumsi bahwa daftar input hanya akan karakter ASCII, tetapi poin brownies akan diberikan untuk kompatibilitas UTF-8.
  • Apakah Aturan 3 sulit diikuti? Begini cara kerjanya:

Tampilkan cuplikan kode

Contoh:

Jika koleksi musik saya hanya terdiri dari dua album, Michael's Off the Wall dan Thriler :

Tampilkan cuplikan kode

Anda dapat menggunakan daftar di atas untuk menguji program Anda. Ini adalah versi mentah dari daftar kedua: 

["Don't Stop 'Til You Get Enough","Rock with You","Working Day and Night","Get on the Floor","Off the Wall","Girlfriend","She's out of My Life","I Can't Help It","It's the Falling in Love","Burn This Disco Out","Wanna Be Startin' Somethin'","Baby Be Mine","The Girl Is Mine","Thriller","Beat It","Billie Jean","Human Nature","P.Y.T. (Pretty Young Thing)"]
code-golf string search optimized-output ayane
sumber
1
Apakah Anda memiliki contoh yang memerlukan beberapa string untuk kunci?
Jonathan Allan
1
Bagaimana dengan ["Wanta Be A Wanna B","Wanta Bea A Wanna B","Wanna Be A Wanna Bea"]?
Jonathan Allan
... tetapi apa yang harus mereka / bisa mereka jika tidak ada ruang yang diizinkan di substring sendiri - perhatikan bahwa semua kata bertabrakan.
Jonathan Allan
Mengapa versi mentah di spoiler?
Leaky Nun
1
Terkait
Robert Fraser

Jawaban:

4

Python 2, 556 byte

Cobalah online.

-10 byte, terima kasih kepada @Riker, @ovs

Butuh saya beberapa malam untuk membuat semuanya berfungsi.
Output nama lagu, array kunci pencarian dan panjang kunci pencarian digabungkan (termasuk spasi dan kutipan)

import re
S=map(str.lower,input())
T=len
for s in S:
 y=s;n=T(s)
 def R(r,t):
    global n,y
    l=T(' '.join(t))+2*sum(map(lambda x:' 'in x,t))
    if l>n:return
    if(lambda K:T([s for s in S if T(s)-T(reduce(lambda x,y:re.sub(re.escape(y),'',x,1),K,s))==T(''.join(K))])==1)(t)and l<n:y=t;n=l
    u=[(lambda s,n:n and[''.join(y) for y in eval('zip(s%s)'%(''.join(',s[%s:]'%-~x for x in range(n))))]or list(s))(r,i)for i in range(T(r))]
    for i in range(T(r)):
     for j in range(T(r)-i):R(r[j+T(u[i][j]):],t+[u[i][j]])
 R(s,[])
 print[' 'in x and'"%s"'%x or x for x in y]

Beberapa penjelasan: 

T=len

Fungsi yang len()sangat sering digunakan di sini, sehingga penggantian nama ini menghemat byte

L=lambda s,n:n and[''.join(y) for y in eval('zip(s%s)'%(''.join(',s[%s:]'%-~x for x in range(n))))]or list(s)

Mengevaluasi semua kemungkinan substring dari panjang string n.
eval(...)menciptakan perintah zip(s,s[1:],s[2:],...,s[n:])
Ini menciptakan substring panjang ndari setiap indeks sjika memungkinkan. Jadi untuk s='budd'dan n='2'itu akan menghasilkan bu, ud, dd

F=lambda K:len([s for s in S if len(s)-len(reduce(lambda x,y:re.sub(re.escape(y),'',x,1),K,s))==len(''.join(K))])==1

Saring untuk memeriksa apakah tombol yang disediakan (K) adalah untuk nama lagu yang unik.
re.sub diminta untuk beberapa kunci identik, seperti ['nn', 'nn'] dalam contoh.

Fungsi dalam def R(r,t)adalah fungsi rekursif untuk membuat semua kombinasi yang mungkin dari substring, yang dapat menggambarkan nama lagu.
Setiap kombinasi dibandingkan dengan yang terpendek saat ini (jika ada) dengan jumlah yang lebih rendah dari kombinasi yang dibuat - jika lebih besar, itu tidak akan diterima sebagai semua turunannya.
Fungsi menggunakan 2 variabel untuk melacak status: nuntuk panjang kombinasi tombol terpendek saat ini dan yuntuk kombinasi itu sendiri

l=T(' '.join(t))+2*sum(map(lambda x:' 'in x,t))

Ini menghitung panjang kombinasi tombol. ' '.jointambahkan spasi di antara kunci dan 2*sum(...)hitung jumlah kutipan yang dibutuhkan untuk kunci dengan spasi.

u=[L(r,i)for i in range(0,T(r))]

Menggunakan fungsi lambda pertama untuk mendapatkan semua kombinasi tombol yang mungkin (dari setiap panjang yang mungkin) untuk string saat ini.

Dua untuk siklus untuk melihat semua kunci yang dihasilkan dan meneruskannya secara individual ke langkah rekursif berikutnya. Tempat kunci ( j) diperlukan untuk benar slice string pada akhir itu: r[j+T(u[i][j]):].
Slice menyediakan string, yang dimulai saat kunci saat ini berakhir, sehingga tidak akan ada tumpang tindih.
Jika tempat tidak diketahui, kunci yang sama akan mengacaukan semuanya. 

[' 'in x and'"%s"'%x or x for x in y]

Jauh lebih lama dari sekadar y, tetapi kunci dengan spasi harus dikelilingi oleh tanda kutip

Possum Mati
sumber
Ini luar biasa. Anda yang pertama mendapatkan aturan 3 dengan benar!
ayane
1
Ngomong-ngomong, Anda harus dapat mencukur dua byte dengan menghapus 0,salah satu rentang Anda: u=[L(r,i)for i in range(0,T(r))]=> u=[L(r,i)for i in range(T(r))].
notjagan
1
Anda bisa menyimpan beberapa byte lagi: dalam output Anda, Anda tidak harus menunjukkan string input dan ukuran string output.
ayane
@ 彩 音 M Terima kasih! Saya telah memangkas beberapa byte ini dari range dan output.
Dead Possum
1
S=map(str.lower,input())untuk -5 byte
ovs