Here is the code

[source]

#include <iostream>
#include <cmath>
#include <iterator>
#include <vector>
#include <algorithm>
#include <fstream>
#include <list>
using namespace std;

#define DEBUG_


#ifdef DEBUG_
const unsigned BOARD_SIZE = 10;
#endif

typedef std::vector<std::string> StringArray;
typedef StringArray GameBoard;

struct Vertex{
typedef std::pair<size_t, size_t> Position;
typedef std::list<Position> NeighborList;
typedef NeighborList::const_iterator ConstNeighborIterator;
typedef NeighborList::iterator NeighborIterator;
Position position;
NeighborList neighbors;
Vertex(){};
Vertex(const Position& p): position(p){}
Vertex(const size_t row, const size_t col): position(Position(row,col)){}
};
enum MatchResult{
NO_MATCH,
MATCH_AND_IS_FULL_WORD,
MATCH_AND_IS_JUST_PREFIX
};

typedef std::vector<std::vector<Vertex> > Neighbors;

void usage();
StringArray readDictionary(const std::string& filePath);
GameBoard readBoard(const std::string& filePath);
Neighbors generateNeighbors(const GameBoard& board);
MatchResult isPrefixMatch(const StringArray& dictionary, const std::string& prefix);
MatchResult isWord(const StringArray& dictionary, const std::string& word);
bool isBoggleWord(const StringArray& dictionary,const std::string& prefix);

StringArray generateBoggleSolution(const GameBoard& board,
const StringArray& dictionary,
const Neighbors& neighbors);
//operators on current vertex
void generateBoggleSolution(std::string& currentPrefix,
std::vector<Vertex::Position>& usedPositionList,
StringArray& solution,
const Vertex::Position& currentVertex,
const GameBoard& board,
const StringArray& dictionary,
const Neighbors& neighbors);
template<typename Iterator>
void print(Iterator begin, Iterator end, const std::string& delim = " ");
ostream& operator <<(ostream& stream, const Vertex::Position& p){
return stream << "(" << p.first << "," << p.second << ")";
}

int main(int argc, char *argv[])
{
#ifndef DEBUG_
if(argc < 3 && false){
usage();
}
else
#endif
{
GameBoard board = readBoard(argv[1]);
StringArray dictionary = readDictionary(argv[2]);
Neighbors neighborMap = generateNeighbors(board);
#ifdef DEBUG_
print(board.begin(),board.end(),"\n");
time_t clkBegin = clock();
#endif
StringArray result = generateBoggleSolution(board,dictionary,neighborMap);
std::sort(result.begin(), result.end());
StringArray::iterator newEnd = std::unique(result.begin(), result.end());
StringArray::iterator begin = result.begin();
while(begin != newEnd){
cout << *begin << endl;
++begin;
}
#ifdef DEBUG_
cout << "Time took = " << float(clock() - clkBegin) / float(CLOCKS_PER_SEC) << "s" << endl;
cout << "Board size = " << board.size() << "x" << board.size() << endl;
cout << "Number of words generated = " << std::distance(result.begin(), newEnd) << endl;
#endif
}
return 0;
}

void usage(){
cout << "Usage = <gameboard.txt> <dictionary.txt> " << endl;
}

StringArray generateBoggleSolution(const GameBoard& board,
const StringArray& dictionary,
const Neighbors& neighbors)
{
StringArray solutionList;
for(int row = 0; row < board.size(); ++row){
for(int col = 0; col < board[row].size(); ++col){
std::vector<Vertex::Position> usedList(1,Vertex::Position(row,col));
std::string prefix(1,board[row][col]);
generateBoggleSolution(prefix,usedList,solutionList,Vertex::Position(row,col),board,dictionary,neighbors);
}
}
return solutionList;
}
void generateBoggleSolution(std::string& currentPrefix,
std::vector<Vertex::Position>& usedPositionList,
StringArray& solution,
const Vertex::Position& currentPosition,
const GameBoard& board,
const StringArray& dictionary,
const Neighbors& neighborMap)
{
const std::list<Vertex::Position>& neighbors = neighborMap[currentPosition.first][currentPosition.second].neighbors;

for(std::list<Vertex::Position>::const_iterator itr = neighbors.begin(); itr != neighbors.end(); ++itr)
{
MatchResult matchResult = isPrefixMatch(dictionary, currentPrefix);

switch (matchResult)
{
case MATCH_AND_IS_JUST_PREFIX:{
if(currentPrefix.size() >= 3 && isWord(dictionary,currentPrefix) == MATCH_AND_IS_FULL_WORD){
solution.push_back(currentPrefix);
}
//continue if only neighbor isn't in our marked list
if(std::find(usedPositionList.begin(), usedPositionList.end(), *itr) == usedPositionList.end())
{
//add new letter to prefix
currentPrefix.push_back(board[itr->first][itr->second]);
//add position to used list
usedPositionList.push_back(*itr);

generateBoggleSolution(currentPrefix,
usedPositionList,
solution,
*itr,
board,
dictionary,
neighborMap);
//undo changes
currentPrefix.erase(currentPrefix.end() - 1);
usedPositionList.erase(usedPositionList.end() - 1);
}
break;
}
default:
break;
}

}
}

MatchResult isPrefixMatch(const StringArray& dictionary, const std::string& prefix)
{
int start = 0, end = int(dictionary.size());
while( start <= end){
int mid = start + (end - start) / 2;
int compResult = dictionary[mid].compare(0,prefix.size(),prefix);
if(compResult == 0 ){
return MATCH_AND_IS_JUST_PREFIX;
}else if(compResult < 0){
start = mid + 1;
}else{
end = mid - 1;
}
}
return NO_MATCH;
}
MatchResult isWord(const StringArray& dictionary, const std::string& word){
int start = 0, end = int(dictionary.size());
while( start <= end){
int mid = start + (end - start) / 2;
if(dictionary[mid] == word){
return MATCH_AND_IS_FULL_WORD;
}else if(dictionary[mid] < word){
start = mid + 1;
}else{
end = mid - 1;
}
}
return NO_MATCH;
}
//generate map for constant time neighbor lookup
//note there's probably better way to do this, but i'm lazy right now
Neighbors generateNeighbors(const GameBoard& board){
//assumtion nxn board
Neighbors neighbors( board.size(), std::vector<Vertex>(board.size()));

for (int row = 0; row < board.size() - 1; ++row) {
for(int col = 0; col < board[row].size() - 1; ++col){
Vertex& currentVertex = neighbors[row][col];
//current to right and reverse
currentVertex.neighbors.push_back(Vertex::Position(row,col + 1));
neighbors[row][col+1].neighbors.push_back(Vertex::Position(row,col));

//current to bottom right and reverse
currentVertex.neighbors.push_back(Vertex::Position(row+1,col+1));
neighbors[row+1][col+1].neighbors.push_back(Vertex::Position(row,col));

//current to bottom
currentVertex.neighbors.push_back(Vertex::Position(row+1,col));
neighbors[row+1][col].neighbors.push_back(Vertex::Position(row,col));
}
}

for (int row = 0; row < board.size() - 1; ++row) {
for(int col = 1; col < board[row].size(); ++col){
Vertex& currentVertex = neighbors[row][col];
//current to bottom left and reverse
currentVertex.neighbors.push_back(Vertex::Position(row+1,col-1));
neighbors[row+1][col-1].neighbors.push_back(Vertex::Position(row,col));
}
}

//for the last column
for(int row = 0; row < board.size() - 1; ++row){
int col = (int)board[row].size() - 1;
Vertex& currentVertex = neighbors[row][col];
//current to bottom and reverse
currentVertex.neighbors.push_back(Vertex::Position(row+1,col));
neighbors[row+1][col].neighbors.push_back(Vertex::Position(row,col));
}
//for the last row
for(int col = 0; col < board.size() - 1; ++col){
int row = (int)board.size() - 1;
Vertex& currentVertex = neighbors[row][col];
//currentEnd to right and reverse
currentVertex.neighbors.push_back(Vertex::Position(row,col + 1));
neighbors[row][col+1].neighbors.push_back(Vertex::Position(row,col));

}
for(int i = 0; i < board.size(); ++i){
for(int j = 0; j < board.size(); ++j){
neighbors[j].position = Vertex::Position(i,j);
}
}

return neighbors;
}
GameBoard readBoard(const std::string& filePath){
StringArray board;
#ifdef _DEBUG_
srand( time(0));
for(int i = 0; i < BOARD_SIZE; ++i)
{
string tmp;
for(int j = 0; j < BOARD_SIZE; ++j)
{
tmp.push_back( rand() % ('z' - 'a') + 'a');

}
board.push_back(tmp);
}
#else
ifstream fileIn(filePath.c_str());
std::copy(std::istream_iterator<std::string>(fileIn),
std::istream_iterator<std::string>(),
std::back_inserter(board));

#endif
return board;

}
StringArray readDictionary(const std::string& filePath){
ifstream fileIn(filePath.c_str());
StringArray result;
std::copy( std::istream_iterator<std::string>(fileIn),
std::istream_iterator<std::string>(),
std::back_inserter(result));
return result;
}
template<typename Iterator>
void print(Iterator begin, Iterator end, const std::string& delim){
while(begin != end){
cout << *begin << delim;
++begin;
}
}
[/source]

I profiled the code using xcode profiler and here is the result


Running Time Self Symbol Name
33.0ms 15.6% 33.0 std::string::compare(unsigned long, unsigned long, std::string const&) const
19.0ms 9.0% 19.0 std::string::_Rep::_M_dispose(std::allocator<char> const&)
16.0ms 7.5% 16.0 isPrefixMatch(std::vector<std::string, std::allocator<std::string> > const&, std::string const&)
11.0ms 5.2% 11.0 bcmp


Most of the time is stuck at std::string::compare in line 168. Any advice on what else can I do? It runs pretty fast already but I wanna make it faster. Just need some tips. Also note that it spends 19ms on removing strings. I might consider using static char arrays but that'll be a hassle.

I've never played Boggle, and I've only skimmed the code and the Wikipedia article, but it looks like you're doing a standard 'generate and test all the words beginning with this prefix', in which case you might want to look at storing your dictionary in a trie instead.

I've never played Boggle, and I've only skimmed the code and the Wikipedia article, but it looks like you're doing a standard 'generate and test all the words beginning with this prefix', in which case you might want to look at storing your dictionary in a trie instead.

I was going to go that route but I realized that constructing a trie from the dictionary is slow, although searching it is fast. I have done both and found my solution much faster. However, I want to point out that I'm testing prefix in a binary fashion instead of just linear searching the dictionary.

If you want to use a trie, but constructing it from the dictionary file is slow, then save the resulting structure after you've created it, and if a saved copy already exists, just load it instead of the dictionary.

I'd guess that a lot of your run-time is spent jumping around memory, as [font=courier new,courier,monospace]std::string[/font], [font=courier new,courier,monospace]std::vector<std::vector>[/font] and [font=courier new,courier,monospace]std::list[/font] will all give you very unpredictable memory access patterns. Using C arrays could help quite a bit with that -- you should be able to fit your entire data set into the L2 cache of a modern CPU if you structure it sensibly.

Replace the dictionary with a single big contiguous block of memory. Just load in the text file and replace newlines with NULL terminators, and store the beginning of each line in a table of [font=courier new,courier,monospace]char*[/font]'schar* dictionaryFile = readFile...
char** dictionaryTable = new char*[numberOfLinesIn(dictionaryFile)]
foreach( line in dictionaryFile )
dictionaryTable = line;
end = findNewLineChar( line )
line[end] = '\0'
Same goes for the game-board, it could just be a 2d array of chars too. To make string compares quick in all directions, I'd pre-rotate the board so you've got multiple copies of it - one copy for each direction you want to search, so that all searches can be done as a horizontal, left-to-right search using [font=courier new,courier,monospace]strcmp[/font].

Vertices shouldn't need to know their position, you should be able to infer it from where you fetched it from.
i.e. [font=courier new,courier,monospace]board[x][y].position == Pos(x,y)[/font] is redundant -- just keep track of x,y in the first place.
Likewise, vertices don't need to store neighbours - you can infer them from the position.

If you want to use a trie, but constructing it from the dictionary file is slow, then save the resulting structure after you've created it, and if a saved copy already exists, just load it instead of the dictionary.

I'd guess that a lot of your run-time is spent jumping around memory, as [font=courier new,courier,monospace]std::string[/font], [font=courier new,courier,monospace]std::vector<std::vector>[/font] and [font=courier new,courier,monospace]std::list[/font] will all give you very unpredictable memory access patterns. Using C arrays could help quite a bit with that -- you should be able to fit your entire data set into the L2 cache of a modern CPU if you structure it sensibly.

Replace the dictionary with a single big contiguous block of memory. Just load in the text file and replace newlines with NULL terminators, and store the beginning of each line in a table of [font=courier new,courier,monospace]char*[/font]'schar* dictionaryFile = readFile...
char** dictionaryTable = new char*[numberOfLinesIn(dictionaryFile)]
foreach( line in dictionaryFile )
dictionaryTable = line;
end = findNewLineChar( line )
line[end] = '\0'
Same goes for the game-board, it could just be a 2d array of chars too. To make string compares quick in all directions, I'd pre-rotate the board so you've got multiple copies of it - one copy for each direction you want to search, so that all searches can be done as a horizontal, left-to-right search using [font=courier new,courier,monospace]strcmp[/font].

Vertices shouldn't need to know their position, you should be able to infer it from where you fetched it from.
i.e. [font=courier new,courier,monospace]board[x][y].position == Pos(x,y)[/font] is redundant -- just keep track of x,y in the first place.
Likewise, vertices don't need to store neighbours - you can infer them from the position.

Ok I was afraid of converting this to a more C-version. I'll give it a shot. Thanks. I guess I should have thought about cache when programming. Great idea!

@Hodgman: Hey can you expand on this point a little bit more

To make string compares quick in all directions, I'd pre-rotate the board so you've got multiple copies of it - one copy for each direction you want to search, so that all searches can be done as a horizontal, left-to-right search using

[color=#282828]

strcmp

[color=#282828][font=helvetica, arial, verdana, tahoma, sans-serif]

.[/font]

[font=helvetica, arial, verdana, tahoma, sans-serif]

[color=#282828]I think I kind of get what you mean but still a little confused[/font]

EDIT: also I'm thinking what would be a good way to store the neighbors of a letter. Would this be more cache friendly?

struct Vertex{
int neighborPosition[8] ; //max neighbor could be 8
size_t neighborSize;
};

typedef Vertex** NeighborType


To make string compares quick in all directions, I'd pre-rotate the board so you've got multiple copies of it - one copy for each direction you want to search, so that all searches can be done as a horizontal, left-to-right search using strcmp

Ah sorry, I forgot the rules of Boggle when I wrote this and I was thinking of find-a-word puzzles, where the words have to be in a straight line... So this isn't relevant to you, but I meant that given the word-search puzzle at the top left, I would generate the other ones from it, so that I could do left/right/up/down/diagonal searches all as left-to-right searches:foo fbb oof bbf
bar oaa rab aao
baz orz zab zro

~~f~~ ~~f~~ ~~o~~ ~~b~~
~b o~ ~o b~ ~r o~ ~a b~
b a o o a b z a f z a f
~a r~ ~r a~ ~a b~ ~r o~
~~z~~ ~~z~~ ~~b~~ ~~o~~

EDIT: also I'm thinking what would be a good way to store the neighbors of a letter. Would this be more cache friendly?

You don't need to store neighbours at all - they can be calculated from the x/y position. To iterate through a node's neighbours, I would use something like:int offsets[8][2] = { {-1,-1}, {0,-1}, {1,-1},
{-1, 0}, {1, 0},
{-1, 1}, {1, 1}, {1, 1} };
int GetOffsetMask( int x, int y )
{
int mask = 0xFF;
mask &= (y==0) ? ~0x07 : ~0; //turn off top 3
mask &= (y==3) ? ~0xE0 : ~0; //turn off bottom 3
mask &= (x==0) ? ~0x29 : ~0; //turn off left 3
mask &= (x==3) ? ~0xA4 : ~0; //turn off right 3
return mask;
}
int LeastSignificantBit(int mask)
{
unsigned long result;
_BitScanForward(&result, mask);
return (int)result;
}
void foo()
{
int x=2, y=2;
int mask = GetOffsetMask(x,y);
while( mask )
{
int index = LeastSignificantBit(mask);//find index of lsb set
mask &= mask - 1;// clear the least significant bit set
int* offset = offsets[index];
int nextX = x + offset[0];
int nextY = y + offset[1];
DoSomething( x, y, nextX, nextY );
}
}The whole bit-mask and only-iterate-number-of-bits-set mechanics might be premature optimisation, but the idea that you can infer your neighbours from your position remains.

[quote name='D.Chhetri' timestamp='1329069612' post='4912296']To make string compares quick in all directions, I'd pre-rotate the board so you've got multiple copies of it - one copy for each direction you want to search, so that all searches can be done as a horizontal, left-to-right search using strcmp

Ah sorry, I forgot the rules of Boggle when I wrote this and I was thinking of find-a-word puzzles, where the words have to be in a straight line... So this isn't relevant to you, but I meant that given the word-search puzzle at the top left, I would generate the other ones from it, so that I could do left/right/up/down/diagonal searches all as left-to-right searches:foo fbb oof bbf
bar oaa rab aao
baz orz zab zro

~~f~~ ~~f~~ ~~o~~ ~~b~~
~b o~ ~o b~ ~r o~ ~a b~
b a o o a b z a f z a f
~a r~ ~r a~ ~a b~ ~r o~
~~z~~ ~~z~~ ~~b~~ ~~o~~

EDIT: also I'm thinking what would be a good way to store the neighbors of a letter. Would this be more cache friendly?

You don't need to store neighbours at all - they can be calculated from the x/y position. To iterate through a node's neighbours, I would use something like:int offsets[8][2] = { {-1,-1}, {0,-1}, {1,-1},
{-1, 0}, {1, 0},
{-1, 1}, {1, 1}, {1, 1} };
int GetOffsetMask( int x, int y )
{
int mask = 0xFF;
mask &= (y==0) ? ~0x07 : ~0; //turn off top 3
mask &= (y==3) ? ~0xE0 : ~0; //turn off bottom 3
mask &= (x==0) ? ~0x29 : ~0; //turn off left 3
mask &= (x==3) ? ~0xA4 : ~0; //turn off right 3
return mask;
}
int LeastSignificantBit(int mask)
{
unsigned long result;
_BitScanForward(&result, mask);
return (int)result;
}
void foo()
{
int x=2, y=2;
int mask = GetOffsetMask(x,y);
while( mask )
{
int index = LeastSignificantBit(mask);//find index of lsb set
mask &= mask - 1;// clear the least significant bit set
int* offset = offsets[index];
int nextX = x + offset[0];
int nextY = y + offset[1];
DoSomething( x, y, nextX, nextY );
}
}The whole bit-mask and only-iterate-number-of-bits-set mechanics might be premature optimisation, but the idea that you can infer your neighbours from your position remains.
[/quote]


Yea I decided to calculate it, but its such a naive attempt compared to yours,


Position* getNeighbor(const size_t MIN_BOUND, const size_t MAX_BOUND, const size_t row, const size_t col, size_t& numberOfNeighbors){
static const size_t MAX_NEIGHBORS = 8;
static Position neighbors[MAX_NEIGHBORS] = { };
static Position possibleNeighbors[MAX_NEIGHBORS] = {{-1,-1}, {0,-1}, {1,-1}, {-1, 0}, {1, 0}, {-1, 1}, {1, 1}, {1, 1} };
size_t size = 0;
//calculate neighbor
for(int i = 0; i < MAX_NEIGHBORS; ++i)
{
int nr = row + possibleNeighbors[0];
int nc = col + possibleNeighbors[1];
//check if within bounds
if(nr >= MIN_BOUND && nr < MAX_BOUND){
if(nc >= MIN_BOUND && nc < MAX_BOUND){
neighbors[size][0] = nr;
neighbors[size][1] = nc;
++size;
}
}
}
numberOfNeighbors = size;
return neighbors;
}


Only if I can understand what your code is actually doing, I need to think about it for a second before I decide to use it or not. I hate using something that I don't know how it works or have some sort of general idea.

EDIT: Neat implementation now that I think about it!