USE PYTHON PROGRAMMING.  The expected outputs seen in the screenshot must be achieved. (Not working = Thumbs Down) You must use the code template below. You cannot modify the class or its methods. You are only allowed to add lines of code to the main part of the program. Thank you. 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--

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...
icon
Related questions
Question

USE PYTHON PROGRAMMING. 

The expected outputs seen in the screenshot must be achieved. (Not working = Thumbs Down)

You must use the code template below. You cannot modify the class or its methods. You are only allowed to add lines of code to the main part of the program. Thank you.

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
Transcribed Image Text: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
• 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)
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 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)
Expert Solution
steps

Step by step

Solved in 2 steps with 1 images

Blurred answer
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
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 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)
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
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY