Longest words in dictionary that can be constructed from a list of letters

The problem is to find the longest words in a dictionary of legal words that can be constructed from a given list of letters.

For example:

\$ ./scrabble dictionary.txt i g h l p r a
argil glair grail graph hilar laigh phial pilar ralph


More details here.

I've already solved this problem in Python (see this).

To brush up my C++ I decided to reproduce the exact same algorithm in C++. I learned C++ as "C with classes" and never learned to use the STL properly, so I usually end up writing more code than necessary to accomplish simple things.

This is what I came up with for this problem:

#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

bool can_make(string word, vector<char> letters);
int get_max_len(vector<string> words);

int main(int argc, char* argv[])
{
// Grab the dictionary.
fstream dict_file(argv[1]);
string in;
vector<string> dict_words;
while(getline(dict_file, in)) dict_words.push_back(in);
dict_file.close();

// Get the list of input letters.
vector<char> letters;
for (int i = 2; i < argc; i++)
letters.push_back(argv[i][0]);

// Get all words.
vector<string> all_words;
vector<string>::iterator it;
for (it = dict_words.begin(); it < dict_words.end(); it++)
if (can_make(*it, letters))
all_words.push_back(*it);

// Get longest words.
int max_len = get_max_len(all_words);
vector<string> longest_words;
for (it = all_words.begin(); it < all_words.end(); it++)
if ((*it).length() == max_len)
longest_words.push_back(*it);

// Print the result.
for (it = longest_words.begin(); it < longest_words.end(); it++)
cout << *it << " ";
cout << endl;

return 0;
}

bool can_make(string word, vector<char> letters)
{
/*
Return true if the word <word> can be generated by all letters in <letters>
and only the letters in <letters>.
*/

if (word.length() > letters.size()) return false;

vector<char> l(letters);
vector<char> word_letters(word.c_str(), word.c_str()+word.length());
vector<char>::iterator it, loc;

// Iterate through <word_letters>. If a letter in <word_letters> also
// appears in <letters>, remove it. Otherwise, return false.
for (it = word_letters.begin(); it < word_letters.end(); it++) {
loc = find(letters.begin(), letters.end(), *it);
if (loc == letters.end()) return false;
letters.erase(loc);
}

return true;
}

int get_max_len(vector<string> words)
{
/*
Return the length of the longest word(s) in <words>.
*/

int max_len = 0;
vector<string>::iterator it;
for (it = words.begin(); it < words.end(); it++)
if ((*it).length() > max_len)
max_len = (*it).length();

return max_len;
}

1. Is this idiomatic C++?
2. How can I make this code more concise?
3. How can I make it more correct?
4. What C++11 features can I use here to make the code even shorter?
5. What features have I used here that I should avoid?

Argument Checking

