Hızlı ve Yavaş İşaretçi

Önceki iki kalıp bir dizide çalıştı: uzunluk biliniyordu, her konuma dizin üzerinden erişilebiliyordu. Bu dersin yapısı farklıdır. Elde bir başlangıç düğümü ve her düğüm için bir ardıl vardır; uzunluk bilinmez, geriye gidilemez, yapının bir sonu olup olmadığı önceden bilinmez.

Kalıp iki işaretçiyi aynı yönde ilerletir ama farklı hızlarda: yavaş olan bir adım, hızlı olan iki adım atar. Ön koşulu tek cümledir: ilerleme tek yönlü olmalı, yani her düğümün tam bir ardılı bulunmalıdır. Bu ders o ön koşulun bozulduğu girdileri sayar ve kalıbın asıl kazancının adımda değil tutulan düğüm sayısında olduğunu gösterir.

Döngü Tespiti

İlk problem şudur: başlangıçtan ilerleyen bir gezinme sonsuza kadar sürer mi. Kâhin, Veri Yapıları kursunun derine aramasıyla döngü arar; oradaki “ziyaret edildi” ile “hâlâ açık” ayrımı tekrarlanmaz, doğrudan kullanılır. Kalıp hiçbir küme tutmaz: iki işaretçi farklı hızda ilerler ve döngü varsa er geç aynı düğümde buluşurlar.

PK18. Yapı 12 düğümlüdür; düğümler bir yol üzerinde dizilir ve yolun sonu ya biter ya geriye bağlanır. Tohum 20260218. PK19. Ön koşulu bozan tek şey bazı düğümlere eklenen ikinci bir geri kenardır. Ön koşulu sağlayan öbek, aynı yapıların ikinci kenarları atılmış biçimidir. PK20. Kalıp her zaman ilk ardılı izler; ikinci kenarın varlığını göremez, çünkü gördüğü tek şey ardil[d][0] değeridir. PK21. Adımın yanında ikinci bir ölçü tutulur: aynı anda tutulan düğüm sayısı. Kâhin için ziyaret kümesinin en büyük boyu, kalıp için iki işaretçidir.

TOHUM, DUGUM, DAGARCIK = 20260218, 12, 40


def uretec(tohum):
    d = tohum

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


def zincir_dagarcik(tohum=TOHUM, n=DAGARCIK, dugum=DUGUM):
    """Her yapida bir yol var. Yolun sonu ya biter ya geriye baglanir; ayrica bazi
    dugumlere IKINCI bir geri kenar eklenir."""
    r = uretec(tohum)
    kume = []
    for i in range(n):
        yol = list(range(dugum))
        for j in range(dugum - 1, 0, -1):
            k = r(j + 1)
            yol[j], yol[k] = yol[k], yol[j]
        ardil = {yol[j]: [yol[j + 1]] for j in range(dugum - 1)}
        ardil[yol[-1]] = [yol[r(dugum)]] if r(100) < 40 else [-1]
        if r(100) < 60:
            p = 2 + r(dugum - 3)
            ardil[yol[p]].append(yol[r(p)])
        kume.append({"no": i + 1, "bas": yol[0], "ardil": ardil})
    return kume


def tek_yonlu(ardil):
    """Ikinci kenarlar atilir: her dugumun tam bir ardili kalir."""
    return {d: [a[0]] for d, a in ardil.items()}


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

    def say(self, tutulan=0):
        self.adim += 1
        self.tutulan = max(self.tutulan, tutulan)


def kahin_dongu(bas, ardil, s):
    """Butun kenarlari gezer. Derine aramanin dongu tespiti dogrudan kullanilir."""
    ziyaret, acik = set(), set()

    def gez(d):
        ziyaret.add(d)
        acik.add(d)
        s.say(len(ziyaret))
        for k in ardil.get(d, []):
            if k == -1:
                continue
            if k in acik:
                return True
            if k not in ziyaret and gez(k):
                return True
        acik.discard(d)
        return False
    return gez(bas)


def kalip_hizli_yavas(bas, ardil, s):
    """ONKOSUL: her dugumun TAM BIR ardili olmali. Kalip ilk ardili izler."""
    yavas = hizli = bas
    while True:
        s.say(2)
        for _ in range(2):
            hizli = ardil[hizli][0]
            if hizli == -1:
                return False
        yavas = ardil[yavas][0]
        if yavas == hizli:
            return True


def olc(kume, tek):
    ayrilan, ak, ah, tk, th = [], 0, 0, 0, 0
    for k in kume:
        ardil = tek_yonlu(k["ardil"]) if tek else k["ardil"]
        s1, s2 = Sayac(), Sayac()
        a = kalip_hizli_yavas(k["bas"], tek_yonlu(k["ardil"]), s1)
        b = kahin_dongu(k["bas"], ardil, s2)
        ak, ah = ak + s1.adim, ah + s2.adim
        tk, th = max(tk, s1.tutulan), max(th, s2.tutulan)
        if a != b:
            ayrilan.append(k["no"])
    return {"ayrilan": len(ayrilan), "ilk_ayrilan": ayrilan[:6],
            "kalip_adim": ak, "kahin_adim": ah, "oran": round(ah / ak, 2),
            "kalip_tutulan": tk, "kahin_tutulan": th}


K = zincir_dagarcik()
print("dagarcik:", len(K), "yapi x", DUGUM, "dugum | ikinci kenari olan:",
      sum(1 for k in K if any(len(a) > 1 for a in k["ardil"].values())))
for ad, tek in (("on_kosul saglaniyor", True), ("on_kosul bozuk    ", False)):
    print(f"  {ad}", olc(K, tek))

dagarcik: 40 yapi x 12 dugum | ikinci kenari olan: 23
  on_kosul saglaniyor {'ayrilan': 0, 'ilk_ayrilan': [], 'kalip_adim': 299, 'kahin_adim': 480, 'oran': 1.61, 'kalip_tutulan': 2, 'kahin_tutulan': 12}
  on_kosul bozuk     {'ayrilan': 14, 'ilk_ayrilan': [2, 8, 11, 12, 16, 19], 'kalip_adim': 299, 'kahin_adim': 480, 'oran': 1.61, 'kalip_tutulan': 2, 'kahin_tutulan': 12}

İki satırın adım sütunları birebir aynı: kalıp 299, kâhin 480, oran 1,61. Tutulan düğüm sütunları da aynı: kalıp 2, kâhin 12. Değişen tek sütun ayrılan girdidir — 0’dan 14’e çıkıyor.

Adım oranı 1,61 zaten mütevazıdır ve kalıbın satış noktası da orası değildir. Kalıp tutulan düğüm sayısında kazanır: kâhin yapının bütün düğümlerini bir kümede tutmak zorundadır, kalıp iki işaretçiden başka hiçbir şey tutmaz. Düğüm sayısı büyüdükçe kâhinin tuttuğu şey büyür, kalıbınki 2’de kalır. Ölçülen kazanç budur ve ön koşul bozulduğunda bu kazanç hiç değişmez — yalnız yanıt bozulur.

Buluşmanın neden güvenceli olduğu da tek ardıl varsayımına dayanır. İki işaretçi döngüye girdikten sonra aralarındaki uzaklık her turda tam bir azalır, çünkü hızlı olan iki, yavaş olan bir adım atar. Uzaklık bir tam sayıdır ve döngü uzunluğu kadar değerden birini alır; her turda bir azaldığı için sonlu sayıda turda sıfıra iner. Uzaklığın bir azalması, her düğümden tek bir yol çıkması demektir. İkinci bir ardıl varken “aralarındaki uzaklık” diye tek bir sayı yoktur ve gerekçe düşer.

İkinci Kenar Neden Görünmüyor

Kalıbın tek bilgi kaynağı ardil[d][0] değeridir. Bir düğümün ikinci bir ardılı varsa kalıp onu sorgulamaz; sorgulayamaz da, çünkü kalıbın tanımı “tek ardıl” varsayımı üzerine kuruludur. Yapıda yalnız ikinci kenar üzerinden kapanan bir döngü varsa, kalıp o döngüye hiç girmez ve False döndürür.

def uretec(tohum):
    d = tohum

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


def zincir_dagarcik(tohum, n=40, dugum=12):
    r = uretec(tohum)
    kume = []
    for i in range(n):
        yol = list(range(dugum))
        for j in range(dugum - 1, 0, -1):
            k = r(j + 1)
            yol[j], yol[k] = yol[k], yol[j]
        ardil = {yol[j]: [yol[j + 1]] for j in range(dugum - 1)}
        ardil[yol[-1]] = [yol[r(dugum)]] if r(100) < 40 else [-1]
        if r(100) < 60:
            p = 2 + r(dugum - 3)
            ardil[yol[p]].append(yol[r(p)])
        kume.append({"no": i + 1, "bas": yol[0], "ardil": ardil})
    return kume


def tek_yonlu(ardil):
    return {d: [a[0]] for d, a in ardil.items()}


def kahin_dongu(bas, ardil):
    ziyaret, acik = set(), set()

    def gez(d):
        ziyaret.add(d)
        acik.add(d)
        for k in ardil.get(d, []):
            if k == -1:
                continue
            if k in acik:
                return True
            if k not in ziyaret and gez(k):
                return True
        acik.discard(d)
        return False
    return gez(bas)


def kalip_hizli_yavas(bas, ardil):
    yavas = hizli = bas
    while True:
        for _ in range(2):
            hizli = ardil[hizli][0]
            if hizli == -1:
                return False
        yavas = ardil[yavas][0]
        if yavas == hizli:
            return True


K = zincir_dagarcik(20260218)
ornek = next(k for k in K
             if kalip_hizli_yavas(k["bas"], tek_yonlu(k["ardil"]))
             != kahin_dongu(k["bas"], k["ardil"]))
print("ayrilan ilk girdi no:", ornek["no"], "| baslangic:", ornek["bas"])
print("  ardil:", {d: a for d, a in sorted(ornek["ardil"].items())})
print("  kalip (ilk ardil):", kalip_hizli_yavas(ornek["bas"], tek_yonlu(ornek["ardil"])))
print("  kahin (butun kenarlar):", kahin_dongu(ornek["bas"], ornek["ardil"]))
print()
print("tohum      on_kosul     dongulu (kahin)  ayrilan/40   oran")
for tohum in (20260218, 20260219):
    K = zincir_dagarcik(tohum)
    for ad, tek in (("saglaniyor", True), ("bozuk     ", False)):
        dongulu = ayrilan = 0
        for k in K:
            ardil = tek_yonlu(k["ardil"]) if tek else k["ardil"]
            b = kahin_dongu(k["bas"], ardil)
            dongulu += b
            ayrilan += (kalip_hizli_yavas(k["bas"], tek_yonlu(k["ardil"])) != b)
        print(f"{tohum}  {ad}  {dongulu:15d}  {ayrilan:8d}   {ayrilan / 40:.4f}")

ayrilan ilk girdi no: 2 | baslangic: 0
  ardil: {0: [8], 1: [2], 2: [7], 3: [-1], 4: [1, 8], 5: [10], 6: [5], 7: [6], 8: [9], 9: [11], 10: [3], 11: [4]}
  kalip (ilk ardil): False
  kahin (butun kenarlar): True

tohum      on_kosul     dongulu (kahin)  ayrilan/40   oran
20260218  saglaniyor               16         0   0.0000
20260218  bozuk                    30        14   0.3500
20260219  saglaniyor               18         0   0.0000
20260219  bozuk                    32        14   0.3500

İkinci girdide düğüm 4’ün iki ardılı var: 1 ve 8. Kalıp yalnız 1’i görüyor ve 0 → 8 → 9 → 11 → 4 → 1 → 2 → 7 → 6 → 5 → 10 → 3 → son yolunu izleyip False diyor. Kâhin 4 → 8 kenarını da deniyor ve 8 → 9 → 11 → 4 döngüsünü buluyor.

PK22. İkinci dağarcık 20260219 tohumundan gelir. İki dağarcıkta da ayrılan girdi 14/40, oran 0,3500; sonuç dağarcığa bağlı değildir.

Orta Eleman ve Durmama

İkinci problem, aynı kalıbın en sık kullanılan ikinci biçimidir: yapının orta düğümünü bulmak. Kâhin düğümleri sırayla toplar, sonra ortadakini seçer — iki geçiş ve bir küme. Kalıp tek geçişte biter: hızlı işaretçi sona ulaştığında yavaş işaretçi ortadadır.

Burada ön koşul değişir. Orta eleman ancak yapının bir sonu varsa tanımlıdır; döngü varsa “orta” diye bir düğüm yoktur. Kâhin bunu görür ve tanimsiz döndürür. Kalıbın göreceği bir şey yoktur: hızlı işaretçi döngü içinde sonsuza kadar döner.

PK23. Bu ölçümde ikinci kenarlar yoktur; yapılar tek ardıllıdır. Bozulan ön koşul döngüsüzlüktür. PK24. Kalıba bir adım sınırı konur (48 adım). Sınıra dayanan koşum durmadi döndürür ve kâhinden ayrılmış sayılır. Sınır olmasaydı ölçüm hiç bitmezdi.

def uretec(tohum):
    d = tohum

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


def yol_dagarcik(tohum=20260218, n=40, dugum=12):
    """`son` yolun son dugumu; oradan geriye baglanti varsa yapida dongu var."""
    r = uretec(tohum)
    kume = []
    for i in range(n):
        yol = list(range(dugum))
        for j in range(dugum - 1, 0, -1):
            k = r(j + 1)
            yol[j], yol[k] = yol[k], yol[j]
        ardil = {yol[j]: yol[j + 1] for j in range(dugum - 1)}
        ardil[yol[-1]] = yol[r(dugum)] if r(100) < 40 else -1
        r(100)
        kume.append({"no": i + 1, "bas": yol[0], "son": yol[-1], "ardil": ardil})
    return kume


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

    def say(self, tutulan=0):
        self.adim += 1
        self.tutulan = max(self.tutulan, tutulan)


