Odtü programlama yarışması 2009

http://www.cclub.metu.edu.tr/yarisma/2009/

sonuclar Finalistler açıklanmış, bu sene de odtü ye gidiyoruz bakalım ^^ Geçen senenin aksine iyi bir grup kurduk bakalım umutluyuz ama oraya gidince durumlar nasıl olacak.

Doğrusu öneleme sorularını biraz özensiz bulmuştum. Geçen sene ki neredeyse bütün sorular bir cinlik gerektiriyordu, bu sene ise 6 sorudan 3 ü çok basit bir biçimde çözülebiliyor. 1 tanesi ise verilen kısıtlamalarla çözülebilir gibime gelmedi. Diğer iki sorudan birisi baya meşhur bir problem, google da arama yapılınca çözüm yardım alınabilecek bir şeydi. Doğrusu tek bir soru benim hoşuma gitti =)

Game of Life! (msw logo üzerinde ^^)

Okulumuzun ilk döneminde bize öğretilen program idi msw logo. Yeni öğrenciler programlamaya giriş yapsın diye bu tip eğitim programları gösteriliyor.

Msw logo bir çizim programı denebilir, fakat kullanıcılar komut girerek çizim yapıyorlar.

logo2

Yukarıdaki üçgen (ismi turtle, eskiden hakikaten kaplumbağa şeklindeymiş ondan adı böyle =)) bizim kalemiz. Biz verdiğimiz komutlarla turtle ı hareket ettiriyor, döndürüyor ve çizim yapıyoruz. Yukarıdaki örnekte turtle karenin sol alt köşesinden başladı ve yukarı bakıyordu. fd 100 (forward 100) ile 100 pixel ileri gitti ve karenin sol kenarını çizdi. rt 90 üçgeni 90 derece saat yönünde döndürdü. Sonra gene fd 100 ile karenin üst kenarını çizdik. Yukarıdaki komutları takip ederek resimdeki şekli oluşturduk.

Kulağa komik bir program gibi gelebilir =), ama gayet geniş bir şey aslında. 3d çizim yapmaya izin veriyor mesela. İnternette araştırılırsa çok güzel çizimler sunan basit kodlar bulunabilir. Mesela bir örnek şu (tıklayarak büyük halini açın):

desen

Bu deseni ortaya çıkartan kod da şurada. Denemek için Edall a tıklayın, kodu yapıştırın, “save and exit” ile çıkın ve komut verilen yere “db 2 6” yazıp çalıştırın. Yapan arkadaş recursive in dibine vurmuş hakikaten.

Benimde yıllar sonra aklıma esti ve game of life ı msw logo üzerinde çalıştırayım dedim =D. Sonucu da burada

gameoflifemswlogo

Kaynak kodumuzda buradan alabilirsiniz.

http://www.shultays.com/gameoflifelogo.txt

Kullanmak için Edall butonuna tıklayın, açılan pencereye bu kodu yapıştırın ve “save and quit” ile pencereyi kapatın. Daha sonra komut yerine “gameoflife 16 16 100” yazarak game of life ı başlatabilirsiniz (ilk 16 değeri satır sayısı, ikinci 16 sütun ve 100 de toplam kaç generation yapılacak onun sayısı, isteğinize göre arttırıp azaltabilirsiniz)

Mswlogo yu indirebilmek için.

http://www.softronix.com/logo.html

Game of Life hakkında bilgi

http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life

Eski Odtü algoritma yarışması sorusu

Geçen yıl finalde sorulan sourlardan birisi o zamandan beri aklıma bir parça takılmıştır. Bir türlü nasip olmadı oturup uğraşmak.

Odtü lü arkadaşların soru için güzel bir hikayesi vardı, şimdi aklımda değil malesef.

Soruda bir input dosyasından dikdörtgen koordinatları okuyoruz (her dikdörtgen için sol-üst ve sağ alt köşenin koordinatları veriliyor). İstenen ise bu dikdörtgenleri tek renk bir kalem ile bir kağıda çizer ve boyar isek oluşan şeklin alanı.

Dikdörtgenlerin boyutlarunda ve koordinatlarında sınır olmadığı için (integer sınırlarında farzedin) “İki boyutlu bir array açayım, dikdörtgen olan yerleri 1 yapayım” gibi bir mantık işe yaramıyor.

Aklıma gelen bir çözüm yolu (ki obvious çözüm gibi bir şey) her yeni eklenen dikdörtgeni öncekiler ile karşılaştırmak ve eğer kesişiyorsa önceki dikdörtgeni kesişmeyen iki dikdörtgene bölmek. Örnek resim:

res11

Mesela soldaki örnekte b dikdörtgeni önceden gelmiş bir dökdörtgen. a ise yeni gelen dikdörtgen. Biz bu b yi şu şekilde ikiye bölüyoruz (Yazının bu kısmında l4d oynamak için ufak bir ara verdim, herkese tavsiye ederim bu oyunu =p)

res2b dikdörtgenini c ve d olarak ikiye ayırdık. Artık kesişme sorunu yok ve alan olarakta aynı alan. Elbette farklı şekilde de bölünebilirdi.

Bu bölme işleminden sonra a yı kalan dikdörtgenlerle (eğer kaldıysa) kontrol edeceğiz. Gerekirse yine aynı şekilde onları da böleceğiz. Her çakışma sonucu ikiye bölünecek diye bir şart yok. Eğer şanslı isek eski dikdörtgen yenisini kapsar ve daha fazla kontrole gerek kalmaz. Veya mesela şu örnek için:

res3Eğer yeni gelen dikdörtgen kırmızı olan ise sadece mavi dikdörtgenin kırmızı içinde kalan kısımlarını çıkartarak (mavi dökdörtgeni bir parça sol tarafından kırparak) çakışmadan kurtulabilirdik. Eğer yeni gelen mavi olan ise ve kırmızıyı bölmeye kalkarsa üçe bölmek zorunda kalacaktık. Bunun yerine algoritmayı biraz değiştirerek yine aynı şekilde maviyi (yeni gelen dikdörgeni) kırparak dikdörtgen sayısını azaltabiliriz. Yine aynı şekilde yeni gelen dikdörtgen eskini kapsıyor ise eskisini listeden çıkartabiliriz, bu durumda hala yeni dikdörtgeni kontrol etmek zorundayız ama en azından toplam dikdörtgen sayımız azaldı.

Yani en kötü ihtimalle her karşılaştırma için bir yeni dikdörtgen oluşturuyoruz. Aklıma gelen şu anlık tek çözüm bu, ama performansı konusunda şüphelerim var. Yani mesela n dikdörgen var ise, n+1 inciyi eklerken her karşılaştırma için 1 artar ise toplamda 2n+1 dikdörtgen olacak. Tabi bu çok uç bir input ve muhtemelen tek bir input dosyası içinde sayısının fazla olması imkansız. Alan hesaplamak içinde en sonunda tek tek bütün dikdörtgenlerin alanlarını toplayacağız.

Son zamanlarda da asıl aklıma takılan böyle bir algoritmanın complexity si ne olur. Yani bir kere O(n^2) den düşük olamayacak (sonuçta her yeni geleni bir öncekilerle kontrol ediyoruz). Ama devamlı dikdörtgenler bölüneceği için n^2 den yüksek bir complexity alması lazım gibi duruyor.

Yapılabilecek başka bir iyileştirme ise dikdörtgenleri sort sağ noktasının x koordinatlarına göre sort edilmiş şekilde tutmak. Eğer yeni dikdörtgenin sol noktasının x koordinatı, eskilerin sağ x ini geçer ise artık kalan dikdörtgenleri kontrol etmeye gerek kalmayacak. Eğer sorted bir şekilde tutar isek dikdörtgenleri linked list yapısında saklamak daha mantıklı çünkü bölünen yeni dikdörtgenler (ve yeni gelen dikdörtgenler) devamlı araya girmeye kalktığında array i shift etme zorluğu yaşamayalım. Bu ayrıntıyıda algoritmaya eklersek bariz bir şekilde iyileştirme sağlayacaktır (eğer bölünme olmasaydı O(nlogn) olacaktı, ama tabi gerçek complexity yi hesaplamak çok daha fazla karıştı =D).

Bu sorunun ikinci kısmı ise çevre hesaplamak idi (sadece şeklin etrafını çevreleyen değil, içerde boşluk varsa o boşluğunda çevresi de hesaba katılacak). Çevrenin tek farkı ise şu. Önce yine aynı şekilde dikdörtgenler kesişmeyecek şekilde oluşturacağız. Sonra her dikdörtgenin çevresini bir toplam çevre değerine ekleyeceğz. Daha sonra, dikdörtgeni bir önceki dikdörtgenler ile karşılaştıracağız, eğer iki dikdörtgen teğet ise ne kadar uzunlukta teğet olduğunu bulacağız ve o değerinin iki katını toplamdan çıkaracağız.

res4 Mesela a ve b nin çevreleri A, B ise ve sarı çizginin (teğet olan kısım) uzunluğu L ise toplam çevre.

Çevre = A + B – 2*L

olacak.

Henüz daha iyi bir çözüm aklıma gelmedi, olabilir diye umuyorum. Algoritmayı koda dökmeye hep üşeniyorum. Çok fazla ağır gibi durmasada iki dikdörtgenin karşılaştırılması ve bölünmesi baya zor olacak gibi duruyor, bir çok ihtimal var sonuçta. Belki daha iyi bir tane bulunabilir bilmiyorum. Odtü finalinde çok kötü bir algoritma yazmıştım, kesişen her iki dikdörtgen için kesişen alanı çıkarıyordu. Ama mesela 3 dikdörtgen aynı noktada kesişirse o durumda patlıyordu. Belki bu algoritma biraz geliştirilerek doğru sonuç verecek bir şeye çevrilebilir belli olmaz.