int main(int argc, char* argv[])
{
fstream dict_file(argv[1]);
// ...


You should check the supplied arguments before using them. Executing your program with no arguments would access an out-of-bound index.

Vectors everywhere

vector<string> dict_words;
while(getline(dict_file, in)) dict_words.push_back(in);
// ...
vector<char> letters;
for (int i = 2; i < argc; i++)
letters.push_back(argv[i][0]);
// ...
vector<string> all_words;
vector<string>::iterator it;
for (it = dict_words.begin(); it < dict_words.end(); it++)
// ...
int max_len = get_max_len(all_words);
vector<string> longest_words;
// ...


That's quite a number of vectors you've made there. I'm not convinced they're all necessary.

bool can_make(string word, vector<char> letters);
int get_max_len(vector<string> words);


To make this usage even more gratuitous you pass those vectors by value too!

Accepting entire argument

// Get the list of input letters.
vector<char> letters;
for (int i = 2; i < argc; i++)
letters.push_back(argv[i][0]);


Here I think it makes more sense to use the entire argument as letters. If need be you can check its input with something like isalpha.

Performance implications

bool can_make(string word, vector<char> letters)
{
// ...
vector<char> l(letters);
// ...
for (it = word_letters.begin(); it < word_letters.end(); it++) {
// ...
letters.erase(loc);
}
// ...
}


Using letters.erase(loc); liberally in a loop like this can result in severe performance problems especially if the vector contains lots of letters. This is due to the linear performance characteristics of vector::erase where removed items have to get shifted over. Also note that your vector<char> l(letters); is unused here.

And finally... a practical example

As others have hinted, you can cutdown on syntactic noise and improve readability(greatly) by using algorithms supplied by the standard library. If you're brushing up on C++ this advice might be fuzzy for you. As an example, here's how I'd do it under the true spirit of generic programming:

You'll need the following headers for the example to work:

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <queue>
#include <iterator>
#include <algorithm>
using namespace std;    // for convenience only -- don't do this on real projects


int main(int argc, char *argv[])
{
if(argc < 3)
{
// Print some error out
return -1;
}

vector<string> dictionary;

string letters = grab_letters(argv + 2, argv + argc);

deque<string> results;
for_each(dictionary.begin(), dictionary.end(), try_match(letters, results));

// No words could be matched
if(results.empty()) return 0;

// Remove short words.
while(results.back().length() > results.front().length())
results.pop_front();

copy(results.begin(),
results.end(),
ostream_iterator<string>(cout, " "));
}


Even without comments, the code above is very understandable. The general usage pattern is to perform some action on a set of inputs. The action is communicated by the algorithm's name (eg. load_dictionary, for_each, copy etc.). The input is specified as a range given by the pair of iterators. Some actions, like copy, take one more iterator to indicate where to copy to.

This is similar to Sjoerd's grab_dictionary function but modified to accept other containers besides vectors.

template <typename T>
void load_dictionary(const char *filename, T appender)
{
ifstream infile(filename);
if(!infile) return;

copy(istream_iterator<string>(infile),
istream_iterator<string>(),
appender);
}


Notice the usage of iterator adapters like istream_iterator and ostream_iterator. With those constructs it allows algorithms to work with almost any kind of iostream as if it's another container.

template <typename T>
string grab_letters(T begin, const T &end)
{
string letters;
while(begin != end) letters += *begin++;

return letters;
}


Even grab_letters follow this pattern for processing extra arguments passed in. This works because conceptually iterators are pointers. That means you can use char *argv[] to indicate where the first argument starts and where it ends.

// Get all words.
deque<string> results;
for_each(dictionary.begin(), dictionary.end(), try_match(letters, results));


This is where the real processing happens. The try_match function creates a functor (conveniently named matcher) and passes it to for_each. When for_each visits each word in turn, it will call the functor via the overloaded operator () with the current word as argument.

template <typename T>
class matcher
{
public:
matcher(const string &letters, T &results);
void operator ()(const string &word);
};

template <typename T>
matcher<T> try_match(const string &letters, T &results)
{
return matcher<T>(letters, results);
}


And from here you can just write whatever processing needs to happen in the matcher functor class.

• In your example please insert the header needed. – Martin York Dec 10 '11 at 16:58
• Note: You do not even need to load the dictionary in memory: for_each(std::istream_iterator<string>(dictFile), std::istream_iterator<string>(), try_match(letters, results)); – Martin York Dec 10 '11 at 16:59
• @Loki That's a good observation, I haven't thought of that. But then again it is starting to be quite a mouthful. D: – greatwolf Dec 11 '11 at 0:01
• Wow, your practical example is just the sort of thing I was looking for. Thanks for that. – Ankur Sethi Dec 12 '11 at 3:00
• @Ankur you're welcome, glad it was helpful. – greatwolf Dec 12 '11 at 3:31

Preface

I am not sure the algorithm you have chosen is the best one. Sorting the letters, or using a frequency table of the letters, are obvious alternatives. However, this is code review, and not algorithm review.

So here we go:

Iterators

Don't use < on iterators, use != on iterators. < only works on bidirectional iterators, != works on all iterators. std::list<> is an example where < won't work.

Use ++it instead of it++. Theoretically, the latter has to return a temporary copy of the original, which is additional overhead when the iterator is a class. Practically, it won't make much of a difference (if any) as most compilers will inline and optimize. Still, it's one of the best signals whether someone is a true C++ expert or a converted C-programmer :P .

So

for (it = dict_words.begin(); it < dict_words.end(); it++)


Will become:

for (it = dict_words.begin(); it != dict_words.end(); ++it)


Predefined algorithms

Many of your one-line loops can be replaced with algorithms from <algorithm>.

In this small case, I wouldn't bother as it wouldn't help to make your code more clear or shorter.

On the other hand, experimenting with them in this case will make you more comfortable with them. With the introduction of lambdas in C++11, those algorithms will become much more common in new code!

C++11

Due to the fact that C++11 hasn't been around long yet (and compilers don't fully implement it yet), idiomatic C++11 will change over the next couple years. So take this section with a grain of salt.

That being said, use auto for the type of it. That part of C++11 has become idiomatic already.

E.g.:

vector<string>::iterator it;
for (it = dict_words.begin(); it != dict_words.end(); ++it)


will become:

for (auto it = dict_words.begin(); it != dict_words.end(); ++it)


EDIT: oops, forgot about the range-based for in C++11. See other answers for that. I'm not that well versed in C++11 yet, but I believe it would look like this:

for (auto it : dict_words)


More functions

Most of your code is in one long function, called main. Try to split it up.

Once you start inserting empty lines and comment headings to clarify what the block does, it's usually a good candidate to turn into a separate function.

E.g. this block of code (limited by empty lines, with a comment):

// Grab the dictionary.
fstream dict_file(argv[1]);
string in;
vector<string> dict_words;
while(getline(dict_file, in)) dict_words.push_back(in);
dict_file.close();


Can be replaced with this function:

void grab_dictionary(const char* filename, vector<string>& dict_words)
{
fstream dict_file(filename);
string in;
while(getline(dict_file, in))
dict_words.push_back(in);
}


Usage from main:

vector<string> dict_words;
grab_dictionary(argv[1], dict_words);


• The comment is no longer needed - usually it has become the name of the function!
• There is no need for dict_file.close() as the destructor will close the file at the right time.
• Thanks! I have a few more questions: why should I use ++it instead of it++? Why is it != letters.end() better than it < letters.end()? And since we are on the topic, could you suggest a better algorithm for this task? – Ankur Sethi Dec 10 '11 at 13:29
• @AnkurSethi Thanks for accepting my answer! However, my answer contains only a few basic rewrites; Other answers all contain valid points as well. IMHO, VictorT's answer comes closest to code a real C++ guru would write. – Sjoerd Dec 11 '11 at 0:46
• yes, VictorT's answer is indeed very good. Great example of generic programming there, just what I was looking for. I think it should be the accepted answer. – Ankur Sethi Dec 12 '11 at 3:03

You use too much of copying from one vector to another. Use filtering.

vector<string>::iterator it;
for (it = words.begin(); it < words.end(); it++)


use

for (vector<string>::const_iterator it = words.begin(), E = words.end(); it != E; ++it)


In C++11 you should use auto wherever it's possible,
use begin/end functions instead of begin/end methods,
and use range-based for loop for iterating over collections.

Your can_make is non-optimal and probably is wrong. (Python solution is non-optimal too).

int get_max_len(vector<string> words)
- don't pass words by value until ypu really need to copy it.
- it should return value of size_t type, enable warnings in your compiler, and enable "treat warnings as errors" option.

Upd: @LokiAstari wrote that it's bad practice to write E = words.end(); it != E, because "The containers are already optimized to do this efficiently.".
In common case, it's incorrect.
It's true that in some trivial cases, compiler can infer that contatiner isn't modified in loop body, and perform such optimization.
But if container is referenced in loop body by non-const reference, compiler can't assume that container isn't modified, so it will get end() iterator on every iteration.
It't the same as ; ++i) vs. ; i++) - in trivial cases, compiler will optimize i++ to ++i, but in non-trivial cases it will not do it.

• Don't do E = words.end(); it != E. The containers are already optimized to do this efficiently. So you gain nothing, the cost is that it makes the code brittle to change. – Martin York Dec 9 '11 at 15:49
• @LokiAstari, can you prove it? What container and what its implementation has such optimization? – Abyx Dec 9 '11 at 15:55
• All of them. This is such a common way of doing things (calling end() after each iteration, that it was one of the first optimizations to the STL) check your copy of the STL. Even if they do not have it your code is brittle to change. – Martin York Dec 9 '11 at 16:44
• @LokiAstari, I don't believe you, but I believe my experience, and some coding standards, like this - llvm.org/docs/CodingStandards.html#ll_end . – Abyx Dec 9 '11 at 23:36
• Please try it. I have. The difference in the generated assemble is so minor as to be insignificant. Thus I will always go with the code that won't break when I modify it. – Martin York Dec 10 '11 at 16:55