## Scrabble

### February 22, 2019

Today’s task is based on the game of Scrabble.

Your task is to write a program to find the dictionary words of length 2 to 7 that can be formed from the letters Q O F T H E A. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 13 Responses to “Scrabble”

1. Paul said

@programmingpraxis: I see the letter S popping up in your results. Your code on ideone has an extra S.

2. Paul said

In Python. All words without the S are printed

```from collections import Counter
thedict = """HOES THEA HEFT OAFS SATE HEAT HOSE SAFE SATE HOSE SEAT HEAT SOFA
FATS FEAST ETHOS HOSE HOSEA SOFA SHAFT HOSE OATH HATS SHAT HAFT
HAFTS SATE SAFE SOFT FOES""".split()

available = Counter("QOFTHEA")

minL, maxL = 4, 7
for word in thedict:
if minL <= len(word) <= maxL:
cnt = Counter(word)
for key in cnt.keys():
if not available[key] >= cnt[key]:
break
else:
print(word)
```
3. Smith said

Assumes letters can be used multiple times

```letters, min_, max_ = set("qofthea"), 2, 7
dictionary = map(lambda w: w.strip().lower() for word in open('/usr/share/dict/words'))
solution = filter(lambda w: set(w).issubset(letters) and (len(w) >= min_ and len(w) <= max_), dictionary)
print(list(solution))
```
4. matthew said

Python solution, sort letters and do an element by element comparison on the sorted letters:

```import sys

def subseq(s,t):
""" All the letters in s occur in t (s and t are ordered) """
i,j = 0,0
while i < len(s):
if j == len(t): return False
elif s[i] > t[j]: j += 1
elif s[i] == t[j]: i += 1; j += 1
else: return False
return True

letters = (len(sys.argv) > 1 and sys.argv[1]) or "softhea"
letters = sorted(letters)
for word in open("/usr/share/dict/words"):
word = word.strip()
if len(word) >= 2 and subseq(sorted(word),letters): print(word)
```
5. Globules said

A Haskell version using the dictionary on a Mac. (The letter ‘q’ doesn’t appear in the output.)

```import           Data.Functor ((<&>))
import qualified Data.Text as T
import qualified Data.Text.IO as IO

matches :: T.Text -> Bool
matches txt = let n = T.length txt
in n >= 2 && n <= 7 && T.all (`elem` "qofthea") (T.toLower txt)

main :: IO ()
main = IO.getContents <&> (filter matches . T.words) >>= mapM_ IO.putStrLn
```
```\$ ./scrabble < /usr/share/dict/words | column -c 80
aa      ate     fate    haaf    heft    oe      taft    teet    theet   toff
ae      atef    fe      haet    Hehe    of      taha    teeth   theft   toffee
affa    Atta    feat    haff    het     off     Tao     teethe  Theo    Toft
afoot   atta    fee     haffet  Ho      Ofo     tao     teff    theta   toft
aft     ea      feoff   haft    ho      oft     Tat     tete    Tho     toho
Ah      eat     feoffee hah     hoe     oh      tat     teth    tho     too
ah      effete  fet     hao     Hohe    oho     tate    th      thof    toot
aha     eft     Fo      hat     hoof    otate   tath    tha     thoft   tooth
Ahet    eh      foe     hate    hoot    Oto     tatta   that    thoo    tot
aho     eta     fohat   hath    hot     Otto    tattoo  The     to      tote
Aht     Etta    foo     hatt    hotfoot otto    te      the     toa     toto
Ao      fa      foot    he      Hotta   ta      tea     Thea    toat
Aotea   fae     foothot heaf    oaf     taa     teat    theah   toatoa
at      faff    fot     heat    oat     tae     teathe  theat   toe
Ata     fat     ha      heath   oath    taffeta tee     thee    toetoe
```
6. Globules said

And here’s the same thing using egrep.

```\$ egrep -i '^[qofthea]{2,7}\$' /usr/share/dict/words | column -c 80
```
7. V said
```  def scrable
regex = /^[qofthea]+\$/
.split(/[\n\r]+/)
.select do |w|
w.chars.size >= 2 &&
w.chars.size <= 7 &&
w =~ regex
end
end
```

Then I saw @Globules elegant solution and realised that mine could be greatly simplified if I just tweaked the regexp.

```  puts STDIN.read.split(/[\n\r]+/).select { |l| l =~ /^[qofthea]{2,7}\$/i }
```

