Czy potrafisz przeliterować to słowo tymi kostkami?

20

Kostki literowe są powszechne w grach słownych. Na przykład zabawne może być pisownia śmiesznych słów za pomocą kostek do gry. Jeśli złapiesz garść kości, są szanse, że nie będziesz w stanie przeliterować niektórych słów. To wyzwanie jest uogólnieniem tego pomysłu.

Wyzwanie

Biorąc pod uwagę listę kości, z których każda ma co najmniej 1 twarz i słowo, Twoim zadaniem jest ustalenie, czy możliwe jest przeliterowanie tego słowa za pomocą danej kości (w takim przypadku powinien on zwrócić prawdziwy wynik). Można użyć tylko jednej litery z każdej kości, a kości można użyć tylko raz. Nie musisz używać wszystkich podanych kości.

Przykłady

W trywialnym przykładzie z kostkami [[A], [C], [T]] i ciągiem CAT wynik jest prawdziwy. BAT oczywiście zwróciłoby wartość false, ponieważ nie ma na nich kości z literą B.

Jeśli podano [[A, E, I, O, U], [A, B, C, T], [N, P, R]] jako zestaw kostek, zwróciłbyś wartość true dla ART, TON i CUR , ale fałsz dla CAT, EAT i PAN, ponieważ te łańcuchy wymagają ponownego użycia kości. Powinno być również dość oczywiste, że CRAB nie może zostać przeliterowany za pomocą tych kości, ponieważ nie ma wystarczającej liczby kości.

Jeśli podano [[A, B, C], [A, E, I], [E, O, U], [L, N, R, S, T]] jako zestaw kości, byłbyś w stanie przeliteruj CAT, BEE, BEAN, TEA, BEET i BAN, ale nie będziesz w stanie przeliterować LONE, CAB, BAIL, TAIL, BAA lub TON

Mogą istnieć wielokrotności tej samej kości. Jeśli podano [[A, B, C], [A, B, C], [A, B, C]], byłbyś w stanie przeliterować CAB, BAA, AAA itp., Ale oczywiście nic bez A, B lub C.

Zasady

  • Brak wykorzystania standardowych luk
  • To jest , więc wygrywa najkrótszy kod.
  • Możesz założyć, że zarówno słowa, jak i kości składają się wyłącznie z wielkich liter.
  • Możesz założyć, że słowo zawsze będzie miało co najmniej 1 literę i że zawsze będzie co najmniej 1 kostka.
  • Możesz założyć, że kostka nigdy nie będzie miała więcej niż jednej litery.
  • Dane wejściowe i wyjściowe mogą być w dowolnym dogodnym formacie.
Wołowina
źródło
Po co tworzyć nowe tagi?
user202729
Czy można wziąć listę (wektor) znaków jako dane wejściowe (podobny format jak kostka do gry)? Pytanie o znajomego, który chciałby zaoszczędzić 27 bajtów.
JayCe
1
@JayCe „Dane wejściowe i wyjściowe mogą być w dowolnym dogodnym formacie”, więc tak.
Beefster

Odpowiedzi:

12

Brachylog , 5 bajtów

∋ᵐ⊇pc

Wypróbuj online!

Używamy zmiennej wejściowej dla kości i zmiennej wyjściowej dla słowa. Wypisuje się, true.gdy można przeliterować słowo i false.inaczej.

Wyjaśnienie

∋ᵐ        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
Fatalizować
źródło
8

Haskell , 48 44 bajtów

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

To anonimowa funkcja. Związany z jakimś identyfikatorem fmoże być użyty jako f "ART" ["AEIOU", "ABCT", "NPR"], co daje True. Wypróbuj online!

Odpowiednikiem niepunktowym jest

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

mapM idnad listą list korzysta z Monadinstancji list i może być postrzegana jako wybór niedeterministyczny . Tak więc np . mapM id ["AB","123"]Plony ["A1","A2","A3","B1","B2","B3"].

Dla każdej z tych kombinacji kości sprawdzamy, czy różnica (\\)listowa danego słowa i kombinacji daje pustą listę.

Laikoni
źródło
@LuisMendo Dzięki za wskazanie! Naprawiono przejście na inną metodę, która zakończyła się oszczędzeniem 4 bajtów.
Laikoni
6

JavaScript (ES6), 68 bajtów

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

Neil
źródło
1
@ RickHitchcock kończy się niepowodzeniem EEE.
Neil
6

Python 2 , 82 bajty

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

Wypróbuj 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.

Łańcuch porównanie w[0]in x>0<f(...)jest równoznaczne z: w[0]in x i x>0 i 0<f(...) .

Drugi z nich jest zawsze prawdziwy ( str> int), a trzeci z nich jest równoważny f(...), więc całość jest krótszym sposobem na napisaniew[0]in x and f(...)

Lynn
źródło
5

JavaScript (ES6), 74 bajty

Trwa wejście w składni currying (w)(a), gdzie w jest słowo szukamy i to lista ciągów opisujących kości. Zwraca 0 lub 1 .

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

Wypróbuj online!

Skomentował

Przekształcamy każdą podzestaw permutacji kostek we wzór wyrażeń regularnych i testujemy je pod kątem słowa docelowego.

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()
Arnauld
źródło
3

Łuska , 5 bajtów

~V`¦Π

Wypróbuj online!

Zwraca wartość niezerową, jeśli można przeliterować słowo, w przeciwnym razie zero.

Wyjaśnienie

~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
Fyr
źródło
2

Perl 5 -plF , 48 46 bajtów

@DomHastings zapisał 2 bajty

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

Wypróbuj online!

Wkład:

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

Wynik:

0dla słowa, które nie jest sprawdzone. Każda dodatnia liczba całkowita dla sprawdzonego słowa

W jaki sposób?

To objaśnienie patrzy na kod w kolejności wykonywania, skutecznie od prawej do lewej dla tego jednowierszowego.

-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
Xcali
źródło
1

JavaScript (Node.js) , 98 bajtów

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

Wypróbuj online!

Zakładając, że jest wystarczająco dużo kości

JavaScript (Node.js) , 100 bajtów

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

Wypróbuj online!

JavaScript (Node.js) , 99 bajtów

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

Wypróbuj online!

l4m2
źródło
1

Galaretka ,  10  9 bajtów

-1 dzięki Erikowi Outgolfer (użyj wzamiast ẇ@>. <)

Œ!Œp€Ẏw€Ṁ

Dyadyczny link akceptujący listę list znaków po lewej stronie (kostki) i listę znaków po prawej stronie (słowo), która zwraca 1, jeśli to możliwe, i 0, jeśli nie.

Wypróbuj online! Lub zobacz pakiet testowy .

W jaki sposób?

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

Szybszy algorytm (także 9 bajtów):

Diadadicowe łącze z tym samym formatem wejściowym, które zwraca dodatnią liczbę całkowitą (prawda), jeśli to możliwe, i 0 (falsey) w przeciwnym razie.

Œ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
Jonathan Allan
źródło
1

R , 192 185 135 117 111 109 bajtów

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

Wypróbuj online!

-2 znaki dzięki Giuseppe.

JayCe
źródło
To się nie powiedzie, jeśli słowo ma mniej liter niż kostka.
Giuseppe,
Myślę, że możesz go zapisać kosztem 21 bajtów, spróbuj tutaj
Giuseppe
@Giuseppe Uratowałeś dzień!
JayCe
nie potrzebujeszF=
Giuseppe
0

Pyth , 21 bajtów

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

Zestaw testowy

Wyjaśnienie:
.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
hakr14
źródło