Az da olsa git sürüm kontrol sistemini anlamak

Aslında uzun süredir yazdığım kodları github'da tutuyor olsam da git'i son birkaç günde çok daha iyi anladığımı söyleyebilirim. Şu ana kadar yaptığım, sürekli tek bir branch üzerinden çalışarak, diğer bilgisayar geçeceğim zaman veya çalışan bir sonraki sürümü yayınlamak istediğimde push yapmaktı. Pardus'da geliştirdiğimiz web projesinde bile sadece stajın son gününde, tek bir commit yaptık hehe(neredeyse tüm projeyi tek bir bilgisayarda pair-programming ile geliştirdiğimizden ihtiyaç duymamıştık, değişiklikleri göstermek istediğimde makinamda kurulu apache'yi çalıştırıyordum ve ağ üzerinden test ediyorlardı. tüm dosya sistemim zaten ağ üzerinden paylaşıma açıktı).

Son günlerde büyük oranda deneyse bir 2d platform oyunu üzerinde çalışıyorum ve sık sık eski haline dönmeyi isteyebileceğim ciddi değişiklikler yapıyorum. Git bana bu konuda nasıl yardımcı olabilir diye biraz araştırdım ve şu ana kadar bunları nasıl farketmedim diye kızdım kendime :P .

Kendime not niteliğinde, bazı olmazsa olmaz(benim için) komutları açıklayacağım.

Başlangıç, depo oluşturma veya mevcut depoyu ekleme

Anladığım kadarıyla bir depoya yazma izninin belirlenmesi biraz da sunucu tarafıyla alakalı. Bizim yapmamız gereken git config --global user.name "isim" ve git config --global user.email "email" ile commitlerimizde gözükecek ismi ve maili belirlemek(mail nerede gözüküyor bilmiyorum). Daha sonra eğer github kullanıyorsak ssh anahtarı oluşturup github'a ekliyoruz. Github'da anladığım kadarıyla ssh key'den kullanıcı adına bakıp depoya yazıp yazamayacağımıza karar veriyor. Bu kısımdan emin değilim açıkçası ama aklıma benim neden Clojure github deposuna push yapamadığımı açıklayacak başka bir senaryo gelmedi aehueah.

Git sunucunuzda depoyu bir şekilde oluşturduktan sonra(Github'da web sayfasından tıklayarak falan) git init ile bilgisayarımızda git deposu oluşturup, buna uzak sunucudaki depoyu git remote add ile ekliyoruz:

➜  ~  mkdir git-test
➜  ~  cd git-test 
➜  git-test  git init
Initialized empty Git repository in /home/sinan/git-test/.git/
➜  git-test git:(master) git remote add git-test git@github.com:osa1/git-tests.git

(Bu arada not: zsh kullanıyorum, oh-my-zshda süper eklentiler var, örneğin benim kullandığım git eklentisinde yukarıda da görebileceğiniz gibi bulunduğum branch'ı gösteriyor, commitlenmemiş değişiklikler varsa bir sembolle belli ediyor, git <tab> yaptığınızda komutları, komutlardan sonra <tab> yaptığınızda branch adlarını vs. tamamlıyor, mükemmel birşey, bir sürü de tema var ayrıca.)

Depoyu oluşturduktan sonra hiç branch'ımız yok aslında. Ama eğer branch oluşturmadan direkt commit yaparsak master diye bir branch oluşturuyor. master adının bir esprisi yok anladığım kadarıyla. Direkt olarak başka isimli bir branch da oluşturulabilir.

git-status ile commitlenmemiş değişiklik olup olmadığını görebiliyoruz. git-log tüm branchlara yapılan tüm commitleri bir 53ea667012c2741e7620e093e05132cd08265c06 benzeri kodla gösteriyor. Bu kodun tam olarak ne olduğunu anlamasam da, önceki bir commit'e dönmem gerektiğinde kullanıyorum.

Branchlar ile alakalı işlemler

➜  git-test git:(master) git checkout -b "branch2"
Switched to a new branch 'branch2'
➜  git-test git:(branch2) git branch           
* branch2
  master

checkout normalde zaten olan bir brancha geçer. Ama eğer "yeni oluştur ve hemen geç" diyorsanız, -b ile bu şekilde kullanılıyor. git branch ile de hangi branchda olduğunuzu görürsünüz(benim yaptığım gibi bir zsh eklentisi kullanıyorsanız zaten gözüküyor gerçi).

Branchlar hakkında yazmak istediğim birkaç şey var. Bir tanesi hangi branchda olursanız olun, başka bir brancha merge yapmadan da o brancha push yapabilirsiniz. Şu şekilde:

➜  git-test git:(branch2) git push git-test branch2:master

Bu syntax'a dikkat: branch2'yi master'a pushla diyorum. Gerekli merge'leri kendisi yapıyor, yapamıyorsa push da yapmıyor. Tabii sonra master branch'ına geçip fetch(master) + merge veya direkt merge(branch2'den) yapmak lazım.

Bunu kullanarak şöyle bir çakallık yapabiliyorsunuz, diyelim ki sunucudan bir branchı uçurmak istiyorsunuz:

➜  git-test git:(branch2) git push git-test :branch2

Bu aslında "branch2'ye hiçbir şeyi pushla" gibi bir anlama geliyor(ben uydurdum aehuaeh). branch2'yi sunucudan siliyor yani. Bilgisayarınızdaki depodan da şu şekilde siliyoruz:

➜  git-test git:(master) git branch -D branch2

Ha neden bir branch'ı sunucudan silmek isteyesiniz bilmiyorum. Geri dönmek isteyebilirsiniz belki, sunucuda durmasında bir zarar yok gibi.

Push ve pull

Şimdi, yukarıda bir branchdan başka bir brancha push yapılabildiğinden bahsetmiştim. Ama pratikte bu bir kolaylık sağlamıyor(sonuçta diğer brancha geçtiğinizde yine fetch + merge(veya sadece merge) yapmanız lazım.

pull ve fetch + merge'den bahsetmek lazım. fetchin yaptığı aslında sunucunuzdaki depodaki istediğiniz branchı depo-adi/branch-adi adlı bir brancha çekmek. Daha sonra bunu branch-adi ile merge etmek istiyorsanız git merge depo-adi/branch-adi ile merge ediyorsunuz. İşte git pull depo-adi branch-adi tam olarak bunu yapıyor.

➜  git-test git:(master) git fetch git-test master
From github.com:osa1/git-tests
 * branch            master     -> FETCH_HEAD
➜  git-test git:(master) git merge git-test/master 
Auto-merging test.markdown
CONFLICT (content): Merge conflict in test.markdown
Automatic merge failed; fix conflicts and then commit the result.

İşte şu anda yaptığım git pullun yapacağının aynısı.

Yanlız burda anlamadığım bir nokta, eğer bu depo-adi/branch-adi branchına geçersek şöyle bir mesaj alıyoruz:

➜  git-test git:(master) git checkout git-test/master 
Note: checking out 'git-test/master'.

You are in 'detached HEAD' state. You can look around, make experimental
changes and commit them, and you can discard any commits you make in this
state without impacting any branches by performing another checkout.

If you want to create a new branch to retain commits you create, you may
do so (now or later) by using -b with the checkout command again. Example:

  git checkout -b new_branch_name

HEAD is now at 53ea667... Merge remote branch 'git-test/master'

Ne demeye çalıştığını çözemedim.

Son olarak hayatımda gördüğüm en güzel şey(abarttım), eski commite geri dönme:

➜  git-test git:(branch3) git checkout 692832aa7a4a3a092e35f6955676be3c6e54e89e -b branch4 
Switched to a new branch 'branch4'

Burdaki commit kodundan ilk başta bahsetmiştim. Yeni bir branch oluşturup eski commite dönüyorum.

Commit hakkında birkaç şey

commit -a, daha önceden takipe aldığınız(git add ile) dosyalardan değişiklik olanları otomatik olarak commite ekler. Teker teker yeniden git add yapmanıza gerek kalmaz(ben ilk başta -a tüm dosyaları ekliyor sanıyordum mesela). commit -m, commit mesajı için $EDITOR çevre değişkenindeki editorü çalıştırmak yerine(bu kısım sanırım sadece bash için geçerli) komut satırından mesaj girmenizi sağlar. Ben commitlerimi şöyle yapıyorum yani:

➜  git-test git:(master) git commit -a -m "mesaj"

Stash

Bu özellik yeni başlayanlar için çok kritik değil sanırım, ama bir arkadaşla bir proje üzerinde çalışırken(ne yaptığımız hakkında hiçbir fikrimiz yok tabi aehueah) git bize "git stash yap istersen" gibi uyarılar veriyordu. Biz de anlam veremiyorduk.

stashın olayı şuymuş, diyelim ki bir branchda değişiklikler yaptınız, bir bug gözünüze çarptı düzelteceksiniz, sadece o kısım düzelmiş olarak commit yapacaksınız. Hemen git stash save ile o ana kadar yaptığınız commitlenmemiş değişiklikleri kaydediyorsunuz ve hemen son commitli haline dönüyor branch. Bugfix yapıp commit/pushluyorsunuz, sonra git stash pop ile son kaydettiğiniz stashe dönüyorsunuz. Birden fazla stash olabiliyor, git stash list ile listeliyorsunuz. İşiniz bittiyse git stash drop ile stashı siliyorsunuz falan. Henüz kullanma fırsatım olmadı, okuduklarımı yazıyorum. Kullandığımda örneklerle düzenleyebilirim.

Biraz dağınık oldu sanırım, amacım burda git'e veya sürüm kontrolüne yeni başlayanlara öğretmek değil de(o kadar bilmiyorum zaten), benim gibi bazı şeylerin ne kadar kolay/kullanışlı olduğunun farkında olmayanlara birşeyler göstermek ve kendime not düşmekt, o yüzden idare edin :P .

SICP hakkında

~2 ay kadar önce okumaya başladığım SICP hakkında birkaç birşey yazmak istedim. Okumak isteyenlere de birkaç tavsiyede bulunacağım. Bu kitabın yanlış anlaşıldığını, küçümsendiğini düşünüyorum. SICP nedir, veya neden SICP diye düşünen varsa, Google'da küçük bir araştırma sizi süper sayfalara yönlendirecektir.

Öncelikle biraz ön bilgi vereyim, kitabı ciddi anlamda okumaya ~2 ay kadar önce başladım, ve fonksiyonel programalama, Lisp dilleri, ve haliyle genel olarak programlama hakkında epey tecrübem vardı. Kitabı ilk okuma denemem lisans'a başladığım dönem(hatta hafta) içinde, bir şekilde biryerlerden kitapdan haberdar olup kütüphanemde bulunduğunu öğrenmemle oldu. Birkaç ay sonra da şöyle bir feed girmişim. Farkedebileceğiniz gibi pek de iyi gitmemiş. Şu anda ise ikinci ve üçüncü bölümdeki 179 alıştırmadan 168'ini çözdüm ve not aldım(%93.8). Çözmediklerimin 5 tanesi 2. bölümün son 5 sorusu, artık konuyu anladığımı düşündüğümden çözmeyeceğim, geriye kalan 6 tanesini de çözemedim, aklımdalar.

İlk bölüm hariç çözdüğüm tüm alıştırmaların çözümleri ve açıklamaları github alanımda. Kitabı okumaya başladığımda çözümlerimi yayınlama gibi bir amacım yoktu, o yüzden ilk bölümdeki alıştırmaların çözümlerini not almadım. Bu aşamadan sonra ~2 hafta kadar ara verip(biraz finallerle ilgileneyim de şu dönemi kazasız belasız atlatıyorum diyorum), kitabı bitirmeye devam edeceğim. Gerçi ara verebileceğimi sanmıyorum, yine okuyacağım ama alıştırmalarla şu ana kadarki gibi yoğun bir şekilde ilgilenemeyeceğim.

Şimdi biraz okumak isteyenler için birşeyler söyleyeyim:

Çalışma ortamı

Emacs'e aşina değilseniz veya benim gibi VIM olmadan düz metin bile yazamayacak halde değilseniz, Racket en ideal ortam gibi. Kendi REPL/Editor'ü yeterince iyi. Kurulumu çok kolay(hatta linux ortamında kurulum yapmadan da çalıştırabiliyorsunuz). "Picture language" bölümündeki gibi tanımı verilmemiş fonksiyonlar kolayca temin edilebiliyor(yeri geldiğimde açıklamalarımda yazdım bunları).

Racket'in kötü yanı, tam olarak Scheme olmadığından, bazı kısımlar çalışmıyor, farklı bir yol izlemeniz gerekiyor. Örneğin mutable data ile ilgilendiğimiz 3. bölümde. Racket'ın pairları immutable olduğundan(Scheme'dekinin aksine), set-car! ve set-cdr! gibi fonksiyonlar yok. Çözümü, bir modül aracılığıyla pair yerine mpair(mutable pair), set-car! yerine set-mcar! vs. kullanmak. Bunları hep açıklamalarda yazdım yeri geldiğinde.

Bu kısımlar için de ben kullandığım dağıtımın(openSUSE 11.4) paket yöneticisinde gördüğüm Scheme48'i kullandım. Her hangi bir standart Scheme implementasyonu kullanılabilir.

Emacs'e alışkın olanlar, veya illa VIM tuşları diyenler için çözüm Quack. Açıkçası profesyonel anlamda Scheme yazacaksanız ne kadar iyidir bilemiyorum, benim ihtiyacım olan Scheme REPL'i ve editorden kulayca kod çalıştırmayı mümkün kılıyor. Tuşları SLIME ile epey benzer. İstediğiniz Scheme'i kullanabiliyorsunuz(run-schemei çalıştırdığınızda kullanmak istediğiniz Scheme'i soruyor). Eğer Racket kullanıyorsanız, mzschemei çalıştırıyorsunuz. Emacs VIM tuşları için de Evil.

Bu arada kitabın bir sürü ders videoları var sağda solda. Berkeley ve MIT'ninkiler gayet iyiydi diye hatırlıyorum. Bana süper sıkıcı geldiğinden(gözlerim kapanıyor ya) dersleri izlemedim.

Zorluk

Baştan söyleyeyim, kitap zor. Alıştırmaları çözmeden öğrenmeniz imkansız. Örneğin ikinci bölümde 90 küsür alıştırma var. Konunun bir kısmı(hatta belki de çoğu kısmı) alıştırmalarda anlatılıp, program yazarak öğretiliyor. Alıştırmalar birbirlerine bağlı, çoğu zaman bir bölüm içinde önceki alıştırmaları çözmeden sonrakini çözemiyorsunuz. Bazı bölümlerde bir paragraf birşey anlatıp, birkaç paragraflık problemler geliyor falan. Çoğu alıştırma çok zevkli olsa da, bazen kendini tekrar edebiliyor(örneğin 2. bölümün sonlarına doğru).

İlk 3 bölümü epey hızlı bitirdiğimi düşünüyorum. Bu şu yüzden olabildi: Kitaba başladığımda, fonksiyonel programlama, Lisp dilleri, ve haliyle programlama hakkında epey tecrübeliydim. Bir süre Common Lisp ile uğraşmıştım, The Little Schemer'ı okumuştum, ve Clojure ile uğraşıyordum. Özellikle ilk bölüm için çok gerekli olan bazı matematiksel kavramları ayrık matematik ve calculus derslerinde görmüştüm. Kitabı ilk okuma denememde aslında bu yüzden yapamamıştım. İşin matematiğinde takılmıştım, ve ilk bölüm matematik ağırlıklı(Scheme biliyorsanız bile kesinlikle atlamamalısınız, iterative process vs. recursive process, tail-call optimization, basit lambda calculus, fixed-point combinator gibi süper konulardan bahsediliyor). Bunların hepsine sıfırda başlayacak biri için bu süreç epey uzun olabilir(MIT veya bu kitabın okutulduğu diğer okullarda kaç dönem sürüyor tüm kitap acaba?).

Fonksiyonel programlama

3. bölüme kadar tamamen fonksiyonel programlama yapıyoruz. 3. bölümde de atama işleminden, mutable datadan, avantajlarından, dezavantajlarından, programları nasıl kompleks bir hale getirdiğinden, fonksiyonel/imperative programlama arasında dengeden bahsediliyor. Daha sonra %100 fonksiyonel bir yol izlemesek de(3. bölümü yeni bitirdim, tam emin değilim) geri kalan kısım yine büyük oranda fonksiyonel gibi.

Burda SICP'in fonksiyonel programlama için mükemmel bir kaynak olduğunu düşünüyorum. Sadece ilk 3 bölüm okunsa bile yeterli olur. 3. bölüme geçtiğimde hiç farkında olmadan sürekli fonksiyonel programlama yaptığımı ve artık bu yolun bana çok doğal geldiğini farkettim. Bundan 1 yıl kadar önce imperative dillerde çok rahat çözebildiğim tüm problemleri şu anda fonksiyonel bir şekilde çözebiliyorum(hatta belkide daha bile rahatımdır, bir süredir imperative dillerle uğraşmıyorum). SICP bu şekilde düşünmeye başlayabilmek için mükemmel bence.

Common Lisp vs Scheme vs Clojure

Bazen denk geliyorum, SICP'i Common Lisp veya Clojure ile çözmeye çalışıyor birileri. Bunun mantıklı olduğunu düşünmüyorum. SICP'i bir Scheme kitabı olarak görmeyin, dil hakkında birşler anlattığı kısımları birleştirsek, ilk 3 bölümde toplam 10 sayfa bile etmez. Scheme çok küçük bir dil. Pek çok dili öğrenirken vaktimizin çoğunu syntax'ını anlamakla geçiriyoruz zaten(programlamaya yeni başlamıyorsak veya çok farklı bir paradigm öğrenmiyorsak). Scheme'de öyle bir dert yok. Ekstra bir dil öğrenmiyorsunuz yani aslında.

Kaldı ki Scheme(ve aslında Common Lisp, ama kendisi çok kompleks bir dil olduğundan bu süreç epey uzun sürecektir) sadece kendisi ile yazılan kitaplar için bile öğrenilebilir bence.

Bir de olaya şu açıdan bakın, bir programlama kitabı düşünün, anlattığı konuların herhangi bir dille alakası yok, genel olarak programalama, programların yapımı, soyutlama, problemlere yaklaşımlar, concurrency, programların yorumlanması ile alakalı, bir yerden sonra okuyucuya o ana kadar kullandığı dilin yorumlayıcısı yazdırılıyor. Bir programlama dili kitabı değil kesinlikle. Bir derleyici kitabı da değil. Daha iyi bir dil biliyor musunuz?

SICP hakkında şimdilik bu kadar. Paylaşmak istediğim birşeyler olursa yine yazacağım. Üzerinde çalıştığım(henüz elle tutulur birşey değil ama) bir Scheme yorumlayıcısıyla alakalı da dağınık notlar var, bir ara ekleyeceğim(4. bölüm tam olarak bu işle alakalı olduğundan, sanırım 4. bölümü bitireceğim önce).

Clojure'da reader macroları

Kendime not: Clojure'da, biraz hacky bir şekilde de olsa reader macroları tanımlanabilir. Örneğin < ile başlayıp > ile biten, arasındaki karakterleri string'e dönüştüren bir reader macrosu şu şekilde tanımlanabiliyor:

(defn reader-macro [ch fun]
  (let [dm (.get
             (doto (.getDeclaredField clojure.lang.LispReader "macros")
               (.setAccessible true))
             nil)]
    (aset dm (int ch) fun)))

(defn native-string [rdr letter-u]
  (loop [s nil
         p \space
         c (char (.read rdr))]
    (let [s (str s p)]
      (if (= c \>)
        s
        (recur s c (char (.read rdr)))))))

(reader-macro \< native-string)

Burda reader-macro fonksyionu, clojure.lang.LispReader sınıfının macros fieldını(IFn[256]) erişilebilir hale getirip(reflection), reader macrosunun çağıracak karakterin(bizim durumumuzda <) yerine okuyacak fonksionu ekliyor. Bizim fonksiyonummuz native-string.

Reader fonksyionunu ilk parametresine clojure.lang.LineNumberingPushbackReader geliyor. read, readLine, unread gibi methodları var. İkinci parametresini çözebilmiş değilim.

Clojure'da bir de dispatch macroları var, bunların tek farkı(muhtemelen bunların vermek istediği bir mesaj var ama ben çözemedim henüz), dispatch macroları # ile başlıyor. Yukarıdaki kodda, reader macrosunu clojure.lang.LispReader.macrosa değil de, clojure.lang.LispReader.dispatchMacrosa ekleyerek dispatch macroları genişletilebilir. Kurcalamak isteyen olursa, LispReader.java.

Kaynaklar: 1, 2

Clojure'da reader macroları bir süredir tartışılıyor aslında. Genel olarak, okunması/anlaşılması zor koda sebep olduğundan, namespace desteğinin olmamasından, Clojure'un zaten çok kullanılan veri yapıları için reader macrolarına sahip olmasından ve benzer başka sebeplerden dolayı reader macrolarımızı tanımlayamıyoruz şu anda. Şurda ilgili bir IRC logu var, şurda da bir mail(bir mail daha vardı ama bulamadım şimdi).

Açıkçası bana bu sebepler mantıklı geliyor. Clojure'a reader macroları gelsin istemem. Common Lisp'den hevesini alamamış biri olarak bu şekilde reader macrolarıyla oynamak bana yetiyor şimdilik :) .

Sıralama algoritmaları ve dillerin kendi sıralama fonksiyonları

Uzun uzun kod örnekleri yazmıştım ama bir yerden sonra sıkıldım. Bugün öğrendiğim birkaç şeyi özet geçeyim:

• Sort işlemini lazy olarak yapmak süper. Çoğu zaman tüm dizinin sıralı haline ihtiyaç duymuyoruz ve bu şekilde arama yapmak karşılaştırma/fonksiyon çağrı sayısnı çok azaltıyor. Yine önce dilin sağladığı imkanları denemekte yarar var. Örneğin kendi yaptığım testlerde, 1000 elemanlı bir diziyi Python'ın sorted() fonksiyonu ile sıralamam, lazy bir quicksort(generator ile) yazıp az hesap yapmamdan 10 kat daha hızlı oldu. İnanılmaz(bu fark tabii ki eleman sayısı arttıkça açılacaktır).

• Aynı şey Clojure için de geçerli. Lazy sort yazacağım diye uğraşmaktansa, builtin sort fonksiyonu ile sıralayabilirsiniz. Kendi yaptığım testlerde, içi Integer dolu diziyi Clojure'un sort fonksiyonuyla çok bariz bir şekilde daha hızlı sıraladım(tabii bu biraz da sıraladığım elemanların Integer olmasıyla alakalıydı sanırım, kodu takip ettiğimde, bu seq'in önce Object[] array'ine dönüştürülüp, karşılaştırma sorasında da her bir elemanın double'a cast edilerek karşılaştırdığını gördüm, bunların çoğu Clojure ile değil Java ile yapılıyor).

