La façon dont les golfeurs de code recherchent une bibliothèque

15

Défi:

J'ai des milliers de chansons dans ma collection de musique, et heureusement pour moi, mon lecteur préféré a une fonction de recherche. J'ai également une excellente mémoire - je me souviens du titre de chaque chanson de ma collection. Cependant, je suis très paresseux et je n'aime pas taper - chaque frappe supplémentaire est une corvée!

  • Quelle est la chaîne la plus courte que je dois rechercher pour isoler une chanson? Aidez-moi à mémoriser une liste de touches que je peux utiliser pour minimiser la saisie lors de la recherche!

C'est le code-golf , donc le code le plus court l'emporte.

Règles:

Étant donné une liste d'entrée de titres de chansons, générez une liste de clés de recherche soumises aux contraintes suivantes:

  1. Chaque titre de chanson doit avoir une clé de recherche.
  2. Le nombre total de caractères dans la liste de sortie doit être le plus petit possible.
  3. Mon lecteur de musique préféré est foobar2000 :
    • La fonction de recherche n'est pas sensible à la casse. ( appleest le même que aPpLE).
    • Chaque clé de recherche doit être constituée d'un ou plusieurs "mots", dans n'importe quel ordre, séparés par des espaces:
      • Chaque mot doit être une sous - chaîne du titre de chanson correspondant.
      • Si la même sous-chaîne est spécifiée plusieurs fois, il doit se produire autant de fois dans son titre de chanson correspondant.
      • Si une sous-chaîne elle-même contient un espace, cette sous-chaîne doit être entourée de guillemets.

Conseils:

  • Souvent, pour certains titres de chansons, il existe plusieurs clés de recherche répondant à la règle 2. Dans ce cas, n'importe quelle clé fera l'affaire, mais vous obtenez des points brownie pour toutes les répertorier.
  • Vous pouvez supposer que la liste de saisie ne comportera que des caractères ASCII, mais des points brownie seront attribués pour la compatibilité UTF-8.
  • La règle 3 était-elle difficile à suivre? Voici comment ça fonctionne:

Afficher l'extrait de code

Exemple:

Si ma collection de musique ne comprenait que deux albums, Michael Jackson's Off the Wall et Thriler :

Afficher l'extrait de code

Vous pouvez utiliser les listes ci-dessus pour tester votre programme. Voici la version brute de la deuxième 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
la source
1
Avez-vous un exemple qui nécessite plusieurs chaînes pour une clé?
Jonathan Allan
1
Et alors ["Wanta Be A Wanna B","Wanta Bea A Wanna B","Wanna Be A Wanna Bea"]?
Jonathan Allan
... mais que devraient-ils / pourraient-ils être si aucun espace n'est autorisé dans les sous-chaînes elles-mêmes - notez que tous les mots entiers entrent en collision.
Jonathan Allan
Pourquoi la version brute est-elle dans un spoiler?
Leaky Nun
1
En relation
Robert Fraser

Réponses:

4

Python 2, 556 octets

Essayez-le en ligne.

-10 octets, merci à @Riker, @ovs

Ça m'a pris quelques soirées pour que tout fonctionne.
Affiche le nom du morceau, le tableau des clés de recherche et la longueur des clés de recherche combinées (y compris les espaces et les guillemets)

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]

Quelques explications: 

T=len

Fonction len()utilisée très souvent ici, donc ce changement de nom économise des octets

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)

Évalue toutes les sous-chaînes possibles de longueur de chaîne n.
eval(...)crée la commande zip(s,s[1:],s[2:],...,s[n:])
Il crée des sous-chaînes de longueur à npartir de chaque index de ssi possible. Donc, s='budd'et n='2'cela produira 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

Filtrez pour vérifier si les touches fournies (K) correspondent à un nom de chanson unique.
re.sub est requis pour plusieurs clés identiques, comme ['nn', 'nn'] dans les exemples.

La fonction interne def R(r,t)est récursive pour créer toutes les combinaisons possibles de sous-chaîne, qui peuvent décrire le nom du morceau.
Chaque combinaison est comparée à la plus courte actuellement (s'il y en avait) à un nombre inférieur de combinaisons créées - si elle est plus grande, elle ne sera pas acceptée comme toutes ses dérivés.
La fonction utilise 2 variables pour suivre l'état: npour la longueur de la combinaison de touches la plus courte actuelle et ypour la combinaison elle-même

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

Ceci calcule la longueur de la combinaison de touches. ' '.joinajouter des espaces entre les clés et 2*sum(...)calcule le nombre de guillemets nécessaires pour les clés avec des espaces.

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

Utilise la première fonction lambda pour obtenir toutes les combinaisons de touches possibles (de toutes les longueurs possibles) pour la chaîne actuelle.

Deux pour que les cycles parcourent toutes les clés générées et les passent individuellement à la prochaine étape récursive. Placer la clé ( j) est nécessaire pour la chaîne de tranche correctement à la fin de celui - ci: r[j+T(u[i][j]):].
Slice fournit une chaîne qui a commencé à la fin de la clé actuelle, il n'y aura donc pas de chevauchement.
Si le lieu est inconnu, des clés égales gâcheraient tout. 

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

Beaucoup plus longtemps que juste y, mais les clés avec des espaces doivent être entourées de guillemets

Possum mort
la source
Ceci est incroyable. Vous êtes le premier à obtenir la bonne règle 3!
ayane
1
Soit dit en passant, vous devriez pouvoir raser deux octets en supprimant le 0,dans l'une de vos plages: u=[L(r,i)for i in range(0,T(r))]=> u=[L(r,i)for i in range(T(r))].
notjagan
1
Vous pourriez économiser quelques octets de plus: dans votre sortie, vous n'avez pas à afficher les chaînes d'entrée et la taille des chaînes de sortie.
ayane
@ 彩 音 M Merci! J'ai coupé ces quelques octets de la plage et de la sortie.
Dead Possum
1
S=map(str.lower,input())pour -5 octets
ovs