INTRODUCTION

• You have been given a list of 12 sites on a map.
• Your objective is to design an optimal path that connects these sites.
• The path needs to be cyclic: it can start at any site but can only visit each subsequent site once (except for the start/end site).
• Your path has an important constraint: you cannot navigate directly North or South. Any other direction is fine.
• Your task is to optimize on length: the shorter the total distance travelled, the better.

ASSIGNMENT

• Read in the coordinates of the sites and store them in an appropriate data structure.
• Find the cycle that connects all sites and minimizes total distance travelled. Remember, each site should be visited only once (except for the start/end site), and you cannot directly travel South → North, or North → South.
• print the order in which the cycle visits the path, and the total distance travelled.

import pandas as pd
import math
import matplotlib.pyplot as plt

# Read in the coordinates of the sites
def read_site_coordinates(filename):
    df = pd.read_csv(filename)
    coordinates = {}
    for index, row in df.iterrows():
        coordinates[index] = (row['x'], row['y'])
    return coordinates

# Calculate the Euclidean distance between two points
def distance(point1, point2):
    return math.sqrt((point1[0] - point2[0])**2 + (point1[1] - point2[1])**2)

# Find the nearest unvisited neighbor from a given site
def find_nearest_neighbor_site(current_site, empty_sites, coordinates):
    min_distance = float('inf')
    nearest_site = None
    current_x, current_y = coordinates[current_site]

    for site in empty_sites:
        if site != current_site:
            x, y = coordinates[site]
            # Exclude sites with x equal to the current site's x (i.e. North)
            if x == current_x:
                continue
            dist = distance(coordinates[current_site], coordinates[site])
            if dist < min_distance:
                min_distance = dist
                nearest_site = site
    return nearest_site

# path connecting all sites using nearest neighbor function
def pathfinder(coordinates, start_site):
    current_site = start_site
    empty_sites = set(coordinates.keys())
    empty_sites.remove(start_site)
    path = [start_site]
    total_distance = 0

    while empty_sites:
        nearest_site = find_nearest_neighbor_site(current_site, empty_sites, coordinates)
        path.append(nearest_site)
        total_distance += distance(coordinates[current_site], coordinates[nearest_site])
        empty_sites.remove(nearest_site)
        current_site = nearest_site

    # Return to the starting site
    total_distance += distance(coordinates[path[-1]], coordinates[start_site])
    path.append(start_site)
    total_distance = round(total_distance,2)

    return path, total_distance

def plot_path(coordinates, path):
    x_values = [coordinates[site][0] for site in path]
    y_values = [coordinates[site][1] for site in path]
    offset = 1.5 

    for i, (x, y) in enumerate(zip(x_values, y_values)):
        plt.text(x + offset, y + offset, str(path[i]), fontsize=10, ha='center', va='center')  # Add offset to labels
    plt.plot(x_values, y_values, marker='o', linestyle='-')
    plt.xlabel('X')
    plt.ylabel('Y')
    plt.title('Optimal Path for Start Site {}'.format(path[0]))
    plt.grid(True)
    plt.show()

def main():
    filename = "1_novel_navigation.csv"  
    coordinates = read_site_coordinates(filename)
    
    shortest_distance = float('inf')
    best_path = None
    
    for start_site in coordinates.keys():
        path, total_distance = pathfinder(coordinates, start_site)
        print("path order from Start Site", start_site, ":", path)
        print("Total distance traveled from Start Site", start_site, ":", total_distance)
        if total_distance < shortest_distance:
            shortest_distance = total_distance
            best_path = path
        plot_path(coordinates, path)

    print('\n\n')
    print("Optimal solution with shortest distance traveled:")
    print("Site order:", best_path)
    print("Total distance:", shortest_distance)
    plot_path(coordinates, best_path)

if __name__ == '__main__':
    main()

path order from Start Site 0 : [0, 1, 2, 4, 8, 6, 10, 11, 7, 9, 5, 3, 0]
Total distance traveled from Start Site 0 : 461.47

path order from Start Site 1 : [1, 0, 3, 5, 9, 7, 11, 10, 6, 8, 4, 2, 1]
Total distance traveled from Start Site 1 : 461.47

path order from Start Site 2 : [2, 4, 0, 1, 5, 3, 7, 9, 8, 6, 10, 11, 2]
Total distance traveled from Start Site 2 : 501.47

path order from Start Site 3 : [3, 5, 1, 0, 4, 2, 6, 8, 9, 7, 11, 10, 3]
Total distance traveled from Start Site 3 : 501.47

path order from Start Site 4 : [4, 2, 3, 5, 1, 0, 6, 8, 9, 7, 11, 10, 4]
Total distance traveled from Start Site 4 : 489.07

path order from Start Site 5 : [5, 3, 2, 4, 0, 1, 7, 9, 8, 6, 10, 11, 5]
Total distance traveled from Start Site 5 : 489.07

path order from Start Site 6 : [6, 8, 9, 7, 3, 5, 1, 0, 4, 2, 11, 10, 6]
Total distance traveled from Start Site 6 : 501.47

path order from Start Site 7 : [7, 9, 8, 6, 2, 4, 0, 1, 5, 3, 10, 11, 7]
Total distance traveled from Start Site 7 : 501.47

path order from Start Site 8 : [8, 6, 2, 4, 0, 1, 5, 3, 7, 9, 10, 11, 8]
Total distance traveled from Start Site 8 : 461.47

path order from Start Site 9 : [9, 7, 3, 5, 1, 0, 4, 2, 6, 8, 11, 10, 9]
Total distance traveled from Start Site 9 : 461.47

path order from Start Site 10 : [10, 11, 7, 9, 8, 6, 2, 4, 0, 1, 5, 3, 10]
Total distance traveled from Start Site 10 : 501.47

path order from Start Site 11 : [11, 10, 6, 8, 9, 7, 3, 5, 1, 0, 4, 2, 11]
Total distance traveled from Start Site 11 : 501.47

Optimal solution with shortest distance traveled:
Site order: [0, 1, 2, 4, 8, 6, 10, 11, 7, 9, 5, 3, 0]
Total distance: 461.47