Çözüm Doğrulama

Önceki ders bir çözümün adım bütçesine sığmasının onu doğru yapmadığını gösterdi: en az adımı harcayan aday, 40 girdinin 18’inde kâhinden ayrılıyordu. O 18 sayısı hazır bir dağarcıktan geldi ve sorgulanmadı. Bu ders o sorgulamayı yapar — hangi girdilerle karşılaştırıldığı, karşılaştırmanın kendisi kadar belirleyicidir.

Test yazma disiplini, kenar durumu düşünme ve gözden geçirme alışkanlıkları başka kurslarda kuruldu ve burada tekrarlanmıyor. Bu dersin eklediği tek şey kâhindir: doğruluğun bir görüşe değil, ikinci bir çözümün yanıtına karşı sayılmasıdır.

Doğrulama Yordamı

Yordam üç adımdır ve sırası değişmez. Birincisi, girdi kümesi üretilir. İkincisi, hem sınanan çözüm hem kâhin aynı girdilerde koşturulur. Üçüncüsü, iki yanıtın farklı çıktığı girdiler sayılır. Çıktı bir sayıdır: ayrılan girdi. Sıfırsa o kümede kanıt bulunamamıştır; sıfırdan büyükse çözüm yanlıştır ve elde somut bir örnek vardır.

• AD11 — Sınanan çözüm sıralı dizide iki işaretçidir. Ön koşul her girdide sağlanır; bu ders ön koşulu değil gerçeklemeyi sınar.
• AD12 — Beş kusurlu sürüm elle üretilir ve her kusur tek satırlık bir değişikliktir: bitiş koşulu, başlangıç konumu, bitiş konumu, ilerleme yönü, boş girdi.
• AD13 — Bir sürüm çöktüğünde bu da ayrılma sayılır; çökme sessiz yanlıştan daha az tehlikelidir ama yine bir ayrılmadır.
• AD14 — Rastgele dağarcık 40 girdidir, her biri tam 12 değer taşır; hedef de aynı üreteçten gelir ve $-18$ ile $22$ arasındadır.
• AD15 — Kenar durumu kümesi 12 girdidir ve elle kurulur: boş dizi, tek eleman, iki eleman, yalnız tekrar eden değerler, uçlardaki değerler, ulaşılamayan hedef.

"""Bes kusurlu surum , iki ayri girdi kumesi , kahin karsisinda."""
TOHUM, IKINCI = 20260218, 20260219


def uretec(tohum):
    d = tohum

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


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

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


def rastgele_kume(tohum=TOHUM, n=40, uzunluk=12):
    r = uretec(tohum)
    return [(sorted(r(30) - 9 for _ in range(uzunluk)), r(41) - 18)
            for _ in range(n)]


KENAR = [([], 11), ([5], 10), ([5], 5), ([5, 6], 11), ([5, 6], 10),
         ([7, 7], 14), ([-9, -9], -18), ([0, 0, 0], 0), ([-9, 20], 11),
         ([1, 2, 3, 4], 3), ([1, 2, 3, 4], 7), ([2, 2, 2, 2], 4)]


def kahin(d, hedef, s):
    for i in range(len(d)):
        for j in range(i + 1, len(d)):
            s.say()
            if d[i] + d[j] == hedef:
                return True
    return False


def iki_isaretci(d, hedef, s, kusur=None):
    """kusur=None dogru surum. Her kusur tek satirdir."""
    sol = 1 if kusur == "K2" else 0
    sag = (len(d) - 2) if kusur == "K3" else (len(d) - 1)
    if kusur == "K5":
        d[0]                                   # bos diziyi hesaba katmiyor
    while (sol <= sag) if kusur == "K1" else (sol < sag):
        s.say()
        t = d[sol] + d[sag]
        if t == hedef:
            return True
        ileri = (t > hedef) if kusur == "K4" else (t < hedef)
        sol, sag = (sol + 1, sag) if ileri else (sol, sag - 1)
    return False


KUSUR = [(None, "dogru surum"), ("K1", "sol <= sag"), ("K2", "ilk eleman atlaniyor"),
         ("K3", "son eleman atlaniyor"), ("K4", "yonler ters"),
         ("K5", "bos dizi hesapta yok")]