def kahin_orta(bas, ardil, s):
    """Once butun dugumleri toplar, sonra ortadakini secer. Ziyaret kumesi tutar."""
    ziyaret, sira, d = set(), [], bas
    while d != -1 and d not in ziyaret:
        ziyaret.add(d)
        sira.append(d)
        s.say(len(ziyaret))
        d = ardil[d]
    if d != -1:
        return "tanimsiz"
    for _ in range(len(sira) // 2 + 1):
        s.say(len(ziyaret))
    return sira[len(sira) // 2]


def kalip_orta(bas, ardil, s, sinir=48):
    """ONKOSUL: yapida dongu olmamali. Tek gecis, yalniz iki isaretci tutulur."""
    yavas = hizli = bas
    while True:
        s.say(2)
        if s.adim > sinir:
            return "durmadi"
        if hizli == -1 or ardil[hizli] == -1:
            return yavas
        hizli = ardil[ardil[hizli]]
        yavas = ardil[yavas]


K = yol_dagarcik()
A = [dict(k, ardil={**k["ardil"], k["son"]: -1}) for k in K]
print("dagarcik:", len(K), "yapi | dongulu olan:",
      sum(1 for k in K if k["ardil"][k["son"]] != -1))
print("on_kosul     ayrilan/40  kalip  kahin   oran  kalip tutulan  kahin tutulan")
for ad, kume in (("saglaniyor", A), ("bozuk     ", K)):
    ayrilan, ak, ah, tk, th = 0, 0, 0, 0, 0
    for k in kume:
        s1, s2 = Sayac(), Sayac()
        a = kalip_orta(k["bas"], k["ardil"], s1)
        b = kahin_orta(k["bas"], k["ardil"], s2)
        ak, ah = ak + s1.adim, ah + s2.adim
        tk, th = max(tk, s1.tutulan), max(th, s2.tutulan)
        ayrilan += (a != b)
    print(f"{ad}  {ayrilan:8d}  {ak:5d}  {ah:5d}  {ah / ak:5.2f}"
          f"  {tk:13d}  {th:13d}")

dagarcik: 40 yapi | dongulu olan: 14
on_kosul     ayrilan/40  kalip  kahin   oran  kalip tutulan  kahin tutulan
saglaniyor         0    280    760   2.71              2             12
bozuk             14    868    662   0.76              2             12

Ön koşul sağlandığında kalıp 280 adımda 40 girdinin 40’ında kâhinle aynı düğümü buluyor; kâhin 760 adım harcıyor, oran 2,71. Döngülü yapılar geldiğinde ayrılan girdi 14 oluyor ve oran 0,76’ya düşüyor — kalıp kâhinden pahalı hâle geliyor.

Bu satır, önceki iki dersin göstermediği bir şeyi gösteriyor. Orada ön koşul bozulunca kalıp yanlış bir yanıt veriyor ve normal adım sayısında bitiyordu. Burada kalıp bitmiyor: 868 adımın büyük bölümü, on dört yapının her birinde sınıra dayanana kadar dönen işaretçilerdir. Sınır konmasaydı ölçüm hiç tamamlanmayacaktı. Ön koşulun bedeli her zaman yanlış yanıt değildir; bazen yanıtın hiç gelmemesidir.

Üç Sayı

Ölçüt	Kâhin	Kalıp	Ayrılan girdi
Döngü tespiti, ön koşul sağlanıyor	480 adım / 12 düğüm	299 adım / 2 düğüm	0/40
Döngü tespiti, ikinci kenarlı	480 adım / 12 düğüm	299 adım / 2 düğüm	14/40
Orta eleman, ön koşul sağlanıyor	760 adım / 12 düğüm	280 adım / 2 düğüm	0/40
Orta eleman, döngülü yapı	662 adım / 12 düğüm	868 adım / 2 düğüm	14/40

Dört satırın hepsinde kalıbın tuttuğu düğüm sayısı 2, kâhinin tuttuğu 12. Bu sütun kalıbın neden var olduğunu açıklar ve dört satırda da değişmez. Ayrılan girdi sütunu ise iki kez sıfır, iki kez on dörttür — ve o sütunu okumadan diğerlerine bakmak, kalıbın on dört girdide yanlış yanıt verdiğini görmemek demektir.

Özet

• Hızlı ve yavaş işaretçi, uzunluğu bilinmeyen tek yönlü bir yapıda döngüyü ve orta düğümü hiçbir küme tutmadan bulur.
• Ön koşul her düğümün tam bir ardılı olmasıdır; ikinci bir kenar eklendiğinde kalıp o kenarı hiç sorgulamaz ve 14 girdide kâhinden ayrılır.
• Ayrılma adım sayısına yansımaz: iki öbekte de kalıp 299, kâhin 480 adım harcar.
• Kalıbın ölçülen kazancı adımda değil tutulan düğüm sayısındadır: 2’ye karşı 12, ve bu oran ön koşul bozulsa da değişmez.
• Orta eleman probleminde ön koşul döngüsüzlüktür; döngülü yapıda kalıp yanlış yanıt vermekle kalmaz, adım sınırına dayanır ve oran 2,71’den 0,76’ya düşer.

Sonraki Adım

Buraya kadarki üç kalıp tek bir geçişte, tek bir yapı üzerinde çalıştı. Sonraki kalıp girdiyi önce yeniden düzenler: örtüşen aralıkları birleştirmek, aralıkları bir ölçüte göre sıralamakla başlar. Ön koşul artık verinin bir özelliği değil, seçilen ölçütün kendisidir — ve yanlış ölçütle sıralamak kalıbı bozar. Sonraki ders üç ayrı sıralama ölçütünü aynı kâhinle karşılaştırıp hangisinin kaç girdide yanlış birleştirdiğini sayacak.