La forma de codificar golfistas de buscar en una biblioteca

15

Desafío:

Tengo miles de canciones en mi colección de música y, por suerte, mi reproductor favorito tiene una función de búsqueda. También tengo un gran recuerdo: puedo recordar el título de cada canción de mi colección. Sin embargo, soy muy vago y no me gusta escribir, ¡cada pulsación de tecla adicional es una tarea!

  • ¿Cuál es la cadena más corta que debo buscar para aislar una canción? ¡Ayúdame a memorizar una lista de teclas que puedo usar para minimizar la escritura al buscar!

Este es el código de golf , por lo que gana el código más corto.

Reglas:

Dada una lista de entrada de títulos de canciones, genere una lista de claves de búsqueda sujetas a las siguientes restricciones:

  1. El título de cada canción debe tener una clave de búsqueda.
  2. El número total de caracteres en la lista de salida debe ser el menor posible.
  3. Mi reproductor de música favorito es foobar2000 :
    • La función de búsqueda no distingue entre mayúsculas y minúsculas. ( applees lo mismo que aPpLE)
    • Cada clave de búsqueda debe constar de una o más "palabras", en cualquier orden, separadas por espacios:
      • Cada palabra debe ser una subcadena del título de la canción correspondiente.
      • Si la misma subcadena se especifica varias veces, entonces debe ocurrir tantas veces en el título de la canción correspondiente.
      • Si una subcadena en sí contiene un espacio, entonces esa subcadena debe estar entre comillas.

Consejos:

  • A menudo, para algunos títulos de canciones, hay varias claves de búsqueda que cumplen con la regla 2. En tal caso, cualquier clave servirá, pero obtienes puntos de brownie por enumerarlas todas.
  • Puede suponer que la lista de entrada solo tendrá caracteres ASCII, pero se otorgarán puntos brownie por compatibilidad con UTF-8.
  • ¿Fue difícil seguir la Regla 3? Así es como funciona:

Mostrar fragmento de código

Ejemplo:

Si mi colección de música consistiera solo en dos álbumes, Off the Wall y Thriler de Michael Jackson :

Mostrar fragmento de código

Puede usar las listas anteriores para probar su programa. Aquí está la versión en bruto de la segunda lista: 

["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
fuente
1
¿Tiene un ejemplo que requiere múltiples cadenas para una clave?
Jonathan Allan
1
¿Qué tal ["Wanta Be A Wanna B","Wanta Bea A Wanna B","Wanna Be A Wanna Bea"]?
Jonathan Allan
... pero qué deberían ser / podrían ser si no se permiten espacios en las propias subcadenas: tenga en cuenta que todas las palabras completas colisionan.
Jonathan Allan
¿Por qué la versión en bruto está en un spoiler?
Leaky Nun
1
Relacionado
Robert Fraser

Respuestas:

4

Python 2, 556 bytes

Pruébalo en línea.

-10 bytes, gracias a @Riker, @ovs

Me llevó un par de noches hacer que todo funcionara.
Muestra el nombre de la canción, la matriz de teclas de búsqueda y la longitud de las teclas de búsqueda combinadas (incluidos espacios y comillas)

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]

Alguna explicación: 

T=len

La función se len()usa muy a menudo aquí, por lo que este cambio de nombre ahorra bytes

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)

Evalúa todas las subcadenas posibles de la longitud de la cadena n.
eval(...)crea comando zip(s,s[1:],s[2:],...,s[n:])
Crea subcadenas de longitud nde cada índice de ssi es posible. Entonces para s='budd'y n='2'producirá 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

Filtre para verificar si las teclas provistas (K) son para un nombre de canción único.
se solicita re.sub para varias claves idénticas, como ['nn', 'nn'] en los ejemplos.

La función interna def R(r,t)es recursiva para crear todas las combinaciones posibles de subcadenas, que pueden describir el nombre de la canción.
Cada combinación se compara con la más corta actualmente (si hubiera alguna) para reducir el número de combinaciones creadas; si es más grande, no se aceptará como todas sus derivadas.
La función utiliza 2 variables para rastrear el estado: npara la longitud de la combinación de teclas más corta actual y ypara la combinación misma

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

Esto calcula la longitud de la combinación de teclas. ' '.joinagrega espacios entre claves y 2*sum(...)calcula el número de comillas necesarias para claves con espacios.

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

Utiliza la primera función lambda para obtener todas las combinaciones de teclas posibles (de cada longitud posible) para la cadena actual.

Dos ciclos para ver todas las claves generadas y pasarlas individualmente al siguiente paso recursivo. Lugar clave ( jse necesita) para encadenar rebanada correctamente al final de la misma: r[j+T(u[i][j]):].
Slice proporciona una cadena, que comenzó donde termina la clave actual, por lo que no habrá superposiciones.
Si se desconoce el lugar, las teclas iguales estropearían todo. 

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

Mucho más que solo y, pero las teclas con espacios deben estar entre comillas

Zarigüeya muerta
fuente
Esto es increíble. ¡Eres el primero en acertar con la regla 3!
ayane
1
Por cierto, deberías poder eliminar dos bytes eliminando 0,uno de tus rangos: u=[L(r,i)for i in range(0,T(r))]=> u=[L(r,i)for i in range(T(r))].
notjagan
1
Podría guardar algunos bytes más: en su salida, no tiene que mostrar las cadenas de entrada y el tamaño de las cadenas de salida.
ayane
@ 彩 音 M ¡Gracias! He recortado estos pocos bytes del rango y la salida.
Dead Possum
1
S=map(str.lower,input())para -5 bytes
ovs