Spaces:
Running
Running
import json | |
import logging | |
from flask import request | |
from routes import app | |
logger = logging.getLogger(__name__) | |
def taxi_driver(): | |
data = request.get_json() | |
#logging.info("data sent for evaluation {}".format(data)) | |
question = data.get("question", 0) | |
logger.info(f"Question: {question}") | |
challenge_input = data.get("challengeInput", {}) | |
# Extract start and end times | |
start_time_str = challenge_input.get("startTime", "00:00") | |
end_time_str = challenge_input.get("endTime", "00:00") | |
# Convert times to minutes | |
def time_str_to_minutes(time_str): | |
hours, minutes = map(int, time_str.split(":")) | |
return hours * 60 + minutes | |
start_time = time_str_to_minutes(start_time_str) | |
end_time = time_str_to_minutes(end_time_str) | |
# Handle end_time crossing midnight | |
if end_time < start_time: | |
end_time += 24 * 60 # Add 24 hours | |
max_time = end_time - start_time # Maximum time available | |
# Get taxi info | |
taxi_info = challenge_input.get("taxiInfo", []) | |
# Get taxi station info | |
taxi_station_info = challenge_input.get("taxiStationInfo", []) | |
# Build dictionaries for easy access | |
taxis = [] | |
for taxi in taxi_info: | |
taxi_id = taxi.get("taxiId") | |
taxi_location = taxi.get("taxiLocation") | |
taxi_dict = { | |
"taxiId": taxi_id, | |
"current_location": taxi_location, | |
"customer": None, | |
"destination": None, | |
"time_until_arrival": 0, | |
} | |
taxis.append(taxi_dict) | |
# Build a dict of taxi stations and their customers | |
stations = {} | |
for station in taxi_station_info: | |
station_name = station.get("taxiStation") | |
customers = station.get("customers", []) | |
stations[station_name] = customers.copy() | |
# Initialize customer removed times | |
customer_removed_times = {} | |
# Simulate other taxis to determine when customers are removed | |
for taxi in taxis: | |
if taxi["taxiId"] != 0: | |
time = start_time | |
while time < end_time: | |
if taxi["time_until_arrival"] > 0: | |
taxi["time_until_arrival"] -= 60 | |
if taxi["time_until_arrival"] <= 0: | |
taxi["current_location"] = taxi["destination"] | |
taxi["destination"] = None | |
taxi["customer"] = None | |
if taxi["time_until_arrival"] <= 0 and taxi["customer"] is None: | |
current_station = taxi["current_location"] | |
station_customers = stations.get(current_station, []) | |
if len(station_customers) > 0: | |
# Other taxis pick first customer in queue | |
customer = station_customers.pop(0) | |
taxi["customer"] = customer | |
taxi["destination"] = customer["destination"] | |
taxi["time_until_arrival"] = 60 # 1 hour | |
# Record when customer is removed | |
customer_removed_times[customer["customerId"]] = time | |
else: | |
# No customers, taxi waits | |
break | |
time += 60 # Advance time by 1 hour | |
# Now proceed to find the best path for Taxi Lo | |
if question == 0 or question == "ONE": | |
# Part 1 | |
# Initialize variables for DFS | |
max_profit = 0 | |
best_path = [] | |
best_customers = [] | |
# Create a copy of stations for Taxi Lo | |
taxi_lo_stations = {station: customers.copy() for station, customers in stations.items()} | |
# Initialize customer removed times for Taxi Lo | |
taxi_lo_customer_removed_times = customer_removed_times.copy() | |
# DFS function to explore all possible paths | |
def dfs(current_station, current_time, profit_so_far, path_so_far, customers_picked_so_far): | |
nonlocal max_profit, best_path, best_customers | |
# Base case: if current time exceeds shift end time | |
if current_time >= end_time or (current_time - start_time) >= max_time: | |
if profit_so_far > max_profit: | |
max_profit = profit_so_far | |
best_path = path_so_far.copy() | |
best_customers = customers_picked_so_far.copy() | |
return | |
# Get available customers at current station and time | |
available_customers = [] | |
for customer in taxi_lo_stations.get(current_station, []): | |
removed_time = taxi_lo_customer_removed_times.get(customer["customerId"], None) | |
if removed_time is None or removed_time > current_time: | |
available_customers.append(customer) | |
# If no customers available, cannot proceed further | |
if not available_customers: | |
if profit_so_far > max_profit: | |
max_profit = profit_so_far | |
best_path = path_so_far.copy() | |
best_customers = customers_picked_so_far.copy() | |
return | |
# Try picking each available customer | |
for customer in available_customers: | |
# Temporarily remove customer | |
taxi_lo_stations[current_station].remove(customer) | |
prev_removed_time = taxi_lo_customer_removed_times.get(customer["customerId"], None) | |
taxi_lo_customer_removed_times[customer["customerId"]] = current_time | |
next_station = customer["destination"] | |
next_time = current_time + 60 # Travel time is 1 hour | |
# Update path and customers picked | |
path_so_far.append(next_station) | |
customers_picked_so_far.append(customer["customerId"]) | |
dfs(next_station, next_time, profit_so_far + customer["fee"], path_so_far, customers_picked_so_far) | |
# Backtrack | |
path_so_far.pop() | |
customers_picked_so_far.pop() | |
taxi_lo_stations[current_station].append(customer) | |
taxi_lo_customer_removed_times[customer["customerId"]] = prev_removed_time | |
# Start DFS from Taxi Lo's starting location | |
taxi_lo = next((taxi for taxi in taxis if taxi["taxiId"] == 0), None) | |
dfs(taxi_lo["current_location"], start_time, 0, [], []) | |
result = { | |
"path": best_path, | |
"customers": best_customers, | |
"profit": max_profit | |
} | |
logging.info("My result :{}".format(result)) | |
return json.dumps(result) | |
else: | |
# For Part 2, similar adjustments are needed | |
# Due to complexity, Part 2 code would require a more advanced approach | |
# This response focuses on correcting Part 1 as per your request | |
return json.dumps({"error": "This code currently handles only Part 1 correctly."}) | |