Created
May 7, 2014 04:21
-
-
Save ACEfanatic02/b400ebcede5546c0f29c to your computer and use it in GitHub Desktop.
Playing with elevator scheduling.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class ElevatorRequest(object): | |
def __init__(self, from_floor, to_floor): | |
self.from_floor = from_floor | |
self.to_floor = to_floor | |
def __cmp__(self, other): | |
return self.from_floor == other.from_floor | |
def __str__(self): | |
return "<ElevatorRequest: From %d to %d>" % (self.from_floor, self.to_floor) | |
class ElevatorCar(object): | |
UP, DOWN = 1, -1 | |
def __init__(self, capacity): | |
self.direction = self.UP | |
self.target_floor = 0 | |
self.current_floor = 0 | |
self.passengers = [] | |
self.capacity = capacity | |
self.request_queue = [] | |
def post_request(self, request): | |
self.request_queue.insert(0, request) | |
def board(self, passenger): | |
self.request_queue.remove(passenger) | |
self.passengers.append(passenger) | |
return passenger.from_floor | |
def get_next_floor(self): | |
passenger_count = len(self.passengers) | |
if passenger_count < self.capacity and len(self.request_queue): | |
if passenger_count == 0: | |
# Empty car, service first request. | |
# return self.request_queue[-1].from_floor | |
return self.board(self.request_queue[-1]) | |
# Find next passenger in the current direction we're heading. | |
# They must: | |
# - be waiting on a floor along our current direction | |
# - be going to a floor along our current direction relative to the from floor. | |
# EX: | |
# Given an elevator on floor 3, going UP: | |
# a passenger on floor 2 will NOT be picked up. | |
# a passenger on floor 5 going to floor 4 will NOT be picked up. | |
# a passenger on floor 4 going to floor 5 WILL be picked up. | |
if self.direction == self.UP: | |
requests_on_route = [p for p in self.request_queue if p.from_floor > self.current_floor] | |
valid_requests = [p for p in requests_on_route if p.to_floor > p.from_floor] | |
if len(valid_requests): | |
next = min([p for p in valid_requests]) | |
return self.board(next) | |
else: | |
requests_on_route = [p for p in self.request_queue if p.from_floor < self.current_floor] | |
valid_requests = [p.from_floor for p in requests_on_route if p.to_floor < p.from_floor] | |
if len(valid_requests): | |
next = max([p for p in valid_requests]) | |
return self.board(next) | |
if passenger_count > 0: | |
# Not picking up passengers | |
# Target the closest requested floor. | |
if self.direction == self.UP: | |
return min(self.passengers).to_floor | |
else: | |
return max(self.passengers).to_floor | |
return 0 # Done, go to lobby | |
def tick(self): | |
next_floor = self.get_next_floor() | |
if next_floor > self.current_floor: | |
self.direction = self.UP | |
elif next_floor < self.current_floor: | |
self.direction = self.DOWN | |
else: | |
pass # No change to direction when stopped. | |
self.target_floor = next_floor | |
# Unload passengers for this floor. | |
self.passengers = [p for p in self.passengers if p.to_floor != car.current_floor] | |
if self.current_floor != self.target_floor: | |
self.current_floor += self.direction | |
if __name__ == '__main__': | |
car = ElevatorCar(5) | |
car.post_request(ElevatorRequest(5, 10)) | |
car.post_request(ElevatorRequest(2, 7)) | |
car.post_request(ElevatorRequest(4, 0)) | |
car.post_request(ElevatorRequest(6, 2)) | |
car.post_request(ElevatorRequest(1, 12)) | |
car.post_request(ElevatorRequest(0, 9)) | |
car.post_request(ElevatorRequest(5, 1)) | |
while len(car.request_queue) or len(car.passengers): | |
def dir_to_str(direction): | |
if direction == ElevatorCar.UP : | |
return "up" | |
else: | |
return "down" | |
print "On floor: %d, targeting: %d, going %s." % ( | |
car.current_floor, car.target_floor, dir_to_str(car.direction)) | |
car.tick() | |
print "%d passengers." % len(car.passengers) | |
print "%d requests waiting." % len(car.request_queue) | |
if len(car.passengers) == 0 and len(car.request_queue): | |
for req in car.request_queue: | |
print req | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment