greedy challenges

# Problem Statement: # Given a set of cities and the distances between them, find the shortest possible route that visits each city # exactly once and returns to the origin city. import random def calc_total_distance(route, distance_matrix): total_distance = 0 for i in range(len(route) - 1): total_distance += distance_matrix[route[i]][route[i + 1]] total_distance += distance_matrix[route[-1]][route[0]] # Return to start return total_distance def two_opt(route, distance_matrix): best_route = route[:] best_distance = calc_total_distance(route, distance_matrix) for i in range(1, len(route) - 1): for j in range(i + 1, len(route)): new_route = route[:i] + route[i:j+1][::-1] + route[j+1:] new_distance = calc_total_distance(new_route, distance_matrix) if new_distance < best_distance: best_route = new_route best_distance = new_distance return best_route, best_distance # Test TSP distance_matrix = [[0, 1, 2, 3], [1, 0, 4, 5], [2, 4, 0, 6], [3, 5, 6, 0]] route = [0, 1, 2, 3] best_route, best_distance = two_opt(route, distance_matrix) print("Best Route:", best_route) print("Best Distance:", best_distance) # Problem Statement: # Given a set of cities and the distances between them, find the shortest possible route that visits each city # exactly once and returns to the origin city. import random def calc_total_distance(route, distance_matrix): total_distance = 0 for i in range(len(route) - 1): total_distance += distance_matrix[route[i]][route[i + 1]] total_distance += distance_matrix[route[-1]][route[0]] # Return to start return total_distance def two_opt(route, distance_matrix): best_route = route[:] best_distance = calc_total_distance(route, distance_matrix) for i in range(1, len(route) - 1): for j in range(i + 1, len(route)): new_route = route[:i] + route[i:j+1][::-1] + route[j+1:] new_distance = calc_total_distance(new_route, distance_matrix) if new_distance < best_distance: best_route = new_route best_distance = new_distance return best_route, best_distance # Test TSP distance_matrix = [[0, 1, 2, 3], [1, 0, 4, 5], [2, 4, 0, 6], [3, 5, 6, 0]] route = [0, 1, 2, 3] best_route, best_distance = two_opt(route, distance_matrix) print("Best Route:", best_route) print("Best Distance:", best_distance) # Problem Statement: # Given a set of jobs, each with a processing time, you need to schedule them on a set of machines to minimize # the total completion time. def schedule_jobs(jobs, num_machines): jobs.sort(reverse=True) # Sort jobs by descending order of time machines = [0] * num_machines # Machines start with 0 time for job in jobs: # Assign the job to the machine with the minimum current load machine_id = machines.index(min(machines)) machines[machine_id] += job return machines # Test Job Scheduling jobs = [10, 15, 20, 25, 30] num_machines = 3 machines = schedule_jobs(jobs, num_machines) print("Job Distribution across Machines:", machines) # Problem Statement: # Place `N` queens on an `N x N` chessboard such that no two queens threaten each other (i.e., no two queens # are in the same row, column, or diagonal). def is_safe(board, row, col): for i in range(row): if board[i] == col or board[i] - i == col - row or board[i] + i == col + row: return False return True def solve_n_queens(board, row, n): if row == n: return [board[:]] solutions = [] for col in range(n): if is_safe(board, row, col): board[row] = col solutions += solve_n_queens(board, row + 1, n) board[row] = -1 # Backtrack return solutions # Test N-Queens n = 4 board = [-1] * n # -1 means no queen placed solutions = solve_n_queens(board, 0, n) print("Solutions:", solutions) # Problem Statement: # You are given an amount and a set of coin denominations. Find the fewest number of coins that make up that amount. def coin_change(coins, amount): coins.sort(reverse=True) result = [] for coin in coins: while amount >= coin: amount -= coin result.append(coin) return result if amount == 0 else "Not possible" # Test Coin Change coins = [1, 5, 10, 25, 50] amount = 63 coins_used = coin_change(coins, amount) print("Coins Used:", coins_used) # Problem Statement: # Given a set of integers, find a subset whose sum is equal to a target value. def subset_sum(nums, target): nums.sort(reverse=True) current_sum = 0 subset = [] for num in nums: if current_sum + num min_temp: next_state = neighbor(current_state) next_value = evaluate(next_state) if next_value < current_value or random.random() < math.exp((current_value - next_value) / temperature): current_state =

Mar 27, 2025 - 04:46


# Problem Statement:
# Given a set of cities and the distances between them, find the shortest possible route that visits each city
# exactly once and returns to the origin city.

import random

def calc_total_distance(route, distance_matrix):
    total_distance = 0
    for i in range(len(route) - 1):
        total_distance += distance_matrix[route[i]][route[i + 1]]
    total_distance += distance_matrix[route[-1]][route[0]]  # Return to start
    return total_distance

