Skip to main content
Source Link

I accept the challenge, and I am using Python to implement this challenge.

import math
import itertools
import time

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

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

def calculate_path_metrics(path):
    """Calculate tastiness, distance, and ratio for a given path"""
    start_point = (0, 0)
    total_tastiness = 0
    total_distance = 0
    
    # Start from origin to first spot
    current_point = start_point
    for spot_id in path:
        spot_coords, tastiness = spots[spot_id]
        total_tastiness += tastiness
        total_distance += euclidean_distance(current_point, spot_coords)
        current_point = spot_coords
    
    ratio = total_tastiness / total_distance if total_distance > 0 else 0
    return total_tastiness, total_distance, ratio

def find_optimal_taco_crawl():
    """Find the optimal path that maximizes tastiness per distance"""
    start_time = time.time()
    
    best_ratio = -1
    best_path = None
    best_tastiness = 0
    best_distance = 0
    paths_evaluated = 0
    
    print("Evaluating all possible paths...")
    
    # Try all path lengths from 1 to 8 spots
    for k in range(1, 9):
        print(f"Checking paths with {k} spots...")
        
        # Generate all permutations of k spots from the 10 available
        for path in itertools.permutations(spots.keys(), k):
            tastiness, distance, ratio = calculate_path_metrics(path)
            paths_evaluated += 1
            
            if ratio > best_ratio:
                best_ratio = ratio
                best_path = path
                best_tastiness = tastiness
                best_distance = distance
    
    end_time = time.time()
    
    print(f"\n{'='*50}")
    print("TACO CRAWL OPTIMIZATION RESULTS")
    print(f"{'='*50}")
    print(f"Total paths evaluated: {paths_evaluated:,}")
    print(f"Computation time: {end_time - start_time:.2f} seconds")
    print(f"{'='*50}")
    
    return best_path, best_tastiness, best_distance, best_ratio

def main():
    """Main function to run the taco crawl optimization"""
    print("National Taco Day Challenge - Optimal Taco Crawl")
    print("Finding the path that maximizes tastiness per distance traveled...")
    print()
    
    # Display the taco spots information
    print("Taco Spots Information:")
    print("-" * 40)
    print(f"{'Spot':<6} {'Coordinates':<12} {'Tastiness':<10}")
    print("-" * 40)
    for spot_id, (coords, tastiness) in spots.items():
        print(f"{spot_id:<6} {str(coords):<12} {tastiness:<10}")
    print()
    
    # Find the optimal path
    optimal_path, tastiness, distance, ratio = find_optimal_taco_crawl()
    
    # Display the optimal path details
    print(f"Optimal Path: {list(optimal_path)}")
    print(f"Total Tastiness: {tastiness}")
    print(f"Total Distance Traveled: {distance:.2f}")
    print(f"Tastiness per Distance: {ratio:.4f}")
    print()
    
    # Display the route step-by-step
    print("Detailed Route:")
    print("-" * 50)
    current_point = (0, 0)
    total_dist = 0
    
    print(f"Start at: {current_point}")
    for i, spot_id in enumerate(optimal_path, 1):
        spot_coords, spot_tastiness = spots[spot_id]
        leg_distance = euclidean_distance(current_point, spot_coords)
        total_dist += leg_distance
        print(f"Step {i}: Go to Spot {spot_id} {spot_coords} "
              f"(tastiness: {spot_tastiness}, "
              f"distance: {leg_distance:.2f}, "
              f"cumulative: {total_dist:.2f})")
        current_point = spot_coords
    
    print(f"\nFinal cumulative distance: {total_dist:.2f}")
    print(f"Final ratio (tastiness/distance): {tastiness}/{total_dist:.2f} = {ratio:.4f}")

if __name__ == "__main__":
    main()
When you run this code, it will:
1. Evaluate all possible paths from 1 to 8 taco spots in all possible orders
2. Calculate the metrics for each path:
    * Total tastiness
    * Total distance traveled (from start through all visited spots)
    * Ratio of tastiness per distance
3. Find the optimal path that maximizes the ratio
4. Display detailed results including:
    * The optimal sequence of spots to visit
    * Total tastiness achieved
    * Total distance traveled
    * The optimized ratio value
    * Step-by-step route details
The code uses a brute-force approach since the problem size is manageable (about 2 million permutations total for paths of length 1-8). It will typically run in a few seconds to a minute depending on your computer's speed.
Key features:
* Clear, readable code with comments
* Progress reporting during computation
* Detailed output showing the reasoning
* Step-by-step route visualization
* Performance metrics (paths evaluated, computation time)
This solution will definitively find the globally optimal path for the taco crawl challenge according to the specified criteria.