Izgara Gezinmesi

Bu konunun yedi kalıbı da tek boyutlu veriyle çalıştı: bir dizi, bir akış, bir ardıl zinciri. Son kalıp veriyi iki boyutta ele alır. Bir ızgarada dolu hücreler vardır ve soru şudur: birbirine bağlı kaç hücre kümesi var.

Izgara aslında yeni bir yapı değildir. Her dolu hücre bir düğüm, her komşu hücre çifti bir kenardır; sorulan şey bağlı bileşen sayısıdır ve yordam Veri Yapıları kursunda kuruldu. Enine ve derine aramanın kendisi, ziyaret işaretlemesinin neden zorunlu olduğu ve $O(V + E)$ maliyeti orada ölçüldü; burada tekrarlanmaz, doğrudan kullanılır.

Kalıbın eklediği şey modellemedir ve ön koşulu da orada durur: komşuluğun ne demek olduğu. Bu ders iki komşuluk tanımının aynı ızgarada kaç farklı yanıt ürettiğini sayar.

Problem, Kâhin ve Kalıp

Kâhin hiçbir gezinme yapmaz. Bütün dolu hücre çiftlerini tarar, bitişik olanları aynı gruba alır ve hiçbir birleşme kalmayana kadar yineler. Kalıp her ziyaret edilmemiş dolu hücreden bir enine arama başlatır ve her arama bir bileşen sayar.

PK56. Dağarcık 40 ızgaradır; her ızgara 8×8’dir ve her hücre 100’de 30 olasılıkla doludur. Tohum 20260218. PK57. İki komşuluk tanımı ölçülür: dört komşuluk (yalnız kenardaş hücreler) ve sekiz komşuluk (köşedeş hücreler de dahil). PK58. Kâhin ve kalıp ayrı ayrı komşuluk tanımıyla çalıştırılır; dört bileşim de ölçülür. Böylece ayrılmanın kalıptan mı tanım farkından mı geldiği görülür. PK59. Ziyaret işaretlemesi kuyruğa eklerken yapılır; bu, enine arama dersinde kurulan kuraldır ve burada gerekçesi tekrarlanmaz.

from collections import deque

TOHUM, BOY, DAGARCIK = 20260218, 8, 40


def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


def izgara_dagarcik(tohum=TOHUM, n=DAGARCIK, boy=BOY):
    r = uretec(tohum)
    return [{"no": i + 1,
             "izgara": [[1 if r(101) < 30 else 0 for _ in range(boy)]
                        for _ in range(boy)]}
            for i in range(n)]


class Sayac:
    def __init__(self):
        self.adim = 0

    def say(self):
        self.adim += 1


def bitisik(a, b, komsuluk):
    di, dj = abs(a[0] - b[0]), abs(a[1] - b[1])
    return di + dj == 1 if komsuluk == 4 else max(di, dj) == 1 and (di or dj)


def kahin_bilesen(izgara, komsuluk, s):
    """Butun hucre ciftlerini tarar, bitisik olanlari ayni gruba alir, degisiklik
    bitene kadar yineler. Her zaman dogru, her zaman pahali."""
    hucre = [(i, j) for i, satir in enumerate(izgara)
             for j, v in enumerate(satir) if v]
    grup = {h: i for i, h in enumerate(hucre)}
    degisti = True
    while degisti:
        degisti = False
        for a in range(len(hucre)):
            for b in range(a + 1, len(hucre)):
                s.say()
                if bitisik(hucre[a], hucre[b], komsuluk) and \
                        grup[hucre[a]] != grup[hucre[b]]:
                    eski, yeni = grup[hucre[b]], grup[hucre[a]]
                    for h in hucre:
                        if grup[h] == eski:
                            grup[h] = yeni
                    degisti = True
    return len(set(grup.values()))


YON4 = ((-1, 0), (1, 0), (0, -1), (0, 1))
YON8 = YON4 + ((-1, -1), (-1, 1), (1, -1), (1, 1))


def kalip_enine(izgara, komsuluk, s):
    """Veri Yapilari kursunun enine aramasi dogrudan kullanilir: isaretleme
    kuyruga EKLERKEN yapilir."""
    yon = YON4 if komsuluk == 4 else YON8
    n, m = len(izgara), len(izgara[0])
    ziyaret, bilesen, en_genis = set(), 0, 0
    for i in range(n):
        for j in range(m):
            if not izgara[i][j] or (i, j) in ziyaret:
                continue
            bilesen += 1
            ziyaret.add((i, j))
            kuyruk = deque([(i, j)])
            while kuyruk:
                en_genis = max(en_genis, len(kuyruk))
                x, y = kuyruk.popleft()
                s.say()
                for dx, dy in yon:
                    a, b = x + dx, y + dy
                    if 0 <= a < n and 0 <= b < m and izgara[a][b] \
                            and (a, b) not in ziyaret:
                        ziyaret.add((a, b))
                        kuyruk.append((a, b))
    return bilesen, en_genis


K = izgara_dagarcik()
dolu = sum(sum(sum(s) for s in k["izgara"]) for k in K)
print("dagarcik:", len(K), "izgara x", BOY, "x", BOY, "| dolu hucre:", dolu,
      "| ortalama", round(dolu / len(K), 2))
print("kalip komsulugu  kahin komsulugu  ayrilan/40  kalip   kahin    oran")
for kk in (4, 8):
    for hk in (4, 8):
        ayrilan, ak, ah = 0, 0, 0
        for kayit in K:
            s1, s2 = Sayac(), Sayac()
            a, _ = kalip_enine(kayit["izgara"], kk, s1)
            b = kahin_bilesen(kayit["izgara"], hk, s2)
            ak, ah = ak + s1.adim, ah + s2.adim
            ayrilan += (a != b)
        print(f"{kk:15d}  {hk:15d}  {ayrilan:10d}  {ak:5d}  {ah:6d}"
              f"  {ah / ak:6.1f}")

dagarcik: 40 izgara x 8 x 8 | dolu hucre: 723 | ortalama 18.07
kalip komsulugu  kahin komsulugu  ayrilan/40  kalip   kahin    oran
              4                4           0    723   12768    17.7
              4                8          38    723   12834    17.8
              8                4          38    723   12768    17.7
              8                8           0    723   12834    17.8

Köşegen satırlar sıfır, diğer ikisi 38. Kalıp, kâhinle aynı komşuluk tanımını kullandığında 40 ızgaranın 40’ında aynı yanıtı veriyor; tanımlar ayrıldığında 40 ızgaranın 38’i ayrılıyor.

Bu tablo bir şeyi kesin kılıyor: ayrılma kalıptan gelmiyor. Enine arama her iki tanımla da doğru çalışır; bozulan şey kalıbın kendisi değil, kalıba verilen komşuluk tanımıdır. Kalıbın adımı iki tanımda da 723, kâhinin adımı 12.768 ile 12.834; oran 17,7. Adım sütunu dört satırda da neredeyse aynı ve ayrılan girdi sütununu hiç haber vermiyor.

Komşuluk Bir Veri Özelliği Değil, Bir Karardır

Önceki yedi kalıpta ön koşul girdinin bir özelliğiydi: sıralı mı, negatif var mı, tekrar var mı. Burada ön koşul girdide değildir; modelleyenin verdiği bir karardır ve veriye bakarak doğrulanamaz. Aşağıdaki küçük ızgara farkı bir bakışta gösterir.

PK60. Küçük örnek elle kurulmuştur; üreteçten gelmez ve yalnız iki tanımın ayrımını göstermek içindir. PK61. İkinci dağarcık 20260219 tohumundan gelir. Ölçülen şey, iki tanımın kaç ızgarada farklı bileşen sayısı verdiğidir.

from collections import deque


def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


def izgara_dagarcik(tohum, n=40, boy=8):
    r = uretec(tohum)
    return [[[1 if r(101) < 30 else 0 for _ in range(boy)] for _ in range(boy)]
            for _ in range(n)]


YON4 = ((-1, 0), (1, 0), (0, -1), (0, 1))
YON8 = YON4 + ((-1, -1), (-1, 1), (1, -1), (1, 1))


def bilesen(izgara, komsuluk):
    """Enine arama ile bagli bilesen sayimi; isaretleme eklerken yapilir."""
    yon = YON4 if komsuluk == 4 else YON8
    n, m = len(izgara), len(izgara[0])
    ziyaret, say = set(), 0
    for i in range(n):
        for j in range(m):
            if not izgara[i][j] or (i, j) in ziyaret:
                continue
            say += 1
            ziyaret.add((i, j))
            kuyruk = deque([(i, j)])
            while kuyruk:
                x, y = kuyruk.popleft()
                for dx, dy in yon:
                    a, b = x + dx, y + dy
                    if 0 <= a < n and 0 <= b < m and izgara[a][b] \
                            and (a, b) not in ziyaret:
                        ziyaret.add((a, b))
                        kuyruk.append((a, b))
    return say


kucuk = [[1, 0, 0, 0, 1],
         [0, 1, 0, 1, 0],
         [0, 0, 1, 0, 0],
         [0, 1, 0, 1, 0],
         [1, 0, 0, 0, 1]]
for satir in kucuk:
    print("  ", "".join("#" if v else "." for v in satir))
print("  4 komsuluk:", bilesen(kucuk, 4), "bilesen")
print("  8 komsuluk:", bilesen(kucuk, 8), "bilesen")
print()
print("tohum      4 komsuluk toplam  8 komsuluk toplam  farkli izgara/40")
for tohum in (20260218, 20260219):
    K = izgara_dagarcik(tohum)
    d4 = [bilesen(g, 4) for g in K]
    d8 = [bilesen(g, 8) for g in K]
    farkli = sum(1 for a, b in zip(d4, d8) if a != b)
    print(f"{tohum}  {sum(d4):17d}  {sum(d8):17d}  {farkli:16d}")

   #...#
   .#.#.
   ..#..
   .#.#.
   #...#
  4 komsuluk: 9 bilesen
  8 komsuluk: 1 bilesen

tohum      4 komsuluk toplam  8 komsuluk toplam  farkli izgara/40
20260218                387                233                38
20260219                377                227                38

Beş satırlık ızgarada dokuz hücre var ve hiçbiri kenardaş değil; hepsi köşegen üzerinde duruyor. Dört komşulukla 9 ayrı bileşen, sekiz komşulukla tek bir bileşen çıkıyor. Aynı veri, aynı yordam, dokuz kat fark.

Kırk ızgaralık dağarcıkta toplam bileşen sayısı 387’den 233’e iniyor ve 38 ızgarada iki tanım farklı yanıt veriyor. İkinci dağarcıkta sayılar 377 ve 227, farklı ızgara yine 38; sonuç dağarcığa bağlı değildir.

Bu ölçümün pratik sonucu şudur: bir ızgara problemi okunurken sorulacak ilk soru komşuluğun tanımıdır. Tanım problem metninde yazmıyorsa, kalıbın verdiği yanıtın doğruluğu sınanamaz — kâhin bile kurulamaz, çünkü kâhinin de aynı tanıma ihtiyacı vardır. Bu, konudaki tek ön koşuldur ki veriye bakarak saptanamaz.

İşaretleme ve Gezinme Yanıtı Değil, Tutulanı Değiştirir

Komşuluk tanımı sabitlendiğinde geriye iki uygulama kararı kalır: işaretleme kuyruğa eklerken mi çıkarırken mi yapılacak, ve gezinme enine mi derine mi olacak. İkisi de bileşen sayısını değiştirmez. Değiştirdikleri şey aynı anda tutulan hücre sayısıdır.

PK62. Bu ölçüm daha büyük ızgarada yapılır: 10 ızgara, her biri 20×20, hücreler 100’de 60 olasılıkla dolu. Küçük ve seyrek ızgarada bu üç yordamın farkı çözünürlüğün altında kalır. PK63. Ölçülen şey, enine aramada kuyruğun en geniş hâli, derine aramada özyineleme derinliğinin en büyük değeridir.

from collections import deque


def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


def izgara_dagarcik(tohum=20260218, n=10, boy=20):
    r = uretec(tohum)
    return [[[1 if r(101) < 60 else 0 for _ in range(boy)] for _ in range(boy)]
            for _ in range(n)]


YON4 = ((-1, 0), (1, 0), (0, -1), (0, 1))


def enine(izgara, eklerken):
    """Isaretleme kuyruga EKLERKEN mi, kuyruktan CIKARIRKEN mi yapiliyor."""
    n, m = len(izgara), len(izgara[0])
    ziyaret, bilesen, adim, en_cok = set(), 0, 0, 0
    for i in range(n):
        for j in range(m):
            if not izgara[i][j] or (i, j) in ziyaret:
                continue
            bilesen += 1
            kuyruk = deque([(i, j)])
            if eklerken:
                ziyaret.add((i, j))
            while kuyruk:
                en_cok = max(en_cok, len(kuyruk))
                x, y = kuyruk.popleft()
                adim += 1
                if not eklerken:
                    if (x, y) in ziyaret:
                        continue
                    ziyaret.add((x, y))
                for dx, dy in YON4:
                    a, b = x + dx, y + dy
                    if 0 <= a < n and 0 <= b < m and izgara[a][b] \
                            and (a, b) not in ziyaret:
                        if eklerken:
                            ziyaret.add((a, b))
                        kuyruk.append((a, b))
    return bilesen, adim, en_cok


def derine(izgara):
    """Ozyinelemeli derine arama; en derin yigit boyu olculur."""
    n, m = len(izgara), len(izgara[0])
    ziyaret, bilesen, adim, en_derin = set(), 0, 0, 0

    def gez(x, y, derinlik):
        nonlocal adim, en_derin
        adim += 1
        en_derin = max(en_derin, derinlik)
        ziyaret.add((x, y))
        for dx, dy in YON4:
            a, b = x + dx, y + dy
            if 0 <= a < n and 0 <= b < m and izgara[a][b] \
                    and (a, b) not in ziyaret:
                gez(a, b, derinlik + 1)

    for i in range(n):
        for j in range(m):
            if izgara[i][j] and (i, j) not in ziyaret:
                bilesen += 1
                gez(i, j, 1)
    return bilesen, adim, en_derin


K = izgara_dagarcik()
temel = [enine(g, True) for g in K]
print("dagarcik: 10 izgara x 20 x 20 | dolu hucre:",
      sum(sum(sum(s) for s in g) for g in K))
print("gezinme                     ayni bilesen  adim  en cok tutulan hucre")
for ad, sonuc in (("enine, eklerken isaretle ", temel),
                  ("enine, cikarirken isaretle", [enine(g, False) for g in K]),
                  ("derine (ozyinelemeli)     ", [derine(g) for g in K])):
    ayni = sum(1 for a, b in zip(sonuc, temel) if a[0] == b[0])
    print(f"{ad}  {ayni:12d}  {sum(x[1] for x in sonuc):4d}"
          f"  {max(x[2] for x in sonuc):20d}")

dagarcik: 10 izgara x 20 x 20 | dolu hucre: 2378
gezinme                     ayni bilesen  adim  en cok tutulan hucre
enine, eklerken isaretle             10  2378                    18
enine, cikarirken isaretle            10  2887                    24
derine (ozyinelemeli)                 10  2378                   103

Üç satırın üçünde de bileşen sayısı aynı: on ızgaranın onunda aynı yanıt. Ayrılan girdi sıfırdır ve bu satırlar bir doğruluk ölçümü değildir.

Ölçülen fark iki sütundadır. İşaretlemeyi kuyruktan çıkarırken yapmak adımı 2378’den 2887’ye, en geniş kuyruğu 18’den 24’e çıkarıyor: aynı hücre ziyaret edilmeden önce birden çok kez kuyruğa giriyor. Derine arama adım sayısında enine aramayla birebir aynı (2378), ama en derin yığıt 103 hücre tutuyor — enine aramanın en geniş kuyruğunun yaklaşık beş buçuk katı.

Son sayı pratik bir sınırdır. Yoğun ve büyük bir ızgarada özyinelemeli derine arama, ızgara büyüklüğüyle orantılı bir yığıt derinliği ister; enine arama ise en geniş katmanla orantılı bir kuyruk ister. Hangisinin daha ucuz olduğu ızgaranın biçimine bağlıdır ve bu ayrım Veri Yapıları kursunun karşılaştırma tablosunda kurulmuştu; burada aynı ayrım sayıyla doğrulanmış oluyor.

Üç Sayı

Ölçüt	Kâhin	Kalıp	Ayrılan girdi
Dört komşuluk, dört komşuluk	12.768 adım	723 adım	0/40
Sekiz komşuluk, dört komşuluk	12.768 adım	723 adım	38/40
Enine arama, 20×20 ızgara	—	2378 adım / 18 hücre	0/10
Derine arama, 20×20 ızgara	—	2378 adım / 103 hücre	0/10

İlk iki satırda kalıbın adımı birebir aynıdır ve ayrılan girdi 0 ile 38 arasında değişir; son iki satırda ayrılan girdi aynıdır ve tutulan hücre sayısı beş buçuk kat değişir. İki tür karar, iki ayrı sütunda görünür — ve hiçbiri öbürünün sütununda iz bırakmaz.

Özet

• Izgara bir çizgedir: dolu hücreler düğüm, komşu hücre çiftleri kenardır; bağlı bileşen sayımı Veri Yapıları kursunun enine ve derine aramasıyla yapılır.
• Kalıp, kâhinle aynı komşuluk tanımını kullandığında 40 ızgaranın 40’ında doğru; tanımlar ayrıldığında 38 ızgarada ayrılıyor ve kalıbın adımı iki durumda da 723’tür.
• Komşuluk tanımı verinin değil modelleyenin bir kararıdır; veriye bakarak saptanamaz ve tanım belirlenmeden kâhin bile kurulamaz.
• Dokuz köşegen hücreden oluşan ızgarada dört komşuluk 9, sekiz komşuluk 1 bileşen veriyor; 40 ızgaralık dağarcıkta toplam 387’den 233’e iniyor.
• İşaretlemeyi çıkarırken yapmak yanıtı değiştirmiyor ama adımı 2378’den 2887’ye, kuyruğu 18’den 24’e çıkarıyor; derine arama aynı adımda 103 hücrelik yığıt tutuyor.

Sonraki Adım

Bu konu sekiz kalıbı aynı çerçeveyle ölçtü: bir kâhin, bir kalıp ve ikisinin ayrıldığı girdi sayısı. Sekiz dersin sekizinde de ayrılmanın kaynağı kalıbın hatası değil, kabul edilip denetlenmeyen bir ön koşuldu — sıra, işaret, tek ardıl, sıralama anahtarı, değer aralığı, denge, sorunun tanımı ve komşuluk. Sonraki konu kalıplardan adı olan problemlere geçer: sırt çantası, gezgin satıcı, en uzun yol, vezir yerleşimi. Orada sorulacak soru değişir — bir kalıbın ön koşulunun bozulup bozulmadığı değil, bir problemin neden zor olduğu sorulur; ve kâhin, o zorluğun ölçüldüğü araç olarak kalır.