September 25, 2011 - Tagged as: python, lisp, tr.
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 rfind_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.