Kasanın şifresi (Çözüm)

Soruyu ilk önce kendi çözdüğüm yöntemle çözeceğim. Daha sonra da daha kolay ve mantıklı olduğunu düşündüğüm bir çözümü vereceğim.

1. Çözüm

Çözüme küçük dizilerle soldan başladım. İlk adım olarak ilk basamağın 0 olamayacağını gördüm. Bu şifrede 0 tane 0 var demek kendisiyle çelişiyor çünkü. Demek ki en az bir tane 0 olmalı.

O zaman çözüm denememe bir tane 0 ile başladım. İlk dizim oldukça kısaydı.

1

Tabii ki bu dizi şartların hiçbirini sağlamıyor. O zaman bir sonraki basamağı da kullanayım dedim. O zaman da bir sorunla karşılaştım ama. Bir tane 1 var dersem yine olmayacak çünkü o zaman dizi 11 olacak, yani iki tane 1 olacak. Bunu geçiştirmek için o basamağa 2 yazım. Dizimin şimdiki hali şöyle oldu:

1 2

Dizide şimdilik bir tane de 2 olduğundan bir sonraki basamağa 1 yazabileceğimi gördüm.

1 2 1

İki tane 1, bir tane 2 kısmı güzel. Sadece bir tane de 0 lazım. O zaman bir sonraki basamağa 0 yazabilirim.

1 2 1 0

Bu mini dizi istenen şartların hepsini sağlıyor. Tek sorun şifrenin 10 basamaklı olması. Burada bu düzeni kullanarak diziyi istediğim şekilde uzatabileceğimi sezdim. Bunun en kolay yolu 0 rakamlarının adedini artırmak. Bu sırada bir adet 1 sayısını kaybedeceğim ama 0 rakamlarının adedinin gösterildiği basamağa o kaybettiğim 1 rakamını yazarsam sorun çözülecek.

Şimdiye kadar dört basamağı hallettim (ilk basamağın değeri henüz tam değil). Yani altı basamak daha var. Bu basamakların hepsi 0 olursa dizi şöyle olur.

7 2 1 0 0 0 0 0 0 0

Tabii ki bir adet 7 rakamını göstermek için bir tane daha 1 lazım ama ona yer kalmadı. O zaman yedi tane değil altı tane 0 olduğunu var saymam lazım diye düşündüm.

6 2 1 0 0 0 1 0 0 0

Dikkat ettiyseniz 6 rakamlarının adedini veren yedinci basamağa bir tane 1 koyunca geriye sadece altı tane 0 için yer kaldı. Bu şifre soruda verilen her şartı sağlamakta. Bu yöntemin bir başka zayıf tarafı da başka bir çözüm olup olmadığını göstermiyor.

2. Çözüm

Bu çözümde şifre sağdan sola doğru aranıyor.

En sağdaki basamak şifredeki 9 rakamının adedini veriyor. Bu basamak 1 olursa diğer herhangi bir basamakta bir adet 9 olmalı. Bu 9 rakamını başka bir yere koyamıyoruz ama. Bunu bir iki örnekle göstermeye çalışayım.

9 0 0 0 0 0 0 0 0 1 Eğer ilk basamağa koyarsak bir tane 0 eksik kalıyor.
1 9 1 1 1 1 1 1 1 1 Eğer ikinci basamağa koyarsak diğer basamaklardaki 1 rakamları kullanılmamış oluyor.

Bu şekilde son rakamın 0 olması gerektiğini bulabiliriz.

Şimdi sağdan ikinci basamağa bakalım. Bu basamak şifredeki 8 rakamının adedini verecek. Buraya da 1 koyarsak dizi aşağıdaki gibi gözükecek

_ _ _ _ _ _ _ _ 1 0

Şimdi 8 için bir yer seçelim. İki aday var, ya ilk basamak ya da ikinci basamak. Çünkü diğer her basamak on basamaktan fazlasını gerektirecek. İlk basamağa 8 koyarsak, şifrede sekiz tane 0 olacak demektir. Bunu bir deneyelim:

8 0 0 0 0 0 0 0 1 0

Neredeyse bir çözüm olabilecekmiş. İkinci basamak 0 olamaz çünkü şifrede en az bir tane 1 var fakat bu basamağa 0 yazmazsak da o zaman sekiz tane 0 kullanamayacağız.

1 8 1 1 1 1 1 1 1 0

Bu da çözüm olamıyor çünkü şifremizde 2, 3, 4, 5, 6, 7, 8 rakamlarını hiç kullanmadık.

Demek ki sondan ikinci basamak da 0 olmalı.

_ _ _ _ _ _ _ _ 0 0

Şimdi sondan üçüncü basamağa bakalım. Bu basamak 1 olursa diğer basamakların birinde 7 olmak zorunda olur. Ayrıca ikinci basamak (1 rakamının adedi) da en az 2 olmalı. İlk basamak da en az 2 olmalı, çünkü şimdiye kadar iki tane 0 kullandık. Bu verilerden sonra 7 rakamını da ya ilk ya ikinci basamakta kullanmak zorundayız. Önce ikinci basamağa bakalım:

1 7 1 1 1 1 1 1 0 0

Bu şifre olmuyor çünkü birinci basamak bile yanlış.

Şimdi 7 rakamını ilk basamakta kullanalım.

7 0 0 0 0 0 0 1 0 0

Bu da olamıyor çünkü şifrede bir adet 1 var fakat ikinci basamak 0.

O zaman son üç basamak 0 olmak zorunda.

_ _ _ _ _ _ _ 0 0 0

Sıradaki basamak şifrede kaç tane 6 olduğunu söylüyor. İki tane 6 için yer olmadığından 1 rakamını deneyelim.

_ _ _ _ _ _ 1 0 0 0

İlk ve ikinci basamaklar dışında 6 kullanamayacağımıza göre (yoksa şifrede altı adet 2, 3, 4 ya da 5 olması gerekecek ve bunu on basamakla yapmak mümkün değil) yine ikinci basamakla denemeye devam edelim.

_ 6 _ _ _ _ 1 0 0 0

Şimdi belirlenmemiş beş basamak var ve altı tane 1 kullanmamız lazım. Demek ki hepsi 1 olmalı ama bu da mümkün değil, ilk basamak en az 3 olmalı (şimdiden üç tane 0 var). O zaman 6 rakamını ilk basamakta deneyelim.

6 _ _ _ _ _ 1 0 0 0

Yine beş rakam bulmamız lazım ve bunların üç tanesi 0 olmalı. Hangi üçünün 0 olduğunu görmek kolay. Üçüncü, dördüncü ya da beşinci basamakta 0 haricindeki herhangi bir rakam için yeterli boş basamağımız olmadığından bu basamakları 0 yapalım.

6 _ _ 0 0 0 1 0 0 0

Şimdiye kadar bir tane 1 kullandık ama ikinci basamağa 1 yazarsak iki tane 1 kullanmış olacağız. Demek ki ikinci basamağa en az 2 yazmamız lazım.

6 2 _ 0 0 0 1 0 0 0

Şifrede bir tane 2 kullandık, o zaman üçüncü basamak da 1 olmalı.

6 2 1 0 0 0 1 0 0 0

Basamakları kontrol edersek bu şifrenin sorudaki şartları sağladığını görürüz.

İkinci çözüm biraz uzunmuş gibi görünse de birinci çözüme göre ihtimalleri daha iyi elemekte. Bu yöntem sona kadar devam ettirilerek başka çözüm olup olmadığı da daha kolay görülebilir bence.

Günlük

Almanya’nın meşhur Eisheilige denen soğuk haftası başladı. Dün hava 20 derecenin üzerindeyken, bugün kar yağıyordu. Cumaya kadar hava yavaş yavaş ısınacak ama geceleri toprak donacak kadar soğuk olabilecek. Sabah evden çıkmadan önce termometreye baktım ve nedense dereceye inanıp tişört ve montla evden çıktım. 16 dereceyi gösteriyordu ama hissedilen 3 filandı heralde. Rüzgar ve yağmur da vardı. En azından bahçeyi sulamaya gerek yok diye düşünerek işe gittim. İşe varana kadar sırılsıklam olmuştum ama.

Trende fizik kitabını okumaya devam ettim. Quantum fiziğinin gerçeklikle ilişkisini ve bu arayışın tarihini anlatan güzel bir popüler kitap. Heyecanla okumaya devam ediyorum. Henüz buna bir cevap bulunduğunu sanmıyorum, herkesin ayrı bir cevabı var gibi.

Bugünkü işlerim iyi gitti sayılmaz. Programda testlere devam ettim ve bir yerde bir tasarım hatasıyla karşılaştım. Yarın bunu düzeltmeyi düşünüyorum.

Pastel boya siparişi vermiştim ama gelmeyeceğini öğrendim. Paket bozulduğundan satıcıya geri gönderilmiş. Biraz bekleyeyim, satıcı paramı geri öderse başka bir set alırım. Belki de yeni bir set gönderirler. Bu korona virüsü zamanında paket gönderileri bir acayip oldu. Ümit’e doğum günü hediyesi almıştım ve 3 Nisan’da gelecek gözüküyordu. Doğum gününe yetişmiyordu ama olsun dedim. Japonya’dan başka bir yerde bulamamıştım zaten. Mayıs oldu ve paket hala gelmedi. Satıcıya yazıp durumu sordum. Hemen özür dilemeye başladılar. Eğer istersem bir tane daha gönderebileceklerini söylediler. Kabul ettim ama ben kabul edebilene kadar bir iki gün yine özür postaları okumaya devam ettim. İki hafta içinde gelmezse yine haber vermemi söyleyip tekrar özür dilediler. Sırf bu özürler bitsin diye umarım bu sefer paket gelir.

Akşam kedileri dışarı çıkarmadım. Hala çok soğuk ve yağmur var. Bu soğukta dış kapıyı açık bırakmak istemiyorum. Varsınlar bana kızsınlar. Sabah zaten küçük bir şok yaşadım, o bana yeter. Ben kalkınca kediler de kalkıyor ve dışarı çıkmak için aşağı iniyorlar. Hafta içi bu kadar erken sadece Lea dışarı çıkabilir. Diğerleri ancak herkes kalkınca çıkabilir, çünkü kapı açık bırakılacak filan. Lea’yı dışarı çıkarıp hazırlanmaya başladım. Tam aşağıya iniyordum ki Lea’yı karşıdan gelirken gördüm. İmkansız bu dedim. Daha beş dakika önce dışarı çıkarmıştım. Heralde bir yerde kapı ya da pencere açıktır da oradan girmiştir. Bu da kötü bir haber ama o zaman diğer kediler de aynı kapı ya da pencereden kaçmış olabilir. Kontrol ettim kapılar ve pencereler kapalıydı. Salona geldiğimde Ümit sabahın körü olmasına ve bu hafta okulu olmamasına rağmen kalkmış televizyon seyrediyordu. Lea’yı içeri kendisinin mi aldığını sordum. Evet deyince acayip rahatladım.

Bu akşam soğukta bahçede çalışmayı düşünmüyorum. Belki evde birkaç tohum ekerim, o kadar.

Günlük

Bugün çocuklarla ormana gittim. Orman evin hemen yanında. Mezarlığı geçince. Yani mezarlık daha yakın. Birçok insan ormanı harika bir yer gibi hayal ediyor olabilir. Her şeyin çok güzel göründüğü bir yer gibi. Aslında alakası yok. Orman güzel bir yerdir gerçekten de ama doğru bakıldığında. Hayvanat bahçesi gibi bir yer değil kesinlikle. Söz konusu hayvanat bahçesi değil de böcekler alemi ise işler değişir ama. Her türlü böcek çevrenizdedir. Yürürken üzerinize konar, ağzınıza uçar. Evdeki sivrisinekler sizi çok rahatsız ediyorsa ormanda kot pantolon üzerinden sizi sokabilecek sineklere hazır olun. Uzun pantolona rağmen keneler sizin damarlarınızı bulmayı başarır. Bitki örtüsü de çiçek bahçesi şeklinde değildir. Yine de sürekli değişen bir biyotoptur. Bu değişikliği görmek için de doğru gözle bakmak gerekir.

