initial work labb5

Apparently I need to implement a second search function here.
I don't agree with the reasoning in the lab description.

> NOTERA: Programmet innehåller två rekursiva sökningar: en för att
> hitta ett specifikt ord inmatat av den mänskliga spelaren och en
> annan för att söka ̈över hela brädet under datorspelarens tur. Du
> tänker kanske att dessa borde gå att kombinera till en integrerad
> funktion, genom att göra all ordsökning i början av spelet, precis
> efter att brädet initierats.  För att bli godkänd på labben måste
> du dock implementera människan och datorn som två separata
> sökfunktioner.  Det finns tillräckliga skillnader mellan de två för
> att de inte ska gå att kombinera rent och snyggt.

1 files changed, 162 insertions, 8 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;
+}