Euler Totient ve Eratosthenes'in Kalburu

Project Euler'deki 72. soruyu çözmek için 2'den n'e kadarki sayıların Euler Totient değerlerini hesaplamak gerekiyor. Düz bir mantıkla, n'den küçük veya eşit tüm asal sayıları hesaplayıp her sayı için Euler formülü ile sonucu hesaplamak mümkün. Aşağıda bu yöntemin kodu var;

Burada asal sayıları ayrı bir listede tutmak gerekli değil. Bunun yerine, sieve  listesini kullanarak totient değerini aşağıdaki gibi hesaplayabiliriz;

Her iki kod da hemen hemen aynı complexity değerlerine sahip ama ikincisi daha kısa :).

Project Euler 113

Sabahlama rutinimin son adımı olarak uyumadan önce bir tane Project Euler sorusu çözüyorum :) Bugünün talihlisi de bu soru.

112379 ya da 98760 gibi, basamaklarındaki rakamların, artan ya da azalan şekilde, sıralanmış hali kendisine eşit olan sayılara monoton sayılar diyelim (her ne kadar soruda böyle bir tanım olmasa da :)). \(10^{100}\)'den küçük kaç tane monoton sayı vardır?

Sorunun çözümünü bulmak için ilk önce kaç tane monoton sayı olduğunu bulmamız lazım. Sonrasında bu toplamdan, her iki durum için de \(11, 1111...\) gibi tüm basamakları birbirine eşit olan sayılar tekrar ettiği için basamak sayısı * 9'u yani \(900\)'ü çıkaracağız.

Artan monoton sayılar: 

\(n\) basamaklı bir sayının artan monoton bir sayı olması için, \(n\). basamağa gelen sayının \(n-1\). basamaktaki sayıdan büyük ya da eşit olması ve sonuna eklendiği \(n-1\) basamaklı sayının da monoton artan bir sayı olması lazım. İlk durum olarak, \(0\) dışındaki her bir sayının monoton artan olduğunu düşünelim. Bu sayede, aşağıdaki fonksiyon ile artan monoton sayıların kaç tane olduğunu bulabiliriz;

\[F(n, digit) = \begin{cases}0, digit = 0 \\ 1, digit > 0 \& n = 0 \\ F(n-1, digit) + F(n, digit - 1), digit > 0 \& n > 0 \end{cases}\]

Azalan monoton sayılar: 

Artan monoton sayılara benzer bir şekilde, \(n\) basamaklı bir sayının azalan monoton sayı olması için, eklenen sayının \(n-1\). basamaktaki sayıdan küçük ya da eşit olması ve sonuna eklendiği \(n-1\) basamaklı sayının da azalan monoton olması gerekmektedir. Bu sayıları da aşağıdaki fonksiyonla bulabiliriz;

\[G(n, digit) = \begin{cases}0, digit = 0 \& n = 0\\ 1, digit = 9 \\ G(n-1, digit) + G(n, digit + 1), digit < 9 \& n > 0 \end{cases}\]

Tüm sayıların toplamını ise

\[\sum\limits_{i=0..100, j=0..9} F(i, j) + G(i, j)\]

ile bulabiliriz.

Project Euler 205

Bu Project Euler sorusu çok kısa; 2 adam var biri Peter diğer Colin. Peter'ın elinde 9 tane, yüzlerinde 1, 2, 3 ve 4 yazan piramit şeklinde zar, Colin'in elinde de 6 tane, üzerinde 1, 2, 3, 4, 5 ve 6 yazan kübik zar var. Zarlardaki olasılıkların uniform olduğunu yani her zardaki sayıların olasılıklarının birbirine eşit olduğunu düşünüyoruz. İki arkadaş da ellerindeki tüm zarları atıyorlar. Zarların toplamına bakıldığında Peter'ın Colin'den fazla puan alma olasılığı nedir?

Peter'ın alabileceği puanlar \([9, 36]\), Colin'in alabileceği puanlar ise \([6, 36]\) aralıklarında değişiyor. Eğer her bir oyuncunun hangi puanı hangi olasılıkla aldığını hesaplarsak Peter'ın Colin'i yenme olasılığı da (\(P(x)\) Peter'ın \(x\) puan alma, \(C(y)\) ise Colin'in \(y\) puan alma olasılığı olmak üzere)

\[\sum\limits_{x=9}^{36} P(x) \sum\limits_{y=6}^{x-1} C(y)\]

formülüyle hesaplanabilir.

Bunun için önce her bir puanın olasılığını hesaplamak lazım. Peter için \(4^9\), Colin içinse \(6^6\) farklı çözüm olduğundan her çözümü tek tek hesaplamak mantıklı değil. Bunun yerine şöyle bir yöntem kullanabiliriz;

Elinde 1 zar bulunduğunu düşünürsek Peter'ın 1, 2, 3, 4 puan alma olasılıkları eşit ve \(P_1(1) =P_1(2) =P_1(3) =P_1(4) = 0.25\) olacaktır. 2. zar atıldığında ise, eski çözümler \(0.25\) olasılıkla 1, 2, 3 ya da 4 olarak artacaktır. Bu durumda ikinci zar ile \(k\) puan kazanma olasılığı \(P_2(k) = 0.25 (P_1(k-1) + P_1(k-2) + P_1(k-3) + P_1(k-4))\) olacaktır. Bu hesabı \(k\) yüzlü \(n\) zar için yapan ve olasılık dağılımını dönen kod aşağıda:

Bu fonksiyon ile Peter ve Colin'in olasılık dağılımını hesapladıktan sonra bunları kullanarak sonucu bulabiliriz.

(main fonksiyon, işlem tekrarı yapmamak için Colin'in kümülatif dağılımını hesaplıyor).

İyi ki açıldın Project Euler :)

Project Euler 121

Bugün, 300 küsur gün sonra ProjectEuler'e bir bakayım dedim. "Unlucky Squares" denen rozeti de almak için 121. soruyu çözmeye çalıştım.

Soruda rastgele diskleri bir torbadan çektiğimiz bir oyun var. Başlangıçta torbada 1 kırmızı 1 de mavi disk var. Her elde torbadan rastgele bir disk seçip torbaya geri atıyoruz. Bunun dışında, her adımda torbaya bir tane de kırmızı disk atıyoruz. Önceden belirlenen kadar adım sonra eğer çektiğimiz mavi toplar kırmızılardan fazlaysa kazanıyoruz. Her oyuncunun oyuna girmeden önce 1£ verdiğini düşünürsek, kazanan oyuncunun ödülü ne kadar olmalı ki kasa zarar etmesin?

Kağıt üzerinde hesabı şöyle; ilk adımda 2 olasılık var, sonrasında bu \(3, 4, ..., n\) olarak artıyor. Her seferinde sadece 1 mavi top olduğu için \(n\) el sonunda \(k\) kez mavi top çekme olasılığı

\[S(n, k) =\frac{1^k F(n, n - k)}{(n+1)!} \]

olacak. Burada \(F(a, b)\), 1'den \(a\)'ya kadar olan tamsayıların bulunduğu kümedeki \(b\) elemanlı altkümelerin elemanları çarpımının toplamı oluyor. Böyle bir fonksiyona ihtiyaç duymamızın sebebi ise, farklı adımlarda kırmızı çekme olasılığının, torbaya her seferinde bir kırmızı disk daha eklediğimiz için değişmesi (artması). Mesela 3 adımlı oyun sonunda 2 defa kırmızı çektiğimiz durumlar

M-K-K, K-M-K, K-K-M

olabilir. İlk durumun olasılığı

\[\frac{1}{2}\frac{2}{3}\frac{3}{4} = \frac{1}{4} \]

iken ikinci durumun olasılığı

\[\frac{1}{2}\frac{1}{3}\frac{3}{4} =\frac{1}{8} \]

üçüncü durumun ise

\[\frac{1}{2}\frac{2}{3}\frac{1}{4} =\frac{1}{12} \]

olacaktır.

Bunu adım adım hesaplamaktansa kapalı bir formülü var mıdır diye araştırırken Quora'da bu sonucu Stirling Sayıları benzeri bir yöntem ile hesaplayabileceğimi öğrendim. \(F(a, b)\) sayısını iki kısımda hesaplayabilirim;

- \(a-1\) elemanla oluşturulmuş \(b\) elemanlı sonuçlar.

- \(a-1\) elemanla oluşturulmuş \(b-1\) elemanlı sonuçlar.

İlk kısım olduğu gibi alınabilir. 2. kısım'daki tüm kümelere \(a\) elemanını eklersek bu kümeleri de sonuca ekleyebiliriz. 2. kısımdaki sonuç \(a F(a-1, b-1)\) olacaktır. Böylece \(F(a, b)\)

\[F(a, b) = F(a-1, b) + a F(a-1, b-1)\]

olacaktır.

Oyuna geri dönersek, tüm olasılıklar içinde oyuncunun kazanacağı oyunların sayısını bu yöntemle basitçe hesaplayabiliriz. Sonrasında hesaplamamız gereken nokta ise ödülün ne kadar olması gerektiği. \(n\) adım sonrası oyuncunun kazanma olasılığına \(x\) diyelim. \(y\) de ödül olmak üzere şu eşitliği yazabiliriz;

\[x(y-1) - (1-x) = 0\]

\(x\)'i daha önce hesapladığımıza göre \(y\) de kolayca hesaplanabilir.

Soruyu çözen kod aşağıdaki gibi

 

Kısa bir soru

Arada bir teknik mülakatların sorularını inceliyorum. Bazıları basit olsa da nedense bir hoşuma gidiyor. Bu da onlardan bir tanesi :)

Bu soruyla bir tane teknik mülakatta karşılaşmıştım. Sonrasında mülakat sorularını incelerken bir yerde daha denk geldim. Sorunun kendisi gayet kısa, verilen bir dizide toplamları N'e eşit olan alt dizilerin sayılarının bulunması isteniyor.

Misal elimizdeki dizi [1, 23, -5, 7, 21, 3, 3, 2, -5], toplam olarak istenen N değeri de 23 olsun.

En basit çözüm olarak aşağıdaki çözüm verilebilir.

 

Bu çözüm tüm index çiftleri için toplamı hesaplayıp, toplam N'e eşitse sonucu 1 arttırıyor. \(O(n^3)\)'lük bir çözüm, bu yüzden büyük diziler için çok da güzel bir çözüm değil. Aşağıdaki çözüm ise kümülatif toplamları tuttuğundan çözümü en içteki for'dan kurtarıyor ve complexity \(O(n^2)\) oluyor.

 

Bu iki çözümü de \(O(n)\)'e yaklaştırmak istiyoruz. Kümülatif toplamları hesapladığımıza göre, totals dizisinin i. elemanı için yapmamız gereken (aslında 2. çözümde de yaptığımız) kümülatif toplamı totals[i] - N olan elemanların sayısını bulmak. Bunun içinse tekrar tekrar lineer arama yapmamıza gerek yok.

 

Son çözümde, her kümülatif toplamdan önceki toplamları bir hashtable'da tuttuk. Böylece, istenen değerlerinin sayısını O(1) zamanda hesaplayabiliyoruz. \(O(n)\) zaman da diziyi dolaşmakla geçiyor ve son çözümün complexity'si \(O(n)\) oluyor.

Umarım bir hata yapmamışımdır :)