2004 yılında ODTÜ Bilgisayar Topluluğu'nun düzenlediği Üniversite Öğrencileri Arası Programlama Yarışması'nda finale kalmıştım. Eleme sorularından biri olan Bilye sorusunun çözümü hakkında yıllar önce bir yazı yazmıştım. Zaman su gibi akıp geçmiş. O zamanki çözümüm C dilindeydi. Bugün ise Scala dili ile gerçeklediğim çözümü paylaşmak istedim. Hem anılarımı tazeledim hem de kod yazdım, eğlendim.
Sorunun tanımı şöyle:
Eski çağlarda Zekado ülkesinde şöyle bir oyun oynanırmış:
Çözümün ayrıntısı daha önce yazdığım yazıda mevcut olduğu için bu yazıda pek fazla ayrıntıya girmeyeceğim. Genel anlamda çözüm için yıllar evvel olduğu gibi Sprague-Grundy teoreminden faydalandım. Her bir durum için bir SG(p,q) = t değeri tanımladım. Kazanan durumda t=1, aksi halde t=0 olduğunu kabul edelim. SG(p,q) durumu ortadan q tane bilye aldım, p tane bilye kaldı anlamına gelsin. Bu durumda ben kazanıyorsam SG(p,q) = 1, aksi halde SG(p,q) = 0 olsun. Kod aşamasını kolaylaştırmak amacıyla 0 ve 1 değerleri yerine sırasıyla false ve true değerlerini kullandım.
İşe verilen p ve q değerleri için Grundy sayısını hesaplayan fonksiyonu yazarak başlayalım. p=0 olan durumlar her zaman kazanan durumdur çünkü ortada bilye kalmamıştır. p ≤ 2 * q olan durumlar kaybeden durumdur çünkü q tane bilye alıp p tane bilye bıraktığımızda rakip 2*q kadar bilye alma hakkına sahip olacaktır. Kalan bilye sayısı yani p değeri 2*q değerine küçük ya da eşit ise rakip tüm bilyeleri alarak oyunu kazanacaktır. Kalan durumlar için ise şu kural geçerli olacak: herhangi bir durum için, o durumdan sonra rakip mümkün tüm hamleler için kaybediyorsa, o durum kazanan durumdur. Aksi halde, yani rakip mümkün hamlelerin yalnızca birinde bile kazanıyor olsa, o durum kaybeden durumdur.
1
2
3
4
5
6
def spragueGrundy(p: Int, q: Int) = {
if (p == 0) true
else if (2 * q < p) {
(q + 1 to 2 * q).foldLeft(true)((a, b) => a & !spragueGrundy(p - b, b))
} else false
}
Yukarıdaki kod belki biraz karışık görünebilir ama daha önce bahsettiğimiz kuralları işletmekten başka bir şey yapmıyor. 4. satırda p değeri 2*q değerinden büyük ise rakip q+1 ile 2*q kapalı aralığındaki muhtemel hamlelerinin tümünde kaybediyorsa true dönüyor. Özyinelemeli bu fonksiyonun aynı değerleri tekrar hesaplamasını engellemek için bir önbellek kullandım. Fonksiyonun önbellekli hali ise şöyle oldu.
val onbellek = collection.mutable.Map[(Int, Int), Boolean]()
def onbellekliSpragueGrundy(p: Int, q: Int): Boolean = {
onbellek.getOrElseUpdate((p, q), spragueGrundy(p, q))
}
def spragueGrundy(p: Int, q: Int) = {
if (p == 0) true
else if (2 * q < p) {
(q + 1 to 2 * q).foldLeft(true)((a, b) => a & !onbellekliSpragueGrundy(p - b, b))
} else false
}Kodun tümü için bir gist hazırladım. Böylece paylaşılması ve iyileştirilmesi çok daha kolay olacaktır. Çözüm için önerileriniz var ise dinlemekten memnun olurum.
Follow me on Twitter