Spaces:
Running
Running
from flask import request, jsonify | |
import logging | |
from routes import app | |
import re | |
from collections import deque | |
logger = logging.getLogger(__name__) | |
from copy import deepcopy | |
import sys | |
import threading | |
# Set recursion limit higher to prevent maximum recursion depth exceeded error | |
sys.setrecursionlimit(100000) | |
from flask import Flask, request, jsonify | |
from copy import deepcopy | |
import sys | |
import threading | |
from collections import deque | |
# Set recursion limit higher to prevent maximum recursion depth exceeded error | |
sys.setrecursionlimit(100000) | |
def parking_lot(): | |
test_cases = request.get_json() | |
responses = [] | |
for test_case in test_cases: | |
response = process_test_case(test_case) | |
responses.append(response) | |
return jsonify(responses) | |
def process_test_case(test_case): | |
minimum_total_fare = test_case["minimumTotalFare"] | |
vehicles_info = {v["plateNumber"]: v for v in test_case["vehicles"]} | |
actions = test_case["actions"] | |
parking_lot = test_case["parkingLot"] | |
# Initialize parking lot state | |
parking_lot_state = ParkingLot(parking_lot) | |
# Keep track of parked vehicles and their positions | |
parked_vehicles = {} | |
total_fare_collected = 0 | |
# Prepare the response actions | |
response_actions = [] | |
# Sort vehicles by parking fare descending to prioritize higher fares | |
vehicles_by_fare = sorted(vehicles_info.values(), key=lambda v: -v["parkingFare"]) | |
vehicles_parked = set() | |
for action in actions: | |
plate_number = action["plateNumber"] | |
vehicle_action = action["action"] | |
vehicle_info = vehicles_info[plate_number] | |
if vehicle_action == "park": | |
# If we need more fare, try to park the vehicle | |
if total_fare_collected < minimum_total_fare: | |
if plate_number not in vehicles_parked: | |
# Try to find a parking position | |
position = parking_lot_state.find_parking_position(vehicle_info) | |
if position: | |
# Park the vehicle | |
parking_lot_state.place_vehicle(vehicle_info, position) | |
parked_vehicles[plate_number] = (vehicle_info, position) | |
vehicles_parked.add(plate_number) | |
response_actions.append({ | |
"plateNumber": plate_number, | |
"action": "park", | |
"execute": True, | |
"position": { | |
"x": position.x, | |
"y": position.y, | |
"direction": position.direction | |
} | |
}) | |
else: | |
# Cannot park the vehicle | |
response_actions.append({ | |
"plateNumber": plate_number, | |
"action": "park", | |
"execute": False, | |
"position": None | |
}) | |
else: | |
# Vehicle already parked | |
response_actions.append({ | |
"plateNumber": plate_number, | |
"action": "park", | |
"execute": False, | |
"position": None | |
}) | |
else: | |
# Already met minimum fare, skip parking | |
response_actions.append({ | |
"plateNumber": plate_number, | |
"action": "park", | |
"execute": False, | |
"position": None | |
}) | |
elif vehicle_action == "exit": | |
if plate_number in parked_vehicles: | |
vehicle_info, position = parked_vehicles[plate_number] | |
# Try to find a path to exit | |
can_exit = parking_lot_state.can_exit_vehicle(vehicle_info, position) | |
if can_exit: | |
# Remove the vehicle | |
parking_lot_state.remove_vehicle(vehicle_info, position) | |
total_fare_collected += vehicle_info["parkingFare"] | |
del parked_vehicles[plate_number] | |
response_actions.append({ | |
"plateNumber": plate_number, | |
"action": "exit", | |
"execute": True, | |
"position": { | |
"x": position.x, | |
"y": position.y, | |
"direction": position.direction | |
} | |
}) | |
else: | |
# Cannot exit the vehicle | |
response_actions.append({ | |
"plateNumber": plate_number, | |
"action": "exit", | |
"execute": False, | |
"position": None | |
}) | |
else: | |
# Vehicle is not parked | |
response_actions.append({ | |
"plateNumber": plate_number, | |
"action": "exit", | |
"execute": False, | |
"position": None | |
}) | |
else: | |
# Unknown action, skip | |
response_actions.append({ | |
"plateNumber": plate_number, | |
"action": vehicle_action, | |
"execute": False, | |
"position": None | |
}) | |
return { | |
"actions": response_actions | |
} | |
class ParkingLot: | |
def __init__(self, parking_lot_map): | |
self.map = parking_lot_map | |
self.height = len(parking_lot_map) | |
self.width = len(parking_lot_map[0]) if self.height > 0 else 0 | |
self.walls = set() | |
self.entrances = set() | |
self.exits = set() | |
self.occupied = set() | |
# Parse the parking lot map | |
for y in range(self.height): | |
for x in range(self.width): | |
cell = parking_lot_map[y][x] | |
if cell == 'X': | |
self.walls.add((x, y)) | |
elif cell == 'I': | |
self.entrances.add((x, y)) | |
elif cell == 'O': | |
self.exits.add((x, y)) | |
# Initialize occupied cells (walls, entrances, exits) | |
if cell != ' ': | |
self.occupied.add((x, y)) | |
def find_parking_position(self, vehicle_info): | |
# Try to find a valid parking position adjacent to an entrance | |
for entrance in self.entrances: | |
ex, ey = entrance | |
possible_directions = [] | |
if ex == 0: | |
possible_directions.append('EAST') | |
if ey == 0: | |
possible_directions.append('SOUTH') | |
for direction in possible_directions: | |
dx, dy = self.direction_to_delta(direction) | |
for step in range(1, max(self.width, self.height)): | |
nx, ny = ex + dx * step, ey + dy * step | |
position = Position(nx, ny, direction) | |
if self.is_valid_parking_position(vehicle_info, position): | |
return position | |
return None | |
def is_valid_parking_position(self, vehicle_info, position): | |
occupied_cells = self.get_vehicle_cells(vehicle_info, position) | |
# Cannot park on walls, entrances, exits, or occupied cells | |
for cell in occupied_cells: | |
if cell in self.walls or cell in self.occupied or cell in self.entrances or cell in self.exits: | |
return False | |
# Check boundaries | |
for cell in occupied_cells: | |
if not (0 <= cell[0] < self.width and 0 <= cell[1] < self.height): | |
return False | |
return True | |
def get_vehicle_cells(self, vehicle_info, position): | |
length = vehicle_info["length"] | |
width = vehicle_info["width"] | |
x = position.x | |
y = position.y | |
direction = position.direction | |
cells = [] | |
if direction == 'NORTH': | |
for dx in range(width): | |
for dy in range(length): | |
cells.append((x + dx, y - dy)) | |
elif direction == 'SOUTH': | |
for dx in range(width): | |
for dy in range(length): | |
cells.append((x + dx, y + dy)) | |
elif direction == 'EAST': | |
for dx in range(length): | |
for dy in range(width): | |
cells.append((x + dx, y + dy)) | |
elif direction == 'WEST': | |
for dx in range(length): | |
for dy in range(width): | |
cells.append((x - dx, y + dy)) | |
return cells | |
def place_vehicle(self, vehicle_info, position): | |
occupied_cells = self.get_vehicle_cells(vehicle_info, position) | |
for cell in occupied_cells: | |
self.occupied.add(cell) | |
def remove_vehicle(self, vehicle_info, position): | |
occupied_cells = self.get_vehicle_cells(vehicle_info, position) | |
for cell in occupied_cells: | |
if cell in self.occupied: | |
self.occupied.remove(cell) | |
def can_exit_vehicle(self, vehicle_info, position): | |
# Check if vehicle can exit directly from its position without collisions | |
possible_directions = [] | |
if position.x + vehicle_info["length"] <= self.width - 1: | |
possible_directions.append('EAST') | |
if position.y + vehicle_info["length"] <= self.height - 1: | |
possible_directions.append('SOUTH') | |
for exit_point in self.exits: | |
ex, ey = exit_point | |
if position.direction == 'EAST' and ex == self.width - 1: | |
return True | |
if position.direction == 'SOUTH' and ey == self.height - 1: | |
return True | |
return False | |
def direction_to_delta(self, direction): | |
if direction == 'NORTH': | |
return (0, -1) | |
elif direction == 'SOUTH': | |
return (0, 1) | |
elif direction == 'EAST': | |
return (1, 0) | |
elif direction == 'WEST': | |
return (-1, 0) | |
class Position: | |
def __init__(self, x, y, direction): | |
self.x = x | |
self.y = y | |
self.direction = direction |