5 Best Ways to Solve Campus Bikes II in Python

Rate this post

πŸ’‘ Problem Formulation: The Campus Bikes II problem involves assigning bikes to workers on a campus in a way that minimizes the sum of the Manhattan distances between each worker and their assigned bike. Given two arrays of worker and bike positions on a 2D grid, we need to write an algorithm that outputs the minimum possible distance sum. For example, if we have workers at positions [[0,0],[2,1]] and bikes at [[1,2],[3,3]], the desired output is 6, with optimal pairing of workers to bikes resulting in the least total distance.

Method 1: Brute Force Backtracking

This method explores all possible assignments of bikes to workers, calculating the total distance for each combination, and determining the minimum. It’s a recursive approach that can solve small instances effectively but has an exponential time complexity, which makes it impractical for larger datasets.

Here’s an example:

def assign_bikes(workers, bikes):
    def dfs(worker_idx, taken, current_sum):
        if worker_idx == len(workers):
            return current_sum
        min_distance = float('inf')
        for bike_idx in range(len(bikes)):
            if not (taken & (1 << bike_idx)):
                dist = abs(workers[worker_idx][0] - bikes[bike_idx][0]) + abs(workers[worker_idx][1] - bikes[bike_idx][1])
                min_distance = min(min_distance, dfs(worker_idx + 1, taken | (1 << bike_idx), current_sum + dist))
        return min_distance
    return dfs(0, 0, 0)

workers = [[0,0],[2,1]]
bikes = [[1,2],[3,3]]
print(assign_bikes(workers, bikes))

Output:

6

This code defines a dfs (Depth-First Search) function to recursively assign each bike to a worker while keeping track of the total distance traveled. It uses a bit mask (taken) to represent which bikes have been assigned. We call this function starting with the first worker and no bikes taken, and we return the minimum distance found.

Method 2: Dynamic Programming with Bit Masking

To overcome the inefficiencies of brute force, we can use dynamic programming (DP) with bit masking. DP stores subproblem solutions to avoid redundant calculations, while bit masking efficiently represents the set of chosen bikes. This method improves the time complexity significantly for medium-sized datasets.

Here’s an example:

def assign_bikes(workers, bikes):
    n, m = len(workers), len(bikes)
    dp = [float('inf')] * (1 << m)
    dp[0] = 0
    
    for mask in range(1 << m):
        x = bin(mask).count('1')
        for b in range(m):
            if mask & (1 << b):
                prev = mask ^ (1 << b)
                dp[mask] = min(dp[mask], dp[prev] + abs(workers[x-1][0] - bikes[b][0]) + abs(workers[x-1][1] - bikes[b][1]))

    return dp[-1]

workers = [[0,0],[2,1]]
bikes = [[1,2],[3,3]]
print(assign_bikes(workers, bikes))

Output:

6

In this code snippet, we use a list dp to store the minimum distance for each set of bike assignments, represented as a bit mask. We iterate over all possible masks, determining the minimum distance for each by considering previously computed states. The final answer is stored in dp[-1].

Method 3: Greedy Algorithm with Sorting

Although the greedy method doesn’t ensure an optimal solution for every instance of this problem, it can provide an approximation by sorting the distances from each worker to each bike and assigning the closest available bike to each worker. This method is fast and works well in practice, especially when the exact minimum value is not critical.

Here’s an example:

import heapq

def assign_bikes(workers, bikes):
    distances = []
    for i, worker in enumerate(workers):
        for j, bike in enumerate(bikes):
            distance = abs(worker[0] - bike[0]) + abs(worker[1] - bike[1])
            distances.append((distance, i, j))
    heapq.heapify(distances)

    result, used_bikes = 0, set()
    while len(used_bikes) < len(workers):
        distance, worker, bike = heapq.heappop(distances)
        if bike not in used_bikes:
            result += distance
            used_bikes.add(bike)

    return result

workers = [[0,0],[2,1]]
bikes = [[1,2],[3,3]]
print(assign_bikes(workers, bikes))

Output:

6

We first calculate all distances between workers and bikes, and use a min-heap to get the smallest distance one at a time. Then, we pop from the heap and assign the bike if it’s not already used. This code returns the sum of distances for the approximation of bike assignments.

Method 4: Genetic Algorithm

Genetic algorithms can provide near-optimal solutions for optimization problems like this by simulating the process of natural selection. We define a fitness function based on the total distance, generate a population of assignments, and iteratively improve them through selection, crossover, and mutation operations. While not guaranteeing the least total distance, it tends to get close enough.

Here’s an example:

# Pseudocode for genetic algorithm implementation
# Define fitness function, initialize population
# while not converged:
#     Select parents from population based on fitness
#     Perform crossover to create children
#     Mutate children at random positions
#     Evaluate new fitness and update population
# Return best solution from population

This pseudocode outlines the general structure of a genetic algorithm applied to the Campus Bikes II problem. Actual implementation would require detailed coding of the fitness function reflecting the total distance, and the genetic operations applied to the population of potential assignments.

Bonus One-Liner Method 5: Linear Assignment Problem (LAP)

The Linear Assignment Problem (LAP) can be used to find the minimum weight matching in a bipartite graph, which is effectively what the Campus Bikes II problem is. By using an efficient LAP solver like the Hungarian algorithm, we can solve the problem in polynomial time. This method achieves optimal results and is best for dense datasets.

Here’s an example:

from scipy.optimize import linear_sum_assignment

def assign_bikes(workers, bikes):
    cost_matrix = [[abs(w[0] - b[0]) + abs(w[1] - b[1]) for b in bikes] for w in workers]
    row_ind, col_ind = linear_sum_assignment(cost_matrix)
    return sum(cost_matrix[i][j] for i, j in zip(row_ind, col_ind))

workers = [[0,0],[2,1]]
bikes = [[1,2],[3,3]]
print(assign_bikes(workers, bikes))

Output:

6

This one-liner uses scipy.optimize.linear_sum_assignment, which implements the Hungarian algorithm to solve the assignment problem. It outputs the perfect match that minimizes the sum of absolute distances between workers and bikes.

Summary/Discussion

    Method 1: Brute Force Backtracking. Simple to understand. Exponential time complexity makes it impractical for larger datasets. Method 2: Dynamic Programming with Bit Masking. Optimizes the brute force method significantly. Still has limits on dataset size due to combinatorial complexity. Method 3: Greedy Algorithm with Sorting. Provides a quick approximation. May not produce the optimal solution, but is fast and practical for many real-world scenarios. Method 4: Genetic Algorithm. Can provide near-optimal solutions. Requires careful tuning and may be overkill for small instances. Bonus One-Liner Method 5: Linear Assignment Problem (LAP). Achieves optimal results and works well for dense datasets. Requires the use of external libraries like scipy.