Los dados de letras son comunes en los juegos de palabras. Puede ser divertido intentar deletrear palabras divertidas con dados de boggle, por ejemplo. Si agarras un puñado de dados, es probable que no puedas deletrear ciertas palabras. Este desafío es una generalización de esa idea.

Desafío

Dada una lista de dados que tienen al menos 1 cara y una palabra, su tarea es determinar si es posible deletrear esa palabra usando los dados dados (en cuyo caso, debería devolver un resultado verdadero). Solo se puede usar una letra de cada dado y un dado solo se puede usar una vez. No necesitas usar todos los dados dados.

Ejemplos

En un ejemplo trivial, con los dados [[A], [C], [T]] y la cadena CAT, el resultado es verdadero. BAT, por supuesto, devolvería falso ya que no hay dados con B en ellos

Si se le da [[A, E, I, O, U], [A, B, C, T], [N, P, R]] como el conjunto de dados, volvería verdadero para ART, TON y CUR , pero falso para CAT, EAT y PAN porque esas cadenas requieren reutilizar dados. También debería ser bastante obvio que CRAB no se puede deletrear con estos dados ya que no hay suficientes dados.

Si se le da [[A, B, C], [A, E, I], [E, O, U], [L, N, R, S, T]] como el conjunto de dados, usted podría deletrea CAT, BEE, BEAN, TEA, BEET y BAN, pero no podrás deletrear LONE, CAB, BAIL, TAIL, BAA o TON

Puede haber múltiplos del mismo dado. Si se le da [[A, B, C], [A, B, C], [A, B, C]], podría deletrear CAB, BAA, AAA, etc. pero obviamente nada sin A, B o C en ella.

Reglas

• No explotar las lagunas estándar
• Este es el código de golf , por lo que gana el código más corto.
• Puede suponer que tanto las palabras como los dados solo estarán formados por mayúsculas.
• Puede suponer que la palabra siempre tendrá al menos 1 letra y que siempre habrá al menos 1 dado.
• Puede suponer que un dado nunca tendrá más de una letra.
• La entrada y salida pueden estar en cualquier formato conveniente.

Brachylog , 5 bytes

∋ᵐ⊇pc

Pruébalo en línea!

Usamos la variable de entrada para los dados y la variable de salida para la palabra. Sale true.cuando es posible deletrear la palabra y de false.otra manera.

Explicación

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

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

Esta es una función anónima. Vinculado a algún identificador fse puede utilizar como f "ART" ["AEIOU", "ABCT", "NPR"], lo que produce True. Pruébalo en línea!

El equivalente no libre de puntos es

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

mapM idsobre una lista de listas usa la Monadinstancia de lista y puede verse como una opción no determinista . Así, por ejemplo, mapM id ["AB","123"]rendimientos ["A1","A2","A3","B1","B2","B3"].

Para cada una de esas combinaciones de dados, verificamos si la diferencia (\\)de la lista de la palabra dada y la combinación produce una lista vacía.

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

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

Pruébalo en línea!

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 cadena de comparación w[0]in x>0<f(...)es equivalente a: w[0]in x y x>0 y 0<f(...) .

El segundo de esos siempre es verdadero ( str> int) y el tercero de esos es equivalente a f(...), por lo que todo es una forma más corta de escribirw[0]in x and f(...)

JavaScript (ES6), 74 bytes

Toma información en la sintaxis de curry (w)(a), donde w es la palabra que estamos buscando y a es una lista de cadenas que describen los dados. Devuelve 0 o 1 .

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

Pruébalo en línea!

Comentado

Convertimos cada subconjunto de permutación de los dados en un patrón de expresión regular y los probamos contra la palabra objetivo.

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

Casco , 5 bytes

~V`¦Π

Pruébalo en línea!

Devuelve un valor distinto de cero si es posible deletrear la palabra, cero en caso contrario.

Explicación

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

@DomHastings guardó 2 bytes

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

Pruébalo en línea!

Entrada:

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

Salida:

0para una palabra que no está validada. Cualquier entero positivo para una palabra validada

¿Cómo?

Esta explicación analiza el código en el orden de ejecución, efectivamente de derecha a izquierda para esta línea.

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

Pruébalo en línea!

Asumiendo que hay suficientes dados

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

Pruébalo en línea!

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

Pruébalo en línea!

Jalea ,  10  9 bytes

-1 gracias a Erik the Outgolfer (use en wlugar de ẇ@>. <)

Œ!Œp€Ẏw€Ṁ

Un enlace diádico que acepta una lista de listas de caracteres a la izquierda (los dados) y una lista de caracteres a la derecha (la palabra) que devuelve 1 si es posible y 0 si no.

Pruébalo en línea! O ver el pruebas .

¿Cómo?

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

Algoritmo más rápido (también 9 bytes):

Un enlace diádico con el mismo formato de entrada que devuelve un entero positivo (verdadero) cuando sea posible y 0 (falsey) de lo contrario.

Œ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 , 192185135117111109 bytes

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

Pruébalo en línea!

-2 caracteres gracias a Giuseppe.

Pyth , 21 bytes

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

Banco de pruebas

.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