/
main.py
148 lines (114 loc) · 5.11 KB
/
main.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
import sys
if len(sys.argv) != 2:
print("Usage: python3 Alice.py <inputfilename>")
sys.exit()
# Here is how you open a file whose name is given as the first argument
f = open(sys.argv[1])
# Read in size of grid.
grid_size = int(f.readline())
global graph
graph = []
for line in f:
row_nodes = line.split()
graph.append(row_nodes)
global nodes_in_next_layer
nodes_in_next_layer = 0
# Initialize a matrix to keep track of visited nodes with step sizes.
def solve_maze(inputfilename):
nodes_left_in_layer = 1
global nodes_in_next_layer
move_count = 0
curr_path = []
global graph
parents = {}
reached_goal = False
visited = []
for i in range(0, grid_size):
row = []
for j in range(0, grid_size):
row.append([])
visited.append(row)
step_size = 1
start = (4, 2, step_size)
curr_path.append(start)
visited[start[0]][start[1]].append(step_size)
while len(curr_path) > 0:
r = curr_path.pop(0)
if graph[r[0]][r[1]] == "G":
reached_goal = True
break
get_destinations(r, r[2], graph, visited, curr_path, parents)
nodes_left_in_layer = nodes_left_in_layer - 1
if nodes_left_in_layer == 0:
nodes_left_in_layer = nodes_in_next_layer
nodes_in_next_layer = 0
move_count = move_count + 1
if reached_goal:
print(move_count)
final_path = []
curr_node = (r[0],r[1], r[2])
for i in range(0, move_count):
final_path.insert(0, curr_node)
# print(parents[curr_node])
curr_node = parents[curr_node]
final_path.insert(0, start)
directional_path = []
for i in range(0, move_count):
if final_path[i][0] < final_path[i + 1][0] and final_path[i][1] == final_path[i + 1][1]:
directional_path.append(("S", final_path[i + 1][2]))
elif final_path[i][0] > final_path[i + 1][0] and final_path[i][1] == final_path[i + 1][1]:
directional_path.append(("N", final_path[i + 1][2]))
elif final_path[i][0] == final_path[i + 1][0] and final_path[i][1] < final_path[i + 1][1]:
directional_path.append(("E", final_path[i + 1][2]))
elif final_path[i][0] == final_path[i + 1][0] and final_path[i][1] > final_path[i + 1][1]:
directional_path.append(("W", final_path[i + 1][2]))
elif final_path[i][0] < final_path[i + 1][0] and final_path[i][1] < final_path[i + 1][1]:
directional_path.append(("SE", final_path[i + 1][2]))
elif final_path[i][0] < final_path[i + 1][0] and final_path[i][1] > final_path[i + 1][1]:
directional_path.append(("SW", final_path[i + 1][2]))
elif final_path[i][0] > final_path[i + 1][0] and final_path[i][1] < final_path[i + 1][1]:
directional_path.append(("NE", final_path[i + 1][2]))
elif final_path[i][0] > final_path[i + 1][0] and final_path[i][1] > final_path[i + 1][1]:
directional_path.append(("NW", final_path[i + 1][2]))
print(directional_path)
return -1
def get_destinations(node, step_size, graph, visited, curr_path, parents):
global nodes_in_next_layer
directions = graph[node[0]][node[1]].split("-")
if int(directions[0]) == 1:
step_size = step_size + 1
elif int(directions[0]) == 2:
step_size = step_size - 1
for direction in directions[1:]:
if direction == "N":
destination = (node[0] - step_size, node[1], step_size)
elif direction == "S":
destination = (node[0] + step_size, node[1], step_size)
elif direction == "E":
destination = (node[0], node[1] + step_size, step_size)
elif direction == "W":
destination = (node[0], node[1] - step_size, step_size)
elif direction == "NW":
destination = (node[0] - step_size, node[1] - step_size, step_size)
elif direction == "NE":
destination = (node[0] - step_size, node[1] + step_size, step_size)
elif direction == "SW":
destination = (node[0] + step_size, node[1] - step_size, step_size)
elif direction == "SE":
destination = (node[0] + step_size, node[1] + step_size, step_size)
else:
destination = (-1, -1, step_size)
if destination[0] < 0 or destination[0] >= grid_size or destination[1] < 0 or destination[1] >= grid_size:
continue
if step_size in visited[destination[0]][destination[1]]:
continue
curr_path.append(destination)
parents[destination] = node
# print(visited)
visited[destination[0]][destination[1]].append(step_size)
nodes_in_next_layer = nodes_in_next_layer + 1
solve_maze(sys.argv[1])
# Press the green button in the gutter to run the script.
if __name__ == '__main__':
solve_maze(sys.argv[1])
# See PyCharm help at https://www.jetbrains.com/help/pycharm/