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