• 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 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) • 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","x"," "," "," ","x","x"]] Sample Output 0 Sample Input 1 [[" "," "," '," "]] Sample Output 1
• 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 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) • 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","x"," "," "," ","x","x"]] Sample Output 0 Sample Input 1 [[" "," "," '," "]] Sample Output 1
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
Please answer the following code problem in PYTHON. DO NOT WRITE A NEW CODE, just INSERT the necessary addition to the given code below. Thank you.
![• 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
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)
• 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", "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%2Fcfa96e8e-b35e-4604-a393-522ac8690641%2F234bc427-6038-4634-9791-a32b371e0b6c%2F9ce7krn_processed.jpeg&w=3840&q=75)
Transcribed Image Text:• 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
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)
• 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", "x"," ","
1,[" "," ","x","x"]]
Sample Output 0
Sample Input 1
[[" ","
"," "," "]]
Sample Output 1
![1
import ast
2
3 vclass WeightedQuickUnion:
4 v
def _init_ (self, size: int) -> None:
6
Initializes the union-find ds
size: number of elements to initialize
8
self.size = size
self.parent = [-1]*self.size
self.group_size = [1]*self.size # create separate list to indicate the size for each element
10
# create a list where all elements are roots
11
12
# (useful for knowing the size in root's perspective)
13
def _str_(self) -> str:
return f"parent: {self.parent}\nsize: {self.group_size}\n"
14
15
16
def get_root(self, p: int) -> int:
""Find the root of p"""
17
18
19
idx = p
while self.parent[idx] >= 0:
idx = self.parent[idx]
20
# root should have a negative value
21
22
return idx
23
def is_connected (self, pl: int, p2:int) -> bool:
return self.get_root(pl) == self.get_root(p2)
24
25
26
def connect(self, pl: int, p2: int) -> None:
""Connects pl and p2"""
rl = self.get_root (pl)
r2 = self.get_root(p2)
rl_size = self.group_size[r1]
r2_size = self.group_size[r2]
if rl_size > r2_size:
self.parent[r2] = rl
self.group_size[rl] += r2_size
else:
27
28
29
30
31
32
33 -
34
35
# increase rl group size by r2 size
36
self.parent[ri] = r2
self.group_size[r2] += rl_size
37
38
# increase r2 group size by rl size
39
40 vif -_name_-
== "__main__":
41
board = input()
42
board = ast.literal_eval(board)
num_rows, num_cols = len(board), len(board[0])
uf = WeightedQuickUnion(size = num_rows num_cols)
43
44
45
46
##INSERT CODE HERE##](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fcfa96e8e-b35e-4604-a393-522ac8690641%2F234bc427-6038-4634-9791-a32b371e0b6c%2Fgjlplla_processed.jpeg&w=3840&q=75)
Transcribed Image Text:1
import ast
2
3 vclass WeightedQuickUnion:
4 v
def _init_ (self, size: int) -> None:
6
Initializes the union-find ds
size: number of elements to initialize
8
self.size = size
self.parent = [-1]*self.size
self.group_size = [1]*self.size # create separate list to indicate the size for each element
10
# create a list where all elements are roots
11
12
# (useful for knowing the size in root's perspective)
13
def _str_(self) -> str:
return f"parent: {self.parent}\nsize: {self.group_size}\n"
14
15
16
def get_root(self, p: int) -> int:
""Find the root of p"""
17
18
19
idx = p
while self.parent[idx] >= 0:
idx = self.parent[idx]
20
# root should have a negative value
21
22
return idx
23
def is_connected (self, pl: int, p2:int) -> bool:
return self.get_root(pl) == self.get_root(p2)
24
25
26
def connect(self, pl: int, p2: int) -> None:
""Connects pl and p2"""
rl = self.get_root (pl)
r2 = self.get_root(p2)
rl_size = self.group_size[r1]
r2_size = self.group_size[r2]
if rl_size > r2_size:
self.parent[r2] = rl
self.group_size[rl] += r2_size
else:
27
28
29
30
31
32
33 -
34
35
# increase rl group size by r2 size
36
self.parent[ri] = r2
self.group_size[r2] += rl_size
37
38
# increase r2 group size by rl size
39
40 vif -_name_-
== "__main__":
41
board = input()
42
board = ast.literal_eval(board)
num_rows, num_cols = len(board), len(board[0])
uf = WeightedQuickUnion(size = num_rows num_cols)
43
44
45
46
##INSERT CODE HERE##
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY