Le jeu des plaques d'immatriculation en Espagne

26

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 , alors le programme le plus court qui m'aide à toujours battre ma femme gagne! :)

Charlie
la source
Combien de temps les mots de la liste de mots sont-ils garantis?
Neil
2
Dans les plaques d'immatriculation réelles, la lettre Q n'est pas autorisée non plus; et W est, bien que ce ne soit pas une vraie lettre espagnole
Luis Mendo
2
Pouvons-nous supposer que les mots de la liste et les trois lettres seront tous dans un seul cas?
Jonathan Allan
1
@LuisMendo W est une lettre espagnole depuis 1969 .
walen
1
@walen C'est pourquoi j'ai dit "propre" :-) Il existe en espagnol, mais il semble étranger
Luis Mendo

Réponses:

7

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.

Emigna
la source
3
3ù #keep only those of length 3pourquoi avez-vous besoin de ça?
Leo
1
@Leo: Non, c'était idiot de ma part. Merci :)
Emigna
6

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
Luis Mendo
la source
6

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!

Jörg Hülsermann
la source
2
La plaque d'immatriculation doit être une chaîne et non un tableau. Mais vous n'avez pas besoin du modificateur.
Titus
@Titus fixed !!
Jörg Hülsermann
You can suppose the case will always be the same in both the word list and the three consonants.- pas besoin du modificateur regex. Avez-vous essayé wordwrapau lieu de join(str_split())?
Titus
@Titus bonne idée
Jörg Hülsermann
5

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))
Jonathan Allan
la source
1
Si je comprends bien votre explication, cela refuserait un mot comme "borracho" pour une séquence de consonnes de "brc", car "brc" n'est pas une sous-chaîne de "brrc"
Leo
@Leo ah, oui bonne prise je pense que ça échouerait ...
Jonathan Allan
@Leo - eh bien c'est fixe (vérifie "existe dans" pour l'ensemble de puissance de chaque mot) mais il peut ne pas être entièrement joué ...
Jonathan Allan
5

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                       
Maria
la source
@JonathanAllan: Fixé! Merci d'avoir fait remarquer cela.
Maria
1
@JonathanAllan: On dirait qu'il a édité la question pour clarifier qu'il devrait retourner une chaîne vide dans ce cas. J'ai modifié ma réponse en conséquence.
Maria
1
Nous avons un méta-opérateur de tri en D, donc vous pouvez remplacer olN par lD
Maltysen
5

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, utilisantle 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.

ais523
la source
4

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

Davide Spataro
la source
1
Vous pouvez remplacer le plus à droite mapet le filterpar une liste de compréhension. Comme vous l'avez déjà Data.Listdans la portée, vous pouvez utiliser sortOn lengthet choisir la tête pour trouver l'élément avec une longueur minimale. Enfin, créez yune fonction infixe. Tout cela fait fet ksuperflu: l#w=sortOn length[p|p<-w,isInfixOf l$filter(`elem`l)p]!!0.
nimi
tu as raison! Je viens de commencer à jouer au golf! Merci!
Davide Spataro
1
Un plus: si vous changez l'importation Data.Lists, vous pouvez utiliser au argminlieu de sortOnet enregistrez le !!0: l#w=argmin length[...]. Data.Listsa de nombreuses fonctions intéressantes
nimi
3

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!

Dom Hastings
la source
Si j'insère "adsd" dans votre liste, votre programme ne le trouve pas. Le premier caractère à rechercher n'a pas besoin d'être le premier du mot.
Charlie
@CarlosAlejo L'entrée a besoin d'une nouvelle ligne de fin, fonctionne bien alors: Essayez-la en ligne! . Cela m'a toutefois pris au dépourvu, car l' <<<opérateur ajoute cela pour moi en ligne de commande!
Dom Hastings
3

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

Arnauld
la source
c=>l=>l.sort((a,b)=>a[b.length]&&1).find(w=>w.match(c.split``.join`.*`))pour 72, je pense
LarsW
@LarsW En effet, merci! Cependant, j'ai choisi une autre approche pour se conformer à la nouvelle règle: ou une chaîne vide si aucun mot ne correspond au modèle de trois consonnes .
Arnauld
3

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!

Jeu de mots intentionnel
la source
1
Bienvenue chez PPCG! Cela ressemble à un extrait où l'entrée est dans des variables codées en dur. Les réponses doivent être soit des programmes complets, soit des fonctions appelables. Vous pouvez jeter un oeil à ce (ou d' autres réponses R) pour d' éventuelles méthodes d' E / S.
Martin Ender
2

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.

Neil
la source
1
Je ne peux pas décider si ce sont trois nombrils ou trois seins.
Charlie
@CarlosAlejo Pensez-vous à Eccentrica Gallumbits par hasard?
Neil
Je pensais à l'étranger de Total Recall, mais Eccentrica pourrait aussi être une option ... :)
Charlie
2
@CarlosAlejo Apparemment, Mary est un hommage à Eccentrica Gallumbits.
Neil
1

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
DLosc
la source
1

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
Kevin Cruijssen
la source
1
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;}
Nevay
0

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!

Uriel
la source
0

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)
Sundar - Rétablir Monica
la source