Gra tablic rejestracyjnych Hiszpanii

26

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 , więc niech wygra najkrótszy program, który pomoże mi zawsze pokonać żonę! :)

Charlie
źródło
Jak długo gwarantowane są słowa z listy słów?
Neil
2
Na rzeczywistych tablicach rejestracyjnych litera Q również nie jest dozwolona; a W to, choć nie jest to właściwy hiszpański list
Luis Mendo
2
Czy możemy założyć słowa z listy, a trzy litery będą w jednym przypadku?
Jonathan Allan
1
@LuisMendo W jest listem hiszpańskim od 1969 roku .
walen
1
@walen Dlatego powiedziałem „właściwy” :-) Istnieje w języku hiszpańskim, ale wydaje się obcy
Luis Mendo

Odpowiedzi:

7

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.

Emigna
źródło
3
3ù #keep only those of length 3dlaczego tego potrzebujesz
Leo
1
@Leo: Nie wiem, to było głupie z mojej strony. Dzięki :)
Emigna
6

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
Luis Mendo
źródło
6

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!

Jörg Hülsermann
źródło
2
Tablica rejestracyjna powinna być ciągiem, a nie tablicą. Ale nie potrzebujesz modyfikatora.
Tytus
@Tytus naprawiony !!
Jörg Hülsermann
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ś wordwrapzamiast join(str_split())?
Titus
@Titus dobry pomysł
Jörg Hülsermann
5

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))
Jonathan Allan
źródło
1
Jeśli dobrze rozumiem twoje wyjaśnienie, to odrzuciłoby słowo takie jak „borracho” dla sekwencji spółgłosek „brc”, ponieważ „brc” nie jest podciągiem „brrc”
Leo
@Leo ah, tak dobry połów Myślę, że to się nie powiedzie ...
Jonathan Allan
@Leo - cóż, naprawiono (sprawdza „istnieje w” dla całego zestawu mocy każdego słowa), ale może nie być w pełni golfa ...
Jonathan Allan
5

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                       
Maria
źródło
@JonathanAllan: Naprawiono! Dzięki za zwrócenie na to uwagi.
Maria,
1
@JonathanAllan: Wygląda na to, że zredagował pytanie, aby wyjaśnić, że w takim przypadku powinien zwrócić pusty ciąg. Odpowiednio zredagowałem swoją odpowiedź.
Maria,
1
W D mamy posortowanego operatora meta, więc możesz zastąpić OLN lD
Maltysen
5

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 wykorzystaniemdomyś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.

ais523
źródło
4

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

Davide Spataro
źródło
1
Możesz zamienić skrajnie prawą mapi filterze zrozumieniem listy. Jak już masz Data.Listzasięg, możesz użyć sortOn lengthi wybrać głowicę, aby znaleźć element o minimalnej długości. Na koniec utwórz yfunkcję infix. Wszystko to sprawia, fi kzbędne: l#w=sortOn length[p|p<-w,isInfixOf l$filter(`elem`l)p]!!0.
nimi
masz rację! Właśnie zacząłem grać w golfa! Dzięki!
Davide Spataro,
1
Jeszcze jedno: jeśli przełączyć do importu Data.Lists, można użyć argminzamiast sortOni zapisać !!0: l#w=argmin length[...]. Data.Listsma wiele fajnych funkcji
nimi
3

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!

Dom Hastings
źródło
Jeśli wstawię słowo „adsd” do listy, Twój program go nie znajdzie. Pierwszy znak do znalezienia nie musi być pierwszym słowem.
Charlie,
@CarlosAlejo Dane wejściowe wymagają nowej linii końcowej, a następnie działają dobrze: Wypróbuj online! . To mnie zaskoczyło, ponieważ <<<operator dodaje to dla mnie z linii poleceń!
Dom Hastings,
3

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

Arnauld
źródło
c=>l=>l.sort((a,b)=>a[b.length]&&1).find(w=>w.match(c.split``.join`.*`))dla 72, myślę
LarsW
@LarsW Rzeczywiście, dzięki! Jednak wybrałem inne podejście, aby zastosować się do nowej zasady: lub pusty ciąg, jeśli żadne słowa nie pasują do wzoru trzech spółgłosek .
Arnauld,
3

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!

Ukarane
źródło
1
Witamy w PPCG! Wygląda to jak fragment kodu, w którym dane wejściowe są zapisane na stałe w zmiennych. Odpowiedzi muszą być pełnymi programami lub pełnymi funkcjami. Możesz spojrzeć na to (lub inne odpowiedzi R) na możliwe metody We / Wy.
Martin Ender
2

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.

Neil
źródło
1
Nie mogę zdecydować, czy są to trzy pępki czy trzy piersi.
Charlie,
@CarlosAlejo Czy przypadkiem myślisz o Eccentrica Gallumbits?
Neil
Myślałem o kosmicie z Total Recall, ale Eccentrica może być również opcją ... :)
Charlie,
2
@CarlosAlejo Najwyraźniej Mary jest hołdem dla Eccentrica Gallumbits.
Neil,
1

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
DLosc
źródło
1

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
Kevin Cruijssen
źródło
1
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;}
Nevay
0

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!

Uriel
źródło
0

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)
sundar - Przywróć Monikę
źródło