^{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 inny string. Jeśli jest to lepsze dla twojego języka, rozważ stringz trzema spółgłosek ostatnią pozycję z całej listy parametrów. Wyjście będzie inne string.
• 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 FLRi GGG.
• 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ę! :)

05AB1E , 10 8 bajtów

Zaoszczędzono 2 bajty dzięki Leo

ʒæså}éR`

Wypróbuj online!

Wyjaśnienie

ʒ         # filter list, keep only members for which the following is true
  så      # input is in the
 æ        # powerset of the current word
    }     # end filter
     é    # sort by length
      R   # reverse
       `  # push separately (shortest on top)

Użyłbym headna końcu zapisania bajtu, ale to by wygenerowało pustą listę, jeśli nie ma dopasowania.

MATL , 30 29 bajtów

xtog!s2$S"1G!'.*'Yc!@gwXXn?@.

Wypróbuj online!

Wyjaśnienie

x         % Implicitly take first input (string with three letters). Delete.
          % Gets copied into clipboard G, level 1
t         % Implicitly take second input (cell array of strings defining the
          % words). Duplicate
o         % Convert to numeric array of code points. This gives a matrix where
          % each string is on a row, right-padded with zeros
g         % Convert to logical: nonzeros become 1
!s        % Sum of each row. This gives the length of each word
2$S       % Two-input sort: this sorts the array of strings according to their
          % lengths in increasing order
"         % For each word in the sorted array
  1G      %   Push first input, say 'xyz'
  !       %   Transpose into a column vector of chars
  '.*'Yc  %   Concatenate this string on each row
  !       %   Transpose. This gives a char array which, when linearized in
          %   column-major order, corresponds to 'x.*y.*z.*'
  @g      %   Push corrent word
  w       %   Swap
  XX      %   Regexp matching. Gives a cell array with substrings that match
          %   the pattern 'x.*y.*z.*'
  n       %   Number of matchings
  ?       %   If non-zero
    @     %     Push cell array with current word, to be displayed as output
    .     %     Break loop
          %   Implicit end (if)
          % Implicit end (for)
          % Implicitly display stack

PHP , 111 bajtów

$y=array_map(str_split,preg_grep("#".chunk_split($_GET[1],1,".*")."#",$_GET[0]));sort($y);echo join($y[0]??[]);

Wypróbuj online!

Galaretka ,  12 11  10 bajtów

ŒPċðÐfLÞḣ1

Peł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?

ŒPċðÐfLÞḣ1 - Main link: words; characters
   ðÐf     - filter keep words for which this is truthy:
ŒP         -   the power-set (all sub-sequences of the word in question)
  ċ        -   count (how many times the list of characters appears)
           - ...note 0 is falsey while 1, 2, 3, ... are truthy
       Þ   - sort by:
      L    -  length
        ḣ1 - head to index 1 (would use Ḣ but it yields 0 for empty lists)
           - implicit print (smashes together the list of lists (of length 1))

Pyth - 22 21 19 12 11 bajtów

h+f/yTQlDEk

-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:

h+f/yTQlDEk
       lDE   # Sort word list by length
  f          # Filter elements T of the word list...
    yT       # by taking the powerset...
   /  Q      # and checking whether the 3-letter string Q is an element of that.
 +        k  # Add empty string to the list (in case no results found)
h            # And take the first result (the shortest)

Stare 19-bajtowe rozwiązanie:

h+olNf/-T"aeiou"QEk                       

Brachylog v2, 11 bajtów

tlᵒ∋.&h⊆.∨Ẹ

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…

tlᵒ∋.&h⊆.∨Ẹ
t            The last element of {standard input}
   ∋.        contains the return value as an element
     &       and
      h      the first element of {standard input}
       ⊆.    is a subsequence of the return value
         ∨   alternate behaviour if no solution is found:
          Ẹ  return empty string
  ᵒ          tiebreak override: favour answers that have a low
 l           length

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 wtedy lᵒ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 programu tlᵒ∋.⊇?₁∨Ẹ, 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.

Haskell 129 125 74 bajty

import Data.List
l#w=sortOn length[p|p<-w,isInfixOf l$filter(`elem`l)p]!!0

CREDIT to @nimi

Perl, 53 bajty

Kod 48 bajtów + 5 dla -paF.

$"=".*";($_)=sort{$a=~y///c-length$b}grep/@F/,<>

Ten wykorzystuje fakt, że listy interpolowane do m//operatora wykorzystać $"zmienną, która zmienia początkowy ciąg wejściowy od psrcelu p.*s.*r, który jest następnie dopasowane do każdego kolejnego słowa jest posortowana na length.

Wypróbuj online!

JavaScript (ES6), 77 75 72 bajtów

Pobiera 3 spółgłosek ci listę słów lw składni curry (c)(l). Oba wejścia są oczekiwane w tym samym przypadku.

c=>l=>l.map(w=>x=!w.match([...c].join`.*`)||!x[w.length]&&x?x:w,x='')&&x

Przypadki testowe

let f =

c=>l=>l.map(w=>x=!w.match([...c].join`.*`)||!x[w.length]&&x?x:w,x='')&&x

console.log(f('psr')(['hola', 'repasar', 'pasarais', 'de', 'caída', 'pequeñísimo', 'agüeros'])) // 'repasar'
console.log(f('dsd')(['dedos', 'deseado', 'desde', 'sedado'])) // 'desde'

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

w=pryr::f((b=y[sapply(gsub(paste('[^',x,']'),'',y),function(l)regexpr(x,l))>0])[which.min(nchar(b))])

Wypróbuj online!

Edycja: Moja wersja to 135, dzięki Scrooble za -34!

Siatkówka , 58 bajtów

O#$^`¶.+
$.&
s`^((.)(.)(.).*¶(?-s:(.*\2.*\3.*\4.*)))?.*
$5

Wypróbuj online! Bierze trzy spółgłoski w jednym wierszu, a następnie listę słów we wszystkich kolejnych wierszach. Objaśnienie: Osortuje 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 efekt s`tak, że tylko jedna linia jest dopasowana.

Pip , 17 bajtów

@:qJ`.*`N_FI#_SKg

Pobiera listę słów jako argumenty wiersza poleceń i spółgłosek ze standardowego wejścia. Wypróbuj online!

Wyjaśnienie

                   g is list of cmdline args (implicit)
              SKg  Sort g using this key function:
            #_      Length of each item (puts shortest words first)
          FI       Filter on this function:
  q                 Line of input
   J`.*`            joined on regex .* (turns "psr" into `p.*s.*r`)
        N_          Count regex matches in item (keeps only words that match)
@:                 Get first element of result (using : meta-operator to lower precedence)
                   If the list is empty, this will give nil, which results in empty output

Java 8, 132 126 bajtów

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;}

-6 bajtów dzięki @Nevay .

Wyjaśnienie:

Wypróbuj online.

s->a->{              // Method with two String-array parameters and String return-type
  String r="";       //  Result-String, starting empty
  for(String x:a)    //  Loop over the words
    r=(x.length()<r.length()
                     //   If a word is smaller than the current `r`,
      |r.isEmpty())  //   or `r` is still empty
      &x.matches(r.format(".*%s.*%s.*%s.*",s))?
                     //   And if the word is valid
       x             //    Change `r` to the current word
      :              //   Else:
       r;            //    Leave `r` the same
  return r;}         //  Return the result

Python, 77 bajtów

import re
lambda s,a:min([x for x in a if re.search('.*'.join(s),x)],key=len)

Wypróbuj online!

MATL , 28 27 26 bajtów

x"l1G@g3XNXm/@gn*v]&X<2Gw)

Wypró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óźniej

1G - 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łowa

Xm- 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 na Infs

@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ści

2G - Naciśnij ponownie drugie wejście

w - 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:

x"@g1Gy3XNXm1w/wn*v]&X<2Gw)

x"@g1Gy3XNXm1w/wn*v]2Gw2$S1)