20
\$\begingroup\$

Background

Scrabble is a word game in which players collaboratively build a board consisting of letter tiles that spell words. Each word must be connected to another word, and players gain points based on the letters they use and where they are placed. Words can be spelled either from left-to-right or top-to-bottom, and their validity is determined via the Scrabble Dictionary. Each contiguous set of more than one letter in a row or column must be a valid word.

The Challenge

Your challenge is to write a function that accepts a 2D grid of letters and determines whether or not it consitutes a valid Scrabble board. A board is valid if every word in every column and row is a valid word according to this text file containing a Scrabble Dictionary.

Your function should take a 2D grid of characters and a list of valid words as input. The board is assumed to be contiguous (every word is connected to the board) and padded with spaces to be rectangular. Your function must return a truthy value of your choice if the board is valid, and a falsey one otherwise. The board is assumed to contain at least 2 letters. This is Code Golf, so the shortest answer wins, and the usual rules/loopholes apply.

Test Cases

All boards' validity is determined according to this list of Scrabble words.

Valid boards:

MAP   
O APP
NEW O
T EEL
HAD E

DANCING 
  A     
  SEEING
  A    O 
  LAZY T

SORDID   
O U      
LEEWAY   
E        
L        
YESTERDAY
       A   

Invalid boards:

MOLAR
A    
RATS 
CR   
HC   
 H   

RASCAL
A     
BAKING
B   OO
ISLAND
T     

JOYFUL 
  OFFER
\$\endgroup\$
8
  • 3
    \$\begingroup\$ @thejonymyster "Your function should take the list of valid words as input". \$\endgroup\$ Oct 18 at 18:57
  • 2
    \$\begingroup\$ I suggest moving the link of the example dictionary down to the Test Cases section and wording as "should take a list of valid words and 2D grid...". \$\endgroup\$ Oct 18 at 18:59
  • 7
    \$\begingroup\$ Do we only need to check that all the words are valid, or also that they could have been played? For instance, do we need to detect words that require playing more than 7 letters in a turn, or that use letters which are no longer available in the bag. And how is the blank tile represented in the input? \$\endgroup\$ Oct 19 at 9:07
  • 1
    \$\begingroup\$ Words longer than 7 can be done if a continuous part is already a word, too \$\endgroup\$
    – masterX244
    Oct 19 at 13:02
  • 2
    \$\begingroup\$ @TobySpeight You only need to check that each word is in the dictionary. \$\endgroup\$ Oct 19 at 14:15
12
\$\begingroup\$

Jelly, 12 9 bytes

-3 bytes thanks to Jonathan Allan

A dyadic function taking a list of lines on the left and a list of words on the right.

Z;⁸KḲḊƇfƑ

Try it online!

Z;⁸         -- concatenate list of columns and list of rows
   KḲ       -- join on spaces and split on spaces to get list of words
      Ƈ     -- keep words that are truthy (non-empty)
     Ḋ      --   when the first character is removed
         Ƒ  -- is this resulting word list invariant when
        f   --   all words not in the dictionary are removed?
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Isn't this 9 characters, but 17 bytes? \$\endgroup\$ Oct 27 at 16:17
7
\$\begingroup\$

Ruby, 60 57 bytes

->b,d{(b+b.transpose).all?{|c|d==d|c.join.scan(/\w\w+/)}}

Try it online!

Takes the board as a list of lists of characters. Returns true for valid boards, false otherwise.

The board is valid if for every word on the board, the union of that word with the dictionary is equal to the dictionary.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 57 bytes \$\endgroup\$ Oct 19 at 0:15
  • \$\begingroup\$ @dingledooper Thanks, was just editing exactly that in! \$\endgroup\$
    – Dingus
    Oct 19 at 0:18
4
\$\begingroup\$

Python 3, 138 \$\cdots\$ 86 79 bytes

lambda b,d:all(i in d+[*s]for s in[*map(''.join,zip(*b))]+b for i in s.split())

Try it online!

Saved a whopping 27 33 bytes thanks to Bubbler!!!
Saved 7 bytes thanks to Jonathan Allan!!!
TIO testing now works thanks to ovs and Bubbler!!!

