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站 - 西瓜

---

Steem to the Moon!