Scrabble
February 22, 2019
I was feeling silly on Thursday evening, when I wrote this exercise, and came up with this shell script:
rack='Q O F T H E A'
while true
do for word in $(shuf -ze $rack)
do for n in 2 3 4 5 6 7
do if $(grep -qi ^$(printf "%${n}.${n}s\n" $word)$ /usr/share/dict/words)
then printf "%${n}.${n}s\n" $word
fi
done
done
done
The shuf program produces a random permutation of its input, the loop on printf produces each 2 to 7 letter prefix of the permutation, and grep determines if the word is in its dictionary. There is no guarantee that all permutations are eventually considered, it is likely that there will be duplicates, and making an entire pass through the dictionary for each potential word is ridiculously expensive. Here is some of the output, limited to words of 4 or more letters by removing 2 and 3 from the loop on n and with Q replaced by S:
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
You can see the program at https://ideone.com/fjS7j7, but can’t run it because there is no dictionary.
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: