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.

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