Sposób przeszukiwania biblioteki przez golfisty

15

Wyzwanie:

W mojej kolekcji muzycznej mam tysiące piosenek i na szczęście mój ulubiony odtwarzacz ma funkcję wyszukiwania. Mam też świetną pamięć - pamiętam tytuł każdej piosenki w mojej kolekcji. Jestem jednak bardzo leniwy i nie lubię pisać na klawiaturze - każde dodatkowe naciśnięcie klawisza jest obowiązkiem!

  • Jaki jest najkrótszy ciąg, którego muszę szukać, aby wyodrębnić jedną piosenkę? Pomóż mi zapamiętać listę klawiszy, których mogę użyć, aby zminimalizować pisanie podczas wyszukiwania!

To jest golf golfowy , więc wygrywa najkrótszy kod.

Zasady:

Biorąc pod uwagę listę tytułów utworów, wygeneruj listę kluczy wyszukiwania z zastrzeżeniem następujących ograniczeń:

  1. Każdy tytuł utworu powinien mieć klawisz wyszukiwania.
  2. Całkowita liczba znaków na liście wyników musi być jak najmniejsza.
  3. Mój ulubiony odtwarzacz muzyki to foobar2000 :
    • Funkcja wyszukiwania nie rozróżnia wielkości liter. ( applejest taki sam jak aPpLE).
    • Każdy klucz wyszukiwania musi składać się z jednego lub więcej „słów”, w dowolnej kolejności, oddzielonych spacjami:
      • Każde słowo musi być podciągiem odpowiedniego tytułu piosenki.
      • Jeśli ten sam podciąg zostanie podany wiele razy, to musi wystąpić wiele razy w odpowiednim tytule utworu.
      • Jeśli sam podciąg zawiera spację, to ten podciąg musi być otoczony cudzysłowami.

Poradnik:

  • Często w przypadku niektórych tytułów utworów istnieje kilka klawiszy wyszukiwania spełniających zasadę 2. W takim przypadku wystarczy jeden klawisz, ale otrzymasz punkty brownie za ich listę.
  • Możesz założyć, że na liście wejściowej będą tylko znaki ASCII, ale punkty brownie zostaną przyznane za zgodność UTF-8.
  • Czy przestrzeganie zasady 3 było trudne? Oto jak to działa:

Pokaż fragment kodu

Przykład:

Jeśli moja kolekcja muzyczna składała się tylko z dwóch albumów, Off the Wall i Thriler Michaela Jacksona :

Pokaż fragment kodu

Możesz użyć powyższych list do przetestowania swojego programu. Oto surowa wersja drugiej listy: 

["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
źródło
1
Czy masz przykład, który wymaga wielu ciągów klucza?
Jonathan Allan
1
Jak o ["Wanta Be A Wanna B","Wanta Bea A Wanna B","Wanna Be A Wanna Bea"]?
Jonathan Allan
... ale jakie powinny / powinny być, jeśli w samych podciągach nie są dozwolone spacje - zwróć uwagę, że wszystkie całe słowa kolidują.
Jonathan Allan
Dlaczego surowa wersja jest w spoilerze?
Leaky Nun
1
Powiązane
Robert Fraser

Odpowiedzi:

4

Python 2, 556 bajtów

Wypróbuj online.

-10 bajtów, dzięki @Riker, @ovs

Zajęło mi kilka wieczorów, żeby wszystko działało.
Wyświetla nazwę utworu, tablicę klawiszy wyszukiwania i długość klawiszy wyszukiwania (łącznie ze spacjami i cudzysłowami)

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]

Niektóre wyjaśnienia: 

T=len

Funkcja len()używana tutaj bardzo często, więc zmiana nazwy pozwala zaoszczędzić bajty

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)

Ocenia wszystkie możliwe podciągi długości łańcucha n.
eval(...)tworzy polecenie zip(s,s[1:],s[2:],...,s[n:])
Tworzy podciągi długości nz każdego indeksu, sjeśli to możliwe. Więc dla s='budd'i n='2'będzie produkować 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

Filtruj, aby sprawdzić, czy dostarczone klawisze (K) dotyczą unikalnej nazwy utworu.
re.sub jest wymagane dla wielu identycznych kluczy, takich jak ['nn', 'nn'] w przykładach.

Funkcja wewnętrzna def R(r,t)jest rekurencyjna, aby utworzyć wszystkie możliwe kombinacje podciągów, które mogą opisywać nazwę piosenki.
Każda kombinacja jest porównywana z aktualnie najkrótszą (jeśli taka była) z mniejszą liczbą utworzonych kombinacji - jeśli jest większa, nie będzie akceptowana jako wszystkie pochodne.
Funkcja używa 2 zmiennych do śledzenia stanu: ndla długości bieżącej najkrótszej kombinacji klawiszy i ydla samej kombinacji

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

Oblicza to długość kombinacji klawiszy. ' '.joindodaj spacje między kluczami i 2*sum(...)oblicza liczbę potrzebnych cudzysłowów dla kluczy ze spacjami.

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

Używa pierwszej funkcji lambda, aby uzyskać wszystkie możliwe kombinacje klawiszy (każdej możliwej długości) dla bieżącego ciągu.

Dwa dla cykli, aby przejrzeć wszystkie wygenerowane klucze i przekazać je indywidualnie do następnego rekurencyjnego kroku. Kluczem miejsce ( j) jest potrzebny do prawidłowego slice ciąg na jego końcu: r[j+T(u[i][j]):].
Plaster zapewnia ciąg znaków, który zaczyna się tam, gdzie kończy się bieżący klucz, więc nie będzie nakładania się.
Jeśli miejsce jest nieznane, równe klucze zepsułyby wszystko. 

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

Znacznie dłużej niż tylko y, ale klawisze ze spacjami powinny być otoczone cudzysłowami

Dead Possum
źródło
To jest niesamowite. Jesteś pierwszym, który uzyskał prawidłową zasadę 3!
ayane
1
Nawiasem mówiąc, powinieneś być w stanie ogolić dwa bajty, usuwając 0,jeden z twoich zakresów: u=[L(r,i)for i in range(0,T(r))]=> u=[L(r,i)for i in range(T(r))].
notjagan
1
Możesz zapisać jeszcze kilka bajtów: w danych wyjściowych nie musisz pokazywać ciągów wejściowych i wielkości ciągów wyjściowych.
ayane
@ 彩 音 M Dzięki! Skróciłem te kilka bajtów z zakresu i wyjścia.
Dead Possum
1
S=map(str.lower,input())dla -5 bajtów
ovs