Zuma Game

Too many downvotes > 50%

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        # start from i and remove continues ball
        def remove_same(s, i):
            if i < 0:
                return s

            left = right = i
            while left > 0 and s[left-1] == s[i]:
                left -= 1
            while right+1 < len(s) and s[right+1] == s[i]:
                right += 1

            length = right - left + 1
            if length >= 3:
                new_s = s[:left] + s[right+1:]
                return remove_same(new_s, left-1)
            else:
                return s

        hand = "".join(sorted(hand))

        # board, hand and step
        q = collections.deque([(board, hand, 0)])
        visited = set([(board, hand)])

        while q:
            curr_board, curr_hand, step = q.popleft()
            for i in range(len(curr_board)+1):
                for j in range(len(curr_hand)):
                    # skip the continue balls in hand
                    if j > 0 and curr_hand[j] == curr_hand[j-1]:
                        continue

                    # only insert at the begin of continue balls in board
                    if i > 0 and curr_board[i-1] == curr_hand[j]: # left side same color
                        continue

                    pick = False
                    # 1. same color with right
                    # 2. left and right are same but pick is different
                    if i < len(curr_board) and curr_board[i] == curr_hand[j]:
                        pick = True
                    if 0<i<len(curr_board) and curr_board[i-1] == curr_board[i] and curr_board[i] != curr_hand[j]:
                        pick = True

                    if pick:
                        new_board = remove_same(curr_board[:i] + curr_hand[j] + curr_board[i:], i)
                        new_hand = curr_hand[:j] + curr_hand[j+1:]
                        if not new_board:
                            return step + 1
                        if (new_board, new_hand) not in visited:
                            q.append((new_board, new_hand, step+1))
                            visited.add((new_board, new_hand))

        return -1

Identifying Problem Isomorphism

“Zuma Game” has an approximate isomorph: “Word Ladder II”.

In “Zuma Game”, you have a row of colored balls and more colored balls in your hands. You have to eliminate all the balls in the row by shooting the balls from your hand with certain rules. We have to find the minimum number of balls you have to shoot.

In “Word Ladder II”, you’re given two words (start and end), and a word list. You need to find all the shortest transformation sequences from start to end, such that only one letter can be changed at a time and each transformed word must exist in the word list.

Both problems have similar structure: they both require finding the minimum transformations (be it balls or words) and have rules around what constitutes a valid transformation. They also both leverage the concept of breadth-first search in their solutions.

“Word Ladder II” is simpler, due to the more straightforward rules of transformation. “Zuma Game” involves more complex conditions, making it more challenging.

“Zuma Game” requires you to use techniques like depth-first search (DFS) and backtracking. It also involves string manipulation and understanding of game theory.

10 Prerequisite LeetCode Problems

Here are 10 problems to prepare:

Combination Sum (LeetCode #39): This problem helps you understand the basic concept of DFS and backtracking.
Generate Parentheses (LeetCode #22): This problem uses DFS and backtracking to generate all combinations of well-formed parentheses, which is helpful for understanding how to approach game-state exploration.
Subsets (LeetCode #78): This problem provides practice with backtracking to explore all possible subsets of a set.
Permutations (LeetCode #46): It also utilizes backtracking to generate all possible permutations of a list.
Word Search (LeetCode #79): This problem involves a 2D grid and requires DFS and backtracking to find if a word exists in the grid.
N-Queens (LeetCode #51): This is a more advanced backtracking problem which can help prepare for the complexity of Zuma Game.
Remove Invalid Parentheses (LeetCode #301): This problem involves manipulation of strings using DFS and backtracking, similar to the operations you might need for the Zuma Game problem.
Word Break II (LeetCode #140): This problem deals with string manipulation and DFS.
Palindrome Partitioning (LeetCode #131): This problem also involves DFS and backtracking, with an added complexity of palindrome checking.
Regular Expression Matching (LeetCode #10): This problem will help you with complex string manipulation and pattern matching, which could be a part of solving the Zuma Game.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        def remove_same(s, i):
            if i < 0:
                return s

            left = right = i
            while left > 0 and s[left-1] == s[i]:
                left -= 1
            while right+1 < len(s) and s[right+1] == s[i]:
                right += 1

            length = right - left + 1
            if length >= 3:
                new_s = s[:left] + s[right+1:]
                return remove_same(new_s, left-1)
            else:
                return s

        hand = "".join(sorted(hand))

        q = collections.deque([(board, hand, 0)])
        visited = set([(board, hand)])

        while q:
            curr_board, curr_hand, step = q.popleft()
            for i in range(len(curr_board)+1):
                for j in range(len(curr_hand)):

                    if j > 0 and curr_hand[j] == curr_hand[j-1]:
                        continue

                    if i > 0 and curr_board[i-1] == curr_hand[j]: 
                        continue

                    pick = False

                    if i < len(curr_board) and curr_board[i] == curr_hand[j]:
                        pick = True
                    if 0 < i < len(curr_board) and curr_board[i-1] == curr_board[i] and curr_board[i] != curr_hand[j]:
                        pick = True

                    if pick:
                        new_board = remove_same(curr_board[:i] + curr_hand[j] + curr_board[i:], i)
                        new_hand = curr_hand[:j] + curr_hand[j+1:]
                        if not new_board:
                            return step + 1
                        if (new_board, new_hand) not in visited:
                            q.append((new_board, new_hand, step+1))
                            visited.add((new_board, new_hand))

        return -1

Problem Classification

The problem involves playing a game where balls are removed when certain conditions are met. This is a Game-playing Strategy Problem.

Language Agnostic Coding Drills

The solution represents a classic game where balls of various colors are arranged on a track. You are given a chance to throw additional balls from your hand onto the track. If there are three or more balls of the same color adjacent, they will explode. The objective is to explode all the balls on the track. The problem is to find the minimum number of balls to throw to explode all the balls on the track.

Here is the breakdown of the approach:

Understanding the problem: The problem requires us to find the minimum number of moves to clear the “board” of balls, by adding balls from our “hand”. A move is successful if it leads to the explosion of the balls. Understanding the conditions that cause an explosion is key to solving this problem.
Data structures: The main data structures used here are strings (to represent the board and the hand), and a queue (for the breadth-first search). It’s important to understand how to manipulate strings (e.g., slicing, concatenation), and how a queue operates (FIFO - First In, First Out).
Recursive function: The ‘remove_same’ function is a recursive function that removes all adjacent same-colored balls that occur in a sequence of 3 or more. If removal of balls creates another sequence of 3 or more same-colored balls, those are removed as well. Understanding recursion and how it works is crucial.
Sorting: The balls in the hand are sorted. This is to facilitate searching for specific colored balls and to make the comparison more efficient.
Breadth-first search (BFS): BFS is used to explore all possible moves in the game. For each state (represented by the current board and hand), all possible next states are generated and added to the queue, and the process repeats until the queue is empty or the board is cleared. BFS is used when we want to find the shortest path (or minimum number of steps) to reach a goal.
State tracking and early stopping: In order to avoid repeating the same state, a ‘visited’ set is used to track the visited states. Also, during the BFS, certain states are skipped to reduce the number of unnecessary explorations.

Targeted Drills in Python

String manipulation: Create strings, perform slicing and concatenation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
# Create a string
s = "abcd"
print(s)

# Slice a string
print(s[:2])  # Output: "ab"

# Concatenate strings
s1 = "hello"
s2 = "world"
print(s1 + " " + s2)  # Output: "hello world"

Working with queue: Implement a simple queue and understand its FIFO nature.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
import collections

# Create a queue
queue = collections.deque()

# Add elements to queue
queue.append("a")
queue.append("b")
queue.append("c")

# Remove elements from queue
print(queue.popleft())  # Output: "a"

Recursive function: Implement a function to calculate the factorial of a number using recursion.

1
2
3
4
5
6
7
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5))  # Output: 120

Sorting a string: Implement a function to sort the characters in a string.

1
2
3
4
def sort_string(s):
    return "".join(sorted(s))

print(sort_string("dcba"))  # Output: "abcd"

Breadth-first search (BFS): Implement BFS to traverse a binary tree.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Node:
    def __init__(self, value):
        self.value = value
        self.left = self.right = None

def bfs(root):
    queue = collections.deque([root])
    while queue:
        node = queue.popleft()
        print(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
bfs(root)  # Output: 1 2 3

State tracking: Implement a simple function to keep track of visited states.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
visited = set()

def visit_state(state):
    if state not in visited:
        print(f"Visiting {state}")
        visited.add(state)
    else:
        print(f"Already visited {state}")

visit_state("a")  # Output: "Visiting a"
visit_state("b")  # Output: "Visiting b"
visit_state("a")  # Output: "Already visited a"