def olc(kusur, kume):
    ayrilan, ak, ah = 0, 0, 0
    for d, hedef in kume:
        s1, s2 = Sayac(), Sayac()
        try:
            a = iki_isaretci(list(d), hedef, s1, kusur)
        except IndexError:
            a = "coktu"
        b = kahin(list(d), hedef, s2)
        ak, ah = ak + s1.adim, ah + s2.adim
        if a != b:
            ayrilan += 1
    return ayrilan, ak, ah


R = rastgele_kume()
print(f"rastgele dagarcik {len(R)} girdi x 12 deger | "
      f"kenar durumu kumesi {len(KENAR)} girdi")
print("kusur                    rastgele  kenar  kalip adim  kahin adim")
for k, ad in KUSUR:
    ar, akr, ahr = olc(k, R)
    ak, akk, ahk = olc(k, KENAR)
    print(f"{ad:22s}  {ar:8d}  {ak:5d}  {akr + akk:10d}  {ahr + ahk:10d}")
print()
Y = rastgele_kume(IKINCI)
print("ikinci dagarcik 20260219 , rastgele kume:",
      {ad: olc(k, Y)[0] for k, ad in KUSUR})

rastgele dagarcik 40 girdi x 12 deger | kenar durumu kumesi 12 girdi
kusur                    rastgele  kenar  kalip adim  kahin adim
dogru surum                    0      0         329        1596
sol <= sag                     3      2         344        1596
ilk eleman atlaniyor           4      5         297        1596
son eleman atlaniyor           3      5         317        1596
yonler ters                   25      2         423        1596
bos dizi hesapta yok           0      1         329        1596

ikinci dagarcik 20260219 , rastgele kume: {'dogru surum': 0, 'sol <= sag': 2, 'ilk eleman atlaniyor': 2, 'son eleman atlaniyor': 2, 'yonler ters': 27, 'bos dizi hesapta yok': 0}

Üç sayı yan yana. Kâhin: 52 girdinin tamamında 1596 adım ve her girdide doğru yanıt. Kalıp: doğru sürüm 329 adım, yani kâhinin 4,85 katı azı. Ayrılan girdi: doğru sürümde iki kümede de 0; beş kusurlu sürümde 0 ile 25 arasında.

Tablonun asıl bulgusu son satırdadır. Rastgele dağarcık 40 girdiyle beş kusurun dördünü yakalıyor ve beşincisini — boş girdiyi hesaba katmayan sürümü — hiç yakalamıyor. Sebep yordamsaldır, şanssızlık değil: dağarcığın her girdisi tam 12 değer taşır, yani boş ve tek elemanlı girdi o kümede hiç yoktur. Bir kusur sınıfı, girdi üretecinin biçimi yüzünden yapısal olarak erişilemez durumdadır ve dağarcığı 40’tan 400’e çıkarmak bunu değiştirmez.

Kenar durumu kümesi bunun tersini yapıyor: 12 girdiyle beş kusurun beşini de yakalıyor. Girdi başına verim 40’ta 4’e karşı 12’de 5’tir — 0,1000’e karşı 0,4167. Buna karşılık kenar kümesi tek başına da yetmiyor: yönleri ters çevrilmiş sürümü yalnız 2 girdide yakalarken rastgele dağarcık onu 25 girdide yakalıyor. İki küme farklı kusur sınıfları görüyor ve biri diğerinin yerini almıyor.

İkinci dağarcık sonucu doğruluyor: 20260219 tohumuyla sayılar 2, 2, 2, 27, 0 çıkıyor — dört kusur yine yakalanıyor, boş girdi kusuru yine kaçıyor, ve yönleri ters sürümün baskınlığı sürüyor. Ayrılan girdi oranı aynı büyüklük düzeninde; sonuç dağarcığa bağlı değildir.

Ayrılan Girdiyi Küçültmek

Bir ayrılma bulunduğunda elde 12 değerlik bir dizi vardır ve o dizinin hangi özelliği kusuru tetikliyor belli değildir. Küçültme bunu çözer: girdiden bir değer çıkarılır, ayrılma sürüyorsa küçük hâli tutulur, sürmüyorsa değer geri konur. İşlem hiçbir çıkarma ayrılmayı korumayana kadar tekrarlanır.

• AD16 — Küçültme yalnız değer çıkarır; değer eklemez ve değiştirmez. Sonuç, başlangıç girdisinin bir alt dizisidir.
• AD17 — Bir deneme, aday girdide hem kusurlu sürümü hem kâhini bir kez koşturmaktır.
• AD18 — Küçültmenin sonucu yerel olarak en küçüktür: tek değer çıkarmayla daha da küçültülemez. Bütün alt diziler arasında en küçük olduğu iddia edilmez.

"""Ayrilan girdiyi en kucuk haline indirme."""
from math import comb

TOHUM = 20260218


def uretec(tohum):
    d = tohum

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


def rastgele_kume(tohum=TOHUM, n=40, uzunluk=12):
    r = uretec(tohum)
    return [(sorted(r(30) - 9 for _ in range(uzunluk)), r(41) - 18)
            for _ in range(n)]


def kahin(d, hedef):
    return any(d[i] + d[j] == hedef
               for i in range(len(d)) for j in range(i + 1, len(d)))


def iki_isaretci(d, hedef, kusur=None):
    sol = 1 if kusur == "K2" else 0
    sag = (len(d) - 2) if kusur == "K3" else (len(d) - 1)
    if kusur == "K5":
        d[0]
    while (sol <= sag) if kusur == "K1" else (sol < sag):
        t = d[sol] + d[sag]
        if t == hedef:
            return True
        ileri = (t > hedef) if kusur == "K4" else (t < hedef)
        sol, sag = (sol + 1, sag) if ileri else (sol, sag - 1)
    return False


def ayriliyor(d, hedef, kusur):
    try:
        return iki_isaretci(list(d), hedef, kusur) != kahin(d, hedef)
    except IndexError:
        return True


def kucult(d, hedef, kusur):
    """Bir deger cikarilir; ayrilma suruyorsa cikarilmis hali tutulur."""
    deneme = 0
    ilerledi = True
    while ilerledi:
        ilerledi = False
        for i in range(len(d)):
            aday = d[:i] + d[i + 1:]
            deneme += 1
            if ayriliyor(aday, hedef, kusur):
                d, ilerledi = aday, True
                break
    return d, deneme


R = rastgele_kume()
print("kusur  ilk ayrilan girdi no  uzunluk  kuculmus  deneme  en kucuk girdi")
for kusur in ("K1", "K2", "K3", "K4"):
    for no, (d, hedef) in enumerate(R, 1):
        if ayriliyor(d, hedef, kusur):
            kd, deneme = kucult(d, hedef, kusur)
            print(f"{kusur:5s}  {no:20d}  {len(d):7d}  {len(kd):8d}"
                  f"  {deneme:6d}  {kd} hedef {hedef}")
            break
print()
print("12 uzunlukta sirali girdi sayisi (degerler -9..20):", comb(41, 12))
print("52 girdilik kume bu uzayin", f"{52 / comb(41, 12):.1e}", "kadarini gorur")

kusur  ilk ayrilan girdi no  uzunluk  kuculmus  deneme  en kucuk girdi
K1                        1       12         1      23  [-8] hedef -16
K2                       17       12         2      31  [-8, -5] hedef -13
K3                        7       12         2      21  [-5, 16] hedef 11
K4                        4       12         3      20  [-3, 18, 20] hedef 15

12 uzunlukta sirali girdi sayisi (degerler -9..20): 7898654920
52 girdilik kume bu uzayin 6.6e-09 kadarini gorur

Dört ayrılan girdinin dördü de 12 değerden 1, 2 ve 3 değere iniyor ve bu 20 ile 31 arası denemeyle oluyor. Küçültmenin kazandırdığı şey adım değil, okunabilirliktir: [-3, 18, 20] ve hedef 15 girdisine bakan biri, yönleri ters çevrilmiş sürümün neden yanıldığını doğrudan görebilir; aynı bilgi 12 değerlik bir dizide gizlidir.

