To pytanie jest oparte na pytaniu, które zadałem w języku hiszpańskim . Tak, poprosiłem o algorytm w języku hiszpańskim. :)
W Hiszpanii obecne tablice rejestracyjne mają następujący wzór:
1234 XYZ
gdzie XYZ to trzy spółgłosek zaczerpnięte z pełnego zestawu spółgłosek hiszpańskich (chyba, że „the”).
Czasami podczas podróży z żoną gramy w grę. Kiedy widzimy tablicę rejestracyjną, bierzemy jej trzy spółgłosek i próbujemy utworzyć słowo, które zawiera te trzy spółgłoski, występujące w tej samej kolejności, co na tablicy rejestracyjnej. Przykłady (w języku hiszpańskim):
BCD
BoCaDo (valid)
CaBezaDa (not valid)
FTL
FaTaL (valid)
FLeTar (not valid)
FTR
FleTaR (valid, wins)
caFeTeRa (valid, loses)
Zwycięzcą jest ten, który używa najmniejszej liczby znaków, jak widać w ostatnim przykładzie.
Wyzwanie
Napisz najkrótszy program lub funkcję, która otrzyma listę słów i zestaw trzech spółgłosek i znajdzie najkrótsze słowo na liście zawierającej trzy spółgłosek w tej samej kolejności. Dla celów tej gry wielkość liter nie ma znaczenia.
- Dane wejściowe dla listy słów (pierwszy parametr) będą tablicą typu twojego języka
string
. Drugi parametr (trzy spółgłosek) będzie innystring
. Jeśli jest to lepsze dla twojego języka, rozważstring
z trzema spółgłosek ostatnią pozycję z całej listy parametrów. Wyjście będzie innestring
. - Słowa z listy słów nie zostaną wymyślone ani nieskończone, będą to słowa występujące w dowolnym standardowym słowniku. Jeśli potrzebujesz limitu, przypuśćmy, że żadne słowo na liście słów nie będzie dłuższe niż 50 znaków.
- Jeśli istnieje kilka słów o tej samej długości, które mogą być prawidłową odpowiedzią, możesz zwrócić dowolne z nich. Upewnij się, że zwrócisz tylko jedno słowo lub pusty ciąg, jeśli żadne słowa nie pasują do wzoru trzech spółgłosek.
- Możesz powtarzać spółgłoski w grupie, więc poprawnymi danymi dla trzech spółgłosek są zarówno
FLR
iGGG
. - Spółgłoski hiszpańskie są dokładnie takie same jak angielskie, z dodatkiem „Ñ”. Samogłoski są takie same jak w przypadku samogłosek akcentowanych: „áéíóúü”. Nie będzie żadnych innych znaków, takich jak „-” lub „”.
- Możesz przypuszczać, że wielkość liter będzie zawsze taka sama zarówno na liście słów, jak i trzech spółgłosek.
Jeśli chcesz przetestować algorytm z prawdziwą kolekcją hiszpańskich słów, możesz pobrać plik (15,9 MB) z Dropbox zawierający ponad milion słów.
Przypadki testowe
Input: 'psr', {'hola' 'repasar' 'pasarais' 'de' 'caída' 'pequeñísimo' 'agüeros'}
Output: 'repasar'
Input: 'dsd', {'dedos' 'deseado' 'desde' 'sedado'}
Output: 'desde'
Input: 'hst', {'hastío' 'chest'}
Output: 'chest'
To jest golf golfowy , więc niech wygra najkrótszy program, który pomoże mi zawsze pokonać żonę! :)
Odpowiedzi:
05AB1E ,
108 bajtówZaoszczędzono 2 bajty dzięki Leo
Wypróbuj online!
Wyjaśnienie
Użyłbym
head
na końcu zapisania bajtu, ale to by wygenerowało pustą listę, jeśli nie ma dopasowania.źródło
3ù #keep only those of length 3
dlaczego tego potrzebujeszMATL ,
3029 bajtówWypróbuj online!
Wyjaśnienie
źródło
PHP , 111 bajtów
Wypróbuj online!
źródło
You can suppose the case will always be the same in both the word list and the three consonants.
- nie ma potrzeby modyfikatora wyrażenia regularnego. Próbowałeśwordwrap
zamiastjoin(str_split())
?Galaretka ,
12 1110 bajtówPełny program, który akceptuje listę list małych liter (słowa) i listę małych liter (litery) i drukuje pierwsze z najkrótszych słów, które zawierają podsekwencję równą literom (lub nic, jeśli żadne nie istnieje ).
Wypróbuj online!
W jaki sposób?
źródło
Pyth -
2221191211 bajtów-1 dzięki Maltysen.
Pobiera 2 linie jako dane wejściowe. Pierwszy to 3-literowy ciąg (małe litery), a drugi to mała lista słów.
Wypróbuj tutaj
Wyjaśnienie:
Stare 19-bajtowe rozwiązanie:
źródło
Brachylog v2, 11 bajtów
Wypróbuj online!
Podanie funkcji. (Łącze TIO zawiera argument wiersza polecenia, aby uruchomić funkcję tak, jakby był to pełny program.)
Wyjaśnienie
Ponownie bezpośrednie tłumaczenie specyfikacji…
Właściwie możesz prawie odpowiedzieć za pomocą
h⊆.&t∋
- zamiana kolejności oceny oznacza, że Brachylog domyślnie wybierze najkrótszą odpowiedź (jako pierwsze ograniczenie, jakie widzi⊆
, które ma raczej dogodny „najkrótszy” jako domyślny podział remisu) - ale w tym przypadku Brachylog algorytm oceny wpadłby niestety w nieskończoną pętlę, gdyby odpowiedź nie została znaleziona. Tak więc prawie połowa odpowiedzi jest poświęcona rozwiązaniu problemu braku odpowiedniej odpowiedzi. Nawet wtedylᵒ
przesłonięcie remisu (co jest technicznie swego rodzaju, z wykorzystaniem∋
domyślny podział preferowanych elementów bliżej początku listy) to tylko dwa bajty; pozostałe trzy wynikają z potrzeby wypisania pustego łańcucha, szczególnie gdy wynik nie zostanie znaleziony, w przeciwieństwie do domyślnej wartości wartownika Brachylog „brak rozwiązań” (ponieważ końcowy wynik.
byłby domyślny, gdybyśmy nie musieli za nim podążać∨
).Co ciekawe, w Brachylog została wcześniej zaimplementowana funkcja, która uratowałaby bajt tutaj. W pewnym momencie, można wyodrębnić elementy z użyciem argumentu wejściowego
?₁
,?₂
itp składnia; co pozwoliłoby ci zmienić układ programutlᵒ∋.⊇?₁∨Ẹ
, który ma tylko 10 bajtów. Niestety zastosowana implementacja nie działała (i spowodowała awarię wielu działających programów), więc została przywrócona. Możesz jednak myśleć o programie jako „koncepcyjnie” o długości 10 bajtów.źródło
Haskell
12912574 bajtyCREDIT to @nimi
źródło
map
ifilter
ze zrozumieniem listy. Jak już maszData.List
zasięg, możesz użyćsortOn length
i wybrać głowicę, aby znaleźć element o minimalnej długości. Na koniec utwórzy
funkcję infix. Wszystko to sprawia,f
ik
zbędne:l#w=sortOn length[p|p<-w,isInfixOf l$filter(`elem`l)p]!!0
.Data.Lists
, można użyćargmin
zamiastsortOn
i zapisać!!0
:l#w=argmin length[...]
.Data.Lists
ma wiele fajnych funkcjiPerl, 53 bajty
Kod 48 bajtów + 5 dla
-paF
.Ten wykorzystuje fakt, że listy interpolowane do
m//
operatora wykorzystać$"
zmienną, która zmienia początkowy ciąg wejściowy odpsr
celup.*s.*r
, który jest następnie dopasowane do każdego kolejnego słowa jest posortowana nalength
.Wypróbuj online!
źródło
<<<
operator dodaje to dla mnie z linii poleceń!JavaScript (ES6),
777572 bajtówPobiera 3 spółgłosek
c
i listę słówl
w składni curry(c)(l)
. Oba wejścia są oczekiwane w tym samym przypadku.Przypadki testowe
Pokaż fragment kodu
źródło
c=>l=>l.sort((a,b)=>a[b.length]&&1).find(w=>w.match(c.split``.join`.*`))
dla 72, myślęR, 101 bajtów
Pierwszy raz w golfa! Jestem pewien, że można to jakoś skondensować
Pobiera ciąg x i wektor znaków y możliwych danych wejściowych
Wypróbuj online!
Edycja: Moja wersja to 135, dzięki Scrooble za -34!
źródło
Siatkówka , 58 bajtów
Wypróbuj online! Bierze trzy spółgłoski w jednym wierszu, a następnie listę słów we wszystkich kolejnych wierszach. Objaśnienie:
O
sortuje listę z¶.+
wyłączeniem pierwszego wiersza kluczowanego#
numerycznie$
według$.&
długości. Następnie szuka się dopasowania dla linii zawierającej kolejno trzy spółgłosek. Jeśli istnieje odpowiednia linia niż ostatnia, tj. Najkrótsza, taka linia staje się wyjściem, w przeciwnym razie wyjście jest puste.?-s:
Czasowo wyłącza efekts`
tak, że tylko jedna linia jest dopasowana.źródło
Pip , 17 bajtów
Pobiera listę słów jako argumenty wiersza poleceń i spółgłosek ze standardowego wejścia. Wypróbuj online!
Wyjaśnienie
źródło
Java 8,
132126 bajtów-6 bajtów dzięki @Nevay .
Wyjaśnienie:
Wypróbuj online.
źródło
s->a->{String r="";for(String x:a)r=(x.length()<r.length()|r.isEmpty())&x.matches(r.format(".*%s.*%s.*%s.*",s))?x:r;return r;}
Python, 77 bajtów
Wypróbuj online!
źródło
MATL ,
282726 bajtówWypróbuj online!
x
- Weź niejawnie pierwsze wejście (ciąg z trzema literami) i usuń je. Pobiera automatycznie kopiowane do schowka G, poziom 1 (ta część została zainspirowana odpowiedzią @Luis Mendo )."
- Niejawnie weź drugie wejście (komórka słów), powtórz je.l
- Naciśnij 1, aby użyć później1G
- Wciśnij pierwsze wejście (powiedz „psr”)@g
- Wciśnij bieżące słowo jako tablicę3XN
-nchoosek
- Uzyskaj wszystkie kombinacje 3 liter ze słowaXm
- Sprawdź, czy kod tablicy rejestracyjnej „psr” jest jedną z tych kombinacji. Zwraca 0 dla wartości false i 1 dla wartości true./
- Dzieląc 1 (który wcześniej wypchnęliśmy) przez ten wynik. Zmienia zera naInf
s@gn
- Uzyskaj długość bieżącego słowa*
- Pomnóż długość przez wynik podziału. Zwraca długość taką, jaka jest, gdy słowo zawiera 3 znaki, w przeciwnym razie zwracaInf
v
- konkatenuj w pionie te wyniki w jedną tablicę]
- Zamknij pętlę&X<
- pobierz indeks minimalnej wartości z tej tablicy, tj. indeks, w którym znaleziono słowo zawierające litery o minimalnej długości2G
- Naciśnij ponownie drugie wejściew
- Przywróć minimalny indeks na wierzch stosu)
- Indeksuj do tablicy słów z indeksem min, zwracając prawidłowe słowo o minimalnej długości(Wyjściowy wynik).
Starsze:
źródło