Zuma Game

The idea here is to use recursion. At each step, we plan to insert the remaining balls in the string hand to the string board. Now the question arises, in which position do we have to insert the ‘i’th character of the string hand? The answer is simple; we have to insert ‘i’th character to all the positions on board to get all possible answers. That’s why we are using the recursive approach. After inserting ‘i’th character to a particular position, we have to always remove all consecutive balls of the same colors if their count is more than 2. After removing, we have to call the function again with the new board and another string hand character. This process continues until the length of the string board will become zero. So, if the board becomes empty, then we return the count of the insertions. Or, if all the balls in hand are inserted, and we haven’t found a solution, then also return. But in this case, we have to return a big integer as we are finding the minimum of all the total insertions, and this case doesn’t end up with a possible solution. After returning, we have to insert ‘i’th character to the next position and again call the same function and follow the exact process.

Again a question arises that what will be the order we have to follow in the string hand? Is any random order leads us to a possible solution? Or is there any particular order available? Well, a one-word answer is to think greedily! First, find the count of each color ball on the string board. Now, sort the string hand according to these counts. The minimum count colors ball will come first, and the maximum count colors ball will come last. This is one of the orders which we have to follow. Another order is to reverse the string hand and call the recursive function. The output must be the minimum of the recursive function’s return value with the above two orders.

Steps:

• Create a vector of pair of data type int, char named count of size 26 to store the count of each character of the string board, vector<pair<int, char>> count(26).
• Run a loop to initialize each first element of the pair to 0 and second to char of the vector count, so in each iteration:
  • Set count[i].first = 0, count[i].second = i+’A’.
• Run a loop from i = 0 to the size of the string board, in each iteration:
  • count[board[i]-’A’].first++.
• Create a HashMap named frequency for string the count of each character of the string hand.
• Run a loop from i = 0 to the size of the string hand, in each iteration:
  • frequency[hand[i]]++.
• Sort the vector of pair count.
• Make the string hand empty, as we are making it as new according to the string board’s characters’ count.
• Run a loop from i = 0  to i < 26, in each iteration:
  • Run a loop from j = 0 to j < frequency[count[i].second], in each iteration:
    • hand += count[i].second.
• After completing these steps, we get our new string hand which is sorted according to the count as discussed earlier.
• Call the function isEmpty(index, board, inserted, hand), where index is the current index of the string hand that is initially 0, board is the given string, inserted is the count of characters that have been inserted that is initially 0, and hand is the string already described.
• Now, reverse the string hand as this is the 2nd order in which we have to call the function isEmpty again.
• Finally, return the minimum of the above two functions calling.

int isEmpty(int ind, string &board, int inserted, string &hand):

• If the length of the string board becomes 0, then return the number inserted, as we have found a possible solution.
• If index == hand.length(), then return some big integer, and in our case, we can return 100 also, as we have not found a solution and the string hand becomes empty.
• Now, call the function again without insertion, i.e., isEmpty(ind+1, board, inserted, hand), and create a variable named res to store the return value of this step.
• Declare a variable i = 0.
• Run a while loop until i becomes greater than board.size(), in each iteration:
  • Insert the character hand[ind] at the ith position of the string board, and make a new string named newBoard, newBoard = board[:i] + hand[ind] + board[i:].
  • Call another function named remove(newBoard), which is removing consecutive occurrence of the balls of the same colors with a count greater than 2.
  • The above function returning an updated string which we can store in our string newBoard.
  • Call the function isEmpty(index+1, newBoard, inserted+1, hand) and also update the res with the return value if previously it is greater than the return value of this function.
  • Just increment i, because we have to now insert hand[index] to the next position.
• Finally, return res.

string remove(string &board):

• This function is just removing all consecutive balls of the same colors if their count is more than 2.
• Run a loop with variable i = 1, j = 0 to i < board.size(), in each iteration:
  • If board[i] == board[i-1], then continue;
  • If i - j > 2, which means we have found more than 2 consecutive balls of the same colours, then make nextStr = board[:j] + board[i:], and return remove(nextStr).
  • Else, set j = i.
• In the end, just check if i - j > 2, then again make nextStr as described above and return remove with nextStr.
• Finally, return the string board.