Gezimizin başında yolda bir sürü bok böceği gördük. Firavunlar zamanında kutsal canlılardan biri olan bu böcek türü çevredeki ormanlarımızın vaz geçilmez vatandaşlarıdır. Sanki bizden önce geçen haylaz bir çocuk inadına hepsini ters çevirmişti. Bazıları debelenip dönmeye çalışıyordu, bazıları da ya artık pes etmişlerdi ya da ölü taklidi yapıyorlardı. Evet, bazı böcek türleri ölü taklidi yaparak hayatta kalmaya çalışır. Biz ezilmemiş olanların hepsini düz çevirdik. Enteresan bir şekilde vücutlarının yuvarlak şekline oranla oldukça uzun bacakları var. Sırf bu yüzden devrilmeden yürümeleri çok kolay olmuyor.

Bundan başka orman gezisi olaysız geçti. Bir kaynaktan su örneği aldım. Bakalım yakında mikroskop altında bu örnekte ilginç şeyler bulabilecek miyim?

Alexa’ya güvenip nasıl olsa pazar akşamı yağmur yağacağını düşündüğümden bahçeyi iki gündür sulamamıştım. Akşam Alexa’ya yine sorduğumda “Yağmur mu? Bugün yağmur yağmayacak” cevabını alınca küfürü bastım. Aceleyle bahçeyi suladım. Sonra da google’a sordum. O da bu gece yağmur yağacak dedi. Allah sizin gibi yapay zekanın belasını versin.

Yorucu bir hafta sonu da böylece bitti. Biraz kitap okuyayım bari.

Günlük

Gün geçmiyor ki meslek hayatımda garip bir şey olmasın. Birkaç gündür başka ekipten bir programcı resmen bizi taciz etmeye başladı. Sanırım şefi ona bizim aletle haberleşen programı baştan sona test etme görevi vermiş. O da yarım saatte bir bizim gruba sorular sormaya başladı. Haberleşme kısmını da ben programladığım için kabak benim başıma patladı.

Bugünkü sorusu da gönderdiğim bir mesajdaki bazı metinlerin 250 karakterden uzun olmasıydı. Daha doğrusu bu sorunun farkında olup olmadığımızı sordu. Elimdeki dökümanlara baktım ve bu uzunlukla ilgili bir kısıtlamanın şimdiye kadar tanımlı olmadığını söyledim. Bir süre cevap gelmeyince bir mesaj daha yazdım. Eğer 250 karakter sınırınız varsa o zaman bu metinleri kesmek sizin işiniz dedim. Bunu zaten yaptıklarını söyledi. Sorun nerede o zaman diye düşünürken bir sonraki cümleyi de okudum. “Ama böyle yapınca veri kaybı oluyor”. İçimden “Aferin Sherlock” dedim. Dışımdan da bir e-mail yazıp, veri kaybının kendi sınırlamaları yüzünden olduğunu anlattım. “Bizim sistemde veri kaybı yok, size geldikten sonra kayboluyor” dedim. Bu konuda da pek yardımcı olamayacağımı belirttim. Bu sınırı kolayca kaldırabileceklerine inandığımdan çözümü de kendilerine alıştırma olarak bıraktım.

Bugün planladığım işleri erkenden bitirdiğimden işten erken çıktım. Erken dediğim kendi normallerime göre erken. İstasyonda maskelerini takmadan ve arada mesafe bırakmadan birbirleriyle hararetli bir şekilde “bu kısıtlamaları azaltmaları yüzünden haftaya kesin korona patlaması yaşarız” konulu bir tartışma yapan iki Alman’ı dinledim.

Akşam da bahçede biraz çalıştım. Bu arada Terence’in kesik bıyıkları sonunda uzamaya başladı. Kedi bıyıklarının bu kadar yavaş uzadığını bilmiyordum.

Terence

Günlük

Bir oyun oynuyorsunuz. Kurallarını öğrenmişsiniz. Oynarken zevk alacağınızı düşünüyorsunuz, ya da buna inanmaya çalışıyorsunuz. Oyunu yöneten kişi sürekli kuralları sizin aleyhinize değiştiriyor. Ne de olsa oyunun kuralı bu, diğerleri de bu kurallara göre oynuyor diye oynamaya devam ediyorsunuz. Bir süre sonra kural değişikliklerinin özellikle sizin gibileri hedef aldığını fark ediyorsunuz. Artık oyundan zevk almıyorsunuz. Oyundan çıkmak istiyorsunuz ama ona da izin yok.

Bu akşam çimlenen çiçeklerimin fotoğraflarını çektim.

Papatyagillerden kirpi otu (Echinacea)
Hüsnüyusuf
Düğün çiçeğigillerden Delphinium
Katmer çiçeği

Haftaya bu yılın son soğukları da bitince yeterince büyümüş olanları yavaş yavaş dışarı alacağım.

Geçen gün başladığım kitabı bitirdim. Bence Philip Dick’e dönmeden önce bir tane daha kısa kitap okuyayım. Momentum kazanmak iyi bir fikir olabilir.

Film seyretmek çoğunlukla kitap okumaktan daha zor oluyor benim için. Zorluğu aslında seyretmekte değil de bitirmekte. Bütün gün çok yorulduğumdan her filmde uyuyakalıyorum. En iyisi şimdi uyuyakalmadan önce geçen gün başladığım filme biraz daha devam edeyim.

Günlük

Bu sabah evden çıktığımda termometreler iki dereceyi gösteriyordu. Umarım soğuklar yakında biter. Salonda saksılardan, mini seralardan yer kalmadı. Hem onlar için de bahçede olmak daha iyi olur.

Trenden inince istasyonun arkasındaki yolu seçtim bu sefer. Elf Freunde anıtına doğru inmeye başladım. Kavşağa geldiğimde yanyana şu iki ağaçla karşılaştım.

Kısa günün karı diyerek şirkete gittim. Bugün işler dünkü kadar yoğun olmasa da daha problemliydi. Neyse ki gün sonunda birkaç sorunun nedenini bulabildim. Korona virüsü nedeniyle kalabalık bürolarda elemanların artık sadece yarısı çalışıyor. Diğer yarısı evlerinden çalışıyor. Bilmediğim bir nedenden ötürü bizim şirkette buna home-office yerine mobil çalışma deniyor. Heralde patronun evle ilgili kötü anıları var.

Bu tenha büroların etkisi mi, yoksa korona korkusu mu bilemiyorum ama artık bürodaki arkadaşlarla bir çok ilişkide aşılamayan osuruk eşiğini geçmiş bulunuyoruz. Umarım bunu daha da abartmayız.

Akşam eve geldiğimde bahçedeki çiçeklerin dün geceki buz gibi havayı atlatmış olduğunu gördüm. Bu moralle aynı ölüm kalım savaşından galip gelmiş olan bir miktar yaban otunu yolmaya giriştim. Bu iş için kullandığım küçük tırmığımın bir dişi yamuldu. Bazı yaban otlarının ölüme canla başla karşı koymaları gerçekten de takdire değer.

Bahçe işinden sonra bir ağaç da mezarlıkta çekeyim dedim. Korona nedeniyle mezarlığa da sadece tek kişi veya tanıdık biri olmak ve mesafeyi korumak şartıyla iki kişi girilebiliyormuş. Bütün bu şartları sağladığıma emin olduktan sonra mezarlığa girdim ve bu fotoğrafı çektim.

Böyle güzel bir manzaraya kavuşmak için ölmek biraz abartı bence ama yine de düşünülebilir.

Günlük

Korona salgını başladığından beri kitap okumakta zorlanıyordum. Okuduğum Philip Dick hikayeleri bir miktar konsantrasyon gerektiriyordu ve bunu bir türlü beceremiyordum. Tabii ki çocukların da sürekli evde olması nedeniyle suçu gürültülü ortama atmak da mümkün ama bunun bir faydası olmaz. Bir iki gün önce verimsiz ısrarımdan vaz geçtim ve daha kısa olan bir çocuk kitabına başladım. Okuma sorunu da yavaş yavaş geçti gibi. Anlaşılan gerçekten de zorla güzellik olmuyor. Hele böyle kısa bir hayatta…

Fotoğraf çekmeye devam ediyorum ama o da anca hafta sonlarında. Turuncu süslüler sezonu kapatmak üzere ve hala ne bir erkek kelebeğin ne de yumurtalarının fotoğraflarını çekemedim. Olsun, bu yıl da böyle geçsin. Ormandaki sarımsak otu nüfusunun artışına bakılırsa belki de gelecek sene çok daha fazla turuncu süslü olacak. Aceleye gerek yok. Belki de fotoğraf makinemi işe giderken de yanımda taşırsam daha iyi olabilir. Çevrede güzel ağaçlar var, onların fotoğraflarını çekebilirim ve belki o fotoğrafları resimler için fikir olarak kullanabilirim. Tabii ki resim yapmayı beceremiyorum ama seviyorum.

Bu arada evet, salgına rağmen işe gidiyorum. Bilgi işlem grubumuz herkes için evden çalışma imkanı sağlayamadı. Ben de evden zaten çalışamayacağımı düşündüğümden şirkete gitmeye karar verdim. Ayrıca yaşadığım eyalette salgın o kadar yaygın değil. Bu iyi bir şey mi yoksa kötü mü onu da bilmiyorum. Buna kafa yormak da istemiyorum.

İşler şu sıralar zaten çok yoğun. Salgın nedeniyle uluslararası fuar ertelendi. En azından fuar projeleri ertelendi derken şirket bünyesinde fuar yapmaya karar verdik ve aynı projeler bu sefer hiç hazır değilken karşımıza geldi. Bunun yanında şu an çalıştığım sürümde çok garip bir sorun çıktı ve bu sorun sadece bu sürümde mi var onu da henüz bilmiyorum. Benim açımdan bu Mayıs ayı hiç de damadın dediği gibi Nisan’dan çok daha iyi olmayacak. Şimdiden yorgunluk belirtileri göstermeye başladım. Yorgunluk dedim de aklıma geldi. En iyisi yatayım şimdi. Uykum da geldi.

Rolling hash

Aslında yazı arama algoritmalarında devam etmek istiyordum ama önce sıradaki algoritmada kullanılan bir teknikle ilgili yazmaya karar verdim. Bu tekniğin adı rolling hash. Rolling hash aslında bir tür hash değeri hesaplama algoritmasıdır. Hash nedir ve yazı aramada hash değeri nasıl işimize yarayabilir?

Hash fonksiyonu, değişken uzunluklu veri kümelerini, sabit uzunluklu veri kümelerine haritalayan algoritma veya alt programdır. Vikipedide verilen tanım bu. Bunu basitçe bir alt metni kullanarak hesapladığımız bir sayı olarak düşünebiliriz.

Bir sonraki metin algoritmasında kısaca metin içinde aradığımız parçanın harflerini tek tek kaydırarak karşılaştırmak yerine ana metinde aradığım alt metinle aynı uzunluktaki parçaların hash değerlerini aradığımız metnin hash değerleriyle karşılaştırmayı deneyeceğim.

Önce metinlerde kullanabileceğim basit bir hash fonksiyonu tanımlamaya çalışayım. Örneğin aradığım metnin harf değerlerini toplamakla başlayabilirim.

