Код-гольфист способ поиска в библиотеке

15

Вызов:

У меня есть тысячи песен в моей музыкальной коллекции, и, к счастью для меня, у моего любимого плеера есть функция поиска. У меня также прекрасная память - я помню название каждой песни в моей коллекции. Тем не менее, я очень ленивый и не люблю печатать - каждое дополнительное нажатие - это рутина!

  • Какую самую короткую строку я должен искать, чтобы выделить одну песню? Помогите мне запомнить список клавиш, которые я могу использовать, чтобы минимизировать ввод при поиске!

Это код-гольф , поэтому выигрывает самый короткий код.

Правила:

С учетом входного списка названий песен сгенерируйте список ключей поиска с учетом следующих ограничений:

  1. Каждое название песни должно иметь поисковый ключ.
  2. Общее количество символов в списке вывода должно быть как можно меньше.
  3. Мой любимый музыкальный проигрыватель - foobar2000 :
    • Функция поиска не чувствительна к регистру. (так appleже, как aPpLE).
    • Каждый ключ поиска должен состоять из одного или нескольких «слов» в любом порядке, разделенных пробелами:
      • Каждое слово должно быть подстрокой соответствующего названия песни.
      • Если одна и та же подстрока указана несколько раз, то это должно происходить столько раз в соответствующем названии песни.
      • Если подстрока сама содержит пробел, то эта подстрока должна быть заключена в кавычки.

подсказки:

  • Зачастую для некоторых названий песен существует несколько ключей поиска, соответствующих правилу 2. В таком случае подойдет любой один ключ, но вы получаете баллы за перечисление их всех.
  • Вы можете предположить, что в списке ввода будут только символы ASCII, но за совместимость с UTF-8 будут начислены баллы.
  • Было ли трудно следовать правилу 3? Вот как это работает:

Показать фрагмент кода

Пример:

Если бы моя музыкальная коллекция состояла только из двух альбомов, Майкла Джексона Off the Wall и Thriler :

Показать фрагмент кода

Вы можете использовать списки выше для проверки вашей программы. Вот сырая версия второго списка: 

["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 Аяне
источник
1
У вас есть пример, который требует несколько строк для ключа?
Джонатан Аллан
1
Как насчет ["Wanta Be A Wanna B","Wanta Bea A Wanna B","Wanna Be A Wanna Bea"]?
Джонатан Аллан
... но какими они / могут быть, если в самих подстроках не допускается пробелов - обратите внимание, что все целые слова сталкиваются.
Джонатан Аллан
Почему сырая версия в спойлере?
Утренняя монахиня
1
Связанные
Роберт Фрейзер

Ответы:

4

Python 2, 556 байт

Попробуйте онлайн.

-10 байт, благодаря @Riker, @ovs

Взял у меня пару вечеров, чтобы все заработало.
Выводит название песни, массив ключей поиска и длину ключей поиска вместе (включая пробелы и кавычки)

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]

Некоторое объяснение: 

T=len

len()Здесь часто используется функция , поэтому переименование экономит байты

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)

Оценивает все возможные подстроки строки s длина n.
eval(...)создает команду zip(s,s[1:],s[2:],...,s[n:])
Это создает подстроки длины nиз каждого индекса, sесли это возможно. Так что для s='budd'и n='2'будет производить бу, уд, дд

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

Фильтр для проверки наличия ключей (K) для уникального названия песни.
re.sub требуется для нескольких идентичных ключей, таких как ['nn', 'nn'] в примерах.

Внутренняя функция def R(r,t)является рекурсивной для создания всех возможных комбинаций подстроки, которые могут описывать название песни.
Каждая комбинация сравнивается с самой короткой (если она была) в настоящее время, чтобы уменьшить количество созданных комбинаций - если она больше, она не будет принята как все ее производные.
Функция использует 2 переменные для отслеживания состояния: nдля длины текущей комбинации самых коротких клавиш и yдля самой комбинации

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

Это вычисляет длину комбинации клавиш. ' '.joinдобавить пробелы между ключами и 2*sum(...)вычисляет количество необходимых кавычек для ключей с пробелами.

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

Использует первую лямбда-функцию, чтобы получить все возможные комбинации клавиш (любой возможной длины) для текущей строки.

Два цикла для просмотра всех сгенерированных ключей и передачи их по отдельности на следующий рекурсивный шаг. Ключевое место ( j) необходимо , чтобы правильно ломтик строка в конце этого: r[j+T(u[i][j]):].
Slice предоставляет строку, которая начинается там, где заканчивается текущий ключ, поэтому перекрытий не будет.
Если место неизвестно, равные ключи могут испортить все. 

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

Гораздо дольше, чем просто y, но ключи с пробелами должны быть заключены в кавычки

Мертвый Опоссум
источник
Это потрясающе. Вы первый, кто правильно понял правило 3!
Аяне
1
Кстати, вы должны иметь возможность сбрить два байта, удалив 0,один из ваших диапазонов: u=[L(r,i)for i in range(0,T(r))]=> u=[L(r,i)for i in range(T(r))].
notjagan
1
Вы можете сохранить еще несколько байтов: при выводе вам не нужно показывать входные строки и размер выходных строк.
Аяне
@ 彩 音 М Спасибо! Я урезал это несколько байтов из диапазона и вывода.
Мертвый Опоссум
1
S=map(str.lower,input())для -5 байт
овса