Jump to content
  • Advertisement
Sign in to follow this  
Concentrate

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.

If you intended to correct an error in the post then please contact us.

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();
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.

Share this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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]

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

Share this post


Link to post
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 this post


Link to post
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!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!