USE PYTHON PROGRAMMING. The expected output per respective input must be achieved (check screenshots below) Use code template below:
USE PYTHON PROGRAMMING.
The expected output per respective input must be achieved (check screenshots below)
Use code template below:
import ast
class WeightedQuickUnion:
def __init__(self, size: int) -> None:
"""
Initializes the union-find ds
size: number of elements to initialize
"""
self.size = size
self.parent = [-1]*self.size # create a list where all elements are roots
self.group_size = [1]*self.size # create separate list to indicate the size for each element
# (useful for knowing the size in root's perspective)
def __str__(self) -> str:
return f"parent: {self.parent}\nsize: {self.group_size}\n"
def get_root(self, p: int) -> int:
"""Find the root of p"""
idx = p
while self.parent[idx] >= 0: # root should have a negative value
idx = self.parent[idx]
return idx
def is_connected(self, p1: int, p2:int) -> bool:
return self.get_root(p1) == self.get_root(p2)
def connect(self, p1: int, p2: int) -> None:
"""Connects p1 and p2"""
r1 = self.get_root(p1)
r2 = self.get_root(p2)
r1_size = self.group_size[r1]
r2_size = self.group_size[r2]
if r1_size > r2_size:
self.parent[r2] = r1
self.group_size[r1] += r2_size # increase r1 group size by r2 size
else:
self.parent[r1] = r2
self.group_size[r2] += r1_size # increase r2 group size by r1 size
if __name__ == "__main__":
board = input()
board = ast.literal_eval(board)
num_rows, num_cols = len(board), len(board[0])
uf = WeightedQuickUnion(size = num_rows*num_cols)
--Insert Code Here--
![assume all list of lists have valid and consistent sizes (i.e., no list will have a different size from other lists)
Output Format
• You are supposed to output the maximum number of bombs that form a group
• The output should only be one number
Sample Input 0
[["x","
" "," "1,["x","x"
" " "1," ",
"x","x"]]
Sample Output 0
Sample Input 1
[[" "," ",
"," "]]
Sample Output 1](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F50530471-3d1d-446c-af31-a941cdfd5635%2F11383b44-9fa7-46f3-89b9-43d619d085d4%2Ffu9hozc_processed.png&w=3840&q=75)
![• You are employed by Microsoft. Unexpectedly, Minesweeper is gaining popularity again and users are
requesting for additional features. Your boss wanted you to help add features in the codebase. You are
tasked to create a helper function that will display the maximum number of bombs that are clustered
together. This is so players can have an idea how scattered the bombs are.
• Upon looking into the codebase, you saw that your coworker recently developed an implementation of
Weighted Quick Union with the intention of using it for another feature. When your boss found out, he/she
told you to use it so you can brush up on your data structures knowledge.
• Given the Minesweeper board below, you should output "4" since the maximum number of bombs (marked
as "X") that are beside each other is 4. Two bombs are considered beside each other if they are horizontally
or vertically touching (diagonals are not considered).
X
X
X
X
X
X
Input Format
• You will be given a list of lists in the following form:
[["x","x"," "," "1,["x","x"," "," "1,[" "," "
x","x"]]
Constraints
• You are required to use the provided WeightedQuickUnion class
• assume all elements of the list are valid (i.e., only "x" and "" are in the list of lists)](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F50530471-3d1d-446c-af31-a941cdfd5635%2F11383b44-9fa7-46f3-89b9-43d619d085d4%2Fn93mvqh_processed.png&w=3840&q=75)
Step by step
Solved in 2 steps
