Project Euler 114

114 epey kısa ama güzel bir Project Euler sorusu; Elimizde n uzunluğunda bir sıra var. Bu sıradaki elemanları siyaha ya da ardışık olarak en az 3 hücre olacak şekilde kırmızıya boyamak istiyoruz, kaç farklı şekilde boyayabiliriz?

Ben şöyle bir yol izledim; \(F(n, k)\) şeklinde bir fonksiyon olsun ve bu fonksiyon \(n\) uzunluğunda ve son \(k\) hücresi kırmızı olan sıraların sayısını tutsun. Fonksiyon için aşağıdakileri yazabiliriz:

  • 3'ten daha kısa kırmızı alt sıra olamayacağından \(F(1, 0) = 1\) ve \(F(2, 0) = 1\). Ayrıca aynı mantıkla tüm \(n\) değerleri için \(F(n, 1) = 0\) ve \(F(n, 2) = 0\).
  • \(F(i, 0) = \sum\limits_{k=0}^{i-1} F(i-1, k)\). Yani, \(n-1\) uzunluktaki herhangi bir sıranın sonuna ancak 1 siyah hücre ekleyerek onu \(n\) uzunlukta ve sıfır kırmızı hücre ile biten bir sıra yapabiliriz.
  • \(n\) uzunlukta ve \(k\) tane kırmızı hücre ile biten sıra sayıları, \(n-k\) uzunlukta ve 0 kırmızı hücre ile biten sıra sayılarına eşittir. Çünkü 0'dan daha fazla kırmızı ile biten sıra sayılarını da dahil edersek, \(k\)'dan daha fazla kırmızı hücre ile biten sıraları da hesaplamış oluruz.

Bu üç maddeye göre \(F(n, k)\) fonksiyonunun değerlerini hesapladığımızda cevap

\[\sum\limits_{i=0}^{50} F(50, i)\]

toplamının sonucu olacak.

Amcalar ve Şapkalar

Dün akşam bir tane soruya denk geldim. Bir tane şirket soruyu yazmış, bunu çözebiliyorsanız başvurun falan demiş. Soru şu şekilde;

8 tane amca var, kağıtlara kendi isimlerini yazıp bir kutuya atıyorlar. Sonra hepsi kutudan rastgele bir kağıt çekiyor. Bu da herkes kendi adından farkli bir kağıt çekene kadar devam ediyor. Herkesin kendi adından farklı kağıt çekme olasılığı kaçtır?

Brute force çözüm olarak düşününce elimizde toplam \({n!}\) tane olasılık var, yani isimleri \({n!}\) farklı şekilde atayabiliriz. Tüm permütasyonları oluşturup başarılı permütasyonlari sayarsak olasılığı da, çıkan toplamı \({n!}\)'e bölerek bulabiliriz. Yani aşağıdaki gibi.

Kodu en kısa nasıl olabilir diye yazdığım için performans olarak idealden uzak. Bu haliyle \(n=9\) için de hesaplayabildim ama \(n=10\) için epey zorlandı.

Peki \(n > 9\) gibi durumlar için ne yapabiliriz? Burada tüm olasılıkları hesaplamak artık biraz zorlaşıyor. Onun yerine bir fonksiyon tanımlayip soruyu daha kısa zamanda cözebiliriz.

Diyelim ki \(D\) matrisi, \(n\) elemanli bir durum için \(k\) elemanın kendi adını çektiği durumları içeren bir matris olsun. Burada şöyle ön çıkarımlar yapabiliriz;

- \(0\) elemanlı her durum için sonuç sıfırdır, yani \(D_{0, i} = 0, i = 0 .. n\)
- Herhangi bir durumda herkesin kendi ismini bulduğu durumlarin sayisi \(1\)'dir, yani \(D_{i, i} = 1, i = 1 .. n\).

Bu durumların dışında ise şunu söyleyebiliriz; \(D_{i, k}\) bize \(i\) elemanın olduğu durumda \(k\) elemanın kendi adını bulduğu, diğerlerinin yani \(i-k\) elemanın ise kendi adından farkli adları bulduğu durumların sayısını versin. Burada \(k\) elemanı\(\binom{i}{k}\) farklı şekilde seçebiliriz. Her bir seçenek icin geriye kalan \(i-k\) eleman ise kendi adından farklı bir adı seçecek. Bu da aslında bizim fonksiyonumuzdaki \(D_{i-k, 0}\) sonucuna denk geliyor. Yani formülünü yazarsak;

\[D_{i, k} =\binom{i}{k} * D_{i-k, 0}\]

Burada tek istisnai durum ise şu; \(k = 0\) durumunda ne yapacagiz? \(k = 0\) iken denklem

\[D_{i, 0} =\binom{i}{0} * D_{i, 0}\]

oluyor yani sonsuz döngüye giriyor. Bundan da şu şekilde kurtulabiliriz; daha öncesinde tüm olası \(D_{i, k}\) değerlerini hesaplamıştık. \(D_i\) satırındaki değerlerin toplamı, \(i\) elemanlı durum için permütasyon sayısını veriyor. \(D_{i, 0}\) değerini de bu mantığı kullanarak

\[D_{i, 0} ={i!} - \sum\limits_{k=1}^i D_{i, k}\]

formülüyle hesaplayabiliriz.

Bunun da kodunu kısa olsun diye uğraşarak aşağıdaki gibi yazdim

Kodlarda ya da mantığımda herhangi bir hata var mı sizce?

İTÜYM Finalinden Bir Soru

Geçen haftasonu ITU IEEE Yazılım Maratonu finali vardı. Etkinlik 2 gün sürdü ve her gün ayrı ayrı şirketlerin hazırladığı 3'er soru soruldu. Ben bir kez daha şunu farkettim ki başlangıçta her ne kadar soruyu çözen algoritmayı bulmak daha zor görünse de asıl zor olan hatasız kod yazabilmek. Ya da ben çok iyi bir günümde değildim bilmiyorum :) . 20 takım arasından 10. oldum, seneye daha iyi yaparım artık. Takım arkadaşım olmadan en azından sonuncu olmadım diye kendimi avutuyorum :) .

Yarışmada sorulan ve benim kodunu düzgün yazamadığım için kaçırdığım güzel bir soru vardı: Elimizde 3 harften (A, B ve C olsun) oluşan bir alfabe ve bu alfabeden türetilen rastgele kelimeler var. Kelimeler arasında ise şöyle bir ilişki var;

- A ile biten bir kelimeden sonra B ile başlayan bir kelime gelmeli
- B ile biten bir kelimeden sonra C ile başlayan bir kelime gelmeli
- C ile biten bir kelimeden sonra A ile başlayan bir kelime gelmeli

Elimizdeki kelime dağarcığını kullanarak \(K (K \leq 10^{18})\) kelime uzunluğunda bir yazı yazmak istiyoruz. Kaç farklı yazı yazabiliriz?

Her kelime çeşidini (A,B,C ile başlayan ve A,B,C ile biten toplam 9 olasılık) bir düğüm olarak düşünürsek  aslında soruda sorulmak istenen şey şu; herhangi bir düğümden başlayarak herhangi başka bir düğüme, aradaki her düğümü istediğimiz kadar ziyaret ederek \(K\) adımda kaç farklı şekilde varabiliriz? Bir düğümden başlayarak diğer bir düğüme, her düğümü istediğimiz kadar ziyaret etme işine graph theory'de walk (yürüyüş) diyoruz. Belirli bir uzunluktaki yürüyüşlerin sayısını bulmak için ise komşuluk matrisinin şu özelliğinden faydalanacağız;

\(A\) komşuluk matrisi olmak üzere, \(A^K\) matrisinin \(A_{i,j}\) değeri, \(n_i\) düğümünden \(n_j\) düğümüne yapılan \(K\) uzunluktaki yürüyüşlerin sayısını verir.

O zaman ilk olarak komşuluk matrisini oluşturmamız gerekiyor. İhtiyacımız olan \(3 \times 3\) lük bir komşuluk matrisi, satır indeksi bize kelimenin ilk karakterini, sütun indeksi ise kelimenin son karakteri ile gidebileceğimiz kelime grubunun ilk karakterini verecek. Örneğin A için 0, B için 1 ve C için 2 değerlerini atarsak, "ABAB" kelimesinin satır indeksi, ilk karakter A olduğu için 0, sütun indeksi ise B'den sonra C geleceği için 2 olacak. Her bir kelimenin bu matriste denk geldiği hücreyi bulup bir arttıracağız.

