Code Challenge #11: Taco crawl optimization
Update on October 8: The original taco spot "tastiness" values were incorrect. Sorry about that! The correct values are now reflected in the table.
Yesterday it was National Taco Day 🌮 in the United States. In honor of the holiday, we have a taco themed challenge.
Tacos are snack-sized and come in many variations. This makes them a great food for a "crawl", an event in which people would try to visit multiple taco spots.
The Challenge
Given a list of taco spots, determine the most optimal path for the taco crawl.
Important details:
There are 10 taco spots, each with a location on a two dimensional space, i.e. (x, y) coordinates.
You can only visit up to 8 of them (hunger isn't infinite).
Each spot has a "tastiness" score - some of the locations have better tacos than others.
The optimal path would return the highest total tastiness per distance traveled.
Sum up the tastiness of the visited taco spots (up to 8 spots)
Sum up the travel distance. Travel distance is the straight-line distance, calculated by the Euclidean distance formula. For example, to travel from (0,0) to (3,3) the distance is sqrt(32+32)=4.24
Divide by the total tastiness by distance traveled to reach those spots. This is the metric we want to optimize for.
You start at (0,0) and finish at the last spot. No need to return back to the start.
You can only visit each taco spot once
| Taco Spot | Coordinates | Tastiness |
|---|---|---|
| 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 |
This is a pass/fail challenge. Everyone who determines the optimal path (and shows their work), will be considered a challenge winner.
At the scale of this challenge, a brute force approach could probably work. That's valid. Other approaches are welcome also.
Key information
You have two weeks from the date this challenge is posted to submit your entry.
October 8: Challenge goes live
October 23: Challenge is complete and we'll announce winners soon after.
Your submission should include:
The optimal routing you determined to visit up to 8 taco spots, e.g. [3, 2, 1 , 7, 9, 4, 6, 8]
The total tastiness achieved
The total distance traveled
The "tastiness per distance" metric (this is what we want to optimize for)
The code you used to solve this challenge
[Optional] Anything you learned or any interesting challenges you faced while coding
Your entry is not permitted to be written by AI. For any feedback on this Challenge, please head over to the Meta post.
