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.
Programming Praxis 
@programmingpraxis: I see the letter S popping up in your results. Your code on ideone has an extra S.
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)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))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)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.putStrLnAnd here’s the same thing using egrep.
$ egrep -i '^[qofthea]{2,7}$' /usr/share/dict/words | column -c 80def scrable regex = /^[qofthea]+$/ STDIN.read .split(/[\n\r]+/) .select do |w| w.chars.size >= 2 && w.chars.size <= 7 && w =~ regex end endThen 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:
👏 to @Globules
This is supposed to be Scrabble so letters can’t be used more than once.
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_ putStrLnHere’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()); }Common Lisp:
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”)))
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: