Spaces:
Sleeping
Sleeping
| from __future__ import annotations | |
| import heapq | |
| from typing import Dict, List, Tuple | |
| from .data_loader import load_edges | |
| def _build_graph() -> Dict[str, List[Tuple[str, int]]]: | |
| graph: Dict[str, List[Tuple[str, int]]] = {} | |
| for edge in load_edges(): | |
| a = edge["from"] | |
| b = edge["to"] | |
| d = int(edge["distance_m"]) | |
| graph.setdefault(a, []).append((b, d)) | |
| graph.setdefault(b, []).append((a, d)) | |
| return graph | |
| GRAPH_CACHE: Dict[str, List[Tuple[str, int]]] | None = None | |
| def get_graph() -> Dict[str, List[Tuple[str, int]]]: | |
| global GRAPH_CACHE | |
| if GRAPH_CACHE is None: | |
| GRAPH_CACHE = _build_graph() | |
| return GRAPH_CACHE | |
| def shortest_path_distance(start: str, goal: str) -> int: | |
| if start == goal: | |
| return 0 | |
| graph = get_graph() | |
| dist: Dict[str, int] = {start: 0} | |
| pq: List[Tuple[int, str]] = [(0, start)] | |
| while pq: | |
| cur_dist, node = heapq.heappop(pq) | |
| if node == goal: | |
| return cur_dist | |
| if cur_dist > dist.get(node, float("inf")): | |
| continue | |
| for neighbor, weight in graph.get(node, []): | |
| nd = cur_dist + weight | |
| if nd < dist.get(neighbor, float("inf")): | |
| dist[neighbor] = nd | |
| heapq.heappush(pq, (nd, neighbor)) | |
| return 0 | |
| def order_by_nearest_neighbor( | |
| attraction_ids: List[str], | |
| node_lookup: Dict[str, str], | |
| start_node: str = "HUB", | |
| ) -> List[str]: | |
| """Order attractions by geography: nearest-neighbor from start_node to minimize walking.""" | |
| current = start_node | |
| to_visit = [a for a in attraction_ids if node_lookup.get(a)] | |
| ordered: List[str] = [] | |
| while to_visit: | |
| best_id: str | None = None | |
| best_dist = float("inf") | |
| for aid in to_visit: | |
| node = node_lookup[aid] | |
| d = shortest_path_distance(current, node) | |
| if d < best_dist: | |
| best_dist = d | |
| best_id = aid | |
| if best_id is None: | |
| break | |
| ordered.append(best_id) | |
| to_visit.remove(best_id) | |
| current = node_lookup[best_id] | |
| return ordered | |
| def greedy_schedule( | |
| attractions_order: List[str], | |
| start_time_minutes: int, | |
| walking_weight: float, | |
| wait_time_lookup: Dict[str, int], | |
| node_lookup: Dict[str, str], | |
| ) -> Tuple[List[Dict], int, int]: | |
| from .data_loader import walking_distance_between, load_attractions | |
| attractions = load_attractions() | |
| current_node = "HUB" | |
| current_time = start_time_minutes | |
| total_wait = 0 | |
| total_walk = 0 | |
| stops: List[Dict] = [] | |
| for attr_id in attractions_order: | |
| attr = attractions[attr_id] | |
| target_node = node_lookup[attr_id] | |
| walk = walking_distance_between(current_node, target_node) | |
| wait = wait_time_lookup.get(attr_id, 10) | |
| total_walk += walk | |
| total_wait += wait | |
| start_time_str = f"{current_time // 60:02d}:{current_time % 60:02d}" | |
| current_time += walk // 80 | |
| current_time += wait | |
| end_time_str = f"{current_time // 60:02d}:{current_time % 60:02d}" | |
| stops.append( | |
| { | |
| "attraction_id": attr.id, | |
| "attraction_name": attr.name, | |
| "node_id": attr.node_id, | |
| "start_time": start_time_str, | |
| "end_time": end_time_str, | |
| "estimated_wait_minutes": wait, | |
| "walking_distance_m": walk, | |
| } | |
| ) | |
| current_node = target_node | |
| return stops, total_wait, total_walk | |