BitSquad---CodeArena/Q5.py at main · Jaybro-git/BitSquad---CodeArena · 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
from collections import deque
from copy import deepcopy

def findStartAndTerminal(grid):
    s=(0,0)
    t=(0,0)
    for i in range(5):
        for j in range(5):
            if grid[i][j] == 'S':
                s = (i, j)
            elif grid[i][j] == 'T':
                t = (i, j)
    return s,t

def findBridges(grid):
    B=[]
    for i in range(5):
        for j in range(5):
            if grid[i][j] == 'B':
                B.append((i,j))
    return B

def rotate_bridges(grid, bridges, step):
    if step % 2 != 0 or not bridges:
        return grid, bridges
    new_grid = deepcopy(grid)

    #Assumption
    #Bridges will travel to the nearest outer boundary position first
    #Then the bridges will rotate clockwise along the boundary
    #While rotating, we skip the start and terminal states but overlaps the walls
    if step == 2:
        mapping = {(1,1):(0,1), (1,3):(0,3), (3,3):(3,4)}

        new_positions=[]

        for b in bridges:
            new_grid[b[0]][b[1]] = '.'

        for b in bridges:
            next_pos = mapping.get(b,b)
            new_positions.append(next_pos)
            new_grid[next_pos[0]][next_pos[1]] = 'B'

        return new_grid, new_positions

    else:
        rotation_map = {(0,0):(0,1),(0,1):(0,2),(0,2):(0,3),(0,3):(0,4),(0,4):(1,4),
                    (1,4):(2,4),(2,4):(3,4),(3,4):(4,3),
                    (4,3):(4,2),(4,2):(4,1),(4,1):(4,0),(4,0):(3,0),
                    (3,0):(2,0),(2,0):(1,0),(1,0):(0,1)}


        new_positions=[]

        for b in bridges:
            new_grid[b[0]][b[1]] = '.'

        for b in bridges:
            next_pos = rotation_map.get(b,b)
            new_positions.append(next_pos)
            new_grid[next_pos[0]][next_pos[1]] = 'B'

        return new_grid, new_positions

def is_valid_move(grid, pos):
    i,j = pos
    if 0<=i<5 and 0<=j<5:
        return grid[i][j] != '#'
    return False

def get_neighbors(pos):
    i,j = pos
    return [(i-1, j),(i+1, j),(i, j-1),(i, j+1)]

def grid_to_string(grid):
    return ''.join(''.join(row) for row in grid)

def findShortestPath(grid):
    start, terminal = findStartAndTerminal(grid)
    bridges = findBridges(grid)

    queue = deque([(start, 0, grid, bridges, [start])])
    visited = set()

    while queue:
        pos, step, current_grid, current_bridges, path = queue.popleft()

        #Ending state found
        if pos == terminal:
            return step, path

        next_grid, next_bridges = rotate_bridges(current_grid, current_bridges, step + 1)

        #Getting the possible and valid moves
        for next_pos in get_neighbors(pos):
            if is_valid_move(next_grid, next_pos):

                #For visited state
                state = (next_pos, (step+1)%2, grid_to_string(next_grid))

                if state not in visited:
                    visited.add(state)
                    new_path = path + [next_pos]
                    queue.append((next_pos, step + 1, next_grid, next_bridges, new_path))

    return -1, [] #Because no paths found


grid = [list("S.#.."),list(".B.B."),list("..#.."),list("...B."),list("....T")]
steps, path = findShortestPath(grid)
if steps == -1:
    print("No path found")
else:
    print(f"Shortest Path Length: {steps}")
    print("Path:")
    for i,j in path:
        print(f"({i},{j})")