The Spain license plates game

Question

^{This question is based on a question I asked in Spanish language. Yes, I asked for an algorithm in Spanish Language. :)}

In Spain, current license plates have this pattern:

1234 XYZ

where XYZ are three consonants taken from the full set of Spanish consonants (except the 'Ñ', I think).

Sometimes, when traveling with my wife, we use to play a game. When we see a license plate, we take its three consonants and try to form a word that contains those three consonants, appearing in the same order as in the license plate. Examples (in Spanish):

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

The winner is the one who uses the least number of characters, as you can see in the last example.

The challenge

Write the shortest program or function that receives a list of words and a set of three consonants and finds the shortest word in the list that contains the three consonants in the same order. For the purposes of this game, case does not matter.

• The input for the word list (first parameter) will be an array of your language string type. The second parameter (the three consonants) will be another string. If it's better for your language, consider the string with the three consonants the last item of the whole list of parameters. The output will be another string.
• The words in the word list won't be invented or infinite words, they will word that appear in any standard dictionary. If you need a limit, suppose no word in the word list will be longer than 50 characters.
• If there are several words with the same lenght that could be the valid answer, you can return any one of them. Just make sure you return just one word, or an empty string if no words match the pattern of three consonants.
• You can repeat consonants in the group, so valid inputs for the three consonants are both FLR and GGG.
• The Spanish consonants are exactly the same as English, with the addition of the "Ñ". The vowels are the same with the adition of the stressed vowels: "áéíóúü". There won't be any other kind of marks such as "-" or "'".
• You can suppose the case will always be the same in both the word list and the three consonants.

If you want to test your algorithm with a real collection of Spanish words, you can download a file (15.9 MB) from Dropbox with more than a million words.

Test cases

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'

This is code-golf, so may the shortest program that helps me to always beat my wife wins! :)

Answer 1

05AB1E, 10 8 bytes

Saved 2 bytes thanks to Leo

ʒæså}éR`

Try it online!

Explanation

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

I would have used head at the end saving a byte but that would output an empty list if there isn't a match.

Answer 2

MATL, 30 29 bytes

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

Try it online!

Explanation

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

Answer 3

PHP, 111 bytes

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

Try it online!

Answer 4

Jelly,  12 11  10 bytes

ŒPċðÐfLÞḣ1

A full program that accepts a list of lists of lowercase characters (the words) and a list of lowercase characters (the letters) and prints the first of the shortest words which contain a sub-sequence equal to the letters (or nothing if none exist).

Try it online!

How?

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

Answer 5

Pyth - 22 21 19 12 11 bytes

h+f/yTQlDEk

-1 Thanks to Maltysen.

Takes 2 lines as input. 1st is the 3-letter string (lowercase), and the 2nd is a lowercase list of words.

Try it here

Explanation:

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)

Old 19-byte solution:

h+olNf/-T"aeiou"QEk                       

Answer 6

Brachylog v2, 11 bytes

tlᵒ∋.&h⊆.∨Ẹ

Try it online!

Function submission. (The TIO link has a command-line argument to run a function as though it were a full program.)

Explanation

Just a direct translation of the specification again…

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

You can actually almost answer with h⊆.&t∋ – swapping the evaluation order means that Brachylog will pick the shortest answer by default (as the first constraint it sees is ⊆, which has the rather convenient "shortest" as a default tiebreak) – but in that case, Brachylog's evaluation algorithm would unfortunately go into an infinite loop if the answer is not actually found. So almost half the answer is dedicated to handling the case of there being no appropriate answer. Even then, the lᵒ tiebreak override (which is technically a sort, making use of ∋'s default tiebreak of preferring elements nearer the start of the list) is only two bytes; the other three come from the need to output an empty string specifically when the output is not found, as opposed to Brachylog's default "no solutions" sentinel value (because the final . would be implicit if we didn't have to follow it with ∨).

Interestingly, there's a feature that was previously implemented in Brachylog that would have saved a byte here. At one point, you could extract elements from the input argument using ?₁, ?₂, etc. syntax; that would allow you to rearrange the program to tlᵒ∋.⊇?₁∨Ẹ, which is only 10 bytes. Unfortunately, the implementation that was used didn't actually work (and caused many otherwise working programs to break), so it was reverted. You can think of the program as being "conceptually" 10 bytes long, though.

Answer 7

Haskell 129 125 74 bytes

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

CREDIT to @nimi

Answer 8

Perl, 53 bytes

48 bytes code + 5 for -paF.

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

This takes advantage of the fact that lists interpolated into the m// operator utilise the $" variable which changes the initial input string from psr to p.*s.*r which is then matched for each additional word and is sorted on length.

Try it online!

Answer 9

JavaScript (ES6), 77 75 72 bytes

Takes the 3 consonants c and the list of words l in currying syntax (c)(l). Both inputs are expected in the same case.

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

Test cases

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'

Answer 10

R, 101 bytes

First time golfing! I'm sure this can be condensed somehow

Takes the string x and a character vector y of possible inputs

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

Try it online!

Edit: My version was 135, thanks Scrooble for the -34!

Answer 11

Retina, 58 bytes

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

Try it online! Takes the three consonants on one line and then the list of words on all subsequent lines. Explanation: O sorts the list ¶.+ excluding the first line # numerically $ keyed by $.& length. A match is then sought for a line that includes the three consonants in order. If a suitable line exists than the last, i.e. shortest, such line becomes the output, otherwise the output is empty. The ?-s: temporarily turns off the effect of s` so that only one line is matched.

Answer 12

Pip, 17 bytes

@:qJ`.*`N_FI#_SKg

Takes the word list as command-line arguments, and the consonants from stdin. Try it online!

Explanation

                   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

Answer 13

Java 8, 132 126 bytes

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 bytes thanks to @Nevay.

Explanation:

Try it 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

Answer 14

Python, 77 bytes

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

Try it online!

Answer 15

MATL, 28 27 26 bytes

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

Try it online!

x - Implicitly take first input (string with three letters) and delete it. Gets copied into clipboard G, level 1 automatically (this part was inspired by @Luis Mendo's answer).

" - Implicitly take second input (cell array of words), iterate through it.

l - Push 1 to be used later

1G - Push first input (say 'psr')

@g - Push the current word as array

3XN - nchoosek - Get all combinations of 3 letters from the word

Xm - See if the license plate code 'psr' is one of these combinations. Returns 0 for false and 1 for true.

/ - Dividing the 1 (that we pushed earlier) by this result. Changes the 0s to Infs

@gn - Get the length of the current word

* - Multiply the length by the division result. Returns the length as it is when word contains the 3 characters, otherwise returns Inf

v - vertically concatenate these results into a single array

] - close loop

&X< - get the index of the minimum value from that array i.e. the index where the word containing the letters and with minimum length was found

2G - Push the second input again

w - Bring the min index back on top of stack

) - Index into array of words with the min index, returning the valid word with minimum length

(Implicit output.)

---

Older:

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

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