two different search functions, some polish

3 files changed, 117 insertions, 43 deletions

diff --git a/labb5/src/Boggle.cpp b/labb5/src/Boggle.cpp
index be4d40b..06880e8 100755
--- a/labb5/src/Boggle.cpp
+++ b/labb5/src/Boggle.cpp
@@ -11,6 +11,7 @@
 #include "shuffle.h"
 #include "strlib.h"
 #include <chrono>
+#include <algorithm>
 
 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
@@ -29,7 +30,7 @@ vector<point> neighbours_in_range_filt(const point& p, int width, int height, co
         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;
+            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);
@@ -63,9 +64,10 @@ bool Boggle::letters_from_string(const string& letters) {
 }
 
 void Boggle::clear() {
-    valid_words.clear();
     user_words.clear();
+    computer_words.clear();
     user_score = 0;
+    computer_score = 0;
 }
 
 void Boggle::shuffle() {
@@ -79,41 +81,80 @@ void Boggle::shuffle() {
     ::shuffle(board);
 }
 
-void Boggle::find_all_words() {
+bool Boggle::find_single_word(const string& word) const {
     auto start = std::chrono::high_resolution_clock::now();
+    bool found = false;
     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>());
+            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();
-    cout << valid_words.size()
-         << " words in "
+    if (found) {
+        cout << "Found word";
+    } else {
+        cout << "Didn't find word";
+    }
+    cout << " in "
          << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count()/1000.0
          << " ms"
          << endl;
+    return found;
+}
+
+bool prefix_matches(const string& prefix, const string& word) {
+    for (int i = 0; i < prefix.length(); i++) {
+        if (prefix[i] != word[i]) return false;
+    }
+    return true;
 }
 
-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);
+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, 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);
+        if (prefix_matches(new_word, word)) {
+            if (find_single_word_helper(word, neighbour, new_word, visited)) {
+                return true;
+            }
         }
     }
-    visited.erase(cur_point);
+    return false;
 }
 
-string Boggle::debug_words() const {
-    string res = "";
-    for (const auto& word : valid_words) {
-        res += word + " ";
+set<string> Boggle::find_all_words() const {
+    set<string> words;
+    auto start = std::chrono::high_resolution_clock::now();
+    for (int y = 0; y < 4; y++) {
+        for (int x = 0; x < 4; 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();
+    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, 4, 4, visited)) {
+        string new_word = cur_word + board[get<1>(neighbour)][get<0>(neighbour)];
+        if (dictionary.containsPrefix(new_word)) {
+            find_all_words_helper(words, neighbour, new_word, visited);
+        }
     }
-    return res;
 }
 
 string Boggle::board_to_string() const {
@@ -127,6 +168,24 @@ string Boggle::board_to_string() const {
     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();
 }
@@ -135,29 +194,29 @@ 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;
+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 : user_words) {
+    for (const auto& word : words) {
         res += word;
-        if (cur_word_idx != user_words.size() - 1) {
+        if (cur_word_idx != words.size() - 1) {
             // comma after every word except the final
             res += ", ";
 
diff --git a/labb5/src/Boggle.h b/labb5/src/Boggle.h
index b6551ee..9e6e9cd 100755
--- a/labb5/src/Boggle.h
+++ b/labb5/src/Boggle.h
@@ -30,26 +30,35 @@ public:
     void clear();
     void shuffle();
 
-    void find_all_words();
-    string debug_words() const;
+    set<string> find_all_words() const;
+    bool find_single_word(const string& word) const;
 
     string board_to_string() const;
     string user_words_to_string(int words_per_line = 3) const;
+    string computer_words_to_string(int words_per_line = 3) const;
+
+    void do_computer_turn();
+    int get_computer_words_size() const;
+    int get_computer_score() 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);
+    void add_user_word(const string& word);
 
 private:
-    void find_words_helper(point cur_point, string cur_word, set<point> visited);
+    void find_all_words_helper(set<string>& words, point cur_point, string cur_word, set<point> visited) const;
+    bool find_single_word_helper(const string& word, point cur_point, string cur_word, set<point> visited) const;
+    string words_to_string(const set<string>& words, int words_per_line) const;
+
     Lexicon dictionary;
     Grid<char> board;
     set<string> user_words;
-    set<string> valid_words;
+    set<string> computer_words;
     int user_score = 0;
+    int computer_score = 0;
 };
 
 #endif
diff --git a/labb5/src/boggleplay.cpp b/labb5/src/boggleplay.cpp
index 914443b..da03d93 100755
--- a/labb5/src/boggleplay.cpp
+++ b/labb5/src/boggleplay.cpp
@@ -36,14 +36,11 @@ void playOneGame(Boggle& boggle) {
     } 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;
+        std::cout << "It's your turn!" << std::endl;
+        cout << boggle.board_to_string() << endl;
+        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) ";
@@ -51,7 +48,7 @@ void playOneGame(Boggle& boggle) {
         if (user_input == "") {
             break;
         }
-        if (!boggle.word_is_valid(user_input)) {
+        if (!boggle.find_single_word(user_input)) {
             cout << "Your word is invalid" << endl;
         } else if (!boggle.word_is_unplayed(user_input)) {
             cout << "Your word has already been played!" << endl;
@@ -62,7 +59,16 @@ void playOneGame(Boggle& boggle) {
             boggle.add_user_word(user_input);
         }
     }
-
+    cout << "It's my turn!" << endl;
+    boggle.do_computer_turn();
+    cout << "My words (" << boggle.get_computer_words_size() << "): " << endl;
+    cout << boggle.computer_words_to_string() << endl;
+    cout << "My score: " << boggle.get_computer_score() << endl;
+    if (boggle.get_computer_score() > boggle.get_user_score()) {
+        cout << "Ha ha ha, I destroyed you. Better luck next time, puny human!" << endl;
+    } else {
+        cout << "WOW, you defeated me! Congratulations!" << endl;
+    }
 }
 
 /*