^{Этот вопрос основан на вопросе, который я задал на испанском языке . Да, я попросил алгоритм на испанском языке. :)}

В Испании нынешние номерные знаки имеют такую ​​схему:

1234 XYZ

где XYZ - три согласных, взятых из полного набора испанских согласных (я думаю, кроме «С»).

Иногда, путешествуя с моей женой, мы играем в игру. Когда мы видим номерной знак, мы берем три его согласные и пытаемся сформировать слово, содержащее эти три согласных, которые появляются в том же порядке, что и номерной знак. Примеры (на испанском):

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

Победителем становится тот, кто использует наименьшее количество символов, как вы можете видеть в последнем примере.

Соревнование

Напишите самую короткую программу или функцию, которая получает список слов и набор из трех согласных и находит самое короткое слово в списке, который содержит три согласных в том же порядке. Для целей этой игры случай не имеет значения.

• Ввод для списка слов (первый параметр) будет массив вашего stringтипа языка . Второй параметр (три согласные) будет другим string. Если это лучше для вашего языка, рассмотрите stringс тремя согласными последний пункт всего списка параметров. Выходной будет другой string.
• Слова в списке слов не будут выдуманными или бесконечными словами, они будут словами, которые появляются в любом стандартном словаре. Если вам нужен предел, предположим, что ни одно слово в списке не будет длиннее 50 символов.
• Если есть несколько слов с одинаковой длиной, которые могут быть правильным ответом, вы можете вернуть любое из них. Просто убедитесь, что вы возвращаете только одно слово или пустую строку, если никакие слова не соответствуют шаблону трех согласных.
• Вы можете повторять согласные в группе, поэтому допустимыми значениями для этих трех согласных являются FLRи GGG.
• Испанские согласные точно такие же, как английские, с добавлением "С". Гласные совпадают с добавлением ударных гласных: «áéíóúü». Никаких других отметок, таких как "-" или "'", не будет.
• Вы можете предположить, что регистр всегда будет одинаковым как в списке слов, так и в трех согласных.

Если вы хотите проверить свой алгоритм на реальной коллекции испанских слов, вы можете загрузить файл (15,9 МБ) из Dropbox с более чем миллионом слов.

Контрольные примеры

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'

Это код-гольф , поэтому, может быть, победит самая короткая программа, которая всегда побеждает мою жену! :)

05AB1E , 10 8 байт

Сохранено 2 байта благодаря Лео

ʒæså}éR`

Попробуйте онлайн!

объяснение

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

В headконце я бы использовал сохранение байта, но это вывело бы пустой список, если совпадения нет.

MATL , 30 29 байт

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

Попробуйте онлайн!

объяснение

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 байт

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

Попробуйте онлайн!

Желе ,  12 11  10 байт

ŒPċðÐfLÞḣ1

Полная программа, которая принимает список списков строчных букв (слов) и список строчных букв (букв) и печатает первое из самых коротких слов, которые содержат подпоследовательность, равную буквам (или ничего, если их нет) ).

Попробуйте онлайн!

Как?

Œ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 байт

h+f/yTQlDEk

-1 Спасибо Малтысену.

Принимает 2 строки в качестве ввода. 1-й - это трехбуквенная строка (строчные буквы), а 2-й - строчный список слов.

Попробуй здесь

Объяснение:

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)

Старое 19-байтовое решение:

h+olNf/-T"aeiou"QEk                       

Brachylog v2, 11 байт

tlᵒ∋.&h⊆.∨Ẹ

Попробуйте онлайн!

Функция представления. (Ссылка TIO имеет аргумент командной строки для запуска функции, как если бы она была полной программой.)

объяснение

Просто прямой перевод спецификации снова ...

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

На самом деле вы можете почти ответить с помощью h⊆.&t∋- замена порядка оценки означает, что Brachylog выберет самый короткий ответ по умолчанию (как первое ограничение, которое он видит ⊆, который имеет довольно удобный «самый короткий» как разрыв связи по умолчанию) - но в этом случае Brachylog Алгоритм оценки, к сожалению, может зайти в бесконечный цикл, если ответ не найден. Таким образом, почти половина ответа посвящена рассмотрению случая отсутствия надлежащего ответа. Даже тогда lᵒпереопределение тай-брейка (что технически является своего рода, используя∋привязка по умолчанию предпочтительных элементов ближе к началу списка) составляет всего два байта; остальные три возникают из-за необходимости выводить пустую строку, в частности, когда вывод не найден, в отличие от значения по умолчанию в брахилоге «без решений» (потому что финал .будет неявным, если мы не будем следовать за ним ∨).

Интересно, что в Brachylog ранее была реализована функция, которая бы сохраняла здесь байт. В какой -то момент, вы можете извлечь элементы из входного аргумента , используя ?₁, ?₂и т.д. синтаксис; это позволит вам переставить программу tlᵒ∋.⊇?₁∨Ẹ, что составляет всего 10 байт. К сожалению, используемая реализация на самом деле не работала (и приводила к сбою многих других работающих программ), поэтому она была отменена. Вы можете думать о программе как о «концептуально» длиной 10 байт.

Haskell 129 125 74 байта

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

КРЕДИТ @nimi

Perl, 53 байта

Код 48 байтов + 5 для -paF.

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

Это имеет преимущество того факта , что списки интерполированные в m//оператора использовать $"переменные , которая изменяет исходную строку ввода от psrдо , p.*s.*rкоторый затем соответствуют для каждого дополнительного слова и сортируются на length.

Попробуйте онлайн!

JavaScript (ES6), 77 75 72 байта

Принимает 3 согласных cи список слов lв карри синтаксиса (c)(l). Оба входа ожидаются в одном и том же случае.

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

Контрольные примеры

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 байт

Первый раз в гольф! Я уверен, что это может быть сжато как-то

Принимает строку x и символьный вектор y возможных входных данных

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

Попробуйте онлайн!

Изменить: Моя версия была 135, спасибо Scrooble за -34!

Сетчатка , 58 байт

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

Попробуйте онлайн! Принимает три согласных в одной строке, а затем список слов во всех последующих строках. Объяснение: Oсортирует список, ¶.+исключая первую строку с #числовым $вводом по $.&длине. Затем ищется совпадение для строки, которая включает три согласных по порядку. Если подходящая строка существует, чем последняя, ​​т.е. самая короткая, такая строка становится выходной, в противном случае выходные данные являются пустыми. ?-s:Временно выключает эффект , s`так что только одна линия соответствует.

Пип , 17 байт

@:qJ`.*`N_FI#_SKg

Принимает список слов в качестве аргументов командной строки и согласные от stdin. Попробуйте онлайн!

объяснение

                   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 байт

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 байт благодаря @Nevay .

Объяснение:

Попробуйте онлайн.

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 байт

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

Попробуйте онлайн!

MATL , 28 27 26 байт

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

Попробуйте онлайн!

x- Неявно взять первый ввод (строка с тремя буквами) и удалить его. Автоматически копируется в буфер обмена G, уровень 1 (эта часть была вдохновлена ответом @Luis Mendo ).

" - Неявно взять второй вход (массив слов слов), итерировать по нему.

l - Нажмите 1, чтобы использовать позже

1G - Нажмите первый ввод (скажем, «PSR»)

@g - выдвинуть текущее слово как массив

3XN- nchoosek- Получить все комбинации из 3 букв из слова

Xm- Проверьте, является ли код номерного знака «psr» одной из этих комбинаций. Возвращает 0 для false и 1 для true.

/- Деление 1 (что мы выдвинули ранее) на этот результат. Изменяет 0 Infс на

@gn - получить длину текущего слова

*- Умножьте длину на результат деления. Возвращает длину как она есть, когда слово содержит 3 символа, в противном случае возвращаетInf

v - вертикально объединить эти результаты в один массив

] - замкнутый цикл

&X< - получить индекс минимального значения из этого массива, т. е. индекс, в котором было найдено слово, содержащее буквы минимальной длины

2G - Нажмите второй вход снова

w - вернуть индекс min на вершину стека

) - Индекс в массив слов с индексом min, возвращая правильное слово с минимальной длиной

(Неявный вывод.)

Старшая:

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

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