Can You Spell This Word With These Dice?

Question

Letter dice are common in word games. It can be fun to try to spell funny words with boggle dice, for instance. If you grab a handful of dice, chances are you won't be able to spell certain words. This challenge is a generalization of that idea.

Challenge

Given a list of dice which each have at least 1 face and a word, your task is to determine if it is possible to spell that word using the given dice (in which case, it should return a truthy result). Only one letter from each die can be used and a die can be used only once. You do not need to use all of the given dice.

Examples

In a trivial example, with the dice [[A], [C], [T]] and the string CAT, the result is true. BAT would, of course, return false since there are no dice with B on them

If given [[A, E, I, O, U], [A, B, C, T], [N, P, R]] as the set of dice, you would return true for ART, TON, and CUR, but false for CAT, EAT, and PAN because those strings require reusing dice. It should also be fairly obvious that CRAB cannot be spelled with these dice since there are not enough dice.

If given [[A, B, C], [A, E, I], [E, O, U], [L, N, R, S, T]] as the set of dice, you would be able to spell CAT, BEE, BEAN, TEA, BEET, and BAN, but you would not be able to spell LONE, CAB, BAIL, TAIL, BAA, or TON

There may be multiples of the same die. If given [[A, B, C], [A, B, C], [A, B, C]], you would be able to spell CAB, BAA, AAA, etc... but obviously nothing without A, B, or C in it.

Rules

• No exploiting standard loopholes
• This is code-golf, so the shortest code wins.
• You may assume that both words and dice will only be made up of capital letters.
• You may assume that the word will always be at least 1 letter long and that there will always be at least 1 die.
• You may assume that a die will never have more than one of the same letter.
• Input and output may be in any convenient format.

Answer 1

Brachylog, 5 bytes

∋ᵐ⊇pc

Try it online!

We use the input variable for the dice and the output variable for the word. It outputs true. when it's possible to spell the word and false. otherwise.

Explanation

∋ᵐ        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

Answer 2

Haskell, 48 44 bytes

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

This is an anonymous function. Bound to some identifier f it can be used as f "ART" ["AEIOU", "ABCT", "NPR"], which yields True. Try it online!

The non-point-free equivalent is

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

mapM id over a list of lists uses the Monad instance of list and can be seen as non-deterministic choice. Thus e.g. mapM id ["AB","123"] yields ["A1","A2","A3","B1","B2","B3"].

For each of those dice combinations, we check if the list difference (\\) of the given word and the combination yields an empty list.

Answer 3

Python 2, 82 bytes

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

Try it online!

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.

The comparison chain w[0]in x>0<f(...) is equivalent to: w[0]in x and x>0 and 0<f(...).

The second of those is always true (str > int) and the third of those is equivalent to f(...), so that the whole thing is a shorter way to write w[0]in x and f(...)

Answer 4

JavaScript (ES6), 68 bytes

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

Answer 5

JavaScript (ES6), 74 bytes

Takes input in currying syntax (w)(a), where w is the word we're looking for and a is a list of strings describing the dice. Returns 0 or 1.

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

Try it online!

Commented

We turn each subset-permutation of the dice into a regular expression pattern and test them against the target word.

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

Answer 6

Husk, 5 bytes

~V`¦Π

Try it online!

Returns a non-zero value if it's possible to spell the word, zero otherwise.

Explanation

~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

Answer 7

Perl 5 -plF, 48 46 bytes

@DomHastings saved 2 bytes

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

Try it online!

Input:

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

Output:

0 for a word that is not validated. Any positive integer for a word that is validated

How?

This explanation looks at the code in the order of execution, effectively right-to-left for this one-liner.

-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

Answer 8

JavaScript (Node.js), 98 bytes

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

Try it online!

Assuming there's enough dice

JavaScript (Node.js), 100 bytes

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

Try it online!

JavaScript (Node.js), 99 bytes

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

Try it online!

Answer 9

Jelly,  10  9 bytes

-1 thanks to Erik the Outgolfer (use w rather than ẇ@ >.<)

Œ!Œp€Ẏw€Ṁ

A dyadic link accepting a list of lists of characters on the left (the dice) and a list of characters on the right (the word) which returns 1 if possible and 0 if not.

Try it online! Or see the test-suite.

How?

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

---

Faster algorithm (also 9 bytes):

A dyadic link with the same input format which returns positive integer (truthy) when possible and 0 (falsey) otherwise.

Œ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

Answer 10

R, 192 185 135 117 111 109 bytes

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

Try it online!

-2 chars thanks to Giuseppe.

Answer 11

Pyth, 21 bytes

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

Test suite

Explanation:

.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