routes/tourist.py

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