Буквенные кубики распространены в играх в слова. Например, может быть забавно пытаться произносить смешные слова с ошеломляющими кубиками. Если вы возьмете несколько кубиков, скорее всего, вы не сможете произнести определенные слова по буквам. Этот вызов является обобщением этой идеи.

Вызов

Учитывая список игральных костей, у каждого из которых есть по крайней мере 1 лицо и слово, ваша задача - определить, возможно ли написание этого слова с использованием данного кубика (в этом случае он должен вернуть правдивый результат). Можно использовать только одну букву из каждого кубика, а кубик можно использовать только один раз. Вам не нужно использовать все данные кости.

Примеры

В тривиальном примере с кубиками [[A], [C], [T]] и строкой CAT результат равен true. BAT, конечно, вернет false, поскольку на них нет кубиков с буквой B

Если дать [[A, E, I, O, U], [A, B, C, T], [N, P, R]] в качестве набора игральных костей, вы вернете true для ART, TON и CUR , но false для CAT, EAT и PAN, потому что эти строки требуют многократного использования игральных костей. Также должно быть достаточно очевидно, что CRAB нельзя записать с помощью этих кубиков, так как их недостаточно.

Если дать [[A, B, C], [A, E, I], [E, O, U], [L, N, R, S, T]] в качестве набора игральных костей, вы сможете заклинание CAT, BEE, BEAN, TEA, BEET и BAN, но вы не сможете произнести LONE, CAB, BAIL, TAIL, BAA или TON

Там могут быть кратные одного и того же кубика. Если дать [[A, B, C], [A, B, C], [A, B, C]], вы сможете написать CAB, BAA, AAA и т. Д. ... но, очевидно, ничего без A, B или C в нем.

правила

• Не использовать стандартные лазейки
• Это код-гольф , поэтому выигрывает самый короткий код.
• Вы можете предположить, что и слова, и кости будут состоять только из заглавных букв.
• Вы можете предположить, что слово всегда будет длиной не менее 1 буквы и что всегда будет хотя бы 1 кубик.
• Вы можете предположить, что у кубика никогда не будет больше, чем одно и то же письмо.
• Ввод и вывод могут быть в любом удобном формате.

Брахилог , 5 байт

∋ᵐ⊇pc

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

Мы используем входную переменную для игры в кости и выходную переменную для слова. Это выводит, true.когда возможно написание слова и false.иначе.

объяснение

∋ᵐ        Map element: Take one side from each die
  ⊇       Subset
   p      Permute
    c     Concatenate into a string: will only succeed if it results in the output word

Хаскелл , 48 44 байта

import Data.List
(.mapM id).any.(null.).(\\)

Это анонимная функция. Привязанный к некоторому идентификатору, fон может быть использован как f "ART" ["AEIOU", "ABCT", "NPR"], что даетTrue . Попробуйте онлайн!

Неточечный эквивалент

f word dice = any(\s -> null $ word\\s) $ mapM id dice

mapM idнад списком списков использует Monadэкземпляр списка и может рассматриваться как недетерминированный выбор . Таким образом, например, mapM id ["AB","123"]урожайность ["A1","A2","A3","B1","B2","B3"].

Для каждой из этих комбинаций игральных костей мы проверяем, (\\)дает ли разница в списке данного слова и комбинации пустой список.

JavaScript (ES6), 68 байт

f=([c,...w],a)=>!c||a.some((d,i)=>d.match(c)&&f(w,a.filter(_=>i--)))

<div oninput=o.textContent=f(i.value,d.value.split`\n`)>
<textarea id=d rows=9>
ABC
AEI
EOU
LNRST
</textarea>
<br>
<input id=i value=BEAN>
<pre id=o>true

Python 2 , 82 байта

f=lambda d,w:w==''or any(w[0]in x>0<f(d[:i]+d[i+1:],w[1:])for i,x in enumerate(d))

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

f=lambda d,w:w==''                                                                 # Base case: we can spell '' with any dice.
                  or any(                                 for i,x in enumerate(d)) # Otherwise, we check if there is some die x such that...
                         w[0]in x                                                  # the first letter is on this die,
                                 >0<                                               # and
                                    f(d[:i]+d[i+1:],w[1:])                         # we can spell the rest of the word with the rest of the dice.

Цепочка сравнения w[0]in x>0<f(...)эквивалентна: w[0]in x и x>0 и 0<f(...) .

Второе из них всегда верно ( str> int), а третье эквивалентно f(...), так что все это более короткий способ записиw[0]in x and f(...)

JavaScript (ES6), 74 байта

Принимает ввод в синтаксисе карри (w)(a), где w - это слово, которое мы ищем, а a - список строк, описывающих кости. Возвращает 0 или 1 .

w=>P=(a,m='')=>w.match(m)==w|a.some((w,i)=>P(a.filter(_=>i--),m+`[${w}]`))

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

