Boggle board solver in C++

Question

This C++ Boggle board solver is intended to take in many boards one after another and score them.

I would like comments on code style, whether there are C++ standard library features that I could use to streamline the code, appropriate division between public and private, etc.

Download code

Download dictionary file

Boggle

Boggle is a board game with a 4x4 board of squares, each of which has a letter, in which you score points by finding words on the board. This is an example Boggle board:

c a t c
a t c a
t c a t
c a t c

This board contains the words 'cat', 'act', 'tact', etc. The words must be made up of neighboring squares (left, right, up, down, and diagonal), and you can't use the same square twice in a word. Words don't need to be in a straight line.

Code

Boggle class

The Boggle class stores the board.

• board stores the letters in a vector of structs, each of which stores a letter, the row and column, and a vector of indices for neighboring squares.
• Load loads a string into the board.
• Print prints the board.
• Score finds all words on the board and calculates how much they're worth.
• Words (private member function) finds all words starting at a given square on the board.

...

#include <map>
#include <string>
#include <unordered_set>
#include <vector>

// Map word lengths to points
std::map<int, int> POINTS = {{3, 1}, {5, 2}, {6, 3}, {7, 5}, {8, 11}};

// Boggle board class
class Boggle {
private:
    struct square {
        std::string value;
        int row;
        int col;
        std::vector<int> neighbors;

        square(int row, int col);
    };

    int size;
    std::vector<square> board;
    Dictionary dict;
    std::map<int, int> points;
    std::unordered_set<std::string> found_words;
    void Words(int position, std::string str = "", std::unordered_set<int> visited = std::unordered_set<int>());

public:
    Boggle(Dictionary dict, int size = 4, std::map<int, int> points = POINTS);
    ~Boggle();

    void Load(std::string letters);
    void Print();
    int Score();
};

// Boggle board constructor
Boggle::Boggle(Dictionary dict, int size, std::map<int, int> points) {
    this->dict = dict;
    this->size = size;
    this->points = points;
    int row, col;

    // Add squares to the board
    for (int i = 0; i < size * size; i++) {
        row = i / size;
        col = i % size;
        board.push_back(square(row, col));
    }

    // Add each square's neighbors
    std::vector<int> shift {-1, 0, 1};
    for (square &sq : board) {
        for (int row_shift : shift) {
            for (int col_shift : shift) {
                row = sq.row + row_shift;
                col = sq.col + col_shift;
                if (row >= 0 & row < size & col >= 0 & col < size & !(row_shift == 0 & col_shift == 0)) {
                    sq.neighbors.push_back(row * size + col);
                }
            }
        }
    }
}

Boggle::~Boggle() {}

// Boggle square constructor
Boggle::square::square(int row, int col) {
    this->row = row;
    this->col = col;
}

// Load a string of letters into the board
void Boggle::Load(std::string letters) {
    int i = 0;
    for (square &it : board) {
        it.value = letters[i];
        i += 1;
    }
    // Clear any previously found words
    found_words.clear();
}

// Print the board
void Boggle::Print() {
    for (const square &sq : board) {
        std::cout << sq.value << " ";
        if (sq.col == size - 1) {
            std::cout << std::endl;
        }
    }
}

// Find all words, then calculate the score
int Boggle::Score() {
    int score = 0;

    // Find words for all squares on the board
    for (int i = 0; i < board.size(); i++) {
        Words(i);
    }

    // For each word, look up points and add to the score
    std::map<int, int>::iterator point;
    for (const std::string &word : found_words) {
        // Find the smallest point map key greater than word length, then move back one step
        // to get the largest key less than or equal to word length, e.g. 4->5->3
        point = points.upper_bound(word.length());
        --point;
        score += point->second;
    }

    return score;
}

// Find all words starting at a given position
void Boggle::Words(int position, std::string string, std::unordered_set<int> visited) {

    square &sq = board[position];
    string = string + sq.value;
    visited.insert(position);

    // If the string is a word, add it to the found words
    if (dict.words.find(string) != dict.words.end()) {
        found_words.insert(string);
    }

    // If the string is a prefix, continue looking
    if (dict.prefixes.find(string) != dict.prefixes.end()) {
        for (const int &neighbor : sq.neighbors) {
            if (visited.find(neighbor) == visited.end()) {
                Words(neighbor, string, visited);
            }
        }
    }
}

Dictionary class

The Dictionary class reads in and stores the dictionary of words and word prefixes. The class constructor takes a path to the dictionary file. A Boggle object needs a Dictionary when the Boggle object is created.

...

#include <fstream>
#include <iostream>
#include <unordered_set>


class Dictionary {
public:
    Dictionary();
    Dictionary(std::string, int word_length = 3);
    ~Dictionary();

    std::unordered_set<std::string> words;
    std::unordered_set<std::string> prefixes;
};

Dictionary::Dictionary() {};

// Load the word dictionary and prefixes dictionary from a given file
Dictionary::Dictionary(std::string path, int word_length) {
    std::string line;
    std::ifstream file(path);
    if (file.is_open()) {
        while (std::getline(file, line)) {
            if (line.length() >= word_length) {
                // Add to word dictionary
                this->words.insert(line);

                // Add to prefixes dictionary
                for (int i = 1; i < line.length(); i++) {
                    this->prefixes.insert(line.substr(0, i));
                }
            }
        }
    }
    file.close();
}

Dictionary::~Dictionary() {};

Example program

int main() {
    Dictionary dict("twl06.txt");
    Boggle b(dict);
    b.Load("serspatglinesers");
    b.Print();
    std::cout << b.Score() << std::endl;
}

Output:

s e r s
p a t g
l i n e
s e r s
3692

Thank you!

Answer 1

About the constructor of Boggle

From a stylistic point of view, instead of assigning member fields inside the constructor in java style, the C++ way is rather to use an initializer list.

That is to say, instead of:

Boggle::Boggle(Dictionary dict, int size, std::map<int, int> points) {
    this->dict = dict;
    this->size = size;
    this->points = points;

You can write:

Boggle::Boggle(Dictionary dict, int size, std::map<int, int> points):
   dict(dict),
   size(size),
   points(point)
{

One big advantage of using an initializer list over assignments inside the constructor's body, is that you can now declare these variables as const, or even use a reference instead, which avoids the copy. Using references will save a lot of work, but you have to make sure that the referred-to object is not deleted before the end of the Boggle instance.

Performance

Your code is likely to be much slower than it could be. One source of slowness is the std::unordered_set<int> visited. Each call to the recursive Word function makes a copy of the set. There are two ideas that could improve this a lot.

The first idea is to use a reference instead of a copy. That is to say, use std::unordered_set<int> &visited. With a reference, you also have to make sure that the set is restored to its initial state before quitting the function: add visited.erase(position); before returning.

Another more important idea is that, instead of using a std::set, you could simply use an array of flags that indicate, for each possible position, whether it was visited or not. insert and erase operations on such a representation of a set will be considerably more efficient: it simply consists in setting an array element to true or false.

Yet another performance idea: using a prefix-tree data structure might be a lot faster: https://en.wikipedia.org/wiki/Trie . But there is not such container in standard C++.