26
\$\begingroup\$

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 , so may the shortest program that helps me to always beat my wife wins! :)

\$\endgroup\$
  • \$\begingroup\$ How long are the words in the word list guaranteed to be? \$\endgroup\$ – Neil Jun 17 '17 at 14:25
  • 2
    \$\begingroup\$ In actual license plates, letter Q is not allowed either; and W is, although not a proper Spanish letter \$\endgroup\$ – Luis Mendo Jun 17 '17 at 14:31
  • 2
    \$\begingroup\$ May we assume the words in the list and the three letters will be all in one case? \$\endgroup\$ – Jonathan Allan Jun 17 '17 at 14:39
  • 1
    \$\begingroup\$ @LuisMendo W has been a Spanish letter since 1969. \$\endgroup\$ – walen Jun 19 '17 at 7:22
  • 1
    \$\begingroup\$ @walen That's why I said "proper" :-) It exists in Spanish, but is feels foreign \$\endgroup\$ – Luis Mendo Jun 19 '17 at 8:47

15 Answers 15

7
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ 3ù #keep only those of length 3 why do you need this? \$\endgroup\$ – Leo Jun 17 '17 at 15:44
  • 1
    \$\begingroup\$ @Leo: I don't, that was silly of me. Thanks :) \$\endgroup\$ – Emigna Jun 17 '17 at 15:45
6
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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!

\$\endgroup\$
  • 2
    \$\begingroup\$ The number plate should be a string, not an array. But you don´t need the modifier. \$\endgroup\$ – Titus Jun 17 '17 at 17:42
  • \$\begingroup\$ @Titus fixed !! \$\endgroup\$ – Jörg Hülsermann Jun 17 '17 at 19:01
  • \$\begingroup\$ You can suppose the case will always be the same in both the word list and the three consonants. - no need for the regex modifier. Have you tried wordwrap instead of join(str_split())? \$\endgroup\$ – Titus Jun 19 '17 at 11:27
  • \$\begingroup\$ @Titus good idea \$\endgroup\$ – Jörg Hülsermann Jun 19 '17 at 11:49
5
\$\begingroup\$

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))
\$\endgroup\$
  • 1
    \$\begingroup\$ If I understand your explanation correctly, this would refuse a word like "borracho" for a sequence of consonants of "brc", because "brc" is not a substring of "brrc" \$\endgroup\$ – Leo Jun 17 '17 at 15:37
  • \$\begingroup\$ @Leo ah, yes good catch I think that it would fail... \$\endgroup\$ – Jonathan Allan Jun 17 '17 at 15:38
  • \$\begingroup\$ @Leo - well it's fixed (checks "exists in" for the entire power-set of each word) but it may not be fully golfed... \$\endgroup\$ – Jonathan Allan Jun 17 '17 at 15:46
5
\$\begingroup\$

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                       
\$\endgroup\$
  • \$\begingroup\$ @JonathanAllan: Fixed! Thanks for pointing that out. \$\endgroup\$ – Maria Jun 17 '17 at 15:26
  • 1
    \$\begingroup\$ @JonathanAllan: It looks like he edited the question to clarify that it should return an empty string in that case. I've edited my answer accordingly. \$\endgroup\$ – Maria Jun 17 '17 at 15:40
  • 1
    \$\begingroup\$ We have a sort-by meta operator in D, so u can replace olN with lD \$\endgroup\$ – Maltysen Jun 19 '17 at 11:33
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ You can replace the rightmost map and the filter with a list comprehension. As you already have Data.List in scope, you can use sortOn length and pick the head to find the element with minimal length. Finally, make y an infix function. All this makes f and k superfluous: l#w=sortOn length[p|p<-w,isInfixOf l$filter(`elem`l)p]!!0. \$\endgroup\$ – nimi Jun 17 '17 at 16:50
  • \$\begingroup\$ you're right! I just started golfing! Thanks! \$\endgroup\$ – Davide Spataro Jun 17 '17 at 17:23
  • 1
    \$\begingroup\$ One more: if you switch the import to Data.Lists, you can use argmin instead of sortOnand save the !!0: l#w=argmin length[...]. Data.Lists has many nice functions \$\endgroup\$ – nimi Jun 17 '17 at 17:42
3
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ If I insert "adsd" into your list, your program fails to find it. The first character to find does not need to be the first in the word. \$\endgroup\$ – Charlie Jun 17 '17 at 16:05
  • \$\begingroup\$ @CarlosAlejo The input needs a trailing newline, works ok then: Try it online!. That did catch me off guard though, as the <<< operator adds that in for me at command line! \$\endgroup\$ – Dom Hastings Jun 17 '17 at 16:39
3
\$\begingroup\$

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'

\$\endgroup\$
  • \$\begingroup\$ c=>l=>l.sort((a,b)=>a[b.length]&&1).find(w=>w.match(c.split``.join`.*`)) for 72, I think \$\endgroup\$ – LarsW Jun 17 '17 at 14:49
  • \$\begingroup\$ @LarsW Indeed, thanks! However I've chosen another approach to comply with the new rule: or an empty string if no words match the pattern of three consonants. \$\endgroup\$ – Arnauld Jun 17 '17 at 14:54
3
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! This looks like a snippet where the input is in hardcoded variables. Answers need to be either full programs or callable functions. You can have a look at this (or other R answers) for possible I/O methods. \$\endgroup\$ – Martin Ender Feb 28 '18 at 21:01
2
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I can't decide if those are three belly buttons or three breasts. \$\endgroup\$ – Charlie Jun 17 '17 at 19:14
  • \$\begingroup\$ @CarlosAlejo Are you thinking of Eccentrica Gallumbits by any chance? \$\endgroup\$ – Neil Jun 17 '17 at 19:17
  • \$\begingroup\$ I was thinking of the alien from Total Recall, but Eccentrica could be also an option... :) \$\endgroup\$ – Charlie Jun 17 '17 at 19:20
  • 2
    \$\begingroup\$ @CarlosAlejo Apparently Mary is a homage to Eccentrica Gallumbits. \$\endgroup\$ – Neil Jun 17 '17 at 19:27
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ 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;} \$\endgroup\$ – Nevay Mar 18 '18 at 8:26
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.