• Timsort diye bir sıralama algoritması var. İlk olarak Python için yazılmış. Şu anda Python, Java SE 7 ve Android'de kullanılıyor. Bu hızın kaynağı sanırım bu algoritma.

• Python'da fonksiyon çağrıları çok masraflı. Denemek için bir quicksort algoritmasını binlerce elemanlı bir listede, her karşılaştırma için bir fonksiyon çağırarak ve bir bir builtin Python operatorunu kullanarak(bu operatorlerin de sonuca __gt__ veya __lt__ gibi fonksiyonları çağırdıklarının farkındayım, ama sonuçta testlerimde fonksyion çağrı sayısını arttırdım) denedim. Performans farkı çok bariz. Filter, map gibi higher-order fonksiyonlar list comprehension'lardan performans açısından çok farklı değiller ama(bkz. ilgili SO başlığı). Haftalar sonra gelen düzenleme: Dropbox ekibi bloglarında küçük bir Python kodunun hızlandırılması hakkında şöyle güzel bir yazı yazmış. Sadece fonksiyon çağrısını kaldırarak %15 performans artışı elde etmişler. Bunun gibi daha bir sürü ipucu var. Mutlaka okuyun.

Şimdilik bu kadar.

Clojure ve bir 4Clojure problemi

Clojure(ve genel olarak Lisp dilleri) ile bir süredir ilgileniyorum, canım sıkıldıkça 4clojure'daki problemleri çözüyordum(bu arada Clojure'a başalyan herkese tavsiye ederim, sitenin en güzel yanı, problemi çözdükten sonra başkalarının çözümlerini görebiliyorsunuz, ve çoğu zaman problemi çözmüş birkaç Clojure geliştirici/katkıcısı bulabiliyorsunuz). Bir süre sonra, artık temellerini kavradığımı düşündüğümde, şu ana kadar en az çözülen probleme, 'For Science!'a bir bakayım dedim. Problem tanıdık geldi. Bu problemin bir benzeriyle ilk kez şurda bahsettiğim programlama yarışmasında karşılaşmış, ve o zaman soruya saf saf bakmaktan başka birşey yapamamıştık. Daha sonra, ilk başta alakasız gibi gözüksede, aslında çok benzeyen bir halini, üzerinde çalıştığım bir oyunun yapım aşamasını kolaylaştırmak için çözmüştüm, ilgili yazı şurda.

Alternatif bir yöntem düşünmeden hemen daha önceden çözdüğüm gibi çözmeye başladım. Çözen Python kodunu birkaç dakika içerisinde yazdım. Algoritmam şu şekilde: gezilebilir olup birbirlerine komşu olan tüm alanları grupluyorum, daha sonra eğer başlangıç ve hedef aynı grupdaysa, birbirlerine erişebilirler demektir.

Python koduyla açıklamak daha kolay:

pos_m = None
pos_c = None

groups = []

Burda pos_m, problemdeki fare(mouse - M)nin başlangıç noktasını temsil ediyor. Alanı gezerken fareyle karşılaştığımızda bunu atayacağız. Aynı şekilde pos_c de peynir(cheese)in yeri.

groups da birbirlerine komşu olan tüm noktaların oluşturduğu grupları tutacak.

def check_adjacency(pos, x, y):
    difx = abs(pos[0]-x)
    dify = abs(pos[1]-y)

    return (difx == 1 and dify == 0) or (difx == 0 and dify == 1)

Bu fonksiyonun yaptığı, bir (X, Y) ikilisinden oluşan noktanın, (x, y) noktasına komşu olup olmadığını dönmek. Burda komşu olma şartı, iki noktanın üst üste veya yan yana bulunmaları(haritada çarpraz ilerleme olmadığından, çarprazdakiler komşu sayılmıyor).

def find_groups(x, y):
    r = []
    for group in groups:
        for pos in group:
            if check_adjacency(pos, x, y):
                r.append(group)
                break
    return r

find_groups, (x, y) noktasının komşu olduğu grupların bir listesini dönüyor. Örneğin bir aşamada elimizde [(1, 1), (2, 2)] ve [(2, 4)] grupları varsa ve biz (2, 3) noktasının komşu olduğu grupları arıyorsak, bu iki grupu bize döndürecek. Bu durumda bu iki grupu birleştirmemiz gerekcek çükü artık bu ikisi birbirine (2, 3) ile bağlı.

def merge_groups(grps):
    for group in grps[1:]:
        grps[0] += group
        groups.remove(group)

Birleştirme işlemini de bu yapıyor işte.

Bundan sonrası basit zaten, teker teker gez, grupları bul, grup yoksa yeni oluştur, varsa onu genişlet, birden fazlaysa birleştir. Kodu takip etmek için kullandığım print statement'larını silmeden koyuyorum:

for y in xrange(len(test_grid)):
    for x in xrange(len(test_grid[0])):
        char = test_grid[y][x]
        print x, y, char,
        if char == '#':
            print "block"
        else:
            if char == 'M':
                pos_m = (x, y)
            elif char == 'C':
                pos_c = (x, y)

            grps = find_groups(x, y)
            if len(grps) > 1:
                merge_groups(grps)
                grps[0].append((x, y))
                print "merge"
            elif len(grps) == 0:
                groups.append([(x, y)])
                print "new group"
            else:
                grps[0].append((x, y))
                print "append"

print pos_m, pos_c
for group in groups:
    if pos_m in group and pos_c in group:
        print "M can reach C"

Çok da güzel bir kod olmayabilir(örneğin liste içinde listelerde lineer arama yerine, set kullanılabilir, Clojure kodumda yaptığım gibi) ama problemi hızlıca çözmek için işimi gördü.

Fonksiyonel programlama yolunu henüz çözebilmiş değilim. Hala daha çoğu zaman yaptığım, bir algoritmadaki değişen durumları(state) bir loop içine alıp, tail-call yapmak(Clojure'da recur yani, bu arada recur'un tail-call optimization olmadığının farkındayım).

Yukarıdaki Python fonksiyonlarının Clojure karşılıklarını şu şekilde yazdım:

(defn abs
  "Absolute value of n"
  [n]
  (if (neg? n)
    (- n)
    n))

(defn check-adjacency
  [[posx posy] x y]
  (let [difx (abs (- posx x))
        dify (abs (- posy y))]
    (or (and (= difx 1) (= dify 0)) (and (= difx 0) (= dify 1)))))

(defn find-adjacent-sets
  [sets [x y]]
  (set (filter (fn [set]
                 (some (fn [p]
                         (check-adjacency p x y))
                       set))
               sets)))

(defn get-char
  [grid [x y]]
  (get (grid y) x))

