Les dés de lettres sont courants dans les jeux de mots. Il peut être amusant d'essayer d'épeler des mots drôles avec des dés de boggle, par exemple. Si vous attrapez une poignée de dés, il est probable que vous ne pourrez pas épeler certains mots. Ce défi est une généralisation de cette idée.

Défi

Étant donné une liste de dés qui ont chacun au moins 1 visage et un mot, votre tâche est de déterminer s'il est possible d'épeler ce mot en utilisant les dés donnés (dans ce cas, il devrait retourner un résultat véridique). Une seule lettre de chaque dé peut être utilisée et un dé ne peut être utilisé qu'une seule fois. Vous n'avez pas besoin d'utiliser tous les dés donnés.

Exemples

Dans un exemple trivial, avec les dés [[A], [C], [T]] et la chaîne CAT, le résultat est vrai. La BAT retournerait bien sûr faux car il n'y a pas de dés avec B dessus

Si donné [[A, E, I, O, U], [A, B, C, T], [N, P, R]] comme ensemble de dés, vous retourneriez vrai pour ART, TON et CUR , mais faux pour CAT, EAT et PAN car ces chaînes nécessitent la réutilisation des dés. Il devrait également être assez évident que CRAB ne peut pas être orthographié avec ces dés car il n'y a pas assez de dés.

Si on donnait [[A, B, C], [A, E, I], [E, O, U], [L, N, R, S, T]] comme ensemble de dés, vous seriez en mesure de épeler CAT, BEE, BEAN, TEA, BEET et BAN, mais vous ne pourrez pas épeler LONE, CAB, BAIL, TAIL, BAA ou TON

Il peut y avoir des multiples du même dé. Si donné [[A, B, C], [A, B, C], [A, B, C]], vous seriez en mesure d'épeler CAB, BAA, AAA, etc ... mais évidemment rien sans A, B ou C dedans.

Règles

• Aucune exploitation des failles standard
• C'est le code-golf , donc le code le plus court l'emporte.
• Vous pouvez supposer que les mots et les dés ne seront composés que de majuscules.
• Vous pouvez supposer que le mot comptera toujours au moins 1 lettre et qu'il y aura toujours au moins 1 dé.
• Vous pouvez supposer qu'un dé n'aura jamais plus d'une même lettre.
• L'entrée et la sortie peuvent être dans n'importe quel format pratique.

Brachylog , 5 octets

∋ᵐ⊇pc

Essayez-le en ligne!

Nous utilisons la variable d'entrée pour les dés et la variable de sortie pour le mot. Il sort true.quand il est possible d'épeler le mot et false.autrement.

Explication

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

Haskell , 48 44 octets

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

Il s'agit d'une fonction anonyme. Lié à un identifiant, fil peut être utilisé comme f "ART" ["AEIOU", "ABCT", "NPR"], ce qui donne True. Essayez-le en ligne!

L'équivalent non ponctuel est

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

mapM idsur une liste de listes utilise l' Monadinstance de liste et peut être considéré comme un choix non déterministe . Ainsi, par exemple, les mapM id ["AB","123"]rendements ["A1","A2","A3","B1","B2","B3"].

Pour chacune de ces combinaisons de dés, nous vérifions si la différence (\\)de liste du mot donné et de la combinaison donne une liste vide.

JavaScript (ES6), 68 octets

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 octets

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

Essayez-le en ligne!

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.

La chaîne de comparaison w[0]in x>0<f(...)est équivalente à: w[0]in x et x>0 et 0<f(...) .

Le second est toujours vrai ( str> int) et le troisième est équivalent à f(...), de sorte que le tout est une manière plus courte d'écrirew[0]in x and f(...)

JavaScript (ES6), 74 octets

Prend une entrée dans la syntaxe de curry (w)(a), où w est le mot que nous recherchons et a est une liste de chaînes décrivant les dés. Renvoie 0 ou 1 .

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

Essayez-le en ligne!

Commenté

Nous transformons chaque permutation de sous-ensemble des dés en un modèle d'expression régulière et les testons par rapport au mot cible.

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

Husk , 5 octets

~V`¦Π

Essayez-le en ligne!

Renvoie une valeur non nulle s'il est possible d'épeler le mot, zéro sinon.

Explication

~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 octets

@DomHastings a enregistré 2 octets

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

Essayez-le en ligne!

Contribution:

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

Production:

0pour un mot non validé. Tout entier positif pour un mot validé

Comment?

Cette explication examine le code dans l'ordre d'exécution, en fait de droite à gauche pour ce 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

JavaScript (Node.js) , 98 octets

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

Essayez-le en ligne!

En supposant qu'il y ait suffisamment de dés

JavaScript (Node.js) , 100 octets

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

Essayez-le en ligne!

JavaScript (Node.js) , 99 octets

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

Essayez-le en ligne!

Gelée ,  10  9 octets

-1 grâce à Erik l'Outgolfer (utilisez wplutôt que ẇ@>. <)

Œ!Œp€Ẏw€Ṁ

Un lien dyadique acceptant une liste de listes de caractères à gauche (les dés) et une liste de caractères à droite (le mot) qui renvoie 1 si possible et 0 sinon.

Essayez-le en ligne! Ou consultez la suite de tests .

Comment?

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

Algorithme plus rapide (également 9 octets):

Un lien dyadique avec le même format d'entrée qui renvoie un entier positif (véridique) lorsque cela est possible et 0 (falsey) sinon.

Œ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 135 117 111 109 octets

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

Essayez-le en ligne!

-2 caractères grâce à Giuseppe.

Pyth , 21 octets

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

Suite de tests

.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