3 files changed, 242 insertions, 16 deletions

diff --git a/labb5/src/Boggle.cpp b/labb5/src/Boggle.cpp
index 9988c4e..be4d40b 100755
--- a/labb5/src/Boggle.cpp
+++ b/labb5/src/Boggle.cpp
@@ -5,18 +5,172 @@
 // TODO: remove this comment header and replace it with your own
 
 #include <sstream>
+#include <iostream>
 #include "Boggle.h"
 #include "random.h"
 #include "shuffle.h"
 #include "strlib.h"
+#include <chrono>
 
-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"
+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"
 };
 
-// TODO: implement the members you declared in Boggle.h
+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 >= height) continue;
+            point new_p = make_pair(x + dx, y + dy);
+            if (visited.count(new_p)) continue;
+            res.push_back(new_p);
+        }
+    }
+    return res;
+}
+
+Boggle::Boggle() {
+    board = Grid<char>(4, 4);
+    dictionary = Lexicon(DICTIONARY_FILE);
+}
+
+bool Boggle::letters_from_string(const string& letters) {
+    if (letters.length() != 16) {
+        return false;
+    }
+    for (const auto& letter : letters) {
+        if (!isalpha(letter)) {
+            return false;
+        }
+    }
+
+    for (int y = 0; y < 4; y++) {
+        for (int x = 0; x < 4; x++) {
+            char c = letters[4*y + x];
+            board[y][x] = c;
+        }
+    }
+    return true;
+}
+
+void Boggle::clear() {
+    valid_words.clear();
+    user_words.clear();
+    user_score = 0;
+}
+
+void Boggle::shuffle() {
+    // Shuffle each dice separately
+    for (int y = 0; y < 4; y++) {
+        for (int x = 0; x < 4; x++) {
+            board[y][x] = CUBES[4*y + x][randomInteger(0, CUBE_SIDES-1)];
+        }
+    }
+    // Shuffle positions
+    ::shuffle(board);
+}
+
+void Boggle::find_all_words() {
+    auto start = std::chrono::high_resolution_clock::now();
+    for (int y = 0; y < 4; y++) {
+        for (int x = 0; x < 4; x++) {
+            find_words_helper(make_pair(x, y), string(1, board[y][x]), set<point>());
+        }
+    }
+    auto end = std::chrono::high_resolution_clock::now();
+    cout << valid_words.size()
+         << " words in "
+         << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count()/1000.0
+         << " ms"
+         << endl;
+}
+
+void Boggle::find_words_helper(point cur_point, string cur_word, set<point> visited) {
+    if (cur_word.length() >= 4 && valid_words.count(cur_word) == 0 && dictionary.contains(cur_word)) {
+        valid_words.insert(cur_word);
+    }
+    visited.insert(cur_point);
+    for (const auto& neighbour : neighbours_in_range_filt(cur_point, 4, 4, visited)) {
+        string new_word = cur_word + board[get<1>(neighbour)][get<0>(neighbour)];
+        if (dictionary.containsPrefix(new_word)) {
+            find_words_helper(neighbour, new_word, visited);
+        }
+    }
+    visited.erase(cur_point);
+}
+
+string Boggle::debug_words() const {
+    string res = "";
+    for (const auto& word : valid_words) {
+        res += word + " ";
+    }
+    return res;
+}
+
+string Boggle::board_to_string() const {
+    string res = "";
+    for (int y = 0; y < 4; y++) {
+        for (int x = 0; x < 4; x++) {
+            res += board[y][x];
+        }
+        res += '\n';
+    }
+    return res;
+}
+
+int Boggle::get_user_words_size() const {
+    return user_words.size();
+}
+
+int Boggle::get_user_score() const {
+    return user_score;
+}
+
+bool Boggle::word_is_valid(const string& word) const {
+    return valid_words.count(word);
+}
+
+bool Boggle::word_is_unplayed(const string& word) const {
+    return !user_words.count(word);
+}
+
+bool Boggle::add_user_word(const string& word) {
+    if (word_is_valid(word) && word_is_unplayed(word) && word.length() >= 4) {
+        user_words.insert(word);
+        user_score += word.length() - 3;
+        return true;
+    }
+    return false;
+}
+
+string Boggle::user_words_to_string(int words_per_line) const {
+    string res = "";
+    long unsigned int cur_word_idx = 0;
+    for (const auto& word : user_words) {
+        res += word;
+        if (cur_word_idx != user_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';
+            }
+        } else {
+            // newline after final
+            res += '\n';
+        }
+        cur_word_idx++;
+    }
+    return res;
+}
diff --git a/labb5/src/Boggle.h b/labb5/src/Boggle.h
index 3abe9b5..b6551ee 100755
--- a/labb5/src/Boggle.h
+++ b/labb5/src/Boggle.h
@@ -9,21 +9,47 @@
 
 #include <iostream>
 #include <string>
-// TODO: include any other header files you need
+#include <set>
+#include "lexicon.h"
+#include "grid.h"
+#include <utility>
 
 using namespace std;
+using point = pair<int, int>;
 
 class Boggle {
 public:
     const string DICTIONARY_FILE = "EnglishWords.dat";
     const int MIN_WORD_LENGTH = 4;
-    const int BOARD_SIZE = 4;
+    static const int BOARD_SIZE = 4;
 
-    // TODO: decide the public member functions and declare them
+    Boggle();
+    bool letters_from_string(const string& letters);
 
-private:
-    // TODO: decide the private member variables/functions and declare them
+    void read_dictionary();
+    void clear();
+    void shuffle();
+
+    void find_all_words();
+    string debug_words() const;
+
+    string board_to_string() const;
+    string user_words_to_string(int words_per_line = 3) const;
 
+    int get_user_words_size() const;
+    int get_user_score() const;
+
+    bool word_is_valid(const string& word) const;
+    bool word_is_unplayed(const string& word) const;
+    bool add_user_word(const string& word);
+
+private:
+    void find_words_helper(point cur_point, string cur_word, set<point> visited);
+    Lexicon dictionary;
+    Grid<char> board;
+    set<string> user_words;
+    set<string> valid_words;
+    int user_score = 0;
 };
 
 #endif
diff --git a/labb5/src/boggleplay.cpp b/labb5/src/boggleplay.cpp
index 76bdcde..914443b 100755
--- a/labb5/src/boggleplay.cpp
+++ b/labb5/src/boggleplay.cpp
@@ -1,6 +1,6 @@
 // You will edit and turn in this CPP file.
 // Also remove these comments here and add your own.
-// TODO: remove this comment header and replace with your own
+// TODO remove this comment header and replace with your own
 
 #include <cstdlib>
 #include <iostream>
@@ -9,13 +9,59 @@
 #include "Boggle.h"
 #include "bogglemain.h"
 #include "strlib.h"
-// TODO: include any other header files you need
+
+#include <string>
 
 /*
  * Plays one game of Boggle using the given boggle game state object.
  */
 void playOneGame(Boggle& boggle) {
-    // TODO: implement this function (and add any other functions you like to help you)
+    boggle.clear();
+    bool input_custom_board = yesOrNo("Input custom board? ");
+    if (input_custom_board) {
+        string input_board;
+        while (true) {
+            cout << "Input your board (16 characters): ";
+            getline(cin, input_board);
+            if (input_board.length() == 16) {
+                if (boggle.letters_from_string(input_board)) {
+                    break;
+                } else {
+                    cout << "Please input a valid string" << endl;
+                }
+            } else {
+                cout << "Please input 16 characters only" << endl;
+            }
+        }
+    } else {
+        boggle.shuffle();
+    }
+    boggle.find_all_words();
+    cout << boggle.debug_words() << endl;
+
+    std::cout << "It's your turn!" << std::endl;
+    cout << boggle.board_to_string() << endl;
+    string user_input;
+    while (true) {
+        cout << "Your words (" << boggle.get_user_words_size() << "):" << endl;
+        cout << boggle.user_words_to_string() << endl;
+        cout << "Your score: " << boggle.get_user_score() << endl;
+        cout << "Type a word (or press Enter to end your turn) ";
+        getline(cin, user_input);
+        if (user_input == "") {
+            break;
+        }
+        if (!boggle.word_is_valid(user_input)) {
+            cout << "Your word is invalid" << endl;
+        } else if (!boggle.word_is_unplayed(user_input)) {
+            cout << "Your word has already been played!" << endl;
+        } else if (user_input.length() < 4) {
+            cout << "Your word is too short!" << endl;
+        } else {
+            cout << "You found a new word!" << endl;
+            boggle.add_user_word(user_input);
+        }
+    }
 
 }