import json import logging from flask import Flask, request, jsonify from collections import defaultdict import heapq from itertools import combinations, permutations logger = logging.getLogger(__name__) from routes import app # Constants (same as your original data) SUBWAY_LINES = { "Tokyo Metro Ginza Line": [ "Asakusa", "Tawaramachi", "Inaricho", "Ueno", "Ueno-hirokoji", "Suehirocho", "Kanda", "Mitsukoshimae", "Nihombashi", "Kyobashi", "Ginza", "Shimbashi", "Toranomon", "Tameike-sanno", "Akasaka-mitsuke", "Nagatacho", "Aoyama-itchome", "Gaiemmae", "Omotesando", "Shibuya" ], "Tokyo Metro Marunouchi Line": [ "Ogikubo", "Minami-asagaya", "Shin-koenji", "Higashi-koenji", "Shin-nakano", "Nakano-sakaue", "Nishi-shinjuku", "Shinjuku", "Shinjuku-sanchome", "Shin-ochanomizu", "Ochanomizu", "Awajicho", "Otemachi", "Tokyo", "Ginza", "Kasumigaseki", "Kokkai-gijidomae", "Akasaka-mitsuke", "Yotsuya", "Yotsuya-sanchome", "Shinjuku-gyoemmae", "Nishi-shinjuku-gochome", "Nakano-fujimicho", "Nakano-shimbashi", "Nakano-sakaue", "Shinjuku-sanchome", "Kokkai-gijidomae", "Kasumigaseki", "Ginza", "Tokyo", "Otemachi", "Awajicho", "Shin-ochanomizu", "Ochanomizu" ], "Tokyo Metro Hibiya Line": [ "Naka-meguro", "Ebisu", "Hiroo", "Roppongi", "Kamiyacho", "Kasumigaseki", "Hibiya", "Ginza", "Higashi-ginza", "Tsukiji", "Hatchobori", "Kayabacho", "Nihombashi", "Kodemmacho", "Akihabara", "Naka-okachimachi", "Ueno", "Iriya", "Minowa", "Minami-senju", "Kita-senju" ], "Tokyo Metro Tozai Line": [ "Nakano", "Ochiai", "Takadanobaba", "Waseda", "Kagurazaka", "Iidabashi", "Kudanshita", "Takebashi", "Otemachi", "Nihombashi", "Kayabacho", "Monzen-nakacho", "Kiba", "Toyosu", "Minami-sunamachi", "Nishi-kasai", "Kasai", "Urayasu", "Minami-gyotoku", "Gyotoku", "Myoden", "Baraki-nakayama", "Nishi-funabashi" ], "Tokyo Metro Chiyoda Line": [ "Yoyogi-uehara", "Yoyogi-koen", "Meiji-jingumae", "Omotesando", "Nogizaka", "Akasaka", "Kokkai-gijidomae", "Kasumigaseki", "Hibiya", "Nijubashimae", "Otemachi", "Shin-ochanomizu", "Yushima", "Nezu", "Sendagi", "Nishi-nippori", "Machiya", "Kita-senju", "Ayase", "Kita-ayase" ], "Tokyo Metro Yurakucho Line": [ "Wakoshi", "Chikatetsu-narimasu", "Chikatetsu-akatsuka", "Heiwadai", "Hikawadai", "Kotake-mukaihara", "Senkawa", "Kanamecho", "Ikebukuro", "Higashi-ikebukuro", "Gokokuji", "Edogawabashi", "Iidabashi", "Ichigaya", "Kojimachi", "Nagatacho", "Sakuradamon", "Yurakucho", "Ginza-itchome", "Shintomicho", "Toyocho", "Kiba", "Toyosu", "Tsukishima", "Shintomicho", "Tatsumi", "Shinonome", "Ariake" ], "Tokyo Metro Hanzomon Line": [ "Shibuya", "Omotesando", "Aoyama-itchome", "Nagatacho", "Hanzomon", "Kudanshita", "Jimbocho", "Otemachi", "Mitsukoshimae", "Suitengumae", "Kiyosumi-shirakawa", "Sumiyoshi", "Kinshicho", "Oshiage" ], "Tokyo Metro Namboku Line": [ "Meguro", "Shirokanedai", "Shirokane-takanawa", "Azabu-juban", "Roppongi-itchome", "Tameike-sanno", "Nagatacho", "Yotsuya", "Ichigaya", "Iidabashi", "Korakuen", "Todaimae", "Hon-komagome", "Komagome", "Nishigahara", "Oji", "Oji-kamiya", "Shimo", "Akabane-iwabuchi" ], "Tokyo Metro Fukutoshin Line": [ "Wakoshi", "Chikatetsu-narimasu", "Chikatetsu-akatsuka", "Narimasu", "Shimo-akatsuka", "Heiwadai", "Hikawadai", "Kotake-mukaihara", "Senkawa", "Kanamecho", "Ikebukuro", "Zoshigaya", "Nishi-waseda", "Higashi-shinjuku", "Shinjuku-sanchome", "Kita-sando", "Meiji-jingumae", "Shibuya" ], "Toei Asakusa Line": [ "Nishi-magome", "Magome", "Nakanobu", "Togoshi", "Gotanda", "Takanawadai", "Sengakuji", "Mita", "Shiba-koen", "Daimon", "Shimbashi", "Higashi-ginza", "Takaracho", "Nihombashi", "Ningyocho", "Higashi-nihombashi", "Asakusabashi", "Kuramae", "Asakusa", "Honjo-azumabashi", "Oshiage" ], "Toei Mita Line": [ "Meguro", "Shirokanedai", "Shirokane-takanawa", "Mita", "Shiba-koen", "Onarimon", "Uchisaiwaicho", "Hibiya", "Otemachi", "Jimbocho", "Suidobashi", "Kasuga", "Hakusan", "Sengoku", "Sugamo", "Nishi-sugamo", "Shin-itabashi", "Itabashi-kuyakushomae", "Itabashi-honcho", "Motohasunuma", "Shin-takashimadaira", "Nishidai", "Hasune", "Takashimadaira", "Shimura-sakaue", "Shimura-sanchome", "Nishidai" ], "Toei Shinjuku Line": [ "Shinjuku", "Shinjuku-sanchome", "Akebonobashi", "Ichigaya", "Kudanshita", "Jimbocho", "Ogawamachi", "Iwamotocho", "Bakuro-yokoyama", "Hamacho", "Morishita", "Kikukawa", "Sumiyoshi", "Nishi-ojima", "Ojima", "Higashi-ojima", "Funabori", "Ichinoe", "Mizue", "Shinozaki", "Motoyawata" ], "Toei Oedo Line": [ "Hikarigaoka", "Nerima-kasugacho", "Toshimaen", "Nerima", "Nerima-sakamachi", "Shin-egota", "Ochiai-minami-nagasaki", "Nakai", "Higashi-nakano", "Nakano-sakaue", "Nishi-shinjuku-gochome", "Tochomae", "Shinjuku-nishiguchi", "Higashi-shinjuku", "Wakamatsu-kawada", "Ushigome-yanagicho", "Ushigome-kagurazaka", "Iidabashi", "Kasuga", "Hongosanchome", "Ueno-okachimachi", "Shin-okachimachi", "Kuramae", "Ryogoku", "Morishita", "Kiyosumi-shirakawa", "Monzen-nakacho", "Tsukishima", "Kachidoki", "Shiodome", "Daimon", "Akasaka-mitsuke", "Roppongi", "Aoyama-itchome", "Shinjuku", "Tochomae", "Shinjuku", "Shinjuku-sanchome", "Higashi-shinjuku", "Wakamatsu-kawada", "Ushigome-yanagicho", "Ushigome-kagurazaka", "Iidabashi", "Kasuga", "Hongosanchome", "Ueno-okachimachi", "Shin-okachimachi", "Kuramae", "Ryogoku", "Morishita", "Kiyosumi-shirakawa", "Monzen-nakacho", "Tsukishima", "Kachidoki", "Shiodome", "Daimon", "Shiodome", "Tsukishima" ] } TRAVEL_TIMES = { "Tokyo Metro Ginza Line": 2, "Tokyo Metro Marunouchi Line": 3, "Tokyo Metro Hibiya Line": 2.5, "Tokyo Metro Tozai Line": 4, "Tokyo Metro Chiyoda Line": 1.5, "Tokyo Metro Yurakucho Line": 2, "Tokyo Metro Hanzomon Line": 2, "Tokyo Metro Namboku Line": 1, "Tokyo Metro Fukutoshin Line": 3, "Toei Asakusa Line": 3.5, "Toei Mita Line": 4, "Toei Shinjuku Line": 1.5, "Toei Oedo Line": 1 } def build_graph(): """ Builds an undirected graph where each node is a station, and edges represent travel times between stations. If multiple lines connect the same two stations with different travel times, the minimum travel time is used. """ graph = defaultdict(dict) for line, stations in SUBWAY_LINES.items(): travel_time = TRAVEL_TIMES.get(line, 2) # Default travel time if not specified for i in range(len(stations) - 1): station_a = stations[i] station_b = stations[i + 1] # If there's already a connection, keep the minimum travel time if station_b not in graph[station_a] or travel_time < graph[station_a][station_b]: graph[station_a][station_b] = travel_time graph[station_b][station_a] = travel_time # Since the graph is undirected return graph GRAPH = build_graph() def compute_distances(graph, stations): # graph: dict of dicts, as before # stations: list of stations to compute distances between N = len(stations) dist = [[float('inf')] * N for _ in range(N)] for i in range(N): station = stations[i] distances = dijkstra(graph, station) for j in range(N): dist[i][j] = distances.get(stations[j], float('inf')) return dist def dijkstra(graph, start): distances = {start: 0} heap = [(0, start)] while heap: cur_dist, u = heapq.heappop(heap) if cur_dist > distances[u]: continue for v, weight in graph.get(u, {}).items(): alt = cur_dist + weight if alt < distances.get(v, float('inf')): distances[v] = alt heapq.heappush(heap, (alt, v)) return distances def find_optimal_path(graph, locations, start, time_limit, dist, station_indices): stations = list(locations.keys()) stations.remove(start) N = len(stations) max_satisfaction = 0 best_path = [start, start] # Generate all subsets of the stations (excluding the starting point) for r in range(1, N + 1): subsets = combinations(stations, r) for subset in subsets: perms = permutations(subset) for perm in perms: path = [start] + list(perm) + [start] total_time = 0 total_satisfaction = 0 valid_path = True for i in range(len(path) - 1): u = path[i] v = path[i + 1] u_idx = station_indices[u] v_idx = station_indices[v] travel_time = dist[u_idx][v_idx] if travel_time == float('inf'): # No path between u and v valid_path = False break total_time += travel_time if i + 1 < len(path) - 1: # Add visit time for intermediate stations visit_time = locations[v][1] total_time += visit_time total_satisfaction += locations[v][0] else: # Last station (returning to start), no visit time pass if not valid_path: continue # Include visit time at starting point (if any) total_time += locations[start][1] if total_time <= time_limit and total_satisfaction > max_satisfaction: max_satisfaction = total_satisfaction best_path = path.copy() return best_path, max_satisfaction @app.route('/tourist', methods=['POST']) def tourist(): logger.info(request.get_data(as_text=True)) if request.is_json: # Ensure the request is JSON data = request.get_json() logger.info(f"Data received for evaluation: {data}") locations = data.get("locations", {}) starting_point = data.get("startingPoint", "") time_limit = data.get("timeLimit", 480) # Default to 480 minutes if not provided if starting_point not in locations: return jsonify({"error": "Starting point must be one of the locations with satisfaction and time values."}), 400 # Build the list of all stations stations = list(locations.keys()) if starting_point not in stations: stations.append(starting_point) all_stations = stations station_indices = {station: i for i, station in enumerate(all_stations)} dist_matrix = compute_distances(GRAPH, all_stations) # Find the optimal path path, satisfaction_value = find_optimal_path(GRAPH, locations, starting_point, time_limit, dist_matrix, station_indices) # Validate that the path starts and ends with starting_point if not (path[0] == starting_point and path[-1] == starting_point): return jsonify({"error": "Path does not start and end with the starting point."}), 400 # Recompute total_time using dist_matrix total_time = 0 for i in range(len(path) -1): current = path[i] next_station = path[i + 1] u_idx = station_indices[current] v_idx = station_indices[next_station] travel_time = dist_matrix[u_idx][v_idx] if travel_time == float('inf'): return jsonify({"error": f"No path between {current} and {next_station}."}), 400 total_time += travel_time if i + 1 < len(path) - 1: # Add visit time for intermediate stations visit_time = locations[next_station][1] total_time += visit_time else: # Last station (returning to start), no visit time pass # Include visit time at starting point (if any) total_time += locations[starting_point][1] if total_time > time_limit: return jsonify({"error": "Total time exceeds the time limit."}), 400 result = { "path": path, "satisfaction": satisfaction_value } logger.info(f"Result: {result}") return jsonify(result) else: return jsonify({"error": "Request must be in JSON format", "data": request.get_data(as_text=True)}), 415