A maneira como o jogador de código procura uma biblioteca

15

Desafio:

Eu tenho milhares de músicas na minha coleção de músicas e, felizmente, meu player favorito tem uma função de pesquisa. Eu também tenho uma ótima memória - lembro o título de todas as músicas da minha coleção. No entanto, sou muito preguiçoso e não gosto de digitar - cada pressionamento de tecla extra é uma tarefa árdua!

  • Qual é a string mais curta que devo procurar para isolar uma música? Ajude-me a memorizar uma lista de teclas que posso usar para minimizar a digitação ao pesquisar!

Isso é código-golfe , então o código mais curto vence.

Regras:

Dada uma lista de entrada de títulos de músicas, gere uma lista de chaves de pesquisa sujeitas às seguintes restrições:

  1. Cada título da música deve ter uma tecla de pesquisa.
  2. O número total de caracteres na lista de saída deve ser o menor possível.
  3. Meu music player favorito é foobar2000 :
    • A função de pesquisa não diferencia maiúsculas de minúsculas. ( appleé o mesmo que aPpLE).
    • Cada chave de pesquisa deve consistir em uma ou mais "palavras", em qualquer ordem, separadas por espaços:
      • Cada palavra deve ser uma substring do título da música correspondente.
      • Se a mesma substring for especificada várias vezes, deverá ocorrer várias vezes no título da música correspondente.
      • Se uma subcadeia em si contiver um espaço, ela deverá estar entre aspas.

Dicas:

  • Geralmente, para alguns títulos de músicas, há várias chaves de pesquisa que cumprem a regra 2. Nesse caso, qualquer tecla serve, mas você obtém pontos brownie por listar todas elas.
  • Você pode supor que a lista de entrada terá apenas caracteres ASCII, mas os pontos brownie serão concedidos pela compatibilidade UTF-8.
  • A Regra 3 foi difícil de seguir? Veja como funciona:

Mostrar snippet de código

Exemplo:

Se minha coleção de músicas consistisse em apenas dois álbuns, Off the Wall and Thriler , de Michael Jackson :

Mostrar snippet de código

Você pode usar as listas acima para testar seu programa. Aqui está a versão bruta da 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
fonte
1
Você tem um exemplo que requer várias seqüências de caracteres para uma chave?
Jonathan Allan
1
Que tal ["Wanta Be A Wanna B","Wanta Bea A Wanna B","Wanna Be A Wanna Bea"]?
Jonathan Allan
... mas o que deveriam / deveriam ser se nenhum espaço fosse permitido nas próprias substrings - observe que todas as palavras inteiras colidem.
Jonathan Allan
Por que a versão bruta está em um spoiler?
Leaky Nun
1
Relacionado
Robert Fraser

Respostas:

4

Python 2, 556 bytes

Experimente online.

-10 bytes, graças a @Riker, @ovs

Levei duas noites para fazer tudo funcionar.
Produz o nome da música, o conjunto de chaves de pesquisa e o comprimento das chaves de pesquisa combinadas (incluindo espaços e aspas)

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]

Alguma explicação: 

T=len

Função len()usada com muita frequência aqui, portanto, essa renomeação salva 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)

Avalia todas as possíveis substrings do comprimento da string n.
eval(...)comando zip(s,s[1:],s[2:],...,s[n:])
create Cria substrings de comprimento nde todos os índices, sse possível. Então, para s='budd'e n='2'produzirá 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 se as teclas fornecidas (K) são para um nome de música exclusivo.
O re.sub é necessário para várias chaves idênticas, como ['nn', 'nn'] nos exemplos.

A função interna def R(r,t)é recursiva para criar todas as combinações possíveis de substring, que podem descrever o nome da música.
Cada combinação é comparada com a menor atualmente (se houver) ao menor número de combinações criadas - se for maior, não será aceita como todos os seus derivados.
A função usa 2 variáveis ​​para rastrear o estado: npara o comprimento da combinação de teclas mais curta atual ey para a própria combinação

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

Isso calcula o comprimento da combinação de teclas. ' '.joinadicione espaços entre as chaves e 2*sum(...)calcule o número de cotações necessárias para chaves com espaços.

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

Usa a primeira função lambda para obter todas as combinações de teclas possíveis (de todos os comprimentos possíveis) para a sequência atual.

Dois para ciclos para examinar todas as chaves geradas e passá-las individualmente para a próxima etapa recursiva. Lugar Key ( j) é necessária para corretamente corda fatia no final do mesmo: r[j+T(u[i][j]):].
O Slice fornece string, iniciada onde termina a chave atual, para que não haja sobreposições.
Se o lugar for desconhecido, chaves iguais estragariam tudo. 

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

Muito mais do que apenas y, mas as teclas com espaços devem estar entre aspas

Gambá morto
fonte
Isso é incrível. Você é o primeiro a acertar a regra 3!
Ayane # 4/17
1
A propósito, você deve conseguir cortar dois bytes removendo o 0,em um dos seus intervalos: u=[L(r,i)for i in range(0,T(r))]=> u=[L(r,i)for i in range(T(r))].
notjagan
1
Você pode salvar mais alguns bytes: na sua saída, não é necessário mostrar as seqüências de entrada e o tamanho das seqüências de saída.
Ayane # 4/17
@ M Obrigado! Eu aparei alguns bytes do intervalo e da saída.
Gambá morto
1
S=map(str.lower,input())para -5 bytes
ovs 8/17