Output of the 🌮 code posted below:
Best path: 7 -> 5 -> 6 -> 2 -> 10 -> 4
Total tastiness: 4997
Total distance: 1733.1451
Tastiness to distance ratio: 2.8689
Code used to solve the 🌮 challenge, I included an optional plot_taco_spots method that visualizes the data and path:
# Taco spot data (x, y, tastiness)
TACO_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)
}
# Parameters
HUNGER = 8 # Number of taco spot that can be visited
START = (0, 0) # Starting point
def plot_taco_spots(spots, path=None):
""" Visualize taco spots and optionally the path taken.
spots: dict of taco spots with index as key and (x, y, tastiness) as value
path: list of spot indices representing the path taken (optional)
"""
import matplotlib.pyplot as plt
# Some contract checks on the inputs to avoid plotting garbage
assert(isinstance(spots, dict) and len(spots) > 0), "Spots must be a non-empty dictionary"
assert(all(isinstance(v, tuple) and len(v) == 3 for v in spots.values())), "Invalid spots format"
assert(path is None or all(i in spots for i in path)), "Path contains invalid spot indices"
x = [spots[i][0] for i in spots]
y = [spots[i][1] for i in spots]
labels = [str(i) for i in spots]
plt.scatter(x, y, s=[spots[i][2]*20 for i in spots]) # Size proportional to tastiness
for i, label in enumerate(labels):
plt.annotate(label, (x[i], y[i]), textcoords="offset points", xytext=(0,10), ha='center')
if path:
path_x = [START[0]] + [spots[i][0] for i in path]
path_y = [START[1]] + [spots[i][1] for i in path]
plt.plot(path_x, path_y, 'r--')
plt.xlabel('X Coordinate')
plt.ylabel('Y Coordinate')
plt.xticks(range(0, 21, 1), [])
plt.yticks(range(0, 21, 1), [])
plt.title('Taco Spots')
plt.grid(True)
plt.axis('equal')
plt.show()
def get_distance_L2(p1, p2):
""" Calculate Euclidean distance between two given points, p1 and p2. Works without math import. """
return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5
def get_ratio(tastiness, distance):
""" Calculate tastiness to distance ratio. """
if distance == 0:
return 0.0 # Avoid division by zero
return tastiness / distance
def print_path(path, tastiness, distance):
""" Print the path in a readable format. """
print(" -> ".join(map(str, path)))
print(f" Total tastiness: {tastiness}")
print(f" Total distance: {distance:.2f}")
print(f" Tastiness to distance ratio: {get_ratio(tastiness, distance):.2f}")
if __name__ == "__main__":
# Stores all completed paths (no further improvements possible)
completed_paths = []
# Each path is a tuple: (path, current_position, current_tastiness, current_distance, remaining_spots, current_hunger)
initial_state = ([], START, 0, 0, set(i for i in TACO_SPOTS.keys()), HUNGER)
routes = [initial_state]
# Visit all possible paths, breadth-first, break early if no improvement is possible along a path
while routes:
new_paths = []
for path, position, tastiness, distance, rem_spots, hunger_left in routes:
improved = False # Track if any improvement was made on this path
# Look for next spots to visit
for spot_index in rem_spots:
spot = TACO_SPOTS[spot_index]
# Try to visit this spot, if hunger allows
if hunger_left > 0:
spot_pos = (spot[0], spot[1])
spot_dist = get_distance_L2(position, spot_pos)
new_tastiness = tastiness + spot[2]
new_distance = distance + spot_dist
prev_ratio = get_ratio(tastiness, distance)
new_ratio = get_ratio(new_tastiness, new_distance)
# Keep all paths alive that improve the tastiness/distance ratio
if new_ratio > prev_ratio:
improved = True
new_path new_path = path + [spot_index]
# Remove the visited spot from remaining spots
new_rem_spots = rem_spots.copy()
new_rem_spots.remove(spot_index)
new_paths.append((new_path, spot_pos, new_tastiness, new_distance, new_rem_spots, hunger_left - 1))
# No improvement, complete this path
if not improved and hunger_left:
completed_paths.append((path, tastiness, distance))
# Follow all active paths in the next iteration
routes = new_paths
# Find the best completed path
best_path = None
best_tastiness = 0
best_distance = float('inf')
for path, tastiness, distance in completed_paths:
if get_ratio(tastiness, distance) > get_ratio(best_tastiness, best_distance):
best_path = path
best_tastiness = tastiness
best_distance = distance
print("Best path: ", end="")
print_path(best_path, best_tastiness, best_distance)
# plot_taco_spots(TACO_SPOTS, best_path)