Inputs the boards as a list of strings (space padded so they're all the same length) and the dictionary as a list of strings.
Returns True for a valid board or False otherwise.

\$\endgroup\$
5
  • \$\begingroup\$ 86 using zip(*b) (also added ovs's dictionary to actually check the test cases) \$\endgroup\$
    – Bubbler
    Oct 19 at 0:38
  • \$\begingroup\$ 80 using set difference. \$\endgroup\$
    – Bubbler
    Oct 19 at 0:44
  • 2
    \$\begingroup\$ 79 using Bubbler's 86 and using the lines themselves as the "acceptable" one letter words. \$\endgroup\$ Oct 19 at 0:50
  • \$\begingroup\$ @Bubbler Wow, that's super sweet - thanks! :D \$\endgroup\$
    – Noodle9
    Oct 19 at 12:24
  • \$\begingroup\$ @JonathanAllan Very nice - thanks! :D \$\endgroup\$
    – Noodle9
    Oct 19 at 12:24
3
\$\begingroup\$

Gaia, 8 bytes

Basically the same as my Jelly answer, but Gaia has a superset builtin.

:t+ṡṡḥ⁇⊃

Try it online!

:t+ṡṡḥ⁇⊃     -- function that expects a 2d-list character above the dictionary as a list of strings
:t           -- duplicate the grid on the stack and transpose the copy
  +          -- append transpose to original grid
   ṡ         -- join list by spaces
    ṡ        -- split resulting string on spaces
     ḥ⁇      -- keep words that are truthy when the first character is removed
       ⊃     -- is the dictionary a superset of this word list

only considers unique item and a list is a superset of itself ( might've been a more accurate symbol). Almost all operators in Gaia are overloaded for different types, which is why can both split and join.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Isn't this 8 characters, but 18 bytes? \$\endgroup\$ Oct 27 at 16:17
  • 2
    \$\begingroup\$ @TimothyZorn that would be true if you encode these characters in UTF-8, but Gaia has a custom codepages which allows to encode each of those characters in a single byte. The same applies for Jelly \$\endgroup\$
    – ovs
    Oct 27 at 17:54
  • \$\begingroup\$ Thank you for the information! The characters in the answer are UTF-8 and in fact 18 bytes, so it confused me. \$\endgroup\$ Oct 28 at 18:57
2
\$\begingroup\$

05AB1E (legacy), 12 bytes

Dø«ðý#ʒ¦Ā}åP

First input is the board as a list of string lines; second is a list of words.

Uses the legacy version of 05AB1E, because it can zip/transpose lists of strings, where in the new version zip/transpose can only be done on character-matrices.

Try it online.

Explanation:

D          # Duplicate the first (implicit) input-list
 ø         # Zip/transpose; swapping rows/columns
  «        # Merge the two lists together
   ðý      # Join the strings with space delimiter
     #     # Then split the entire string by spaces
      ʒ    # Filter this list of strings:
       ¦   #  Remove the first character
        Ā  #  And check if it's non-empty
      }    # After the filter: we have a list of the words
       å   # Check for each word if it's in the second (implicit) input-list
        P  # Check if this is truthy for all of them
           # (after which the result is output implicitly)

I came up with it independently, but I noticed it's basically a port of @ovs' Jelly answer, with just larger builtins / stack management. (For convenient I also copied their test case to my TIO.)

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Isn't this 12 characters, but 20 bytes? \$\endgroup\$ Oct 27 at 16:18
  • 2
    \$\begingroup\$ @TimothyZorn No, 05AB1E uses a custom code page with the 256 characters it knows (linked in the title of my answer), which are 1 byte each. It's fairly common for codegolf languages, like Jelly, Charcoal, etc. The 12 bytes of my program above (in hexadecimal) are: 44, F8, AB, F0, FD, 23, 01, A6, 90, 7D, E5, 50, and 05AB1E's codepage simply transforms it into something more readable with those 256 characters. You can run and verify the program with these 12 bytes with the --osabie flag: try it online. \$\endgroup\$ Oct 27 at 16:33
  • \$\begingroup\$ Thank you for the information! The characters in the answer are UTF-8 and in fact 20 bytes, so it confused me. \$\endgroup\$ Oct 28 at 18:56
1
\$\begingroup\$

Japt, 12 bytes

cUy)¸¸fÅe!øV

Try it

\$\endgroup\$
1
  • \$\begingroup\$ Isn't this 12 characters, but 16 bytes? \$\endgroup\$ Oct 27 at 16:18
1
\$\begingroup\$

Kotlin, 159 129 bytes

{d,b->(b+b[0].indices.map{c->b.indices.joinToString(""){"${b[it][c]}"}}).all{r->r.split(" ").filter{it.length>1}.all{w->w in d}}}

-30 bytes thanks to using lambda and type inference (Parlor Trick)

Try it online!

Explanation:

First, merge the original and transposed board. In each row, find all words longer than 1 letter and for all of them, check their presence in the dictionary.

\$\endgroup\$
3
  • \$\begingroup\$ Welcome to CGCC! The code looks good but the third test case is showing false because of a stray H under the Y in LEEWAY. You might like to check out Tips for golfing in Kotlin if you haven't already. \$\endgroup\$
    – Dingus
    Oct 21 at 12:42
  • \$\begingroup\$ I actually added this H on purpose, to produce an "invalid board" case with this single two-word vertical word. How do we approach the topic of using test cases in our TIO links? I saw other people using other test cases. Thanks for the golfing tips, I'm planning to read it thoroughly and iteratively improve my solution. \$\endgroup\$
    – PiotrK
    Oct 21 at 12:56
  • 1
    \$\begingroup\$ Ah I see. Often people use the test cases provided in the question to illustrate that their code behaves as expected but you're free to change them if you want to. All that really matters is that the code works. \$\endgroup\$
    – Dingus
    Oct 21 at 13:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.