Skip to content

Instantly share code, notes, and snippets.

@jakab922
Last active November 28, 2020 14:59
Show Gist options
  • Save jakab922/1500848046bc7ac038f0d3820b25d329 to your computer and use it in GitHub Desktop.
Save jakab922/1500848046bc7ac038f0d3820b25d329 to your computer and use it in GitHub Desktop.
Boggle board solver in C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
vector<int> endings;
unordered_map<char, Node*> followers;
};
void insert_trie(Node *node, const string &word, int index) {
int ws = word.size();
for(int i = 0; i < ws; i++) {
if(node->followers.find(word[i]) == node->followers.end()) node->followers[word[i]] = new Node;
node = node->followers[word[i]];
}
node->endings.push_back(index);
}
bool is_in(const int i, const int j, const int height, const int width) {
return 0 <= i && i < height && 0 <= j && j < width;
}
const vector<pair<int, int>> deltas {
{0, 1},
{0, -1},
{1, 0},
{-1, 0},
{1, 1},
{-1, -1},
{1, -1},
{-1, 1}
};
void fill_in(const vector<vector<char>> &board, const int i, const int j, Node *node, vector<bool> &was, vector<vector<bool>> &occupied) {
const int height = board.size(), width = board[0].size();
if(is_in(i, j, height, width) && !occupied[i][j] && node->followers.find(board[i][j]) != node->followers.end()) {
occupied[i][j] = true;
Node *new_node = node->followers[board[i][j]];
for(const auto index : new_node->endings) was[index] = true;
for(const auto &delta : deltas) fill_in(board, i + delta.first, j + delta.second, new_node, was, occupied);
occupied[i][j] = false;
}
}
vector<string> boggleBoard(vector<vector<char>> board, vector<string> words) {
int ws = words.size();
vector<bool> was(ws, false);
int height = board.size(), width = board[0].size();
vector<vector<bool>> occupied(height, vector<bool>(width, false));
Node *root = new Node;
for(int i = 0; i < ws; i++) insert_trie(root, words[i], i);
for(int i = 0; i < height; i++) {
for(int j = 0; j < width; j++) {
fill_in(board, i, j, root, was, occupied);
}
}
vector<string> ret;
for(int i = 0; i < ws; i++) {
if(was[i]) ret.push_back(words[i]);
}
return ret;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment