Herkese merhabalar. AoC’un 12. günüyle beraberiz. Gitgide zorlaşan bulmacalarda bugün en kısa yolu bulmamızı isteyen bir algoritma tasarlamamızı istiyor. Hikayemizin başlığı Tepe Tırmanma Algoritması ve hikaye şu şekilde başlıyor:
El cihazınızı kullanarak Elflerle iletişim kurmaya çalışıyorsunuz, ancak takip ettiğiniz nehir iyi bir sinyal almak için çok alçak olmalı.
Cihazdan çevredeki alanın yükseklik haritasını istiyorsunuz (bulmaca girdiniz). Yükseklik haritası, yerel alanı yukarıdan bir ızgaraya bölünmüş olarak gösterir; ızgaranın her karesinin yüksekliği tek bir küçük harfle verilir, burada a en düşük yüksekliktir, b bir sonraki en düşük yüksekliktir ve bu şekilde en yüksek yükseklik olan z’ye kadar devam eder.
Ayrıca yükseklik haritasında mevcut konumunuz (S) ve en iyi sinyali alması gereken konum (E) için işaretler bulunur. Mevcut konumunuz (S) a yüksekliğine ve en iyi sinyali alması gereken konum (E) z yüksekliğine sahiptir.
E’ye ulaşmak istiyorsunuz, ancak enerjiden tasarruf etmek için bunu mümkün olduğunca az adımda yapmalısınız. Her adımda tam olarak bir kare yukarı, aşağı, sola veya sağa hareket edebilirsiniz. Tırmanma ekipmanlarınızı çıkarmanıza gerek kalmaması için, hedef karenin yüksekliği mevcut karenizin yüksekliğinden en fazla bir daha yüksek olabilir; yani, mevcut yüksekliğiniz m ise, n yüksekliğine adım atabilirsiniz, ancak o yüksekliğine adım atamazsınız.
https://adventofcode.com/2022/day/12
Örneğin:
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
Burada sol üst köşeden başlıyorsunuz; hedefiniz ortaya yakın. Aşağı veya sağa doğru hareket ederek başlayabilirsiniz, ancak sonunda alttaki e’ye doğru gitmeniz gerekecek. Oradan hedefe doğru spiral çizebilirsiniz:
v..v<<<<
>v.vv<<^
.>vv>E^^
..v>>>^^
..>>>>>^
Yukarıdaki diyagramda semboller, yolun her bir kareden yukarı (^), aşağı (v), sola (<) veya sağa (>) hareket ederek çıktığını gösterir. En iyi sinyali alması gereken konum hala E’dir ve . ziyaret edilmemiş kareleri gösterir.
Bu yol, hedefe mümkün olan en az sayıda, 31 adımda ulaşır.
Mevcut konumunuzdan en iyi sinyali alması gereken konuma gitmek için gereken en az adım nedir?
Hayli bir zaman harcadıktan sonra maalesef bu probleme bir sonuç üretemedim. Bu sebeple bazı youtube kanalları üzerinden ilgili bulmaca hakkında videolar izledim ve sonuç olarak problemin çözümü olarak aşağıdaki kodu yazdım:
from string import ascii_lowercase
from heapq import heappop, heappush
with open("heightmap.txt") as fin:
lines = fin.read().strip().split()
grid = [list(line) for line in lines]
n = len(grid)
m = len(grid[0])
for i in range(n):
for j in range(m):
char = grid[i][j]
if char == "S":
start = i, j
if char == "E":
end = i, j
def height(s):
if s in ascii_lowercase:
return ascii_lowercase.index(s)
if s == "S":
return 0
if s == "E":
return 25
# Determine neighbors
def neighbors(i, j):
for di, dj in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
ii = i + di
jj = j + dj
if not (0 <= ii < n and 0 <= jj < m):
continue
if height(grid[ii][jj]) <= height(grid[i][j]) + 1:
yield ii, jj
# Dijkstra's
visited = [[False] * m for _ in range(n)]
heap = [(0, start[0], start[1])]
while True:
steps, i, j = heappop(heap)
if visited[i][j]:
continue
visited[i][j] = True
if (i, j) == end:
print(steps)
break
for ii, jj in neighbors(i, j):
heappush(heap, (steps + 1, ii, jj))
Buradaki çözüm yaklaşımı şu şekilde:
Sonuç olarak bu kod, ‘S’ ile işaretlenmiş bir başlangıç noktasından ‘E’ ile işaretlenmiş bir bitiş noktasına en kısa yoldan gitmek için bir yol bulmaya çalışır. Öncelikle, ‘S’ ve ‘E’ karakterleri bulunur ve ‘start’ ve ‘end’ değişkenlerine atanır. Bu değişkenler, başlangıç ve bitiş noktalarının koordinatlarını içerir. height’ adlı bir fonksiyon tanımlanır. Bu fonksiyon bir karakter alır ve bunun küçük harflerden birinin sırasını (Eğer karakter bir küçük harf değilse, 0 döndürür), ‘S’ karakterini (0 döndürür), veya ‘E’ karakterini (25 döndürür) belirtir. Daha sonra komşu hücreler bulunur. Son olarak en kısa yol Dijkstra's algoritması kullanılarak bulunur.
İkinci Bölüm:
Tepeye doğru yürürken, Elflerin burayı bir yürüyüş parkuruna dönüştürmek isteyeceğinden şüpheleniyorsunuz. Yine de başlangıç pek manzaralı değil; belki daha iyi bir başlangıç noktası bulabilirsiniz.
Yürüyüş sırasında egzersizi en üst düzeye çıkarmak için patika mümkün olduğunca alçaktan başlamalıdır: a yüksekliği. Hedef hala E işaretli karedir. Ancak patika yine de doğrudan olmalı, hedefe ulaşmak için en az adımı atmalıdır. Bu nedenle, a yüksekliğindeki herhangi bir kareden E işaretli kareye giden en kısa yolu bulmanız gerekir.
Yine yukarıdaki örneği ele alalım:
Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi
Şimdi, başlangıç pozisyonu için altı seçenek var (a ile işaretlenmiş beş kare, artı a yüksekliğinde sayılan S ile işaretlenmiş kare). Sol alttaki kareden başlarsanız hedefe en hızlı şekilde ulaşabilirsiniz:
...v<<<<
...vv<<^
...v>E^^
.>v>>>^^
>^>>>>>^
Bu yol, hedefe mümkün olan en az sayıda adımla, sadece 29 adımda ulaşır.
Yüksekliği a olan herhangi bir kareden başlayarak en iyi sinyali alması gereken konuma gitmek için gereken en az adım nedir?
Bu bulmaca için yazılan Python kodu aşağıdaki gibidir:
from string import ascii_lowercase
from heapq import heappop, heappush
with open("heightmap.txt") as fin:
lines = fin.read().strip().split()
grid = [list(line) for line in lines]
n = len(grid)
m = len(grid[0])
for i in range(n):
for j in range(m):
char = grid[i][j]
if char == "S":
start = i, j
if char == "E":
end = i, j
def height(s):
if s in ascii_lowercase:
return ascii_lowercase.index(s)
if s == "S":
return 0
if s == "E":
return 25
# Determine neighbors
def neighbors(i, j):
for di, dj in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
ii = i + di
jj = j + dj
if not (0 <= ii < n and 0 <= jj < m):
continue
if height(grid[ii][jj]) >= height(grid[i][j]) - 1:
yield ii, jj
# Dijkstra's
visited = [[False] * m for _ in range(n)]
heap = [(0, end[0], end[1])]
while True:
steps, i, j = heappop(heap)
if visited[i][j]:
continue
visited[i][j] = True
if height(grid[i][j]) == 0:
print(steps)
break
for ii, jj in neighbors(i, j):
heappush(heap, (steps + 1, ii, jj))
Bu çözüm için kodumuz çok çok az değişti. Belki de fark etmişsinizdir, şimdi en sondan yani E’den başlayıp S’ye doğru geldik.
AoC’un onuncu günü de bu kadardı. Vakit ayırıp okuduğunuz için teşekkür ederim. Eğer yazıyı beğendiyseniz, kodlamaya meraklı arkadaşlarınızla paylaşmayı unutmayın
Herhangi bir sorunuz olursa veya benimle iletişim kurmak isterseniz tüm sosyal medya hesaplarıma bu linke tıklayarak ulaşabilirsiniz. Ayrıca tüm çözümlerimi görebilmeniz için bir github reposu açtım. Bu repoya da bu linkten ulaşabilirsiniz.
Turhan Can Kargın 