Son olarak ise \(A^K\) değerini hesaplamamız gerekiyor. \(K\)'nın çok büyük olduğunu göz önünde bulundurursak \(A\)'yı art arda \(K\) kez çarpmak iyi bir yöntem değil, onun yerine 2'li üs alma yöntemini kullanabiliriz.

Bu işlem karmaşıklığı \(O(K \times N^3)\)'ten \(O(N^3 \times logK)\)'ya düşürecek. En sonunda yapacağımız işlem ise tüm hücre değerlerini toplamak.

Benim yarışmada yaptığım hata ise, mul fonksiyonunda matrisleri çarparken indeksleri karıştırmak :) .

LeetCode Online Judge

LeetCode, yazılımcı mülakatlarına hazırlanmak için bir sürü sorular barındıran bir site. Sorulara C, C++, Java ve Python'la cevap verilebiliyor.

Birkaç gündür buradaki soruları inceliyordum, gördüm ki C# desteği için bir çalışma başlatmışlar, mevcut soruları C#'a çevirecek insanlar arıyorlar. İşin asıl güzel tarafı da 10 tane çevirene kitap veriyorlar. Beleş kitaptan daha değerli ne var diyerek atladım. Bu akşam 7 tane soru çevirdim, yarın 10'a tamamlayıp kitabımı beklemeye başlayacağım :)

Beleş kitap candır diyenler admin@leetcode.com adresine "sorularınızı C#'a çevirmek istiyorum, email adresim de bu, şu kadar senedir C#'la uğraşıyorum" tarzı bir mail atıp şifre alabilirler.

Dizideki Eksik Elemanı Bulma

İş görüşmelerinde sorulan klasik bir soru var; \([-1, 2, -1, 3, 2]\) gibi bir dizinin içinde, biri hariç tüm sayılardan 2 tane, diğer sayıdan ise 1 tane vardır. Bu sayı hangisidir?

Bu sorunun envai çeşit çözümü var. Her elemanın dizideki diğer çiftini arayabiliriz (\(O(n^2)\), hatta genelleştirilmiş durumda, k tekrar varsa \(O(n^k)\)), diziyi sıralayıp kontrol edebiliriz (\(O(nlogn)\)), hashtable'a atıp sayılarını tutabiliriz (\(O(n)\), fakat ekstradan alan gerekli) falan filan.

En yaygın çözümü de tüm elemanları xorlayıp çıkan sonucu dönmektir. Bu çözüm aşağıdaki iki kurala dayanır

\[a \oplus a = 0\]

\[a \oplus 0 = a\]

Bu durumda tüm 2 sayılar 0 olacak, tek sayıyı da 0'la xorlayıp sayının kendisini elde edeceğiz.

Peki bu problemi daha da genelleştirirsek nasıl çözebiliriz? Diyelim ki elimizdeki sayı dizisindeki sayılar, biri hariç \(n\) defa tekrar ediyor, diğer sayı da, \(0 < k < n\) olmak üzere, \(k\) defa tekrar ediyor olsun. \(k\) defa tekrar eden sayıyı nasıl bulabiliriz? Tabii ki yöntem olarak da \(O(1)\) ekstra alan kullanan ve \(O(n)\) işlemde biten bir yöntemi tercih ediyoruz.

İlk durumda sayıların 1 bitlik olduğunu düşünelim, yani dizi sadece 1 ve 0'lardan oluşuyor. Dizinin toplamını alırsak sonuç ya \(0 \times n + 1 \times k\) ya da \(1 \times n + 0 \times k\) olacak. Bu toplamların \(n\)'e göre modunu aldığımızda çıkan sonuç \(0\) ya da \(k\) olacak. Bu sonuclar da aslında

\[k \times a\]

ifadesine eşit. \(a\) da bizim aradığımız sayı.

Kısacası; ifadenin modu \(0\) ise aradığımız sayı \(0\), değilse \(1\).

32 bitlik sayı dizilerinde ise yapmamız gereken, bu işlemi tüm sayılardaki her bite uygulamak. sonrasında çıkan sonuçlar tek tek bize \(k\) defa tekrarlanan sayıyı verecek.

Genel çözümün kodu aşağıdaki gibi olacak.

Bu çözümde işaret bitini de dikkate aldığımız için bu çözüm negatif sayılar için de çalışacaktır.