Created
August 31, 2024 10:01
-
-
Save justagist/6b418e93c7d7684925957f4b6327e572 to your computer and use it in GitHub Desktop.
Implementing depth-first and breadth-first search for a 2D grid in python.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from typing import List, Tuple, Dict | |
| def find_start(grid: List[List[str]], start_val="S") -> Tuple[int, int]: | |
| for i in range(len(grid)): | |
| for j in range(len(grid[i])): | |
| if grid[i][j] == start_val: | |
| return (i, j) | |
| raise ValueError(f"No start val {start_val} found in grid.") | |
| def make_tree(grid: List[List[str]]) -> Dict[Tuple[int, int], List[Tuple[int, int]]]: | |
| tree = {} | |
| for i in range(len(grid)): | |
| for j in range(len(grid[i])): | |
| tree[(i, j)] = [] | |
| # Check Up | |
| if i < len(grid) - 1 and grid[i + 1][j] not in ["O", "S"]: | |
| tree[(i, j)].append((i + 1, j)) | |
| # Check Down | |
| if i > 0 and grid[i - 1][j] not in ["O", "S"]: | |
| # making sure not to add the node that we just came from | |
| if (i, j) not in tree[(i - 1, j)]: | |
| tree[(i, j)].append((i - 1, j)) | |
| # Check Right | |
| if j < len(grid[i]) - 1 and grid[i][j + 1] not in ["O", "S"]: | |
| tree[(i, j)].append((i, j + 1)) | |
| # Check Left | |
| if j > 0 and grid[i][j - 1] not in ["O", "S"]: | |
| # making sure not to add the node that we just came from | |
| if (i, j) not in tree[(i, j - 1)]: | |
| tree[(i, j)].append((i, j - 1)) | |
| return tree | |
| def find_shortest_path_depth_first( | |
| grid: List[List[str]], | |
| start_pos: Tuple[int, int] | None = None, | |
| end_val: str = "X", | |
| ) -> List[Tuple[int, int]]: | |
| if start_pos is None: | |
| start_pos = find_start(grid=grid) | |
| tree = make_tree(grid=grid) | |
| visited = set() # Keep track of visited nodes | |
| def dfs(current_pos, path): | |
| if current_pos in visited: # Base case: Cycle detected | |
| return None | |
| visited.add(current_pos) | |
| path.append(current_pos) | |
| if grid[current_pos[0]][current_pos[1]] == end_val: | |
| return path # Found the target | |
| for next_pos in tree[current_pos]: | |
| result = dfs(next_pos, path.copy()) # Explore recursively | |
| if result is not None: # Path found! | |
| return result | |
| return None # No path found from this point | |
| return dfs(start_pos, []) or [] # Start the DFS from the start position | |
| def find_shortest_path_breadth_first( | |
| grid: List[List[str]], | |
| start_pos: Tuple[int, int] | None = None, | |
| end_val: str = "X", | |
| ) -> List[Tuple[int, int]]: | |
| if start_pos is None: | |
| start_pos = find_start(grid=grid) | |
| tree = make_tree(grid=grid) | |
| queue = [(start_pos, [start_pos])] # Store (position, path) in the queue | |
| visited = set() | |
| while queue: | |
| (current_pos, path) = queue.pop(0) | |
| if current_pos not in visited: | |
| visited.add(current_pos) | |
| if grid[current_pos[0]][current_pos[1]] == end_val: | |
| return path # Return the path when the target is found | |
| for next_pos in tree[current_pos]: | |
| if next_pos not in visited: | |
| # Add next position and updated path | |
| queue.append((next_pos, path + [next_pos])) | |
| return [] # No path found | |
| if __name__ == "__main__": | |
| grid1 = [ | |
| ["S", ".", ".", "O", ".", ".", ".", "."], | |
| [".", "O", ".", ".", ".", "O", ".", "O"], | |
| [".", ".", ".", "O", ".", ".", ".", "."], | |
| [".", "O", "O", ".", ".", "O", ".", "X"], | |
| [".", ".", ".", ".", ".", ".", "O", "."], | |
| ] | |
| print( | |
| f"breadth first {str(find_shortest_path_breadth_first(grid=grid1))}; {str(len(find_shortest_path_breadth_first(grid=grid1)))}" | |
| ) | |
| print( | |
| f"depth first {str(find_shortest_path_depth_first(grid=grid1))}; {str(len(find_shortest_path_depth_first(grid=grid1)))}" | |
| ) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment