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.