diff options
Diffstat (limited to 'labb5/src/Boggle.cpp')
| -rwxr-xr-x | labb5/src/Boggle.cpp | 119 |
1 files changed, 89 insertions, 30 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 += ", "; |