Project Euler #53

Birilerinin Project Euler sorularının cevaplarını yayınladığını öğrendiğimde öfkelenmiştim. Ben adım adım çözerek yükselirken birileri siteye girip “çat çat” cevapları vererek listede yükselebiliyordu. Sonra düşündüm ki, bana ne? Project Euler insanın kendini geliştirebilmesi ve zaman geçirebilmesi için yaratılmış bir site. Ben aşağıda #53’ün cevabını yazacağım. Yani şimdiden bir spoiler ibaresi koyuyorum. 🙂 İstemeyen bakmaz.

Soru #53, bizden 1<= n <= 100 aralığında kaç tane C(n,r)’nin 1 milyondan yukarda olduğunu soruyor. Distinct value bulmaya gerek yok, basit bir brute force ile sonuca gidilebilir. Kombinasyon hesaplama işi bilgisayarı uzun süre meşgul edebiliyor, çünkü kombinasyon belli sayıların faktöriyellerine bakılarak bulunuyor:

C(n,r) = n! / r!(n-r)!

O nedenle gerektiği yerde bu faktöriyel sonuçlarını cachelemeye karar verdim. Sonuç olarak, aşağıdaki kodla çift çekirdekli 2.4 GHz makinede 0.15 saniyelik bir runtime ile cevaba ulaştım. Project Euler’de diğer cevaplara baktığımda daha verimli algoritmalara da ulaştım, bazıları Pascal Triangle kullanmış – ki bence mükemmel bir fikir. Ama benim algoritmam da hızlı bir şekilde sonuca ulaştırdı.

import sys
import math
import time
 
## author: Ekin Ocalan
## date: Mar 14, 2013
## project euler #53
 
fact_results = []
 
def fact(i):
	if i == 1:
		return i
	elif i &lt; 1:
 		return 1
 	else: 		return i * fact(i-1) 
 
def comb( i, j):
 	global fact_results
 	if fact_results[i] == 0:
 		fact_results[i] = fact(i)
 	if fact_results[j] == 0:
 		fact_results[j] = fact(j)
 	if fact_results[i-j] == 0:
 		fact_results[i-j] = fact(i-j) 	return fact_results[i] / (fact_results[j] * fact_results[i-j]) 
 
def main():
 	global fact_results
 	count = 0
 	for i in range(101):
 		fact_results.append(0)
 	for i in range(23,101):
 		for j in range(1,i+1):
 			if comb( i, j) &gt; 1000000:
				count += 1
				print 'found one on %d.C.%d' % (i,j)
 
	print 'finished. total: %d' % (count)
 
if __name__ == '__main__':
	start_time = time.time()
	main()
	print time.time() - start_time, "seconds"

Project Euler ve Asal Sayılar

Asal sayılara karşı tuhaf bir ilgim var. Otomattan yiyecek ya da içeçek seçerken dahi asal sayıdan seçmeye nedense özen gösteriyorum, hoşuma gidiyor.

Project Euler ise projecteuler.net adresinde yer alan, matematik ve kodlama egzersizi yapabileceğiniz hoş bir web sitesi. Şu anda 417 adet farklı probleme ev sahipliği yapmasının yanında her hafta yeni bir problem de ekleniyor. Zamanında ilk 50 problemi çözmüş ve bırakmıştım. O zamandan beri aklımın bir köşesinde hep dönüp problemlerin tümünü bitirmek vardı. Geçen haftalar içerisinde ise bu amacıma ulaşmak için problemleri çözmeye devam etmeye başladım.

Gelelim Project Euler ile asal sayılar arasındaki ilişkiye ve bu yazının asıl konusuna. Project Euler’de çözdüğüm birçok problemin içinde asal sayıların bir şekilde kullanımı mevcut. Problemler, çözen kişiyi time and space‘de optimizasyona yönelttiği için (milyonlar ve hatta milyarlara ulaşan sayıları bazen tek tek kontrol etmeniz gerekebiliyor) kullandığınız dilin de, algoritmanın da önemi büyüyebiliyor. Algoritmaya fazla önem vermeden problemleri çözen kişilerin genel olarak dil tercihi Assembly bile olabiliyor – ki bu bana düşünülmeden yazılmış kodlara yol açtığı için inanılmaz saçma geliyor. High-level bir programlama dili ile yazılmış, iyi tasarlanmış bir algoritmayla, Project Euler’in kendisinin de söylediği gibi soruları 1 dakikanın altında bir sürede çözmek neredeyse kesin. Problemler bu bağlamda tasarlanıyor.

Çözdüğüm ilk 50 soruda kullandığım asal sayı algoritmalarının (bir sayı asal mı değil mi) hiç de verimli olmadığını, problemleri çözmeye devam etmeye başladığım birkaç hafta öncesinde fark ettim. True ya da False döndüren küçük isPrime fonksiyonumun içinde sayıyı 2 ile kendisi arasında bir döngüye alıp kontrol ediyordum. Oysa ki buna gerek yokmuş; 2 ile sayının (bu sayıya x diyelim) karekökü arasında döngüye almak yeterli oluyor. Bunun sebebi de eğer x’in karekök(x)’ten büyük bir böleni (q diyelim) varsa (x=q*p), p sayısı karekök(x)’ten küçük oluyor. Böylece kontrol edilmesi mecburi olan sayılar azalıyor. Aşağıda örnek bir Python kodu var:

import math
 
## author: Ekin Ocalan
## date: Feb 3, 2013
## project euler #51
 
def is_prime(n):
	for i in xrange( 2, int(math.floor(math.sqrt(n)))):
		if n%i==0:
			return False
	return True

Fractional Knapsack Problem

Algoritma dersi alırken bir hafta Knapsack Problem ile ilgili küçük bir araştırma yapmıştım. Türkçe kaynak pek yoktu, İngilizce olaraksa basit bir dil kullanan çok az sayıda yayın buldum. Bunlardan birini de University of Nebraska-Lincoln’ün Computer Science dekanı Dr. Steve Goddard’ın dersi için hazırladığı sunumlardan birinde buldum. Oldukça basit bir şekilde 0/1 Knapsack Problem’ı açıklamış. Üstüne biraz daha araştırma yaparak Knapsack Problem üzerine çalıştım ve algoritma anlatımını daha da basitleştirdim. Sonra da hem Türkçe bir kaynak bulunması için, hem de kendime ilerde referans olarak bırakmak için buraya yazmaya karar verdim. 🙂

Knapsack Problem’ın iki çeşidi var. İlki, Dynamic Programming ile çözülen 0/1 Knapsack Problem. İkincisi de Greedy Algorithm ile çözülen Fractional Knapsack Problem. Fractional Knapsack Problem çok daha kolay. O nedenle öncelikle Fractional’ın üstünden geçeceğim, sonra da 0/1’ı daha detaylı bir şekilde anlatacağım. Ama öncelikle bilmeyenler için Knapsack Problem’ın biraz üstünden geçelim. Bu problemde elimizde sınırlı hacme sahip boş bir çanta var. Bu çantaya, elimizdeki çeşitli hacimdeki ve değerdeki eşyaları sığdırmaya ve bu yerleştirmeden maksimum değer elde etmeye çalışıyoruz. Yani amacımız çantamızı doldurarak maksimum değeri elde etmek. Değişkenlerimiz: Çantanın toplam hacmi (W), eşyalarımızın hacimleri (w_i) ve eşyalarımızın değerleri (b_i). Burdaki “i”yi, eşyalarımızın bir nevi id’si olarak düşüneceğiz. Yani 2 numaralı eşyamızın hacmi w_2, değeri de b_2 değişkeniyle anılacak. Devam edecek olursak…

Fractional Knapsack Problem, eşyaları bölerek kullanmamıza izin verir. Yani hacmi 6 olan bir eşyayı çantaya tüm olarak koymak zorunda değiliz. 2/3’ünü alıp çantaya koyma imkanımız var. Peki bunun bize ne gibi bir faydası olabilir? Diyelim ki çantamızı son eşyaya kadar doldurduk ve çantamızda 4 hacimlik yer kaldı. Kullanabileceğimiz son eşyamızın da hacmi 6. Yani eşyayı olduğu gibi yerleştiremiyoruz. Biz de eşyanın 2/3’ünü alıp çantaya koyuyoruz. Böylece eşyanın değerinin 2/3’ünü de çantamızın getireceği değere ekleyebiliyoruz. Çok basit.

Şimdi küçük bir örnek yapalım. Aşağıda her birinin hacim ve değerleri verilen 4 eşyamız var. Çantamızın hacmi de, W = 6.

Hacim (weight); Değer (benefit)

w_1 = 3; b_1 = 5
w_2 = 2; b_2 = 3
w_3 = 1; b_3 = 0.5
w_4 = 2; b_4 = 2

Açıkça görüldüğü üzere üç eşyanın toplam hacmi 8, yani çantaya hepsini koyamıyoruz. Yapacağımız ilk işlem, her bir eşyanın göreceli değerlemesini bulmak. Bunun için hacim başına düşen değeri bulacağız. Biz buna kazanç (n_i) diyelim.

n_1 = b_1 / w_1 = 5/3
n_2 = b_2 / w_2 = 3/2
n_3 = b_3 / w_3 = 0.5/1 = 1/2
n_4 = b_4 / w_4 = 2/2

Görüldüğü üzere n_1 > n_2 > n_4 > n_3. Bu sıralama, bizim eşyaları çantaya koyma sıralamamız. Çantada yer oldukça koymaya çalışacağımız eşya önce 1 numara, sonra yer kalırsa 2 numara, sonra yine yer kalırsa 4 numara, sonra yine yer kalırsa 3 numara.

1 numaralı eşyayı çantaya koyduk. Çantanın kalan hacmi: 3. Elde ettiğimiz toplam değer: 5.
2 numaralı eşyayı çantaya koyduk. Çantanın kalan hacmi: 1. Elde ettiğimiz toplam değer: 8.
4 numaralı eşyayı çantaya koyamadık. Çünkü çantanın kalan hacmi 1, sıradaki eşyanın (4 numara) hacmi 2. Burda dikkat etmemiz gereken şey, 3 numaralı eşyanın hacmi 1 olmasına rağmen bu eşyayı değil, hacmi 2 olan 4 numaralı eşyayı koymak istiyoruz. Çünkü 4 numaralı eşyanın 1 hacminden kazanacağımız değer daha fazla. Çantanın kalan hacmi 1 ise, biz de 4 numaralı eşyanın 1 hacmini alıp çantaya koyuyoruz. Bu hacim bize 1 değer getirecek.

Çantanın kalan hacmi: 0. Elde ettiğimiz toplam değer: 9.

Böylece çantamızı optimal şekilde doldurmuş olduk. Çantaya koyduğumuz eşyalar 1 ve 2’nin tamamı ile 4’ün bir kısmı. Elde ettiğimiz toplam değer ise 9 oldu. Bu çözüm için pseudo-code vermiyorum, çünkü oldukça basit.

Aslında 0/1 Knapsack Problem’ı da bu postta anlatacaktım ama yazacak pek gücüm kalmadı. Önümüzdeki günlerde 0/1 yazısı da gelecek.

Dipnot 1: Aslında weight’in türkçesi “ağırlık” anlamına geliyor ama ben hacim demeyi tercih ediyorum.

Dipnot 2: Dr. Steve Goddard’ın orijinal sunumuna ulaşmak için buraya tıklayabilirsiniz.