Avent of Code - Day 12 - Hill Climbing Algorithm

in adventofcode •  2 years ago 

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

image.png

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.


Steem to the Moon!

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE BLURT!