-
Notifications
You must be signed in to change notification settings - Fork 0
/
ps7All4ProbsOneFile.py
executable file
·297 lines (241 loc) · 8.92 KB
/
ps7All4ProbsOneFile.py
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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
# 6.00x Problem Set 7: Simulating robots
import math
import random
import ps7_visualize
import pylab
# For Python 2.7:
from ps7_verify_movement27 import testRobotMovement
# If you get a "Bad magic number" ImportError, comment out what's above and
# uncomment this line (for Python 2.6):
# from ps7_verify_movement26 import testRobotMovement
# === Provided class Position
class Position(object):
"""
A Position represents a location in a two-dimensional room.
"""
def __init__(self, x, y):
"""
Initializes a position with coordinates (x, y).
"""
self.x = x
self.y = y
def getX(self):
return self.x
def getY(self):
return self.y
def getNewPosition(self, angle, speed):
"""
Computes and returns the new Position after a single clock-tick has
passed, with this object as the current position, and with the
specified angle and speed.
Does NOT test whether the returned position fits inside the room.
angle: float representing angle in degrees, 0 <= angle < 360
speed: positive float representing speed
Returns: a Position object representing the new position.
"""
old_x, old_y = self.getX(), self.getY()
# Compute the change in position
delta_y = speed * math.cos(math.radians(angle))
delta_x = speed * math.sin(math.radians(angle))
# Add that to the existing position
new_x = old_x + delta_x
new_y = old_y + delta_y
#print "new x = " + str(new_x) + " new y " + str(new_y)
#print "floor of x = " + str(math.floor(new_x)) + " floor of y = " + str(math.floor(new_y))
return Position(new_x, new_y)
def __str__(self):
return "(%0.2f, %0.2f)" % (self.x, self.y)
# === Problem 1
class RectangularRoom(object):
"""
A RectangularRoom represents a rectangular region containing clean or dirty
tiles.
A room has a width and a height and contains (width * height) tiles. At any
particular time, each of these tiles is either clean or dirty.
"""
def __init__(self, width, height):
"""
Initializes a rectangular room with the specified width and height.
Initially, no tiles in the room have been cleaned.
width: an integer > 0
height: an integer > 0
"""
self.width = width
self.height = height
self.room = [[False]*height for _ in range(width)]
self.clean = 0
def cleanTileAtPosition(self, pos):
"""
Mark the tile under the position POS as cleaned.
Assumes that POS represents a valid position inside this room.
pos: a Position
"""
x = int(pos.getX())
y = int(pos.getY())
if not self.room[x][y]:
self.clean += 1
self.room[x][y] = True
def isTileCleaned(self, m, n):
"""
Return True if the tile (m, n) has been cleaned.
Assumes that (m, n) represents a valid tile inside the room.
m: an integer
n: an integer
returns: True if (m, n) is cleaned, False otherwise
"""
return self.room[m][n]
def getNumTiles(self):
"""
Return the total number of tiles in the room.
returns: an integer
"""
return self.width * self.height
def getNumCleanedTiles(self):
"""
Return the total number of clean tiles in the room.
returns: an integer
"""
return self.clean
def getRandomPosition(self):
"""
Return a random position inside the room.
returns: a Position object.
"""
x = random.random() * self.width
y = random.random() * self.height
return Position(x, y)
def isPositionInRoom(self, pos):
"""
Return True if pos is inside the room.
pos: a Position object.
returns: True if pos is in the room, False otherwise.
"""
test_x = 0 <= pos.getX() < self.width
test_y = 0 <= pos.getY() < self.height
return test_x and test_y
class Robot(object):
"""
Represents a robot cleaning a particular room.
At all times the robot has a particular position and direction in the room.
The robot also has a fixed speed.
Subclasses of Robot should provide movement strategies by implementing
updatePositionAndClean(), which simulates a single time-step.
"""
def __init__(self, room, speed):
"""
Initializes a Robot with the given speed in the specified room. The
robot initially has a random direction and a random position in the
room. The robot cleans the tile it is on.
room: a RectangularRoom object.
speed: a float (speed > 0)
"""
self.room = room
self.speed = speed
self.direction = int(random.random() * 360)
self.position = room.getRandomPosition()
room.cleanTileAtPosition(self.position)
def getRobotPosition(self):
"""
Return the position of the robot.
returns: a Position object giving the robot's position.
"""
return self.position
def getRobotDirection(self):
"""
Return the direction of the robot.
returns: an integer d giving the direction of the robot as an angle in
degrees, 0 <= d < 360.
"""
return self.direction
def setRobotPosition(self, position):
"""
Set the position of the robot to POSITION.
position: a Position object.
"""
self.position = position
def setRobotDirection(self, direction):
"""
Set the direction of the robot to DIRECTION.
direction: integer representing an angle in degrees
"""
self.direction = direction
def updatePositionAndClean(self):
"""
Simulate the raise passage of a single time-step.
Move the robot to a new position and mark the tile it is on as having
been cleaned.
"""
raise NotImplementedError # don't change this!
# === Problem 2
class StandardRobot(Robot):
"""
A StandardRobot is a Robot with the standard movement strategy.
At each time-step, a StandardRobot attempts to move in its current
direction; when it would hit a wall, it *instead* chooses a new direction
randomly.
"""
def updatePositionAndClean(self):
"""
Simulate the raise passage of a single time-step.
Move the robot to a new position and mark the tile it is on as having
been cleaned.
"""
position = self.position.getNewPosition(self.direction, self.speed)
if self.room.isPositionInRoom(position):
self.setRobotPosition(position)
self.room.cleanTileAtPosition(position)
else:
self.setRobotDirection(int(random.random() * 360))
# === Problem 3
def runSimulation(num_robots, speed, width, height, min_coverage, num_trials,
robot_type):
"""
Runs NUM_TRIALS trials of the simulation and returns the mean number of
time-steps needed to clean the fraction MIN_COVERAGE of the room.
The simulation is run with NUM_ROBOTS robots of type ROBOT_TYPE, each with
speed SPEED, in a room of dimensions WIDTH x HEIGHT.
num_robots: an int (num_robots > 0)
speed: a float (speed > 0)
width: an int (width > 0)
height: an int (height > 0)
min_coverage: a float (0 <= min_coverage <= 1.0)
num_trials: an int (num_trials > 0)
robot_type: class of robot to be instantiated (e.g. StandardRobot or
RandomWalkRobot)
"""
anim = True
steps = 0
for _ in range(num_trials):
robots = []
room = RectangularRoom(width, height)
for _ in range(num_robots):
robots.append(robot_type(room, speed))
total_tiles = float(room.getNumTiles())
if anim:
anim = ps7_visualize.RobotVisualization(num_robots, width, height)
while room.getNumCleanedTiles() / total_tiles < min_coverage:
steps += 1
for r in robots:
if anim:
anim.update(room, robots)
r.updatePositionAndClean()
if anim:
anim.done()
return steps / float(num_trials)
# === Problem 4
class RandomWalkRobot(Robot):
"""
A RandomWalkRobot is a robot with the "random walk" movement strategy: it
chooses a new direction at random at the end of each time-step.
"""
def updatePositionAndClean(self):
"""
Simulate the passage of a single time-step.
Move the robot to a new position and mark the tile it is on as having
been cleaned.
"""
position = self.position.getNewPosition(self.direction, self.speed)
if self.room.isPositionInRoom(position):
self.setRobotPosition(position)
self.room.cleanTileAtPosition(position)
self.setRobotDirection(int(random.random() * 360))