powered by text files


Target (redux)

After having spent some of last week solving the Target word problem using Haskell, I thought I might try another language.

C++ is one of those languages that retains low level control and simple machine semantics while providing high abstraction levels. The first language I learnt, it is also the one I’ve used the most. I usually skip it for attempting to understand an algorithmic problem, but once the algorithm is well understood it can make a big speed difference.

As I’ve been pondering this from a productivity point of view, the interesting bit is how I approached the problem. Fortunately, C++ includes pseudo functional constructs via the STL. This meant that I could keep a reasonable level of abstraction. Loops replaced recursion, as it is technically possible to use recursion in C++, it just doesn’t feel right.

The time spent building the C++ version was around the same time as for the Haskell version. When run against a large dictionary of words (234937), the Haskell version took around 4.5 seconds, with the C++ version taking just less than a second.

I believe there is still some optimisation space left in both programs.

Given a similar problem, I would pick Haskell to explore, even with a slower result. For some reason, it was more fun to program against.

To continue this, I’m going to pick a trickier problem and try implementation in multiple languages. In theory, there is a Cocoa to Haskell binding …

For future reference, my code looks like:

#include <iostream>
#include <iterator>
#include <fstream>
#include <vector>
#include <set>

using namespace std;

bool containsWord(char const&, string const&, string const&);
bool includesAllLetters(string const &, string const &);

int main(int argc, char** argv) {
    string from, word;
    char letter;

    if(argc < 4) {
        cout << "usage: mainChar allLetters wordList\n";
        return 0;

    letter = argv[1][0];
    word = argv[2];
    from = argv[3];

    ifstream is(from.c_str());
    istream_iterator<string> ii(is), eos;

    int count = 0;
    vector<string> targets;
    cout << "Words: ";
    for( ; ii != eos; ++ii)
        if(containsWord(letter, word, *ii)) {
            cout << *ii << " ";
            if(word.length() == (*ii).length())

    cout << "\n";
    cout << "Found " << count << " words.\n";

    cout << "Targets: ";
    for(vector<string>::iterator p = targets.begin(); p!=targets.end(); ++p)
        cout << *p << " ";
    cout << "\n";

    return !is.eof();

bool containsWord(char const& c, string const &word, string const &testWord) {
    if(testWord.length() < 4 || testWord.length() > word.length() || testWord.find(c) == testWord.npos) return false;

    if(includesAllLetters(word, testWord)) return true;

    return false;

bool includesAllLetters(string const &word, string const &testWord) {
    string letters(word);
    for(string::const_iterator p = testWord.begin(); p !=testWord.end(); ++p) {
        size_t loc = letters.find(*p);
        if(loc == letters.npos)
            return false;
            letters.erase(loc, 1);

     return true;