Word wheel

Word wheel is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

A "word wheel" is a type of word game commonly found on the "puzzle" page of newspapers. You are presented with nine letters arranged in a circle or 3x3 grid. The objective is to find as many words as you can using only the letters contained in the wheel or grid. Each word must contain the letter in the centre of the wheel or grid. Usually there will be a minimum word length of 3 or 4 characters. Each letter may only be used as many times as it appears in the wheel or grid.

For example:

N	D	E
O	K	G
E	L	W

Task

Write a program to solve the above "word wheel" puzzle. Specifically:

• Find all words of 3 or more letters using only the letters in the string "ndeokgelw".
• All words must contain the central letter "k".
• Each letter may be used only as many times as it appears in the string.
• For this task we'll use lowercase English letters exclusively.

A "word" is defined to be any string contained in the file located at http://wiki.puzzlers.org/pub/wordlists/unixdict.txt. If you prefer to use a different dictionary please state which one you have used.

C++

The puzzle parameters are hard-coded but could easily be replaced by e.g. command line arguments. <lang cpp>#include <array>

1. include <iostream>
2. include <fstream>
3. include <map>
4. include <string>
5. include <vector>

// A multiset specialized for strings consisting of lowercase // letters ('a' to 'z'). class letterset { public:

   explicit letterset(const std::string& str) {
       count_.fill(0);
       for (char c : str) {
           if (c >= 'a' && c <= 'z')
               ++count_[c - 'a' + 1];
           else
               ++count_[0];
       }
   }
   bool contains(const letterset& set) const {
       for (size_t i = 0; i < count_.size(); ++i) {
           if (set.count_[i] > count_[i])
               return false;
       }
       return true;
   }
   unsigned int count(char c) const {
       if (c >= 'a' && c <= 'z')
           return count_[c - 'a' + 1];
       return 0;
   }
   bool is_valid() const {
       return count_[0] == 0;
   }

private:

   // elements 1..26 contain the number of times each lowercase
   // letter occurs in the word
   // element 0 is the number of other characters in the word
   std::array<unsigned int, 27> count_;

};

template <typename iterator, typename separator> std::string join(iterator begin, iterator end, separator sep) {

   std::string result;
   if (begin != end) {
       result += *begin++;
       for (; begin != end; ++begin) {
           result += sep;
           result += *begin;
       }
   }
   return result;

}

int main(int argc, char** argv) {

   const int min_length = 3;
   const char* letters = "ndeokgelw";
   const char central_letter = 'k';
   const char* dict(argc == 2 ? argv[1] : "unixdict.txt");
   std::ifstream in(dict);
   if (!in) {
       std::cerr << "Cannot open file " << dict << '\n';
       return 1;
   }
   letterset set(letters);
   std::string word;
   std::map<size_t, std::vector<std::string>> words;
   while (getline(in, word)) {
       if (word.size() < min_length)
           continue;
       letterset subset(word);
       if (subset.count(central_letter) > 0 && set.contains(subset)) {
           words[word.size()].push_back(word);
       }
   }
   for (const auto& p : words) {
       const auto& v = p.second;
       auto n = v.size();
       std::cout << "Found " << n << " " << (n == 1 ? "word" : "words")
           << " of length " << p.first << ": "
           << join(v.begin(), v.end(), ", ") << '\n';
   }
   return 0;

}</lang>

Output:

Found 5 words of length 3: eke, elk, keg, ken, wok
Found 10 words of length 4: keel, keen, keno, knee, knew, know, kong, leek, week, woke
Found 1 word of length 5: kneel
Found 1 word of length 9: knowledge