^{Cette question est basée sur une question que j'ai posée en langue espagnole . Oui, j'ai demandé un algorithme en espagnol. :)}

En Espagne, les plaques d'immatriculation actuelles ont ce modèle:

1234 XYZ

où XYZ sont trois consonnes tirées de l'ensemble complet des consonnes espagnoles (sauf le 'Ñ', je pense).

Parfois, lorsque je voyage avec ma femme, nous jouons à un jeu. Lorsque nous voyons une plaque d'immatriculation, nous prenons ses trois consonnes et essayons de former un mot qui contient ces trois consonnes, apparaissant dans le même ordre que dans la plaque d'immatriculation. Exemples (en espagnol):

BCD
    BoCaDo (valid)
    CaBezaDa (not valid)
FTL
    FaTaL (valid)
    FLeTar (not valid)
FTR
    FleTaR (valid, wins)
    caFeTeRa (valid, loses)

Le gagnant est celui qui utilise le moins de caractères, comme vous pouvez le voir dans le dernier exemple.

Le défi

Écrivez le programme ou la fonction la plus courte qui reçoit une liste de mots et un ensemble de trois consonnes et trouve le mot le plus court dans la liste qui contient les trois consonnes dans le même ordre. Aux fins de ce jeu, le cas n'a pas d'importance.

• L'entrée pour la liste de mots (premier paramètre) sera un tableau de votre stringtype de langue . Le deuxième paramètre (les trois consonnes) en sera un autre string. Si c'est mieux pour votre langue, considérez stringavec les trois consonnes le dernier élément de toute la liste des paramètres. La sortie en sera une autre string.
• Les mots de la liste de mots ne seront pas inventés ou des mots infinis, ils seront des mots qui apparaissent dans n'importe quel dictionnaire standard. Si vous avez besoin d'une limite, supposez qu'aucun mot de la liste de mots ne dépasse 50 caractères.
• S'il y a plusieurs mots de même longueur qui pourraient être la réponse valide, vous pouvez renvoyer l'un d'eux. Assurez-vous de ne renvoyer qu'un seul mot ou une chaîne vide si aucun mot ne correspond au modèle de trois consonnes.
• Vous pouvez répéter les consonnes dans le groupe, donc les entrées valides pour les trois consonnes sont à la fois FLRet GGG.
• Les consonnes espagnoles sont exactement les mêmes que l'anglais, avec l'ajout du "Ñ". Les voyelles sont les mêmes avec l'adition des voyelles accentuées: "áéíóúü". Il n'y aura aucun autre type de marque comme "-" ou "'".
• Vous pouvez supposer que le cas sera toujours le même dans la liste de mots et dans les trois consonnes.

Si vous souhaitez tester votre algorithme avec une véritable collection de mots espagnols, vous pouvez télécharger un fichier (15,9 Mo) depuis Dropbox avec plus d'un million de mots.

Cas de test

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'

C'est du golf de code , alors le programme le plus court qui m'aide à toujours battre ma femme gagne! :)

05AB1E , 10 8 octets

Enregistré 2 octets grâce à Leo

ʒæså}éR`

Essayez-le en ligne!

Explication

ʒ         # 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)

J'aurais utilisé headà la fin l'enregistrement d'un octet mais cela produirait une liste vide s'il n'y a pas de correspondance.

MATL , 30 29 octets

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

Essayez-le en ligne!

Explication

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 octets

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

Essayez-le en ligne!

Gelée ,  12 11  10 octets

ŒPċðÐfLÞḣ1

Un programme complet qui accepte une liste de listes de caractères minuscules (les mots) et une liste de caractères minuscules (les lettres) et imprime le premier des mots les plus courts qui contiennent une sous-séquence égale aux lettres (ou rien s'il n'en existe pas) ).

Essayez-le en ligne!

Comment?

Œ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 octets

h+f/yTQlDEk

-1 Merci à Maltysen.

Prend 2 lignes en entrée. Le premier est la chaîne de 3 lettres (en minuscules) et le second est une liste de mots en minuscules.

Essayez-le ici

Explication:

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)

Ancienne solution à 19 octets:

h+olNf/-T"aeiou"QEk                       

Brachylog v2, 11 octets

tlᵒ∋.&h⊆.∨Ẹ

Essayez-le en ligne!

Soumission de fonction. (Le lien TIO a un argument de ligne de commande pour exécuter une fonction comme s'il s'agissait d'un programme complet.)

Explication

Encore une traduction directe de la spécification…

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

Vous pouvez en fait presque répondre avec h⊆.&t∋- permuter l'ordre d'évaluation signifie que Brachylog choisira la réponse la plus courte par défaut (comme la première contrainte qu'il voit est ⊆, qui a le "plus court" plutôt pratique comme bris d'égalité par défaut) - mais dans ce cas, Brachylog's l'algorithme d'évaluation entrerait malheureusement dans une boucle infinie si la réponse n'est pas réellement trouvée. Ainsi, près de la moitié de la réponse est consacrée au traitement de l'absence de réponse appropriée. Même dans ce cas, la lᵒdérogation de départage (qui est techniquement une sorte, utilisant∋le bris d'égalité par défaut consistant à préférer les éléments au début de la liste) n'est que de deux octets; les trois autres proviennent de la nécessité de générer une chaîne vide spécifiquement lorsque la sortie n'est pas trouvée, contrairement à la valeur sentinelle par défaut de "aucune solution" de Brachylog (car la finale .serait implicite si nous n'avions pas à la suivre ∨).

Fait intéressant, il existe une fonctionnalité qui a été précédemment implémentée dans Brachylog qui aurait enregistré un octet ici. À un moment donné, vous pouvez extraire des éléments de l'argument d'entrée à l' aide ?₁, ?₂etc. syntaxe; cela vous permettrait de réorganiser le programme en tlᵒ∋.⊇?₁∨Ẹ, ce qui n'est que de 10 octets. Malheureusement, l'implémentation qui a été utilisée n'a pas vraiment fonctionné (et a causé la rupture de nombreux programmes qui fonctionnaient autrement), elle a donc été annulée. Vous pouvez penser au programme comme étant "conceptuellement" long de 10 octets.

Haskell 129 125 74 octets

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

CRÉDIT à @nimi

Perl, 53 octets

Code de 48 octets + 5 pour -paF.

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

Ceci tire profit du fait que les listes interpolées dans l' m//opérateur utilisent la $"variable qui modifie la chaîne d'entrée initiale à partir psrde p.*s.*rlaquelle est ensuite identifié pour chaque mot supplémentaire et est triée sur length.

Essayez-le en ligne!

JavaScript (ES6), 77 75 72 octets

Prend les 3 consonnes cet la liste de mots ldans la syntaxe de curry (c)(l). Les deux entrées sont attendues dans le même cas.

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

Cas de test

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 octets

Golf pour la première fois! Je suis sûr que cela peut être condensé en quelque sorte

Prend la chaîne x et un vecteur de caractères y des entrées possibles

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

Essayez-le en ligne!

Edit: Ma version était de 135, merci Scrooble pour le -34!

Rétine , 58 octets

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

Essayez-le en ligne! Prend les trois consonnes sur une ligne puis la liste des mots sur toutes les lignes suivantes. Explication: Otrie la liste ¶.+excluant la première ligne #numérique $calée par $.&longueur. Une correspondance est alors recherchée pour une ligne qui inclut les trois consonnes dans l'ordre. S'il existe une ligne appropriée à la précédente, c'est-à-dire la plus courte, cette ligne devient la sortie, sinon la sortie est vide. Le ?-s:désactive temporairement l'effet de s`sorte qu'une seule ligne est mise en correspondance.

Pip , 17 octets

@:qJ`.*`N_FI#_SKg

Prend la liste de mots comme arguments de ligne de commande et les consonnes de stdin. Essayez-le en ligne!

Explication

                   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 octets

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 octets grâce à @Nevay .

Explication:

Essayez-le en ligne.

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 octets

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

Essayez-le en ligne!

MATL , 28 27 26 octets

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

Essayez-le en ligne!

x- Prenez implicitement la première entrée (chaîne de trois lettres) et supprimez-la. Obtient copié dans le presse-papiers G, niveau 1 automatiquement (cette partie a été inspirée par la réponse de @Luis Mendo ).

" - Prenez implicitement la deuxième entrée (tableau de cellules de mots), parcourez-la.

l - Appuyez sur 1 pour être utilisé plus tard

1G - Appuyez sur la première entrée (dites «psr»)

@g - Poussez le mot actuel comme tableau

3XN- nchoosek- Obtenez toutes les combinaisons de 3 lettres du mot

Xm- Vérifiez si le code de plaque d'immatriculation «psr» est l'une de ces combinaisons. Renvoie 0 pour faux et 1 pour vrai.

/- Diviser le 1 (que nous avons poussé plus tôt) par ce résultat. Change les 0 en Infs

@gn - Obtenez la longueur du mot actuel

*- Multipliez la longueur par le résultat de la division. Renvoie la longueur telle qu'elle est lorsque le mot contient les 3 caractères, sinon renvoieInf

v - concaténer verticalement ces résultats dans un seul tableau

] - boucle fermée

&X< - obtenir l'index de la valeur minimale de ce tableau, c'est-à-dire l'index où le mot contenant les lettres et avec une longueur minimale a été trouvé

2G - Appuyez à nouveau sur la deuxième entrée

w - Ramener l'index min en haut de la pile

) - Index dans un tableau de mots avec l'index min, renvoyant le mot valide avec une longueur minimale

(Sortie implicite.)

Plus âgée:

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

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