-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathrobot_movements.py
More file actions
50 lines (41 loc) · 1.7 KB
/
robot_movements.py
File metadata and controls
50 lines (41 loc) · 1.7 KB
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
"""
A robot is located at the top-left corner of a 4x4 grid.
The robot can move either up, down, left, or right, but can not visit the same spot twice.
The robot is trying to reach the bottom-right corner of the grid.
Print out the unique number of ways the robot can reach its destination
"""
class RobotMovement:
def __init__(self, height, width):
self.visited = {}
self.height = height
self.width = width
self.count = 0;
for i in range(self.height):
for j in range(self.width):
self.visited[(i,j)] = False
def findPaths(self, position):
if(position == (self.height -1, self.width -1)):
self.count += 1
if (not self.visited[position]):
self.visited[position] = True
for pos in self.availablePositions(position):
self.findPaths(pos)
self.visited[position] = False
def availablePositions(self, startingPoint):
result = []
top = (startingPoint[0] - 1, startingPoint[1])
bottom = (startingPoint[0] + 1, startingPoint[1])
left = (startingPoint[0], startingPoint[1] - 1)
right = (startingPoint[0], startingPoint[1] + 1)
result.append(top)
result.append(bottom)
result.append(left)
result.append(right)
result = [x for x in result if self.isValid(x)]
return result
def isValid(self, position):
valid = position[0] >= 0 and position[0] < self.height and position[1] >= 0 and position[1] < self.width;
return valid
r = RobotMovement(4,4)
r.findPaths((0,0))
print r.count