path: root/labb5/src/Boggle.cpp

// This is the .cpp file you will edit and turn in.
// We have provided a minimal skeleton for you,
// but you must finish it as described in the spec.
// Also remove these comments here and add your own.
// TODO: remove this comment header and replace it with your own

#include "Boggle.h"

#include <algorithm>
#include <chrono>
#include <iostream>
#include <sstream>
#include "random.h"
#include "shuffle.h"
#include "strlib.h"

static const int NUM_CUBES = 16;    // the number of cubes in the game
static const int CUBE_SIDES = 6;    // the number of sides on each cube
static string CUBES[NUM_CUBES] = {  // the letters on all 6 sides of every cube
    "AAEEGN", "ABBJOO", "ACHOPS", "AFFKPS",
    "AOOTTW", "CIMOTU", "DEILRX", "DELRVY",
    "DISTTY", "EEGHNW", "EEINSU", "EHRTVW",
    "EIOSST", "ELRTTY", "HIMNQU", "HLNNRZ"
};

/*
 * Find all immediate neighbours (including diagonally).
 *
 * Only returns points where x is in [0, w) and y is in [0, h).
 * Additionally, points in visited are ignored.
 */
vector<point> neighbours_in_range_filt(const point& p, int width, int height, const set<point>& visited) {
    int x, y;
    tie(x, y) = p;
    vector<point> res = vector<point>();
    for (int dy = -1; dy <= 1; dy++) {
        if (y + dy < 0 || y + dy >= height) continue;
        for (int dx = -1; dx <= 1; dx++) {
            if (dy == 0 && dx == 0) continue;
            if (x + dx < 0 || x + dx >= width) continue;
            point new_p = make_pair(x + dx, y + dy);
            if (visited.count(new_p)) continue;
            res.push_back(new_p);
        }
    }
    return res;
}

/*
 * Return whether word starts with prefix.
 */
bool prefix_matches(const string& prefix, const string& word) {
    //NOTE There is a string::starts_with in C++20.
    for (int i = 0; i < prefix.length(); i++) {
        if (prefix[i] != word[i]) return false;
    }
    return true;
}

Boggle::Boggle() {
    board = Grid<char>(BOARD_SIZE, BOARD_SIZE);
    dictionary = Lexicon(DICTIONARY_FILE);
}

bool Boggle::board_from_string(const string& letters) {
    if (letters.length() != BOARD_SIZE * BOARD_SIZE) {
        return false;
    }
    for (const auto& letter : letters) {
        if (!isalpha(letter)) {
            return false;
        }
    }

    for (int y = 0; y < BOARD_SIZE; y++) {
        for (int x = 0; x < BOARD_SIZE; x++) {
            char c = letters[BOARD_SIZE*y + x];
            board[y][x] = c;
        }
    }
    return true;
}

void Boggle::clear() {
    user_words.clear();
    computer_words.clear();
    user_score = 0;
    computer_score = 0;
}

void Boggle::shuffle() {
    // Shuffle each dice separately
    for (int y = 0; y < BOARD_SIZE; y++) {
        for (int x = 0; x < BOARD_SIZE; x++) {
            board[y][x] = CUBES[(BOARD_SIZE*y + x) % NUM_CUBES][randomInteger(0, CUBE_SIDES-1)];
        }
    }
    // Shuffle positions
    ::shuffle(board);
}

bool Boggle::find_single_word(const string& word) const {
    auto start = std::chrono::high_resolution_clock::now();
    // We break immediately if we find a match.
    // Without the clock we would return right away.
    bool found = false;
    for (int y = 0; y < BOARD_SIZE; y++) {
        for (int x = 0; x < BOARD_SIZE; x++) {
            found = find_single_word_helper(word, make_pair(x, y), string(1, board[y][x]), set<point>());
            if (found) break;
        }
        if (found) break;
    }
    auto end = std::chrono::high_resolution_clock::now();
    if (debug_mode) {
        if (found) {
            cout << "Found word";
        } else {
            cout << "Couldn't find word";
        }
        cout << " in "
             << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count()/1000.0
             << " ms"
             << endl;
    }
    return found;
}

bool Boggle::find_single_word_helper(const string& word, point cur_point, string cur_word, set<point> visited) const {
    if (cur_word == word) {
        return true;
    }
    visited.insert(cur_point);
    for (const auto& neighbour : neighbours_in_range_filt(cur_point, BOARD_SIZE, BOARD_SIZE, visited)) {
        int n_x, n_y;
        tie(n_x, n_y) = neighbour;
        string new_word = cur_word + board[n_y][n_x];
        if (prefix_matches(new_word, word)) {
            if (find_single_word_helper(word, neighbour, new_word, visited)) {
                return true;
            }
        }
    }
    return false;
}

set<string> Boggle::find_all_words() const {
    set<string> words;
    auto start = std::chrono::high_resolution_clock::now();
    for (int y = 0; y < BOARD_SIZE; y++) {
        for (int x = 0; x < BOARD_SIZE; x++) {
            find_all_words_helper(words, make_pair(x, y), string(1, board[y][x]), set<point>());
        }
    }
    auto end = std::chrono::high_resolution_clock::now();
    if (debug_mode) {
        cout << words.size()
             << " words in "
             << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count()/1000.0
             << " ms"
             << endl;
    }
    return words;
}

void Boggle::find_all_words_helper(set<string>& words, point cur_point, string cur_word, set<point> visited) const {
    if (cur_word.length() >= 4 && words.count(cur_word) == 0 && dictionary.contains(cur_word)) {
        words.insert(cur_word);
    }
    visited.insert(cur_point);
    for (const auto& neighbour : neighbours_in_range_filt(cur_point, BOARD_SIZE, BOARD_SIZE, visited)) {
        int n_x, n_y;
        tie(n_x, n_y) = neighbour;
        string new_word = cur_word + board[n_y][n_x];
        if (dictionary.containsPrefix(new_word)) {
            find_all_words_helper(words, neighbour, new_word, visited);
        }
    }
}

string Boggle::board_to_string() const {
    string res = "";
    for (int y = 0; y < board.numRows(); y++) {
        for (int x = 0; x < board.numCols(); x++) {
            res += board[y][x];
            res += ' ';
        }
        res += '\n';
    }
    return res;
}

void Boggle::do_computer_turn() {
    set<string> all_words = find_all_words();
    set_difference(all_words.begin(), all_words.end(),
                   user_words.begin(), user_words.end(),
                   inserter(computer_words, computer_words.begin()));
    for (const auto& word : computer_words) {
        computer_score += word.length() - 3;
    }
}

int Boggle::get_computer_words_size() const {
    return computer_words.size();
}

int Boggle::get_computer_score() const {
    return computer_score;
}

int Boggle::get_user_words_size() const {
    return user_words.size();
}

int Boggle::get_user_score() const {
    return user_score;
}

bool Boggle::word_is_unplayed(const string& word) const {
    return !user_words.count(word);
}

bool Boggle::word_is_valid(const string& word) const {
    return dictionary.contains(word);
}

void Boggle::add_user_word(const string& word) {
    user_words.insert(word);
    user_score += word.length() - 3;
}

string Boggle::user_words_to_string(int words_per_line) const {
    return words_to_string(user_words, words_per_line);
}

string Boggle::computer_words_to_string(int words_per_line) const {
    return words_to_string(computer_words, words_per_line);
}

string Boggle::words_to_string(const set<string>& words, int words_per_line) const {
    string res = "";
    long unsigned int cur_word_idx = 0;
    for (const auto& word : words) {
        res += word;
        if (cur_word_idx != words.size() - 1) {
            // comma after every word except the final
            res += ", ";

            // newline after some amount of words
            // +1 so the first line works out
            if ((cur_word_idx+1) % words_per_line == 0) {
                res += '\n';
            }
        }
        cur_word_idx++;
    }
    return res;
}