algo_final_assignment's Introduction

Algo_final_assignment: Maze Solver

Solution should be sum of coins collected on the way out of maze.

S : start point , G : end point , X : wall

[INPUT]

maze text file

[OUTPUT]

LEAST coins collected

[My Solution]

7X7 maze
Solution is 6+1+3+8+4+6+4+7+3+0+5 == 47
11X11 maze
Solution is 6+8+6+2+4+2+3+3+9+9+0+8+3+6+9+5+2+5+1+4+1+7+0
+7+0+2+8+1+0+1+0+9+6+5+2+3+2+8+7+7+3+2+1+5+9 == 191
31X31 maze
1616
101X101 maze
2480

def bfs(x,y):
    # deque library used for implementing queue
    queue = deque()
    queue.append((x,y))

    while queue: # until queue is empty
        x,y = queue.popleft()

        for i in range(4): # check the location in 4 directions from the current location
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >=len(arr) or ny >= len(arr[0]): #outsize of maze
                continue
            if arr[nx][ny] == 'X': # walls
                continue
            if not visited[nx][ny]: # record shortest path only on first visit
                if arr[nx][ny] == 'G': # if 'G', return the shortest path
                    return arr[x][y]
                else: 
                    arr[nx][ny] = str(int(arr[x][y]) + int(arr[nx][ny])) if arr[x][y] != 'S' else arr[nx][ny] 
                    queue.append((nx,ny))
        
        visited[x][y] = True

[TIME & SPACE complexity]

time
bfs-queue(deque library)
This BFS code uses the visited list variable to visit only nodes that have not been visited before.

=> O(N)
space
f:TextIOWrapper
arr:list -> n^2
line:str
visited:list[list[bool]] -> n^2
i:int
sx,sy:int
dx,dy:list[int]
x,y:int
queue:deque -> n
nx,ny:int

=> O(n^2)