and use it like this:

```  cat /usr/share/dict/words | ruby scrable.rb | column -c 80
```

👏 to @Globules

8. matthew said

This is supposed to be Scrabble so letters can’t be used more than once.

9. Globules said

Here is a more Scrabble-conforming version, where each letter is used at most once.

```import Data.Char (toLower)
import Data.Functor ((<&>))
import Data.List ((\\))

matches :: String -> Bool
matches txt = let n = length txt
in n >= 2 && n <= 7 && null (map toLower txt \\ "qofthea")

main :: IO ()
main = getContents <&> (filter matches . words) >>= mapM_ putStrLn
```
```\$ ./scrabble < /usr/share/dict/words | column -c 80
ae      Ao      eh      feat    haet    heat    oaf     ta      tha     thof
aft     at      eta     fet     haft    heft    oat     tae     The     to
Ah      ate     fa      Fo      hao     het     oath    Tao     the     toa
ah      atef    fae     foe     hat     Ho      oe      tao     Thea    toe
Ahet    ea      fat     fohat   hate    ho      of      te      Theo
aho     eat     fate    fot     he      hoe     oft     tea     Tho
Aht     eft     fe      ha      heaf    hot     oh      th      tho
```
10. matthew said

Here’s a trie-based solution – read the set of words into a trie (using the sorted letters of each word for the trie entries, rather than the word itself). Then we can find subsets of the given letter multiset reasonably efficiently. Since it’s Scrabble, just consider all-lowercase words (no proper nouns allowed).

```#include <iostream>
#include <string>
#include <vector>
#include <cctype>
#include <cassert>
#include <memory>
#include <algorithm>

struct Node {
Node() : next(26) {}
std::vector<std::string> words;
std::vector<std::unique_ptr<Node>> next;
};

typedef std::unique_ptr<Node> NodePtr;

void insert(NodePtr &pnode, const char *letters, const std::string &word) {
if (!pnode) pnode = NodePtr(new Node());
if (*letters == 0) {
pnode->words.push_back(word);
} else {
insert(pnode->next[*letters-'a'],letters+1,word);
}
}

void lookup(const NodePtr &pnode, const char *letters) {
for (auto s : pnode->words) std::cout << s << "\n";
for (int c = 'a'; c <= 'z'; c++) {
const NodePtr &pnext = pnode->next[c-'a'];
if (!pnext) continue;
const char *p = letters;
while (*p != 0 && *p < c) p++;
if (*p == c) lookup(pnext,p+1);
}
}

int main(int argc, char *argv[]) {
assert(argc == 2);
NodePtr root;
std::string word,letters;
while (std::cin >> word) {
if (word.size() < 2) continue;
if (!std::all_of(word.begin(),word.end(),islower)) continue;
letters = word;
std::sort(letters.begin(),letters.end());
insert(root,letters.c_str(),word);
}
letters = argv[1];
std::sort(letters.begin(),letters.end());
lookup(root,letters.c_str());
}
```
```\$ g++ -O3 -Wall -g -std=c++11 scrabble.cpp -o scrabble
\$ ./scrabble qofthea < /usr/share/dict/words | sort | columns
aft  ah   at   ate  eat  eh   eta  fa   fat  fate feat feta foe  ha   haft
hat  hate he   heat heft ho   hoe  hot  oaf  oat  oath of   oft  oh   tea
the  tho  to   toe
```
11. deathgrindfreak said

Common Lisp:

[sourcecode lang="lisp"]
(defun is-scrabble-word (word letters)
(and (<= 2 (length word) 7)
(every #'(lambda (c) (find c letters)) word)))

(defun filter-dictionary (path letters)
(with-open-file (in path)
(loop for line = (read-line in nil nil)
while line
when (is-scrabble-word (string-upcase line) letters) collect line)))

(defun print-scrabble ()
(format t “~{~a ~}” (filter-dictionary “/usr/share/dict/words” “QOFTHEA”)))

12. Daniel said

Here’s a solution in Python:

```from collections import Counter

c = Counter('QOFTHEA')

with open('/usr/share/dict/words') as f:
for word in f:
word = word.strip()
if 2 <= len(word) <= 7 and not Counter(word.upper()) - c:
print(word)
```

Output:

```ae
aft
Ah
ah
Ahet
aho
Aht
Ao
...
Tho
tho
thof
to
toa
toe
```