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:

+----------------------+ +--------+ +----------------+ +------------------------------------+
|         Input        | | Output | |   Statistics   | |             Explanation            |
|----------------------| |--------| |----------------| |------------------------------------|
|                      | | Search | |  Key   |  # of | |                                    |
|      Song title      | |  Key   | | length | words | |   Why is the output what it is?    |
|----------------------| |--------| |--------|-------| |------------------------------------|
| Wanna Be A Wanna Bea | | e e    | |      3 |     2 | |      ["Wanna Be A Wanna Bea"]      |
|                      | |        | |        |       | |   is the only string containing    |
|                      | |        | |        |       | |            ["e"] twice             |
|----------------------| |--------| |--------|-------| |------------------------------------|
| Wanta Bea A Wanna B  | | t ea   | |      4 |     2 | |       ["Wanta Bea A Wanna B"]      |
|                      | |        | |        |       | | is the only string containing both |
|                      | |        | |        |       | |          ["t"] and ["ea"]          |
|----------------------| |--------| |--------|-------| |------------------------------------|
| Wanta Be A Wanna B   | | t "e " | |      6 |     2 | |       ["Wanta Be A Wanna B"]       |
|                      | |        | |        |       | | is the only string containing both |
|                      | |        | |        |       | | ["t"] and ['e' preceding a space]  |
+----------------------+ +--------+ +----------------+ +------------------------------------+

Total number of characters in output (par): 13

Przykład:

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

+--------------------------------+ +--------+ +----------------+
|             Input              | | Output | |   Statistics   |
|--------------------------------| |--------| |----------------|
|                                | | Search | |  key   | # of  |
|           Song title           | |  key   | | length | words |
|--------------------------------| |--------| |--------+-------|
| Don't Stop 'Til You Get Enough | | Do     | |      2 |     1 |
| Rock with You                  | | Ro     | |      2 |     1 |
| Working Day and Night          | | Wo     | |      2 |     1 |
| Get on the Floor               | | Fl     | |      2 |     1 |
| Off the Wall                   | | ff     | |      2 |     1 |
| Girlfriend                     | | lf     | |      2 |     1 |
| She's out of My Life           | | Sh     | |      2 |     1 |
| I Can't Help It                | | Ca     | |      2 |     1 |
| It's the Falling in Love       | | v      | |      1 |     1 |
| Burn This Disco Out            | | Bu     | |      2 |     1 |
| Wanna Be Startin' Somethin'    | | nn     | |      2 |     1 |
| Baby Be Mine                   | | Ba     | |      2 |     1 |
| The Girl Is Mine               | | G M    | |      3 |     2 |
| Thriller                       | | hr     | |      2 |     1 |
| Beat It                        | | Bea    | |      3 |     1 |
| Billie Jean                    | | J      | |      1 |     1 |
| Human Nature                   | | Hu     | |      2 |     1 |
| P.Y.T. (Pretty Young Thing)    | | .      | |      1 |     1 |
| The Lady in My Life            | | La     | |      2 |     1 |
+--------------------------------+ +--------+ +----------------+

Total number of characters in output (par): 37

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)"]

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