Daha sonra bunları kullanarak problemin çözümü:

(defn can-reach?
  [grid]
  (let [rang (for [y (range (count grid)) 
                   x (range (count (first grid)))] [x y])]
    (loop [positions rang
           sets #{}
           posm nil
           posc nil]
      (if (nil? positions)
        (let [m-set (first (filter #(% posm) sets))
              c-set (first (filter #(% posc) sets))]
          (= m-set c-set))
        (let [pos (first positions)
              ch (get-char grid pos)
              adj-sets (find-adjacent-sets sets pos)
              set-count (count adj-sets)]
          (if (not= ch \#)
            (recur (next positions)
                   (conj (difference sets adj-sets) (union (apply union adj-sets) #{pos}))
                   (if (= ch \M) pos posm)
                   (if (= ch \C) pos posc))
            (recur (next positions)
                   sets
                   posm
                   posc)))))))

4clojure çözümlerde birden fazla fonksiyon kabul etmediğinden, tüm yardımcı fonksiyon tanımlarımı ana fonksiyonumun içine almam gerekti. 4clojure'a yolladığım çözüm şurda.

Clojure hakkında karmaşık duygular içerisindeyim(eheh, bir programlama dili hakkında böyle bir cümle kurmak). Pek çok ileri-seviye özelliklerini henüz bilmiyorum. Fonksiyonel programlamayı da, yukarıda bahsettiğim gibi, henüz çözebilmiş değilim. Macroları şu ana kadar hiç kullanmadım. Bu dönem sonuna kadar SICP'in ilk 3 bölümünü bitirip, tüm alıştırma çözümlerini yayınlamayı planlıyorum(ilk bölüm bitti, ikincisi bitmek üzere, birkaç alıştırmayı çözemedim gerçi). Daha sonra McCarthy'nin ilk Lispini bir dilde(büyük ihtimalle C olacak) implement ettikten sonra muhtemelen type theoryye dalmak için Haskell(veya daha uygun başka bir Lisp dili) ile uğraşacağım(sonunda muhtemelen bu dediklerimin yarısını falan yapmış olacağım ama olsun eheh).

Bu arada birşey farkettim, bir süredir çeşitli programlama problemleriyle ilgileniyorum, bir de yarışma tecrübemiz oldu ve C ile katıldık. C böyle bir iş için seçilebilecek en kötü alternatif. C'de elinizden hiçbir veri yapısı ve veri yapıları üzerinde işlemler yapabileceğiniz hiçbir fonksiyon yok. Çoğu zaman Java, C++ ve Python gibi alternatifler de oluyor bu gibi problemlerde. Java'da zaten elinizin altında yüzlerce sınıf var. C++'da STL var, Python'da zaten bir sürü builtin veri yapısı var. C ile ne gerekiyorsa yazmak zorundasınız. Aslında bu gibi yarışlamarda daha adil olması açısından C kodlarını glib ile derleyebilirler. Performans deseniz, çoğu zaman takıldığınız nokta performans olmuyor(eğer problemi C++ veya en kötü ihtimalle Java ile çözmüşseniz). Kısaca, C ile çözmeye çalışmayın, en azından biraz STL bilip, C++ ile çözülebilir.