Public Group

# Help me optimize this boggle solver[ C++ ]

This topic is 2500 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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();
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
{
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())
{
currentPrefix.push_back(board[itr->first][itr->second]);
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;
}
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;

}
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.

##### Share on other sites
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.

##### Share on other sites

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.

##### Share on other sites
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.

##### Share on other sites

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!

##### Share on other sites
@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]

### [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 

##### Share on other sites
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.

##### Share on other sites

[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!

1. 1
2. 2
Rutin
20
3. 3
khawk
16
4. 4
A4L
14
5. 5

• 11
• 16
• 26
• 10
• 11
• ### Forum Statistics

• Total Topics
633756
• Total Posts
3013707
×