diff options
| -rwxr-xr-x | labb5/src/Boggle.cpp | 80 | ||||
| -rwxr-xr-x | labb5/src/Boggle.h | 1 |
2 files changed, 63 insertions, 18 deletions
diff --git a/labb5/src/Boggle.cpp b/labb5/src/Boggle.cpp index 6d3fd32..9da2947 100755 --- a/labb5/src/Boggle.cpp +++ b/labb5/src/Boggle.cpp @@ -29,17 +29,30 @@ static string CUBES[NUM_CUBES] = { // the letters on all 6 sides of every cube * 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) { +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; + 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; + 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; + if (visited.count(new_p)) { + continue; + } res.push_back(new_p); } } @@ -52,7 +65,9 @@ vector<point> neighbours_in_range_filt(const point& p, int width, int height, co 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; + if (prefix[i] != word[i]) { + return false; + } } return true; } @@ -92,7 +107,8 @@ 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)]; + board[y][x] = CUBES[(BOARD_SIZE*y + x) % NUM_CUBES] + [randomInteger(0, CUBE_SIDES-1)]; } } // Shuffle positions @@ -100,18 +116,23 @@ void Boggle::shuffle() { } bool Boggle::find_single_word(const string& word) const { - auto start = std::chrono::high_resolution_clock::now(); + using clock = std::chrono::high_resolution_clock; + + auto start = clock::now(); // We break immediately if we find a match. - // Without the clock we would return right away. + // Without the clock we could 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>()); + 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(); + auto end = clock::now(); if (debug_mode) { if (found) { cout << "Found word"; @@ -119,19 +140,28 @@ bool Boggle::find_single_word(const string& word) const { cout << "Couldn't find word"; } cout << " in " - << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count()/1000.0 + << 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 { +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)) { + 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]; @@ -149,7 +179,10 @@ set<string> Boggle::find_all_words() const { 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>()); + find_all_words_helper(words, + make_pair(x, y), + string(1, board[y][x]), + set<point>()); } } auto end = std::chrono::high_resolution_clock::now(); @@ -163,12 +196,23 @@ set<string> Boggle::find_all_words() const { 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)) { +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)) { + 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]; diff --git a/labb5/src/Boggle.h b/labb5/src/Boggle.h index 8e065d7..8f68e92 100755 --- a/labb5/src/Boggle.h +++ b/labb5/src/Boggle.h @@ -90,6 +90,7 @@ public: 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; |