def two_opt(route, distance_matrix):
    best_route = route[:]
    best_distance = calc_total_distance(route, distance_matrix)

    for i in range(1, len(route) - 1):
        for j in range(i + 1, len(route)):
            new_route = route[:i] + route[i:j+1][::-1] + route[j+1:]
            new_distance = calc_total_distance(new_route, distance_matrix)

            if new_distance < best_distance:
                best_route = new_route
                best_distance = new_distance

    return best_route, best_distance

# Test TSP
distance_matrix = [[0, 1, 2, 3], [1, 0, 4, 5], [2, 4, 0, 6], [3, 5, 6, 0]]
route = [0, 1, 2, 3]
best_route, best_distance = two_opt(route, distance_matrix)
print("Best Route:", best_route)
print("Best Distance:", best_distance)


# Problem Statement:
# Given a set of cities and the distances between them, find the shortest possible route that visits each city
# exactly once and returns to the origin city.

import random

def calc_total_distance(route, distance_matrix):
    total_distance = 0
    for i in range(len(route) - 1):
        total_distance += distance_matrix[route[i]][route[i + 1]]
    total_distance += distance_matrix[route[-1]][route[0]]  # Return to start
    return total_distance

def two_opt(route, distance_matrix):
    best_route = route[:]
    best_distance = calc_total_distance(route, distance_matrix)

    for i in range(1, len(route) - 1):
        for j in range(i + 1, len(route)):
            new_route = route[:i] + route[i:j+1][::-1] + route[j+1:]
            new_distance = calc_total_distance(new_route, distance_matrix)

            if new_distance < best_distance:
                best_route = new_route
                best_distance = new_distance

    return best_route, best_distance

# Test TSP
distance_matrix = [[0, 1, 2, 3], [1, 0, 4, 5], [2, 4, 0, 6], [3, 5, 6, 0]]
route = [0, 1, 2, 3]
best_route, best_distance = two_opt(route, distance_matrix)
print("Best Route:", best_route)
print("Best Distance:", best_distance)




# Problem Statement:
# Given a set of jobs, each with a processing time, you need to schedule them on a set of machines to minimize 
# the total completion time.

def schedule_jobs(jobs, num_machines):
    jobs.sort(reverse=True)  # Sort jobs by descending order of time
    machines = [0] * num_machines  # Machines start with 0 time

    for job in jobs:
        # Assign the job to the machine with the minimum current load
        machine_id = machines.index(min(machines))
        machines[machine_id] += job

    return machines

# Test Job Scheduling
jobs = [10, 15, 20, 25, 30]
num_machines = 3
machines = schedule_jobs(jobs, num_machines)
print("Job Distribution across Machines:", machines)




# Problem Statement:
# Place `N` queens on an `N x N` chessboard such that no two queens threaten each other (i.e., no two queens
# are in the same row, column, or diagonal).

def is_safe(board, row, col):
    for i in range(row):
        if board[i] == col or board[i] - i == col - row or board[i] + i == col + row:
            return False
    return True

def solve_n_queens(board, row, n):
    if row == n:
        return [board[:]]

    solutions = []
    for col in range(n):
        if is_safe(board, row, col):
            board[row] = col
            solutions += solve_n_queens(board, row + 1, n)
            board[row] = -1  # Backtrack
    return solutions

# Test N-Queens
n = 4
board = [-1] * n  # -1 means no queen placed
solutions = solve_n_queens(board, 0, n)
print("Solutions:", solutions)




# Problem Statement:
# You are given an amount and a set of coin denominations. Find the fewest number of coins that make up that amount.

def coin_change(coins, amount):
    coins.sort(reverse=True)
    result = []

    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)

    return result if amount == 0 else "Not possible"

# Test Coin Change
coins = [1, 5, 10, 25, 50]
amount = 63
coins_used = coin_change(coins, amount)
print("Coins Used:", coins_used)



# Problem Statement:
# Given a set of integers, find a subset whose sum is equal to a target value.

def subset_sum(nums, target):
    nums.sort(reverse=True)
    current_sum = 0
    subset = []

    for num in nums:
        if current_sum + num <= target:
            subset.append(num)
            current_sum += num

    return subset if current_sum == target else "No solution"

# Test Subset Sum
nums = [1, 2, 3, 4, 5, 6]
target = 10
subset = subset_sum(nums, target)
print("Subset:", subset)





# Problem Statement:
# You are given an optimization problem where the search space is too large to check all possible solutions.
# How can you find a good solution in a reasonable amount of time?

import random
import math

def simulated_annealing(initial_state, evaluate, neighbor, temperature=1000, cooling_rate=0.995, min_temp=0.1):
    current_state = initial_state
    current_value = evaluate(current_state)

    while temperature > min_temp:
        next_state = neighbor(current_state)
        next_value = evaluate(next_state)

        if next_value < current_value or random.random() < math.exp((current_value - next_value) / temperature):
            current_state = next_state
            current_value = next_value

        temperature *= cooling_rate

    return current_state, current_value

