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
169
170
171
172
173
174
175
|
#!/usr/bin/env python3
import copy
from enum import Enum
class Elevator:
def __init__(self, e_id, floor, goal):
self.id = e_id
self.floor = floor
self.goal = goal
self.pickup_direction = None # the direction we're handling pickup requests for
self.dropoffs = []
def direction(self):
' the direction the elevator is currently moving in '
if self.goal is None:
return None
if self.goal > self.floor:
return Direction.UP
else:
return Direction.DOWN
def dropoff(self, floor):
if floor in self.dropoffs:
assert self.goal is not None
return
assert floor != self.floor
assert self.pickup_direction is None
if self.goal is None:
self.goal = floor
self.dropoffs.append(floor)
else:
direction = self.direction()
# TODO: handle opposite direction dropoffs
if direction == Direction.UP:
if floor > self.goal:
self.goal = floor
self.dropoffs.append(floor)
self.dropoffs.sort()
elif direction == Direction.DOWN:
if floor < self.goal:
self.goal = floor
self.dropoffs.append(floor)
self.dropoffs.sort(reverse=True)
def estimate_pickup_time(self, floor, direction):
# while dropping off, can handle requests in same elevator dir in between current and goal
# while picking up, can handle requests in same dir as request dir
# when requested floor is in dir of elevator
our_dir = self.direction()
if our_dir is None:
return abs(floor - self.floor)
if self.dropoffs: # we are moving and have dropoffs
if our_dir == Direction.UP:
if self.floor <= floor and direction == our_dir:
return floor - self.floor
else:
to_goal = self.goal - self.floor
to_request = abs(self.goal - floor)
return to_goal + to_request
else:
if self.floor >= floor and direction == our_dir:
return self.floor - floor
else:
to_goal = self.floor - self.goal
to_request = abs(self.goal - floor)
return to_goal + to_request
else: # we are moving to pick up a request
assert self.pickup_direction is not None
if our_dir == Direction.UP:
if self.floor <= floor <= self.goal and direction == self.pickup_direction:
return floor - self.floor
else:
return float('inf')
else:
if self.floor >= floor >= self.goal and direction == self.pickup_direction:
return self.floor - floor
else:
return float('inf')
def __repr__(self):
attrs = ', '.join('%s=%s' % t for t in self.__dict__.items())
return 'Elevator(%s)' % attrs
class Direction(Enum):
UP = 1
DOWN = 2
class ElevatorControlSystem:
def __init__(self, num_elevators):
self.elevators = {i: Elevator(i, 1, None) for i in range(num_elevators)}
self.pickup_requests = []
def pickup(self, floor, direction):
self.pickup_requests.append((floor, direction))
def dropoff(self, elevator_id, floor):
self.elevators[elevator_id].dropoff(floor)
def step(self):
# serve pickup requests
for floor, direction in copy.copy(self.pickup_requests):
min_time = float('inf')
min_elevator = None
for elevator in self.elevators.values():
time = elevator.estimate_pickup_time(floor, direction)
if time < min_time:
min_time = time
min_elevator = elevator
if min_elevator:
# only handle the request now if the min_elevator is right here or doing nothing. if
# it's moving, min_time should improve by at least 1 per step. handle this request
# later (in case some other elevator finishes a dropoff and can pickup sooner)
if min_time == 0:
assert min_elevator.floor == floor
self.pickup_requests.remove((floor, direction))
elif min_elevator.goal is None:
min_elevator.goal = floor
min_elevator.pickup_direction = direction
self.pickup_requests.remove((floor, direction))
# move elevators to requested floors
for elevator in self.elevators.values():
if elevator.goal is not None:
if elevator.goal > elevator.floor:
elevator.floor += 1
elif elevator.goal < elevator.floor:
elevator.floor -= 1
# check dropoffs and goal after moving
if elevator.dropoffs and elevator.dropoffs[0] == elevator.floor:
elevator.dropoffs = elevator.dropoffs[1:]
if elevator.goal == elevator.floor:
elevator.goal = elevator.pickup_direction = None
if __name__ == '__main__':
ecs = ElevatorControlSystem(2)
print(' '*4, ecs.elevators)
print('requesting pickup on floor 2 down')
ecs.pickup(2, Direction.DOWN)
ecs.step()
print(' '*4, ecs.elevators)
print('requesting dropoff on floor 1 and pickup on floor 1 up')
ecs.dropoff(0, 1)
ecs.pickup(1, Direction.UP)
ecs.step()
print(' '*4, ecs.elevators)
print('requesting dropoff on floor 5 and 3')
ecs.dropoff(1, 5)
ecs.dropoff(1, 3)
ecs.step()
print(' '*4, ecs.elevators)
print('requesting pickup on floor 3 up')
ecs.pickup(3, Direction.UP)
ecs.step()
print(' '*4, ecs.elevators)
print('requesting pickup on floor 5 down')
ecs.pickup(5, Direction.DOWN)
ecs.step()
print(' '*8, ecs.pickup_requests)
print(' '*4, ecs.elevators)
ecs.step()
print(' '*8, ecs.pickup_requests)
print(' '*4, ecs.elevators)
ecs.step()
print(' '*8, ecs.pickup_requests)
print(' '*4, ecs.elevators)
|
