Bisakah Anda Mengeja Kata Ini Dengan Dadu Ini?

20

Letter dadu adalah hal biasa di permainan kata. Misalnya, bisa mengeja kata-kata lucu dengan boggle dadu. Jika Anda meraih beberapa dadu, kemungkinan Anda tidak akan bisa mengeja kata-kata tertentu. Tantangan ini adalah generalisasi dari gagasan itu.

Tantangan

Diberikan daftar dadu yang masing-masing memiliki setidaknya 1 wajah dan sebuah kata, tugas Anda adalah untuk menentukan apakah mungkin untuk mengeja kata itu menggunakan dadu yang diberikan (dalam hal ini, itu harus mengembalikan hasil yang benar). Hanya satu huruf dari setiap dadu dapat digunakan dan dadu hanya dapat digunakan satu kali. Anda tidak perlu menggunakan semua dadu yang diberikan.

Contohnya

Dalam contoh sepele, dengan dadu [[A], [C], [T]] dan string CAT, hasilnya benar. BAT akan, tentu saja, mengembalikan false karena tidak ada dadu dengan B pada mereka

Jika diberikan [[A, E, I, O, U], [A, B, C, T], [N, P, R]] sebagai set dadu, Anda akan mengembalikan true untuk ART, TON, dan CUR , tetapi salah untuk CAT, EAT, dan PAN karena string tersebut membutuhkan dadu yang digunakan kembali. Seharusnya juga cukup jelas bahwa CRAB tidak dapat dieja dengan dadu ini karena tidak ada cukup dadu.

Jika diberikan [[A, B, C], [A, E, I], [E, O, U], [L, N, R, S, T]] sebagai himpunan dadu, Anda dapat mengeja CAT, BEE, BEAN, TEH, BEET, dan BAN, tetapi Anda tidak akan bisa mengeja LONE, CAB, BAIL, TAIL, BAA, atau TON

Mungkin ada kelipatan dari dadu yang sama. Jika diberikan [[A, B, C], [A, B, C], [A, B, C]], Anda akan dapat mengeja CAB, BAA, AAA, dll ... tapi jelas tidak ada yang tanpa A, B, atau C di dalamnya.

Aturan

  • Tidak mengeksploitasi celah standar
  • Ini , jadi kode terpendek menang.
  • Anda dapat berasumsi bahwa kata dan dadu hanya terdiri dari huruf kapital.
  • Anda mungkin berasumsi bahwa kata itu akan selalu setidaknya 1 huruf dan bahwa akan selalu ada setidaknya 1 mati.
  • Anda mungkin berasumsi bahwa dadu tidak akan pernah memiliki lebih dari satu surat yang sama.
  • Input dan output mungkin dalam format apa pun yang nyaman.
Beefster
sumber
Mengapa membuat tag baru?
user202729
Bisakah seseorang mengambil daftar (vektor) karakter sebagai input (format yang sama seperti dadu)? Meminta teman yang ingin menyimpan 27 byte.
JayCe
1
@JayCe "Input dan output mungkin dalam format yang nyaman", jadi ya.
Beefster

Jawaban:

12

Brachylog , 5 byte

∋ᵐ⊇pc

Cobalah online!

Kami menggunakan variabel input untuk dadu dan variabel output untuk kata. Ini keluar true.saat dimungkinkan untuk mengeja kata dan false.sebaliknya.

Penjelasan

∋ᵐ        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
Fatalisasi
sumber
8

Haskell , 48 44 byte

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

Ini adalah fungsi anonim. Terikat pada beberapa pengidentifikasi fyang dapat digunakan sebagai f "ART" ["AEIOU", "ABCT", "NPR"], yang menghasilkan True. Cobalah online!

Setara non-point-free adalah

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

mapM idlebih dari daftar daftar menggunakan Monadinstance dari daftar dan dapat dilihat sebagai pilihan non-deterministik . Jadi misalnya mapM id ["AB","123"]hasil ["A1","A2","A3","B1","B2","B3"].

Untuk masing-masing kombinasi dadu itu, kami memeriksa apakah perbedaan daftar (\\)kata yang diberikan dan kombinasi menghasilkan daftar kosong.

Laikoni
sumber
@LuisMendo Terima kasih telah menunjukkan! Diperbaiki dengan beralih ke metode lain yang akhirnya menghemat 4 byte.
Laikoni
6

JavaScript (ES6), 68 byte

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
sumber
1
@RickHitchcock Gagal untuk EEE.
Neil
6

Python 2 , 82 byte

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

Cobalah 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.

Rantai perbandingan w[0]in x>0<f(...)setara dengan: w[0]in x dan x>0 dan 0<f(...) .

Yang kedua selalu benar ( str> int) dan yang ketiga adalah sama dengan f(...), sehingga semuanya adalah cara yang lebih singkat untuk menulisw[0]in x and f(...)

Lynn
sumber
5

JavaScript (ES6), 74 byte

Mengambil input dalam sintaks currying (w)(a), di mana w adalah kata yang kita cari dan a adalah daftar string yang menggambarkan dadu. Mengembalikan 0 atau 1 .

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

Cobalah online!

Berkomentar

Kami mengubah setiap subset-permutasi dadu menjadi pola ekspresi reguler dan mengujinya terhadap kata target.

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
sumber
3

Sekam , 5 byte

~V`¦Π

Cobalah online!

Mengembalikan nilai non-nol jika memungkinkan untuk mengeja kata, nol sebaliknya.

Penjelasan

~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
sumber
2

Perl 5 -plF , 48 46 byte

@HomHastings menyelamatkan 2 byte

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

Cobalah online!

Memasukkan:

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

Keluaran:

0untuk kata yang tidak divalidasi. Setiap bilangan bulat positif untuk kata yang divalidasi

Bagaimana?

Penjelasan ini melihat kode dalam urutan eksekusi, efektif dari kanan ke kiri untuk liner satu ini.

-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
sumber
1

JavaScript (Node.js) , 98 byte

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

Cobalah online!

Dengan asumsi ada cukup dadu

JavaScript (Node.js) , 100 byte

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

Cobalah online!

JavaScript (Node.js) , 99 byte

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

Cobalah online!

l4m2
sumber
1

Jelly ,  10  9 byte

-1 berkat Erik the Outgolfer (gunakan wdaripada ẇ@>. <)

Œ!Œp€Ẏw€Ṁ

Tautan diad menerima daftar daftar karakter di sebelah kiri (dadu) dan daftar karakter di sebelah kanan (kata) yang mengembalikan 1 jika mungkin dan 0 jika tidak.

Cobalah online! Atau lihat test-suite .

Bagaimana?

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

Algoritma yang lebih cepat (juga 9 byte):

Sebuah link diad dengan format input yang sama yang mengembalikan bilangan bulat positif (kebenaran) bila memungkinkan dan 0 (falsey) sebaliknya.

Œ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
sumber
1

R , 192 185 135 117 111 109 byte

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

Cobalah online!

-2 karakter berkat Giuseppe.

JayCe
sumber
Ini akan gagal jika sebuah kata memiliki lebih sedikit huruf daripada yang Anda miliki.
Giuseppe
Saya pikir Anda dapat menyimpannya dengan biaya 21 byte, coba di sini
Giuseppe
@ Giuseppe Anda telah menyelamatkan hari!
JayCe
Anda tidak perluF=
Giuseppe
0

Pyth , 21 byte

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

Suite uji

Penjelasan:
.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
sumber