import math
import itertools

# Taco spot data
spots = {
    1: {'coords': (2, 8), 'tastiness': 7},
    2: {'coords': (15, 3), 'tastiness': 17},
    3: {'coords': (6, 6), 'tastiness': 8},
    4: {'coords': (20, 15), 'tastiness': 30},
    5: {'coords': (11, 2), 'tastiness': 12},
    6: {'coords': (14, 1), 'tastiness': 15},
    7: {'coords': (7, 3), 'tastiness': 5},
    8: {'coords': (1, 12), 'tastiness': 12},
    9: {'coords': (3, 6), 'tastiness': 3},
    10: {'coords': (14, 13), 'tastiness': 18}
}

def euclidean_distance(coord1, coord2):
    """Calculate Euclidean distance between two points"""
    return math.sqrt((coord1[0] - coord2[0])**2 + (coord1[1] - coord2[1])**2)

def calculate_path_metrics(path):
    """Calculate total tastiness and distance for a given path"""
    total_tastiness = 0
    total_distance = 0
    
    # Start from origin (0,0)
    current_pos = (0, 0)
    
    for spot_id in path:
        spot_coords = spots[spot_id]['coords']
        total_tastiness += spots[spot_id]['tastiness']
        total_distance += euclidean_distance(current_pos, spot_coords)
        current_pos = spot_coords
    
    return total_tastiness, total_distance, total_tastiness / total_distance if total_distance > 0 else 0

def find_optimal_path():
    """Find the optimal path visiting up to 8 spots"""
    best_metric = 0
    best_path = None
    best_tastiness = 0
    best_distance = 0
    
    # Try all combinations of 1 to 8 spots
    for k in range(1, 9):
        for combo in itertools.combinations(range(1, 11), k):
            # Try all permutations of this combination
            for perm in itertools.permutations(combo):
                tastiness, distance, metric = calculate_path_metrics(perm)
                
                if metric > best_metric:
                    best_metric = metric
                    best_path = perm
                    best_tastiness = tastiness
                    best_distance = distance
    
    return best_path, best_tastiness, best_distance, best_metric

# Find optimal solution
optimal_path, total_tastiness, total_distance, metric = find_optimal_path()

print("OPTIMAL PATH:")
print(f"Path: {list(optimal_path)}")
print(f"Total Tastiness: {total_tastiness}")
print(f"Total Distance: {total_distance:.2f}")
print(f"Tastiness per Distance: {metric:.4f}")

# Verify the path
print("\nPATH DETAILS:")
current_pos = (0, 0)
cumulative_distance = 0
cumulative_tastiness = 0

print(f"Start at (0, 0)")
for i, spot_id in enumerate(optimal_path, 1):
    spot_coords = spots[spot_id]['coords']
    segment_distance = euclidean_distance(current_pos, spot_coords)
    cumulative_distance += segment_distance
    cumulative_tastiness += spots[spot_id]['tastiness']
    
    print(f"{i}. Spot {spot_id}: {spot_coords}, Tastiness: {spots[spot_id]['tastiness']}")
    print(f"   Segment distance: {segment_distance:.2f}, Cumulative: {cumulative_distance:.2f}")
    print(f"   Cumulative tastiness: {cumulative_tastiness}")
    
    current_pos = spot_coords

print(f"\nFinal Metric: {cumulative_tastiness}/{cumulative_distance:.2f} = {metric:.4f}")