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]+$/
        STDIN.read
          .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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: