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

 

Matplotlib ile İlgili Bir Not

2-3 haftadır falan Matplotlib'i kullanarak bir proje geliştirmeye çalışıyorum. Proje çeşitli robot hareket ve sensör modellerini içerecek bir simulator aslında (Aşağıdaki görüntüde odometri modeli var).

ss

 

Burada, özellikle sampling ile çalışırken her dağılım için epey bir nokta çizdirmek gerekiyor. Ben ilk yazdığımda çok dikkat etmediğim için aşağıdaki gibi bir kodla çizdiriyordum:

Sonradan ortaya çıktı ki, meğerse bu plot fonksiyonu epey maliyetliymiş. Bu yukarıdaki kod netbookumda 17 sn.'de çalışıyor mesela. Aşağıdaki yöntemin ise bir öncekiyle arasında baya bir performans farkı var:

Bu da 0.01 sn gibi bir sürede çalışıyor.

Demek ki neymiş; ne kadar az plot çağırırsak o kadar iyiymiş :).

Yol Bulma Algoritmaları ve Jump Point Search

Grid yapılarında en kısa yolu bulmak için klasik arama algoritmaları kullanılabilir. Bunlar Depth-First Search (DFS) gibi uninformed, yani arama stratejisi hedefin konumuna göre değişmeyen algoritmalar olabileceği gibi A* gibi informed algoritmalar da olabilir.

DFS optimal bir algoritma olmamasıyla, Breadth-First Search (BFS) ise bellek kullanımının üstel olmasıyla arama ağacının derin olduğu durumlar için uygun değildir. Pratikte bu tarz bir problemde kullanmayacak olsak da en azından karşılaştırma yapmak için bu algoritmaların sonuçlarını da ekledim.

A* algoritması, heuristic fonksiyonlar kullanarak optimal sonucu elde eder. Yapı olarak Best-First Search algoritmasının modifiye edilmiş halidir, yani o an için elindeki hedefe en yakın node hangisiyse onu seçip ilerler. Best-First Search'ten farkı ise bunu sadece heuristic (\(h(x)\)) fonksiyonu kullanarak değil, o ana kadarki maliyeti de (\(g(x)\)) tutarak

\[f(x) = g(x) + h(x)\]

fonksiyonu ile yapar. Wikipedia sayfasındaki Optimality bölümünde, doğru heuristic fonksiyonla nasıl en iyi çözümü bulduğu daha ayrıntılı olarak okunabilir.

A* algoritmasının bir özelliği de çözüme birer adım atarak yaklaşmasıdır, bu özelliği yüzünden çok fazla node'u ziyaret edebilir. Grid yapıları düşünüldüğünde, önünde herhangi bir engel olmayan büyük bir boş alanda her noktada durup tekrar tekrar baştan yol planlamanın bir anlamı yoktur. Jump Point Search ise A*'ın bu özelliğinin iyileştirilip bellek kullanımının ve çalışma zamanının iyileştirilmiş bir versiyonudur.

Jump Point Search kısaca prune (budama) ve jump adımlarından oluşur.

- Prune: Buradaki temel varsayım şudur. \(x\) o an bulunulan konum ve \(parent(x)\), \(x\)'ten bir önceki konum olmak üzere; \(parent(x) -> x -> y_i\) şeklinde, \(parent(x)\)'ten başlayıp \(y_i\)'de biten iki adım atıldığında, \(y_i\)'ye ulaşan en kısa yolların hepsi \(x\)'ten geçiyorsa \(y_i\) değerlendirmeye alınır, diğer node'lar yoksayılır. Eğer \(x\)'in etrafındaki bir engelden dolayı \(y_i\) bu kümeye dahil oluyorsa \(y_i\) forced (zoraki) komşu, eğer her koşulda dahil olan bir node ise doğal komşu olarak adlandırılır.

- Jump: \(x -> y_i\) doğrultusunda, \(y_i\)'nin herhangi bir zoraki komşusu yoksa, bir adım daha atılabilir.

Algoritmanın detayı buradan okunabilir.

Denerken kullandığım şekil aşağıdaki gibi. Siyah kutular duvar, mavi kutu başlangıç ve kırmızı kutu da bitiş noktası olarak alınıyor.

 

figure_1

Depth first search bu harita üzerinde aşağıdaki gibi bir yol izleyecektir. Bulduğu çözüm beklendiği gibi optimal değil.

figure_2

BFS, A* ve Jump Search ise optimal çözümlere ulaşacaktır.

figure_3

DFS dışındaki algoritmaların hepsi aynı performansı göstermiş gibi görünse de, aşağıdaki tablodaki node expansion sayıları ile fark anlaşılabilir.

 

Algoritma Mesafe Node sayısı
DFS 10.65 12
BFS 8.07 24
A* 8.07 17
JPS 8.07 9

Matplotlib ile İki Değişkenli Normal Dağılımların Gösterimi

Olasılıksal süreçlerde, iş olasılık dağılımlarının gösterimine geldiğinde iki yöntem kullanabiliriz;

  • Sampling, yani dağılımdan veri üretilmesi.
  • Contour ya da heatmap denilen, örnekleme yapmadan gösterim.

Sampling yaklaşımının gösterilmesi diğer yönteme göre daha basittir. Hesaplamaları yaptığımız ortamlarda (scipy, MATLAB vs.) Gauss dağılımına göre rastgele sayı üretme fonksiyonu bulunduğundan, tek yapılacak iş belirli bir örnek sayısı kadar rastgele sayıyı bu dağılımdan üretmek olacaktır.

Elimizde

\[\mu = (4, 4)^T\]


ve

\[\sum = \begin{pmatrix}3 & 0.4 \\ 0.4 & 0.15\end{pmatrix}\]

parametrelerine sahip bir Gauss dağılımı olsun. Örnek sayısı 200 olmak üzere, Sampling yöntemini kullanırsak grafik aşağıdaki gibi olacaktır (kırmızı nokta ortalama noktasını göstermektedir).

sampled

Örnek sayısı arttıkça üstteki grafik gerçek dağılıma daha çok benzeyecektir.

Sampling yöntemi varyansla ilgili bir fikir verse de, grafiği daha anlaşılır yapmak için contour yöntemi kullanılır. Bu yöntem, 3 boyutlu ortamda Gaussian dağılıma tepeden bakmak olarak da tanımlanabilir. Grafiğin renkleri olasılığın değerine göre değişecektir.

direct

Bu grafikte büyük olasılık değerleri siyah renge yakın olarak gösterilmektedir.

Matplotlib'de bu tip grafikleri oluşturmak için, pyplot  içindeki  pcolormesh fonksiyonu kullanılır. Bu fonksiyon, grafik üzerindeki bir dikdörtgenin içerisinde bu işlemi yapar ve yapabilmek için bu dikdörtgenin her bir hücresine denk gelen \(x\), \(y\) ve \(p(x, y)\) değerlerini birer matrix olarak alır. Yukarıdaki grafiği çizen kod parçası aşağıdaki gibidir.

 

Grafiğe verilecek diğer colormap değerleri http://wiki.scipy.org/Cookbook/Matplotlib/Show_colormaps adresinden görülebilir.