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
if __name__ == "__main__": | |
print("\nBFS") | |
print("\nshortest depth: ", bfs()) | |
print("\nDFS") | |
print("\nshortest depth: ", dfs()) | |
print("\nIDDFS", end="") | |
print("\nshortest depth: ", iddfs()) |
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
def iddfs(): | |
root = get_root() | |
res = float("inf") | |
def iddfs_search(node, depth, limit): | |
if depth <= limit and node is not None: | |
val = node.val | |
if val >= 10: | |
nonlocal res | |
res = min(res, depth) |
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
def dfs(): | |
root = get_root() | |
res = float("inf") | |
def dfs_search(node, depth): | |
if node is not None: | |
val = node.val | |
if val >= 10: | |
nonlocal res | |
res = min(res, depth) |
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
def bfs(): | |
root = get_root() | |
queue = collections.deque() | |
queue.appendleft((root, 0)) | |
res = -1 | |
while queue: | |
node, depth = queue.pop() | |
if node.val >= 10: | |
res = depth |
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
class Node: | |
def __init__(self, val=None): | |
self.val = val | |
self.left = None | |
self.right = None | |
def get_root(): | |
values = iter([1, 6, 4, 7, None, None, 9, 8, None, None, | |
10, None, None, 5, None, None, 2, 3, None, None, 11, None, None]) |
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
def path_search(row_len, col_len): | |
dp = [[0 for _ in range(col_len)] for _ in range(row_len)] | |
for r in reversed(range(row_len)): | |
for c in reversed(range(col_len)): | |
if r == row_len-1 and c == col_len-1: | |
dp[r][c] = 1 | |
else: | |
if r+1 < row_len: | |
dp[r][c] += dp[r+1][c] | |
if c+1 < col_len: |
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
import heapq | |
def dijkstra(grid): | |
seen = set() | |
heap = [] | |
dist = grid[0][0] | |
heapq.heappush(heap, (dist, 0, 0)) | |
row_len = len(grid) | |
col_len = len(grid[0]) | |
min_dist = float('inf') |
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
def a_star(grid): | |
def get_heuristic(current, target): | |
return max(abs(current[0] - target[0]), abs(current[1] - target[1])) | |
if grid[0][0] == 1 or grid[-1][-1] == 1: | |
return -1 | |
n = len(grid) | |
target = (n - 1, n - 1) | |
heap = [] |
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
def get_nei(x, y): | |
return [(x + 1, y), (x - 1, y), (x + 1, y - 1), (x - 1, y - 1), (x + 1, y + 1), (x - 1, y + 1), (x, y + 1), | |
(x, y - 1)] |
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
def dijkstra(grid): | |
if grid[0][0] == 1 or grid[-1][-1] == 1: | |
return -1 | |
n = len(grid) | |
heap = [] | |
seen = set() | |
heapq.heappush(heap, (1, 1, 0, 0)) | |
cache = {(0, 0): 1} | |
while heap: |
NewerOlder