Avent of Code - Day 12 - Hill Climbing Algorithm
Advent of Code occurs at Dec 01 to 25 where each day, you will need to solve a puzzle. It is Festival and the problem statement is mostly related to Christmas.
Day 12 - Hill Climbing Algorithm
https://adventofcode.com/2022/day/12
Q1
import sys
from collections import defaultdict, deque
file1 = open(sys.argv[1], "r")
grid = []
while True:
line = file1.readline()
if not line:
break
line = line.strip()
if not line:
continue
grid.append(list(line))
rows = len(grid)
cols = len(grid[0])
start = None
end = None
print(grid)
print(rows, cols)
for r in range(rows):
for c in range(cols):
if grid[r][c] == 'S':
start = (r, c)
grid[r][c] = 'a'
elif grid[r][c] == 'E':
end = (r, c)
grid[r][c] = 'z'
print(start, end)
q = deque([(start[0], start[1], 0)])
seen = set([start])
while q:
r, c, d = q.popleft()
if (r, c) == end:
print(d)
break
for dr, dc in ((1, 0), (0, 1), (-1, 0), (0, -1)):
nr, nc = dr + r, dc + c
if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen:
if ord(grid[nr][nc]) <= 1 + ord(grid[r][c]):
seen.add((nr, nc))
q.append((nr, nc, d + 1))
Q2
import sys
from collections import defaultdict, deque
file1 = open(sys.argv[1], "r")
grid = []
while True:
line = file1.readline()
if not line:
break
line = line.strip()
if not line:
continue
grid.append(list(line))
rows = len(grid)
cols = len(grid[0])
end = None
q = deque()
for r in range(rows):
for c in range(cols):
if grid[r][c] == 'S' or grid[r][c] == 'a':
grid[r][c] = 'a'
q.append((r, c, 0))
elif grid[r][c] == 'E':
end = (r, c)
grid[r][c] = 'z'
seen = set()
while q:
r, c, d = q.popleft()
if (r, c) == end:
print(d)
break
for dr, dc in ((1, 0), (0, 1), (-1, 0), (0, -1)):
nr, nc = dr + r, dc + c
if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen:
if ord(grid[nr][nc]) <= 1 + ord(grid[r][c]):
seen.add((nr, nc))
q.append((nr, nc, d + 1))
Today is about Breadth First Search (BFS), possibly you can do it using Depth First Search or Iterative Deepening Search.
- Day 540 (2022-11-21): Nearest Exit from Entrance in Maze via Breadth First Search Algorithm (BFS) 广度优先搜索算法找迷宫入口最近的出口 Youtube - B站 - 西瓜
- Day 542 (2022-11-28): Nearest Exit from Entrance in Maze via Recursive Depth First Search Algorithm (DFS) 深度优先搜索算法找迷宫入口最近的出口(递归) Youtube - B站 - 西瓜
- Day 543 (2022-12-03): Nearest Exit from Entrance in Maze via Iterative Deepening Search Algorithm (IDS) 迭代加深搜索算法(IDS)找迷宫最近的出口 Youtube - B站 - 西瓜