комментарии

Мы превращаем каждую подмножество перестановок кубиков в шаблон регулярного выражения и проверяем их на соответствие целевому слову.

w =>                        // w = target word
  P =                       // P = recursive function taking:
    (a,                     //   a[] = list of dice
        m = '') =>          //   m   = search pattern
    w.match(m) == w |       // force a truthy result if w matches m
    a.some((w, i) =>        // for each word w at position i in a[]:
      P(                    //   do a recursive call:
        a.filter(_ => i--), //     using a copy of a[] without the current element
        m + `[${w}]`        //     and adding '[w]' to the search pattern
      )                     //   end of recursive call
    )                       // end of some()

Шелуха , 5 байт

~V`¦Π

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

Возвращает ненулевое значение, если можно записать слово, иначе ноль.

объяснение

~V`¦Π  Arguments: word [Char], dice [[Char]]
 V     Checks if any element of a list (2) satisfies a predicate (1)
~      Composes both arguments of the above function
  `¦     (1) Is the word a subset of the element?
    Π    (2) Cartesian product of the dice list

Perl 5 -plF , 48 46 байт

@DomHastings сохранил 2 байта

$_=grep/@{[sort@F]}/,map"@{[sort/./g]}",glob<>

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

Входные данные:

word               # The word to validate
{A,B,C}{D,E,F}     # Each die is surrounded by braces, commas between the letters

Выход:

0за слово, которое не подтверждено. Любое положительное целое число для слова, которое проверено

Как?

Это объяснение рассматривает код в порядке выполнения, фактически справа налево для этой строки.

-F             # The first line of input is automatically split by the -F command option into the @F array.
glob<>         # Read the rest of the input and enumerate all of the permutations of it
map"@{[sort/./g]}",  # Split the permutation into separate letters, sort them and put them back together
/@{[sort@F]}/, # use the sorted letters of the target to match against
$_=grep        # check all of those permutations to see if the desired word is in them
-p             # Command line option to output the contents of $_ at the end

JavaScript (Node.js) , 98 байт

f=(s,d,u=[])=>d<1?s.every(t=>u.pop().match(t)):d.some((x,i)=>f(s,e=[...d],[...u,x],e.splice(i,1)))

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

Предполагая, что есть достаточно кости

JavaScript (Node.js) , 100 байт

f=(s,d,u=[''])=>d<1?s.every(t=>u.pop().match(t)):d.some((x,i)=>f(s,e=[...d],[...u,x],e.splice(i,1)))

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

JavaScript (Node.js) , 99 байт

s=>f=(d,u=[''])=>d<1?s.every(t=>u.pop().match(t)):d.some((x,i)=>f(e=[...d],[...u,x],e.splice(i,1)))

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

Желе ,  10  9 байт

-1 спасибо Эрику-аутголферу (используйте wвместо ẇ@>. <)

Œ!Œp€Ẏw€Ṁ

Диадическая ссылка, принимающая список списков символов слева (кубик) и список символов справа (слово), который возвращает 1, если возможно, и 0, если нет.

Попробуйте онлайн! Или посмотрите набор тестов .

Как?

Œ!Œp€Ẏw€Ẹ - Link: list of lists of characters Dice, list of characters Word
Œ!        - all permutations of the dice (i.e. all ways to order the dice)
  Œp€     - Cartesian product of €ach (i.e. all ways to roll each ordering)
     Ẏ    - tighten (i.e. all ordered ways to roll the dice)
       €  - for each:
      w   -   first index (of sublist W) in the result (positive if there, 0 otherwise)
        Ẹ - any truthy? (1 if it is possible to roll the word, 0 otherwise)

Более быстрый алгоритм (также 9 байт):

Двоичная ссылка с тем же форматом ввода, которая возвращает положительное целое число (истина), когда это возможно, и 0 (ложь) в противном случае.

Œpf€Ṣ€ċṢ} - Link: list of lists of characters Dice, list of characters Word
Œp        - Cartesian product of the dice (all rolls of the dice)
  f€      - filter keep for €ach (keep the rolled letters if they are in the word)
    Ṣ€    - sort €ach result
       Ṣ} - sort Word
      ċ   - count occurrences

R , 192 185 135 117 111 109 байт

function(x,...)s(x)%in%apply(expand.grid(lapply(list(...),c,"")),1,s)
s=function(x)paste(sort(x),collapse="")

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

-2 символа благодаря Джузеппе.

Pyth , 21 байт

.Em}eQdsm.ps.nd.U*bZh

Тестирование

.Em}eQdsm.ps.nd.U*bZhQ # Code with implicit variables
.E                     # Print whether any of
       sm.ps  d        # all positive length permutations of each element in
        m   .nd.U*bZhQ # the Cartesian product of the list of dice
  m}eQd                # contain the target word