Aradığım metin ABC ise harflerin ASCII değerlerini toplamayı düşünebilirim. A = 65, B = 66 ve C = 67 olduğuna göre hash(ABC) = 65 + 66 + 67 = 198 olur. Oldukça kolay olan bu algoritmanın bir dezavantajı var ama. hash(ABC) = hash(CBA) olacaktır. Daha doğrusu basitçe harf değerlerini toplamak aradığım harflerin sırası değiştiğinde de aynı hash değerini hesağlayacağından arama işlemlerinde çok faydalı olmayabilir. Aslında tanıma dikkatli baktığımızda hash değerlerinin farklı harflerden oluşan diziler için de aynı olabileceğini görebiliriz, çünkü bu hash fonksiyonu asla birebir olmayacaktır. Harf dizisi sayısı hesapladığımız sayılardan fazladır, demek ki bazı diziler ne yaparsak yapalım aynı hash değerlerine sahip olacaktır. Yine de elimizden geldiğince bu çakışmaları azaltmakta fayda var.

Harflerin pozisyonlarına göre değişik değerler üretebilmeleri için bu harflerin değerlerini harfin konumuna göre değişik sayılarla çarpıp toplayacağım. Çarptığım sayıları da bir tabanın kuvvetleri olarak seçeceğim. Bu seçim bu yazının konusu olan rolling hash hesabında oldukça faydalı olacak. Bu yazıda bu iş için en uygun sayıların nasıl bulunacağına girmeyeceğim. Sadece kabaca algoritmanın bir simulasyonunu vereceğim. Yazıda ve simulasyonda taban olarak 7 sayısını kullanacağım.

Bu durumda \(hash(ABC) = 65\cdot {7^0} + 66\cdot{7^1} + 67\cdot{7^2} = 65 + 66\cdot{7} + 67\cdot{49} = 65 + 462 + 3283 = 3810 \) olur. Harflerin yerlerini değiştirdiğimde de \(hash(CBA) = 67\cdot {7^0} + 66\cdot{7^1} + 65\cdot{7^2} = 67 + 66\cdot{7} + 65\cdot{49} = 65 + 462 + 3185 = 3714 \) sonucu çıkıyor. Demek ki bu yöntem harf sıralamasındaki değişikliklerde daha iyi bir performans sağlıyor. Tabii ki buna rağmen çakışmalar olabilir ama önemli olan bu ihtimalin azalması.

Ana metin içinde aramayı yaparken aradığımız metin uzunluğundaki parçaların hash değerlerini hesaplamamız gerekecek. İyi de bu hash değerleri metni bir kaydırıp bütün harfleri tek tek karşılaştırmaktan nasıl daha iyi olabilir ki? Her kaydırmadan sonra daha çok çarpma ve toplama yapmamız gerekiyor ve sonuçta zaten hash değerleri aynı çıksa bile çakışma riski nedeniyle iki diziyi yine harf harf karşılaştırmamız gerekecek. Bu yöntemin daha iyi olabilmesi için hash değeri hesaplamayı çok daha kolay bir hale getirmem gerekecek.

Metnimiz ABCD olsun ve aradığımız metin de üç harf uzunluğunda olsun. Kontrol etmemiz gereken iki tane alt dizi olacak. ABC ve BCD. Şimdi bunların hash değerlerine bakalım.

\(hash(ABC) = 65\cdot {7^0} + 66\cdot{7^1} + 67\cdot{7^2} = 65 + 66\cdot{7} + 67\cdot{49} = 65 + 462 + 3283 = 3810 \)

\(hash(BCD) = 66\cdot {7^0} + 67\cdot{7^1} + 68\cdot{7^2} = 66 + 67\cdot{7} + 68\cdot{49} = 66 + 469 + 3332 = 3867 \)

Kaydırma adımına bakarsak ilk diziden A harfi çıkarılıyor ve yerine D harfi ekleniyor. Bu adımı ilk hesaplana hash değeri ile beraber kullanırsak şöyle bir hesaplama çıkarabiliriz. Önce çıkarılan harfin değerini önceki hash değerinden çıkaralım:

\(3810 – 65 = 3745 \)

