Avent of Code - Day 12 - Hill Climbing Algorithm
Tags: adventofcode, programming, hillclimbing, algorithms
Published: 2022-12-12 20:13:33

[Advent of Code](https://adventofcode.com/) 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

![image.png](https://cdn.steemitimages.com/DQmQMZ5n5P9JCy6z7woDQCy2WPWLxqbg72pu7vDyttuBNYD/image.png)

### Q1
```python
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
```python
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)](https://helloacm.com/teaching-kids-programming-nearest-exit-from-entrance-in-maze-via-breadth-first-search-algorithm/) 广度优先搜索算法找迷宫入口最近的出口 [Youtube](https://youtu.be/mJD_8NFaT1A) - [B站](https://www.bilibili.com/video/BV14G4y157Yd/)  - [西瓜](https://www.ixigua.com/7170087898337772043) 
- Day 542 (2022-11-28): [Nearest Exit from Entrance in Maze via Recursive Depth First Search Algorithm (DFS)](https://helloacm.com/teaching-kids-programming-nearest-exit-from-entrance-in-maze-via-depth-first-search-algorithm/) 深度优先搜索算法找迷宫入口最近的出口(递归) [Youtube](https://youtu.be/fZnSWurPn24) - [B站](https://www.bilibili.com/video/BV1c14y1J7hp/)  - [西瓜](https://www.ixigua.com/7172696384355697204) 
- Day 543 (2022-12-03): [Nearest Exit from Entrance in Maze via Iterative Deepening Search Algorithm (IDS)](https://helloacm.com/teaching-kids-programming-nearest-exit-from-entrance-in-maze-via-iterative-deepening-search-algorithm-ids/) 迭代加深搜索算法(IDS)找迷宫最近的出口 [Youtube](https://youtu.be/JmtZdwv-Oe8) - [B站](https://www.bilibili.com/video/BV1a14y1K77j/)  - [西瓜](https://www.ixigua.com/7174788238082015802) 

<hr/>

### [Steem](https://steemyy.com) to the Moon!