Birinci satır iki bölümü birbirine bağlıyor. Bitiş koşulu bozuk sürümün en küçük ayrılan girdisi tek elemanlı bir dizidir: [-8], hedef $-16$. O tek elemanlı girdi, önceki bölümdeki kenar durumu kümesinde elle yazılmıştı. Yani küçültme, elle kurulan kenar durumlarının bir kısmını kendiliğinden üretiyor — rastgele bir 12 değerlik girdiden yola çıkıp aynı yere varıyor. Kenar durumu listesi bir sezgi ürünü olmak zorunda değildir; ayrılan bir girdiden türetilebilir.

Kâhinin Bağımsız Olması

Yordamın tamamı kâhinin doğruluğuna dayanıyor. Kâhin yanlışsa ayrılan girdi sayısı yanlış çıkar, ve bu yanlışlık en tehlikeli yönde çıkar: sıfır. Kâhin, sınanan çözümle aynı gözden kaçırmayı paylaşıyorsa ikisi de aynı yanlış yanıtı verir ve karşılaştırma hiçbir şey bulmaz.

• AD19 — Kâhin, sınanan çözümle aynı düşünceden türetilmemiş olmalıdır. Kaba kuvvet bu şartı taşır, çünkü hiçbir kalıp varsayımı kullanmaz.
• AD20 — Aynı gözden kaçırmayı paylaşan bir kâhin, sınanan çözümle 0 ayrılan girdi üretir; bu sıfır bir doğruluk kanıtı değil, bir bağımlılık belirtisidir.

"""Kahinin bagimsizligi: ayni yanlisi paylasan iki cozum 0 ayrilan girdi verir."""
TOHUM = 20260218


def uretec(tohum):
    d = tohum

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


def rastgele_kume(tohum=TOHUM, n=40, uzunluk=12):
    r = uretec(tohum)
    return [(sorted(r(30) - 9 for _ in range(uzunluk)), r(41) - 18)
            for _ in range(n)]


def tara(d, hedef):
    return any(d[i] + d[j] == hedef
               for i in range(len(d)) for j in range(i + 1, len(d)))


def kahin_dogru(d, hedef):
    return tara(d, hedef)


def kahin_kusurlu(d, hedef):
    """Ayni gozden kacirma: son eleman hic bakilmiyor."""
    return tara(d[:-1], hedef)


def kalip_kusurlu(d, hedef):
    """Iki isaretci son elemani hic gormuyor."""
    sol, sag = 0, len(d) - 2
    while sol < sag:
        t = d[sol] + d[sag]
        if t == hedef:
            return True
        sol, sag = (sol + 1, sag) if t < hedef else (sol, sag - 1)
    return False


def ayrilan(a, b, kume):
    return sum(1 for d, hedef in kume if a(d, hedef) != b(d, hedef))


R = rastgele_kume()
print("karsilastirilan iki cozum              ayrilan girdi / 40")
print("kusurlu kalip  -  dogru kahin         ", ayrilan(kalip_kusurlu, kahin_dogru, R))
print("kusurlu kalip  -  kusurlu kahin       ", ayrilan(kalip_kusurlu, kahin_kusurlu, R))
print("kusurlu kahin  -  dogru kahin         ", ayrilan(kahin_kusurlu, kahin_dogru, R))

karsilastirilan iki cozum              ayrilan girdi / 40
kusurlu kalip  -  dogru kahin          3
kusurlu kalip  -  kusurlu kahin        0
kusurlu kahin  -  dogru kahin          3

Aynı kusurlu kalıp, aynı 40 girdide, iki farklı kâhine karşı 3 ve 0 veriyor. Ortadaki satırın sıfırı bir doğruluk haberi gibi okunur ve değildir: kalıp da kâhin de son elemanı görmüyor, ikisi de aynı girdilerde aynı yanlış yanıtı veriyor, ve fark ölçen bir yordam farkı olmayan yerde kör kalıyor. Üçüncü satır kusurlu kâhinin kendisinin 3 girdide yanlış olduğunu gösteriyor — yani hata oradaydı, ölçüm onu göremedi.