ABC dizisindeki harfler bir sonraki dizide BC şeklinde bir harf sola kaydığına göre basamak değerleri de ona göre kayacak. İlk hesapta B’nin basamak değeri \(7^1 = 7 \) iken ikinci hesapta basamak değeri \(1 \) olacak. C’nin basamak değeri de ilk hesapta \(7^2 = 49\) iken ikinci hesapta \(7 \) olmakta. Yani kaydırma sırasında düşen harfi çıkardıktan sonra kalan harflerin değerleri öncekinin yedide biri oluyor, yani kalan sayısı 7’ye böleceğim.

\(3745 : 7 = 535 \)

Şimdi yeni hash değerini bulmak için sadece kaydırma sonunda diziye eklenen harfin değerini toplamak kaldı. Yeni eklenen harfin basamak değeri her zaman \(7^2=49 \) olduğundan son işlemimiz

\(535 + 68\cdot49 = 535 + 3332 = 3867\) olur. Bu da normal hesapladığımızda çıkan sonuca eşittir.

Simulasyon linkine geçmeden önce bu algoritmanın istediğimiz performansı vermesi için tabii ki aradığımız metin parçasının uzun olması gerektiğini ekleyeyim. Çünkü her durumda yapılması gereken işlem sayısı aynı. Bir çıkarma, bir bölme, bir çarpma ve bir toplama ve bir kuvvet alma. Bu işlemlerin toplamdaki yükü aranan dizinin boyu uzadıkça azalacaktır. Simulasyona geçmeden önce bir de tanımdaki sabit uzunluklu kısmına dikkat çekmek istiyorum. Buraya kadar anlattığım yöntemde hash değeri sonuçta keyfi uzunlukta bir harf dizisinin oluşturduğu polinomun değeri olacağından bu haliyle sabit bir uzunluğa sahip olmayacaktır. Bu sorunu gidermek için sonucu seçtiğimiz bir sayıya göre modulo işlemi yaparak bulabiliriz. Böylece hash değerimiz her zaman sınırlı olacaktır. Simulasyonda şimdilik bu modulo işlemini kullanmadım ama ileride bunu da ekleyebilirim.

Simulasyon

Simulasyonda her kaydırma işleminden sonra diziden çıkarılan harf kırmızı ile diziye yeni eklenen harf ise yeşil renkle gösterilmiştir.

Kasanın şifresi

Bu sefer de bir arkadaşımdan öğrendiğim bir bilmeceyi sorayım.

Bir kasanın on basamaklı bir şifresi var.

Şifrenin ilk rakamı şifrede kaç tane 0 bulunduğunu söylüyor.

Şifrenin ikinci rakamı şifrede kaç tane 1 bulunduğunu söylüyor.

Şifrenin üçüncü rakamı şifrede kaç tane 2 bulunduğunu söylüyor.

Şifrenin dördüncü rakamı şifrede kaç tane 3 bulunduğunu söylüyor.

Şifrenin beşinci rakamı şifrede kaç tane 4 bulunduğunu söylüyor.

Şifrenin altıncı rakamı şifrede kaç tane 5 bulunduğunu söylüyor.

Şifrenin yedinci rakamı şifrede kaç tane 6 bulunduğunu söylüyor.

Şifrenin sekizinci rakamı şifrede kaç tane 7 bulunduğunu söylüyor.

Şifrenin dokuzuncu rakamı şifrede kaç tane 8 bulunduğunu söylüyor.

Şifrenin onuncu rakamı şifrede kaç tane 9 bulunduğunu söylüyor.

Kasanın şifresi nedir?

Çözüm

Günün avı

Pandemi nedeniyle parklara giremediğimiz ama ormana gidebildiğimiz bu günlerde rüzgara rağmen dışarıda şansımı denedim. Günün avları aşağıda.

https://www.instagram.com/p/B_siz5XJSdt/
bombyliidae familyasından bir sinek turnagagsı çiçeğine konmuş
https://www.instagram.com/p/B_sly_Hp7ww/
Adaçayı üzerinde poz veren bir böcek
https://www.instagram.com/p/B_smNdiJqoI/
Bugün böceklerde poz verme arzusu dikkat çekicii boyutlarda
Evde de heyecanlı gelişmeler var. Katmer çiçeği çimleniyor.