From 5216d920fb26638ceda9f6391c5449c5e7bc8409 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Sun, 29 Nov 2020 01:44:00 +0100 Subject: initial work labb5 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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. --- labb5/src/Boggle.cpp | 170 ++++++++++++++++++++++++++++++++++++++++++++--- labb5/src/Boggle.h | 36 ++++++++-- labb5/src/boggleplay.cpp | 52 ++++++++++++++- 3 files changed, 242 insertions(+), 16 deletions(-) (limited to 'labb5/src') 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 +#include #include "Boggle.h" #include "random.h" #include "shuffle.h" #include "strlib.h" +#include -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 neighbours_in_range_filt(const point& p, int width, int height, const set& visited) { + int x, y; + tie(x, y) = p; + vector res = vector(); + 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(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()); + } + } + auto end = std::chrono::high_resolution_clock::now(); + cout << valid_words.size() + << " words in " + << std::chrono::duration_cast(end - start).count()/1000.0 + << " ms" + << endl; +} + +void Boggle::find_words_helper(point cur_point, string cur_word, set 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 #include -// TODO: include any other header files you need +#include +#include "lexicon.h" +#include "grid.h" +#include using namespace std; +using point = pair; 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 visited); + Lexicon dictionary; + Grid board; + set user_words; + set 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 #include @@ -9,13 +9,59 @@ #include "Boggle.h" #include "bogglemain.h" #include "strlib.h" -// TODO: include any other header files you need + +#include /* * 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); + } + } } -- cgit v1.2.1