Bu, kaba kuvvetin neden bu kursta kâhin olarak kaldığının ölçülmüş gerekçesidir. Kaba kuvvet hiçbir kalıp varsayımı taşımaz: sıralılık, işaret, aralık, tekillik varsaymaz. Bir kalıbın hızlandırılmış bir sürümünü kâhin yapmak, hızlandırmanın dayandığı varsayımı ölçümün içine taşımak demektir.

Sıfır Ayrılan Girdi Ne Kanıtlar

Doğru sürüm iki kümede de 0 ayrılan girdi verdi. Bu, sürümün doğru olduğunu kanıtlamaz ve öyle yazılamaz. Son iki satır neden olmadığını söylüyor: değerleri $-9$ ile $20$ arasında olan 12 uzunluklu sıralı girdilerin sayısı 7.898.654.920, ve 52 girdilik küme bu uzayın 6,6·10^-9 kadarını görüyor. Hedefin de 41 ayrı değer aldığı düşünülürse oran daha da küçülür.

Bu yüzden doğrulamanın çıktısı iki farklı cümledir ve karıştırılmamalıdır. Ayrılan girdi sıfırdan büyükse: çözüm yanlıştır, elde kanıt vardır, ve kanıt küçültülerek okunabilir hâle getirilebilir. Ayrılan girdi sıfırsa: bu kümede kusur bulunamamıştır — kusur yok değildir, bulunamamıştır. İkinci cümlenin gücü kümenin genişliğiyle değil, kapsadığı kusur sınıflarıyla artar; 40 rastgele girdi boş girdi kusurunu 400’e çıkarılsa da yakalayamazdı, 12 elle kurulmuş girdi ise tek satırda yakaladı.

Özet

• Doğrulama yordamı üç adımdır: dağarcık üret, kâhini aynı girdilerde koştur, iki yanıtın ayrıldığı girdiyi say. Çıktı bir görüş değil, bir sayıdır.
• 40 girdilik rastgele dağarcık beş kusurun dördünü yakalıyor; boş girdiyi hesaba katmayan kusuru yakalayamıyor, çünkü dağarcığın her girdisi tam 12 değer taşıyor ve o kusur sınıfı yapısal olarak erişilemez.
• 12 girdilik kenar durumu kümesi beş kusurun beşini de yakalıyor; girdi başına verim 0,1000’e karşı 0,4167. Ama yönleri ters sürümü yalnız 2 girdide yakalıyor, rastgele dağarcık onu 25 girdide yakalıyor — iki küme birbirinin yerine geçmiyor.
• İkinci dağarcık aynı sonucu veriyor (2, 2, 2, 27, 0). Ayrılan bir girdi, tek değer çıkarma denemeleriyle 12 değerden 1–3 değere iniyor ve bu 20–31 deneme tutuyor; bitiş koşulu bozuk sürümün en küçük ayrılan girdisi [-8], yani elle yazılmış kenar durumlarından biri.
• Kâhin sınanan çözümle aynı gözden kaçırmayı paylaşırsa ayrılan girdi 3’ten 0’a düşüyor; o sıfır doğruluk değil, bağımlılık belirtisidir. Kaba kuvvet kâhin olarak kalır çünkü hiçbir kalıp varsayımı taşımaz.
• Sıfır ayrılan girdi doğruluk kanıtı değildir: 52 girdilik küme, 7.898.654.920 girdilik uzayın 6,6·10^-9 kadarını görüyor.

Sonraki Adım

İki ders bir çözümün nasıl seçileceğini ve nasıl sınanacağını sayıya bağladı. Geriye tek bir soru kalıyor ve o soru tek bir çözümle ilgili değil: bu işi tekrar tekrar yapan biri ilerlediğini nereden bilecek. Sonraki ders alıştırma ortamlarının türlerini ayırır ve tekrarlı çalışmanın ilerleme ölçütünü ortak tanımın kalıp kümesi üzerinde sayar. Ölçülecek şey şaşırtıcıdır: çözülen problem sayısı bir ilerleme ölçütü değildir, ve bunun neden olmadığı üç ortam türünde ayrı ayrı sayılacaktır.