# Example Test Problem
def evaluate(state):
    return sum(state)  # Just a simple example, can be replaced

def neighbor(state):
    next_state = state[:]
    next_state[random.randint(0, len(state)-1)] = random.randint(1, 10)  # Modify randomly
    return next_state

# Test Simulated Annealing
initial_state = [random.randint(1, 10) for _ in range(5)]
best_state, best_value = simulated_annealing(initial_state, evaluate, neighbor)
print("Best State:", best_state)
print("Best Value:", best_value)

# Problem Statement:
# Given a graph with vertices and edges, assign colors to each vertex such that no two adjacent vertices have
# the same color, using the smallest number of colors possible.

def is_valid_coloring(graph, coloring):
    for node in graph:
        for neighbor in graph[node]:
            if coloring[node] == coloring[neighbor]:
                return False
    return True

def graph_coloring(graph, num_colors):
    coloring = {node: -1 for node in graph}  # -1 means no color assigned
    nodes = list(graph.keys())

    def assign_colors(node_idx):
        if node_idx == len(nodes):
            return True

        node = nodes[node_idx]
        for color in range(num_colors):
            coloring[node] = color
            if is_valid_coloring(graph, coloring) and assign_colors(node_idx + 1):
                return True
            coloring[node] = -1  # Backtrack

        return False

    assign_colors(0)
    return coloring

# Test Graph Coloring
graph = {0: [1, 2], 1: [0, 2], 2: [0, 1]}
colors = graph_coloring(graph, 2)
print("Graph Coloring:", colors)





# Problem Statement:
# Given a graph and a subset of vertices, find the minimum weight tree that connects the subset of vertices.

# A simple greedy solution to Steiner Tree isn't feasible.
# A complex algorithm is needed like Minimum Spanning Tree with Steiner points.
# But for the sake of simplicity, here's a sample greedy approach:

def steiner_tree(graph, terminals):
    # Simple greedy approach (not optimal)
    # Start with a terminal node and greedily add the nearest neighbors
    tree = set(terminals)
    while len(tree) < len(graph):
        best_edge = None
        best_distance = float('inf')
        for node in tree:
            for neighbor in graph[node]:
                if neighbor not in tree and graph[node][neighbor] < best_distance:
                    best_edge = (node, neighbor)
                    best_distance = graph[node][neighbor]
        tree.add(best_edge[1])
    return tree

# Test Steiner Tree
graph = {0: {1: 1, 2: 2}, 1: {0: 1, 2: 1}, 2: {0: 2, 1: 1}}
terminals = [0, 2]
tree = steiner_tree(graph, terminals)
print("Steiner Tree:", tree)

# Problem Statement:
# Given a graph, partition the vertices into two sets such that the number of edges between the sets is maximized.

import random

def max_cut(graph):
    cut = random.choice([0, 1])
    partitions = {node: cut for node in graph}

    # Simple greedy approach (not optimal)
    for node in graph:
        if any(partitions[neighbor] != partitions[node] for neighbor in graph[node]):
            partitions[node] = 1 - partitions[node]  # Flip to opposite partition

    cut_value = sum(1 for node in graph for neighbor in graph[node] if partitions[node] != partitions[neighbor])
    return cut_value, partitions

# Test Max Cut
graph = {0: [1, 2], 1: [0, 2], 2: [0, 1]}
cut_value, partitions = max_cut(graph)
print("Max Cut Value:", cut_value)
print("Partitions:", partitions)





# Problem Statement:
# Given a partially filled Sudoku grid, fill in the missing numbers such that each row, column, and 3x3 subgrid 
# contains every number from 1 to 9.

def is_safe(board, row, col, num):
    for i in range(9):
        if board[row][i] == num or board[i][col] == num:
            return False
    start_row, start_col = row - row % 3, col - col % 3
    for i in range(3):
        for j in range(3):
            if board[i + start_row][j + start_col] == num:
                return False
    return True

def solve_sudoku(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:
                for num in range(1, 10):
                    if is_safe(board, row, col, num):
                        board[row][col] = num
                        if solve_sudoku(board):
                            return True
                        board[row][col] = 0
                return False
    return True

# Test Sudoku Solver
board = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]
solve_sudoku(board)
print("Solved Sudoku:")
for row in board:
    print(row)


# Problem Statement:
# Given an array of integers, find the contiguous subarray with the maximum sum.

def max_subarray(nums):
    max_sum = current_sum = nums[0]
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

# Test Maximum Subarray
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum = max_subarray(nums)
print("Maximum Subarray Sum:", max_sum)