Exact Cover, Dancing Links ve Sudoku Çözme

Donald Knuth tarafından geliştirilmiş olan "Dancing Links" algoritması, "exact cover" problemi ve bu probleme çevirilebilen sudoku gibi problemlerin çözümü için bir hayli etkin bir yöntem sunuyor. Bu yazıda, "exact cover" problemi, "dancing links" algoritması, sudoku probleminin exact cover problemine dönüştürülmesi konularından bahsedeceğim. Ayrıca, Ali Assaf tarafından "Algorithm X in 30 lines!" yazısında bahsedilen yönteme kısaca değineceğim.

Devamını oku…

Bir optimizasyon hikayesi

Birazdan okuyacaklarınız, Python'da yazdığım basit bir fonksiyonu optimize etme hikayemdir.

Çözmeye çalıştığım problem şu; bir string ve alt string verildiğinde, büyük string'in hangi indexlerindeki karakterleri birleştirerek alt string'i elde edebileceğimi bulan bir algoritma yazmak. Örneğin, büyük string "yasar arabaci", küçük string de "aa" olduğu zaman, algoritmanın vereceği sonuç [(1, 3), (1, 6), (1, 8), (1, 10), (3, 6), (3, 8), (3, 10), (6, 8), (6, 10), (8, 10)] olmalı. Örnekten de anlayacağınız üzere, alt stringi oluşturmak için, büyük string'den alacağım karakterlerin sırasının değişmesini istemiyorum. Diğer bir deyişle, sonuçlar içinde (3,1) istemiyorum.

Bu problemi çözmek için yazdığım ilk algoritma şu oldu:

Devamını oku…

Pixel Sıralama Videoları

Geçen gün Python ile tersine erime efekti yazısını gördüm. Yaptığı şey çok hoşuma gitti, ben de özendim, o tarz birşey yapayım dedim. Tam olarak ne yapsam diye düşünürken, aklıma sorting algoritmaları geldi. Sort algoritmalarını bir resim üzerinde uygulasam ve ara adımlardan bir video oluştursam ilginç olabilir diye düşündüm, ve çeşitli sıralama algoritmaları ile birkaç video hazırladım. Buyurun bakalım, umarım beğenirsiniz:

Devamını oku…

Neden str toplamamalısınız

Günlerden pazar, bir yandan çay içip bir yandan Python kurcalarken, aklıma döngü optimizasyon yöntemlerini denemek geldi. Daha önce bir yerde gördüğümü hatırladığım için, bir liste içindeki int'leri karaktere dönüştürüp, bir str içinde birleştirmeyi deniyorum. Bu yöntem bu kadar hızlı, şu yöntem bu kadar yavaş derken, acaba str objelerini + ile toplamak ne kadar kötü olabilir ki diye merak ettim. 1 milyon karakter ile şunu denedim:

Devamını oku…

Debugging Decorator

Kod yazarken ve bu kodun tam olarak ne yaptığını anlamazken, fonksiyonların içine ara ara print serpiştiriyordum ki, neler döndüğünü görebileyim. Ancak malumunuz, bu printleri teker teker yazması, sonra teker teker silmesi bir hayli zahmetli bir işe dönüşebiliyor. Bu problemin üstesinden gelmek için, aşağıdaki decorator'u yazdım. İndirmek isteyenler debugging.py adresinden indirebilir.

Devamını oku…

Bloğu nasıl sunucuya yüklüyorum?

Bu bloğu barındırdığım sunucumda, rsync kullanma ihtimalim yok, çünkü sadece html dosyaları upload edebildiğim bir paket kullanıyorum. SSH erişimi gibi bir şansım yok. Bundan önce dosyaları sunucuya atmak için, filezilla kullanıyordum. Filezilla ile upload yaparken, boyutu farklı ise veya kaynak daha yeniyse upload et gibi bir seçeneği var. Bu az çok işimi görüyordu. Ancak bunun da kendine göre bir takım sıkıntıları var. Bazen output klasörünü silip baştan oluşturma ihtiyacı duyuyorum. Bu gibi durumlarda, çoğu dosyanın içereği aslında değişmemiş olsa bile, tüm dosyaları baştan upload ediyor. Bir de bazen dosyaları yanlış yere atma gibi bir problem yaşıyorum. Geçenlerde anasayfa'nın index sayfası üzerine, başka bir klasörün index sayfasını atmışım mesela, biraz geç farkettim. Ayrıca, önceden attığım ama sonradan sildiğim içeriğin takibi yapmam da mümkün olmuyordu bu şekilde.

Devamını oku…