Rummikub

/*****************************************************************//** * \file rummikub.cpp * \author(s) Jennifer Assid * * \date 2/21/2022 *********************************************************************/ #include "rummikub.h" #include <algorithm> // Default constructor RummiKub::RummiKub() {} // Debugging function void RummiKub::PrintHand() const { // Iterate through the current hand and print out each tile for (unsigned int i = 0; i < static_cast<unsigned>(hand_.size()); i++) { std::cout << hand_[i] << " "; } std::cout << std::endl; } // Debugging function void RummiKub::PrintRuns() { std::cout << "Runs" << std::endl; for (unsigned int i = 0; i < static_cast<unsigned>(runs_.size()); i++) { for (unsigned int j = 0; j < static_cast<unsigned>(runs_[i].size()); j++) { std::cout << runs_[i][j] << " "; } std::cout << std::endl; } } // Debugging function void RummiKub::PrintGroups() { std::cout << "Groups" << std::endl; for (unsigned int i = 0; i < static_cast<unsigned>(groups_.size()); i++) { for (unsigned int j = 0; j < static_cast<unsigned>(groups_[i].size()); j++) { std::cout << groups_[i][j] << " "; } std::cout << std::endl; } } // Compares the denomination to see if the first tile is less than the second tile bool compareDenomination(Tile const& tile1, Tile const& tile2) { return (tile1.denomination < tile2.denomination); } // Adds a new tile to the hand void RummiKub::Add(Tile const& tile) { hand_.push_back(tile); } // Returns the groups std::vector< std::vector< Tile > > RummiKub::GetGroups() const {return groups_;} // Returns the runs std::vector< std::vector< Tile > > RummiKub::GetRuns() const {return runs_;} // See if the tile can be placed elsewhere in the list bool RummiKub::CanThisBePlacedElsewhereRuns(Tile const& tile, int& index) { // Store the current index into a temp variable int temp = index; // Iterate through the rest of the runs for (index = index + 1; index < static_cast<int>(runs_.size()); index++) { // If the run is already valid - skip if (runs_[index].size() >= 3) continue; // If the color doesn't match (the tile can't be placed) - skip if (runs_[index].front().color != tile.color) continue; // If the tile can be added to the end of the run - return true if (tile.denomination == runs_[index].back().denomination + 1) { return true; } } // Reset the index variable - return false index = temp; return false; } // See if the tile can be placed elsewhere in the list bool RummiKub::CanThisBePlacedElsewhereGroups(Tile const& tile, int& index) { // Store the index in a local variable int temp = index; // Iterate through the rest of the groups for (index = index + 1; index < static_cast<int>(groups_.size()); index++) { // If the group is valid - skip if (groups_[index].size() >= 3) continue; // If the denomiation doesn't match (the tile can't be placed) - skip if (tile.denomination != groups_[index].front().denomination) continue; // Initiate the valid bool to default setting bool valid = true; // Iterate through the group for (unsigned int j = 0; j < static_cast<unsigned>(groups_[index].size()); j++) { // If the color is already in the group - break out of loop if (tile.color == groups_[index][j].color) { valid = false; break; } } // If a valid group has been found - return true if (valid) return true; } // Reset the index and return false index = temp; return false; } // Determines if the tile can continue a run bool RummiKub::CanContinueRun(Tile const& tile, int& index) { // If there are no runs to add too - return false if (runs_.empty()) { return false; } // Check all runs to see which is valid for (int i = 0; i < static_cast<int>(runs_.size()); i++) { // Continue if the colors are not the same if (tile.color != runs_[i].front().color) continue; // If the run is valid and the tile can be placed elsewhere, continue if (runs_[i].size() >=3) { if (CanThisBePlacedElsewhereRuns(tile, i)) { index = i; return true; } } // If the tile can be added to the back - add it to the back if (tile.denomination == runs_[i].back().denomination + 1) { //PrintRuns(); index = i; return true; } } // Return false if no valid run has been found return false; } // Determine if the given tile can continue a group bool RummiKub::CanContinueGroup(Tile const& tile, int& index) { bool valid; // If there are no groups to add too - return false if (groups_.empty()) return false; // Iterate through the groups for (int i = 0; i < static_cast<int>(groups_.size()); i++) { // If the group is at max size - skip if (groups_[i].size() == 4) continue; // If the denomiation doesn't match (the tile cannot be added) - skip if (tile.denomination != groups_[i].front().denomination) continue; // If the group is already valid and the tile can be placed elsewhere if (groups_[i].size() >=3) { if (CanThisBePlacedElsewhereGroups(tile, i)) { // Set the index to the determined value - return true index = i; return true; } } valid = true; // Iterate through the group for (unsigned int j = 0; j < static_cast<unsigned>(groups_[i].size()); j++) { // If the color is already in the group - break if (tile.color == groups_[i][j].color) { valid = false; break; } } // If the color was not found - set the index to the determined value and return true if (valid) { index = i; return true; } } // Set index to default value and return false index = -1; return false; } // Perform the action is it is valid int RummiKub::PerformActionIfValid(Actions action, Tile const& tile) { // Initialize the index variable int index = -1; switch (action) { case Actions::Cont_Run: // If the tile can continue a run, push the tile back onto the run and return the index if (CanContinueRun(tile, index)) { runs_[index].push_back(tile); return index; } break; case Actions::Cont_Group: // If the tile can continue a group, push the tile back onto the group and return the index if (CanContinueGroup(tile, index)) { groups_[index].push_back(tile); return index; } break; case Actions::Create_Run: // Create a new run with the tile on it - return the index runs_.push_back({tile}); return static_cast<int>(runs_.size()) - 1; break; case Actions::Create_Group: // Create a new group with the tile on it - return the index groups_.push_back({tile}); return static_cast<int>(groups_.size()) - 1; break; } // Return the default value return -1; } // Checks if the current runs / groups are a valid solution bool RummiKub::CheckValidity() { // Iterate through the groups for (unsigned int i = 0; i < static_cast<unsigned>(groups_.size()); i++) { // If the group size is invalid - return false if (static_cast<int>(groups_[i].size()) < 3 || static_cast<int>(groups_[i].size()) > 4) return false; } // Iterate through the runs for (unsigned int i = 0; i < static_cast<unsigned>(runs_.size()); i++) { // If the run size is invalid - return false if (static_cast<int>(runs_[i].size()) < 3) return false; } // Return the default value return true; } // Removes the last action to be performed void RummiKub::RemoveAction(Actions action, int index) { // If the index is invalid - return if (index == -1) return; switch (action) { case Actions::Cont_Run: // Remove last tile on the run runs_[index].pop_back(); break; case Actions::Cont_Group: // Remove last tile on the group groups_[index].pop_back(); break; case Actions::Create_Run: // Remove the last run runs_.pop_back(); break; case Actions::Create_Group: // Remove the last group groups_.pop_back(); break; } } // Function called by the user to solve the current hand void RummiKub::Solve() { // Sorts the hand based on the tile denomiation std::sort(hand_.begin(), hand_.end(), compareDenomination); // Initiates recursion solve_rec(0); } // Recursive function to determine if the hand is solvable bool RummiKub::solve_rec(int index) { // Base case - if all of the tiles have been evaluated if (index == static_cast<int>(hand_.size())) { // If the solution was found - return true if (CheckValidity()) { return true; } // Return default condition return false; } // Iterate through the possible actions for (unsigned int i = 1; i <= 4; i++) { // Perform the action and return the index int result = PerformActionIfValid(static_cast<Actions>(i), hand_[index]); // If the action was successfully performed if (result != -1) { // If the recursive call with the next tile returns true - return true (solution was found later on) if (solve_rec(index + 1)) return true; // Undo last action performed RemoveAction(static_cast<Actions>(i), result); } } // Return the default condition return false; }