Python coding test course, building bridges

Problem Description

There are several given islands. Each island is located in different positions, and we want to build bridges between the islands. At this time, bridges can only be constructed vertically or horizontally, and the bridges must stretch out in a straight line. Additionally, we need to minimize the total length of the bridges so that as many islands as possible can be connected.

Write a function that outputs the minimum total length of the bridges when the coordinates of the given islands are provided as (x, y).

def minimum_bridge_length(islands: List[Tuple[int, int]]) -> int:
    pass

Input

The number of islands N (2 ≤ N ≤ 10,000) and a list of coordinates (x, y) for each island will be provided.

Output

Return the minimum total length of the bridges as an integer.

Problem Solving Process

1. Understanding the Problem

The goal of the problem is to find the minimum total length of bridges connecting the given islands. The key to this problem is understanding how the bridge length between each pair of islands is calculated. If there are coordinates (x1, y1) and (x2, y2) for two islands, the bridge length between them can be calculated as |x1 – x2| + |y1 – y2|. In other words, it is the sum of the differences in the x-coordinates and y-coordinates of the islands.

2. Algorithm Design

We can solve the problem by considering all combinations of the islands to build bridges. However, since N can be as large as 10,000, considering all combinations would lead to an O(N^2) time complexity, which is inefficient. Instead, we can use a Minimum Spanning Tree (MST) algorithm to connect the bridges minimally.

To construct the MST, we can use either Kruskal’s or Prim’s algorithm. Here, we will use Prim’s algorithm. This algorithm starts from one vertex of the graph and builds the MST by adding the shortest edge one at a time.

3. Implementing Prim’s Algorithm

First, we prepare a list to store the coordinates of each island and a priority queue to store the connection costs. Then, starting from one island, we calculate the lengths of the bridges to all connected islands and repeat the process of adding the island with the shortest length.

import heapq
from typing import List, Tuple

def minimum_bridge_length(islands: List[Tuple[int, int]]) -> int:
    n = len(islands)
    visited = [False] * n
    min_heap = []
    
    # Start from the first island
    for i in range(1, n):
        dist = abs(islands[0][0] - islands[i][0]) + abs(islands[0][1] - islands[i][1])
        heapq.heappush(min_heap, (dist, i))
    
    visited[0] = True
    total_length = 0
    edges_used = 0
    
    while min_heap and edges_used < n - 1:
        dist, island_index = heapq.heappop(min_heap)
        
        if visited[island_index]:
            continue
        
        visited[island_index] = True
        total_length += dist
        edges_used += 1
        
        for i in range(n):
            if not visited[i]:
                new_dist = abs(islands[island_index][0] - islands[i][0]) + abs(islands[island_index][1] - islands[i][1])
                heapq.heappush(min_heap, (new_dist, i))
    
    return total_length

4. Complexity Analysis

The time complexity of this algorithm is O(E log V), where E is the number of edges and V is the number of vertices. However, since we do not consider all combinations and generate bridges based on each island, the actual performance is better.

5. Example

Now, let's solve an example using this algorithm.

islands = [(0, 0), (1, 1), (3, 1), (4, 0)]
print(minimum_bridge_length(islands))  # Output: 4

In the above example, we can connect the bridge from (0, 0) to (1, 1), from (1, 1) to (3, 1), and from (3, 1) to (4, 0). The total length of the bridges becomes 4.