Spaces:
Running
Running
File size: 7,322 Bytes
0d3476b |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 |
import json
import logging
from flask import request
from routes import app
logger = logging.getLogger(__name__)
@app.route('/taxi-driver', methods=['POST'])
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."})
|