Programming_Languages_I/BackToAthens/moves.py at main · AntonisAk/Programming_Languages_I · GitHub

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
(" moves.py ")

from collections import deque
import sys

# Parse file
with open(sys.argv[1],'r') as input:
    size = int(input.readline())

    # Initialize and read input
    grid = [[int]*size]*size
    for i in range(0,size):
        grid[i] = list(map(int,input.readline().split()))
    input.close()

visited = [[False for _ in range(size)] for _ in range(size)]
myQueue = deque([])
prev = [[(0,0) for _ in range(size)] for _ in range(size)]
step = [["CC" for _ in range(size)] for _ in range(size)]
solved = False

# Starting node
visited[0][0] = True
myQueue.append((0,0))

# Next moves function
def moves(n):
    x = n[0]
    y = n[1]
    if (x+1) < size and (y+1) < size:
        if grid[x+1][y+1] < grid[x][y]:
            # SE
            if visited[x+1][y+1] == False:
                step[x+1][y+1] = "SE"
                prev[x+1][y+1] = (x,y)
                visited[x+1][y+1] = True
                myQueue.append((x+1,y+1))

    if (y+1) < size:
        if grid[x][y+1] < grid[x][y]:
            # E
            if visited[x][y+1] == False:
                step[x][y+1] = "E"
                prev[x][y+1] = (x,y)
                visited[x][y+1] = True
                myQueue.append((x,y+1))

    if (x+1) < size:
        if grid[x+1][y] < grid[x][y]:
            # S
            if (visited[x+1][y] == False):
                step[x+1][y] = "S"
                prev[x+1][y] = (x,y)
                visited[x+1][y] = True
                myQueue.append((x+1,y))

    if (x-1) >= 0 and (y+1) < size:
        if grid[x-1][y+1] < grid[x][y]:
            # NE
            if visited[x-1][y+1] == False:
                step[x-1][y+1] = "NE"
                prev[x-1][y+1] = (x,y)
                visited[x-1][y+1] = True
                myQueue.append((x-1,y+1))

    if (x+1) < size and (y-1) >= 0:
        if grid[x+1][y-1] < grid[x][y]:
            # SW
            if visited[x+1][y-1] == False:
                step[x+1][y-1] = "SW"
                prev[x+1][y-1] = (x,y)
                visited[x+1][y-1] = True
                myQueue.append((x+1,y-1))

    if (x-1) >= 0:
        if grid[x-1][y] < grid[x][y]:
            # N
            if visited[x-1][y] == False:
                step[x-1][y] = "N"
                prev[x-1][y] = (x,y)
                visited[x-1][y] = True
                myQueue.append((x-1,y))

    if (y-1) >= 0:
        if grid[x][y-1] < grid[x][y]:
            # W
            if visited[x][y-1] == False:
                step[x][y-1] = "W"
                prev[x][y-1] = (x,y)
                visited[x][y-1] = True
                myQueue.append((x,y-1))

    if (x-1) >= 0 and (y-1) >= 0:
        if grid[x-1][y-1] < grid[x][y]:
            # NW
            if visited[x-1][y-1] == False:
                step[x-1][y-1] = "NW"
                prev[x-1][y-1] = (x,y)
                visited[x-1][y-1] = True
                myQueue.append((x-1,y-1))
    return

while len(myQueue) > 0:
    curr = myQueue.popleft()
    if curr == (size-1,size-1):
        solved = True
        break
    else:
        moves(curr)

if solved:
    path = step[curr[0]][curr[1]] + ']'
    curr = prev[curr[0]][curr[1]]
    while curr!=(0,0):
        path = step[curr[0]][curr[1]] + ',' + path
        curr = prev[curr[0]][curr[1]]
    path = '['+ path
    print(path)

else:
    print("IMPOSSIBLE")


print()