Der Code-Golfer beim Durchsuchen einer Bibliothek

15

Herausforderung:

Ich habe Tausende von Songs in meiner Musiksammlung und zum Glück hat mein Lieblingsspieler eine Suchfunktion. Ich habe auch ein tolles Gedächtnis - ich kann mich an den Titel jedes Songs in meiner Sammlung erinnern. Ich bin jedoch sehr faul und tippe nicht gerne - jeder zusätzliche Tastendruck ist eine lästige Pflicht!

  • Was ist die kürzeste Zeichenfolge, nach der ich suchen muss, um ein Lied zu isolieren? Hilf mir, eine Liste mit Schlüsseln zu speichern, mit denen ich das Tippen bei der Suche minimieren kann!

Das ist Code-Golf , also gewinnt der kürzeste Code.

Regeln:

Erstellen Sie anhand einer eingegebenen Liste mit Songtiteln eine Liste mit Suchschlüsseln, die den folgenden Einschränkungen unterliegen:

  1. Jeder Songtitel sollte einen Suchschlüssel haben.
  2. Die Gesamtzahl der Zeichen in der Ausgabeliste muss so gering wie möglich sein.
  3. Mein Lieblings-Musikplayer ist foobar2000 :
    • Die Suchfunktion unterscheidet nicht zwischen Groß- und Kleinschreibung. ( appleist dasselbe wie aPpLE).
    • Jeder Suchbegriff muss aus einem oder mehreren "Wörtern" in beliebiger Reihenfolge bestehen, die durch Leerzeichen getrennt sind:
      • Jedes Wort muss eine Teilzeichenfolge des entsprechenden Songtitels sein .
      • Wenn derselbe Teilstring mehrmals angegeben wird, muss er im entsprechenden Songtitel so oft vorkommen.
      • Wenn eine Teilzeichenfolge selbst ein Leerzeichen enthält, muss diese Teilzeichenfolge in Anführungszeichen gesetzt werden.

Hinweise:

  • Oft gibt es für einige Songtitel mehrere Suchschlüssel, die Regel 2 erfüllen. In einem solchen Fall reicht jeder Schlüssel aus, aber Sie erhalten Brownie-Punkte, wenn Sie alle auflisten.
  • Sie können davon ausgehen, dass die Eingabeliste nur ASCII-Zeichen enthält, für die UTF-8-Kompatibilität werden jedoch Brownie-Punkte vergeben.
  • War es schwierig, Regel 3 zu befolgen? So funktioniert das:

Code-Snippet anzeigen

Beispiel:

Wenn meine Musiksammlung nur aus zwei Alben bestand, Michael Jacksons Off the Wall und Thriler :

Code-Snippet anzeigen

Sie können die obigen Listen verwenden, um Ihr Programm zu testen. Hier ist die Rohversion der zweiten Liste: 

["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
quelle
1
Haben Sie ein Beispiel, für das mehrere Zeichenfolgen für einen Schlüssel erforderlich sind?
Jonathan Allan
1
Wie wäre es ["Wanta Be A Wanna B","Wanta Bea A Wanna B","Wanna Be A Wanna Bea"]?
Jonathan Allan
... aber was sollen / könnten sie sein, wenn keine Leerzeichen in den Unterzeichenfolgen selbst zulässig sind - beachten Sie, dass alle ganzen Wörter kollidieren.
Jonathan Allan
Warum ist die Rohversion in einem Spoiler?
Undichte Nonne
1
Related
Robert Fraser

Antworten:

4

Python 2, 556 Bytes

Probieren Sie es online aus.

-10 Bytes, danke an @Riker, @ovs

Ich brauchte ein paar Abende, um alles zum Laufen zu bringen.
Gibt den Namen des Songs, eine Reihe von Suchschlüsseln und die Länge der Suchschlüssel zusammen aus (einschließlich Leerzeichen und Anführungszeichen)

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]

Einige Erklärungen: 

T=len

Funktion len()wird hier sehr oft verwendet, so dass durch das Umbenennen Bytes gespart werden

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)

Wertet alle möglichen Teilzeichenfolgen mit der Länge n aus.
eval(...)Erzeugt einen Befehl. zip(s,s[1:],s[2:],...,s[n:])
Erzeugt naus jedem Index, swenn möglich, Teilfolgen mit einer Länge . Also für s='budd'und n='2'es wird bu, ud, dd produzieren

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

Filtern Sie, um zu überprüfen, ob die angegebenen Tasten (K) für einen eindeutigen Songtitel stehen.
resub wird für mehrere identische Schlüssel benötigt, z. B. ['nn', 'nn'] in den Beispielen.

Die innere Funktion def R(r,t)ist eine rekursive Funktion , um alle möglichen Kombinationen von Teilzeichenfolgen zu erstellen, die den Songtitel beschreiben können.
Jede Kombination wird mit der aktuell kürzesten (sofern vorhanden) verglichen, um die Anzahl der erstellten Kombinationen zu verringern. Wenn sie größer ist, werden sie nicht als alle Ableitungen akzeptiert.
Die Funktion verwendet 2 Variablen, um den Status zu verfolgen: nfür die Länge der aktuell kürzesten Tastenkombination und yfür die Kombination selbst

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

Dies berechnet die Länge der Tastenkombination. ' '.joinFügen Sie Leerzeichen zwischen die Schlüssel ein und 2*sum(...)berechnen Sie die Anzahl der erforderlichen Anführungszeichen für Schlüssel mit Leerzeichen.

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

Verwendet die erste Lambda-Funktion, um alle möglichen Tastenkombinationen (von jeder möglichen Länge) für die aktuelle Zeichenfolge abzurufen.

Zwei for-Zyklen, um alle generierten Schlüssel zu durchsuchen und einzeln an den nächsten rekursiven Schritt weiterzuleiten. Key Ort ( j) am Ende der es richtig Scheibe String benötigt: r[j+T(u[i][j]):].
Slice enthält eine Zeichenfolge, die dort beginnt, wo der aktuelle Schlüssel endet, sodass keine Überlappungen auftreten.
Wenn der Ort unbekannt ist, würden gleiche Schlüssel alles durcheinander bringen. 

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

Viel länger als nur y, aber Schlüssel mit Leerzeichen sollten in Anführungszeichen gesetzt werden

Totes Opossum
quelle
Das ist großartig. Du bist der erste, der Regel 3 richtig macht!
Ayane
1
Übrigens sollten Sie in der Lage sein, zwei Bytes zu sparen, indem Sie das 0,in einem Ihrer Bereiche entfernen : u=[L(r,i)for i in range(0,T(r))]=> u=[L(r,i)for i in range(T(r))].
Notjagan
1
Sie könnten noch ein paar Bytes einsparen: In Ihrer Ausgabe müssen Sie nicht die Eingabezeichenfolgen und die Größe der Ausgabezeichenfolgen anzeigen.
Ayane
@ 彩 彩 M Danke! Ich habe diese paar Bytes aus dem Bereich und der Ausgabe gekürzt.
Dead Possum
1
S=map(str.lower,input())für -5 Bytes
Ovs