Hiperkocka.hu

Clojure és a nyolc királynő

2010-01-02T00:00:00-08:00

Az egész tavaly Húsvétkor kezdődött. Verpeléten voltunk Kriszti anyukájánál három napot. Kellett valami elfoglaltság, ezért megvásároltam Stuart Halloway Programming Clojure című könyvének PDF verzióját. Nem nagyon kommunikáltam eztán a külvilággal a következő néhány napban, amíg a végére nem értem. Remek olvasmány volt, nagyon jól bemutatja a Clojure és a funkcionális programozás lenyűgözően elegáns mivoltát. Belelkesedtem, de aztán lecsendesedett a dolog. Felvettem egy rakás Clojure-rel foglalkozó blog-ot a reader-ben, amiket szorgalmasan olvastam is, de kódot nem nagyon írtam. Egészen most karácsonyig.

Amikor is (nem meglepő módon) kiderült, hogy egy programnyelvet nem lehet megtanulni, ha csak olvasol róla. Bármennyit is olvasol róla. A nyelvet használni kell, s közben vért izzadni a legtriviálisabb problémák megoldásáért is. Amiket következő alkalommal persze már csuklóból old meg az ember.

Első feladatként a Nyolc királynő problémát tűztem magam elé. A megoldása nem különösebben bonyolult, éppen megfelelő egy új nyelv felfedezéséhez. A nyolc királnyő probléma arról szól, hogyan lehet 8 db királynőt feltenni egy sakktáblára úgy, hogy ne támadják egymást. Összesen 92 db megoldása van.

Backtracking

A módszert, amivel a nyolc királynő problémát meg szokás oldani, backtracking-nek hívják. A lényege pontokba szedve röviden a következő:

Az összes olyan állapotot keressük, melyek megoldásai a problémának.
A folyamat során mindig rendelkezünk egy állapottal, ami általában részleges, de néha teljes megoldás.
Minden részleges megoldáshoz meg tudjuk mondani az őt követő állapotok halmazát. Ezek egy lépéssel közelebb vannak egy teljes megoldáshoz.
Egy állapotról el kell tudnunk dönteni, hogy az teljes megoldása-e a problémának.
Ha egy részleges megoldáshoz tartozó követő állapotok halmaza üres, akkor zsákutcába kerültünk, ezért visszalépünk az őt megelőző állapotba (ez a backtrack), és ott egy másik részleges megoldás felé indulunk tovább.

Ha a fenti pontokat a nyolc kiránynő problámra vetítem, akkor a következőket kapom:

Mind a 92 megoldást szeretném megkapni.
Az állapotot egy tömb reprezentálja, ami kezdetben üres. Később a tömb i. eleme mondja meg, hogy az i. oszlopban lévő királynő melyik sorban van.
Részleges megoldás esetén k oszlophoz rendeltünk királynőt, ahol k < 7 (a számozást nullával kezdjük). Ekkor a követő állapotok halmaza azon állapotokat tartalmazza, melyekben már a k + 1-dik oszlopban is van királynő, és ez semelyik előzőt sem támadja.
Mivel minden részleges megoldásunkra igaz, hogy senki nem támad senkit, egy állapot teljes megoldás, ha az állpot tömbjénak hossza 8.

Clojure implementáció

A kód megtekinthető egyben a ebben a gist-ben, de itt most szeretnék végigmenni rajta, hogy lássuk, hogyan épül fel a program. Csapjunk is a lovak közé!

(def N 8)

(defn distance [x y] (Math/abs (- x y)))

(defn solution? [state]
  (= N (count state)))

(defn next-states [s]
  (map #(conj s %) (range N)))

N a tábla oldalának hossza, sakktábla esetén 8. A distance egy segédfüggvény, két szám különbségének abszolút értékét számolja ki. A solution? prediktátum eldönti egy állapotról, hogy az teljes megoldás-e. Esetünkben ez akkor igaz, ha a tömb hossza 8.

Az első izgalmasabb dolgot a next-states függvény végzi. Kiszámolja az s nevű paraméterként kapott állapotból elérhető állapotok listáját. A (range N) esetünkben a (0 1 2 3 4 5 6 7) szekvenciává értékelődik ki. A map végigmasíroz ezen a kollekción, és mindegyik elemet hozzácsapja s-hez. A map értéke minden esetben egy nyolc elemű vector lesz. Lássunk két példát a next-states-re:

(next-states [])  ; => ([0] [1] [2] [3] [4] [5] [6] [7])
(next-states [1]) ; => ([1 0] [1 1] [1 2] [1 3] [1 4] [1 5] [1 6] [1 7])

El kell tudnunk dönteni azt, hogy két királynő támadja-e egymást egy bizonyos állapotban. Épp ezt teszi a következő függvény.

(defn attack? [s i j]
  (let [xi (s i)
        xj (s j)]
    (or (= xi xj)
        (= (distance xi xj) (distance i j)))))

Az s paraméter az állapotvektor, az i és j pedig a két összehasonlítandó királynő indexei. A két királynő az alábbi esetekben támadja egymást:

egy oszlopban vannak – ez itt a reprezentációból következően nem lehetséges
egy sorban vannak – (= xi xj) feltétel
átlósan támadják egymást – ez akkor van, ha a sorindexeik különbsége megegyezik az oszlopindexeik különbségével, azaz (= (distance xi xj) (distance i j))

Azt is el kell tudnunk dönteni, hogy egy állapot érvényes-e, azaz nincs-e két olyan királynő, akik támadják egymást. Mivel az algoritmusunk csak érvényes állapotból lép tovább, elég csak azt megvizsgálnunk, hogy az utoljára felrakott királynő támadja-e valamelyik már korábban fentlévőt.

(defn valid-state? [s]
  (let [max-idx (dec (count s))
        pairs (map #(list % max-idx) (range max-idx))
        no-attack? (fn [pair]
                     (not (attack? s (first pair) (last pair))))]
    (every? no-attack? pairs)))

A max-idx az utoljára felrakott királynő indexe. A pairs azon indexpárok listája, amelyeket vizsgálnunk kell. Abban az esetben példul, ha most raktuk fel a negyedik királnyőt a pairs értéke ((0 3) (1 3) (2 3)) lesz, hiszen az új (3-as indexű) királynőt össze kell vetnünk a 0,1,2-es indexűvel. A no-attack? egy függvény (predikátum), ami paraméterként egy indexpárt kap, és a korábban megírt attack? függvény segítségével eldönti, hogy a pár-hoz tartozó királynők támadják-e egymást. A valid-state? visszatérési értékét végül az (every? no-attack? pairs) kifejezés szolgáltatja. Az every? a pairs-ban lévő összes indexpárral meghívja a no-attack?-ot, és ha mindegyik true-val tér vissza, akkor az értéke igaz lesz, egyébként hamis.

Következő függvényünk megmondja, hogy egy állapotból milyen következő érvényes állapotokba mehetünk tovább.

(defn next-valid-states [s]
  (filter valid-state? (next-states s)))

Majd ezután nincs más hátra, mint megkeresnünk a megoldásokat. Ezt a rekurzív backtrack függvény végzi. Paramérként egy állapotot kap. Ha ez az állapot egy megoldás, akkor visszatér vele, ez a rekurzió egyik alapesete (az alapeset - base case - az az ág, amikor a rekurzív függvény nem hívja meg magát). Minden más esetben kiszámolja a következő állapotok listáját, majd a mapcat mindegyikre rekurzívan meghívja a backtrack-et és a végén konkatenálja az eredményként kapott listákat. A másik alapeset az, amikor a következő állapotok listája egy üres lista. Az eight-queens-nek, ami a végső megoldást szolgáltatja nem kell mást tennie, mint egy üres vektorral meghívnia a backtrack-et.

(defn backtrack [state]
  (if (solution? state)
    [state]
    (let [next-states (next-valid-states state)]
      (mapcat backtrack next-states))))

(defn eight-queens [] (backtrack []))

Végül néhány segédfüggvény, ami az eredmények kiírását végzi.

(defn format-solution [solution]
  (let [letters (vec (seq "ABCDEFGH"))
        positions (map #(str-join "" [%1 (+ 1 %2)]) letters solution)]
    (str-join ", " positions)))

(defn print-solutions [solutions]
  (doseq [solution solutions]
    (println (format-solution solution))))

(defn print-all-solution []
  (print-solutions (eight-queens)))

Kicsit hosszúra sikerült ez a poszt, de ha valaki végiolvassa remélem felkelti az érdklődését a Clojure iránt. Hajrá!

Pomodoro technika

2009-05-10T00:00:00-07:00

A pomodoro technika egy egyszerű módszer arra, hogyan végezzük el napi feladatainkat kellemes és folyamatos tempóban. Segít elkerülni a halogatást. És segít a kívülről és belülről folyamatosan érkező zavaró tényezők leküzdésében.

Az alapgondolat a nap felosztása 25 perces egységekre. Az időmérésre a hardcore pomodoro júzerek egy paradicsom alakú konyhai órát használnak, innen a módszer neve, a pomodoro olaszul paradicsomot jelent.

A módszer rövid bemutatása

Tömören és velősen: következő feladat kiválasztva, óra 25 percre felteker, meló indul, meló megy, meló megy, meló megy, idő letel, óra csörög, pomodoro befejeződött. 25 perc elég rövid idő ahhoz, hogy maximálisan koncentrálni tudjunk az adott feladatra, és eseteleg az időközben beérkező zavaró tényezőket is el tudjuk tolni a végéig.

A 25 perces időtartamot nevezzük egy pomodoro-nak. Eztán 5 perc szünet következik, amikor is kötelező nem munkával foglalkozni. Ez tökéletes alkalom, hogy készítsünk magunknak egy kávét, felkeressük a mellékhelységet vagy lecsekkoljuk az email fiókunkat. Amint letelt a szünet, kezdődik a következő pomodoro.

Négy pomodoro után nagyszünet következik (mint az iskolában), ami 15-30 perc. Erre is érvényes mindaz, ami a kisszünetre. Ha letelt, a mókuskerék indul tovább.

A pomodorotechnique.com weboldalról letölthető pdf-ből sokkal okosabbak lehetünk. Megtudhatjuk miért érdemes egy kis könyveléssel is kiegészíteni a mókát. Csináljunk naponta egy To-Do sheet-et, jelöljük melyik feladatra hány pomodoro-t használtunk. Nap végén ezt vezessük át perzisztensebb formába (adatbázis, excell sheet), hogy később rendelkezzünk statisztikával, amiből folyamatosan következtetéseket levonva fejleszthetjük magunkat tovább és tovább a GTD és Agile nirvána felé vezető úton.

Saját tapasztalatok

Egy hetes tesztidőszak után kijelenthetem, hogy látok fantáziát a dologban. A könyveléses és statisztkakészítős részből egyelőre csak annyit alkalmaztam, hogy valahova felírtam a feladatokat, és hogy hány pomodoro-nyi időt töltöttem velük. Valahogy az az érzésem, hogy jó lenne ezt szoftverrel megtámogatni, de még nem találtam ilyet.

Szóval lássuk csak, hogy nekem miért tetszik:

Már gyerekkoromban is úgy nyírtam otthon a füvet, hogy téglalapokra osztottam a területet, és egyesével végezetem velük. A munkaidő felosztása 25 perces szakaszokra teljesen analogizál ezen perverz hajlammal.
Amióta vannak az 5 perces szünetek nincs akkora rumli a dolgozószobámban, sőt az egész lakásban. Pár perc alatt csomó mindent odébb lehet rakni.
Ha valami megszakítás érkezik, (pl. barátnő éppen filmet akar nézni, de nem tudja a feliratot beüzemelni), akkor sokkal meggyőzőbb a következő: “várjál kicsi 5 percet, lejár a vekker és már ott is vagyok”, minthogy “na még ezt a webservice hívást lefejlesztem”.
Ha valamibe nagyon nincs kedvem belefogni, könnyebb úgy tekinteni rá, hogy csinálok 2 pomodoro-t, aztán abba is hagyom, ha végeztem, ha nem.
Nap végén nem azt látom, hogy egy kis feladatot megcsináltam, aztán belekezdtem egy nagyobbba és azzal meg sehol sem állok, hanem azt, hogy összesen megcsináltam 10 pomodoro-t és ez jó érzés.

Az eddigi tapasztalataim tehát pozitívak, de meglátjuk mit hoz a jövő. Ha sikerül elmerülnöm a módszer rejtelmeibe elképzelhető, hogy írok még róla, addig is mindenkinek ajánlom a friss napérlelte olasz paradicsomot!

Frissítés (2009.07.08)

Néhány alkalmazás, melyek segíthetenek a módszer alkalmazásában:

mytomatoes.com (webalkalmazás)
focus booster (Adobe AIR kliens)
Pomodairo (Adobe AIR kliens)
e.ggtimer.com (online timer, webalkalmazás)
Pomodoro Desktop (Mac alkalmazás)
tomatoist.com (webalkalmazás)

Ha felfedeztek valami jópofa alkalmazást, ami nem szerepel a listán, írjátok meg kommentben, és frissítem a posztot. Egyébként, ha valaki nyomon akarja követni új eszközök megjelenését, akkor a pomodorotechnique és a pomodorotechnique-timer google group-okat érdemes figyelni.

Memori, avagy szótanulás az iWiW-en!

2009-04-21T00:00:00-07:00

Ha minden igaz ma hajnalban élesbe áll az iWiW-re fejlesztett alkalmazásom, ami a keresztségben a Memori nevet kapta. Idegen nyelvű szavak, kifejezések tanulását támogatja a Leitner módszer segítségével. A módszer egy pofonegyszerű algoritmus, aminek eredményeként a tanulásra szánt időnket hatékonyabban tudjuk kihasználni, mintha egy szótárfüzetből bifláznánk a szavakat. Mitől hatékony? Attól, hogy a számunkra könnyebb szavakat kevesebbszer, a nehezebbeket többször kérdezi. Lássuk a részleteket!

A Leitner módszer

Van N db dobozunk, megszámozva egytől N-ig. A tanulandó szavainkat kártyákra írjuk, egyik oldalára magyarul a másikra mondjuk angolul, és a dobozokba rakjuk, kezdetben az első dobozba. Gyakorlás során húzunk véletlenszerűen egy kártyát a k-dik dobozból, megnézzük a magyar kifejezést, majd megpróbáljuk felidézni az angolt. Ha nem sikerül visszatesszük az első dobozba, ha viszont igen, akkor egy időre félretesszük a kártyát pihentetni (minél magasabb számú dobozból vettük elő, annál nagyobb ez az idő), majd visszatesszük a k+1-dik számű dobozba.

kártyák mozgása a tanulás során

A Memoriban 5 dobozunk van, és az idő, amíg a program egy sikeres gyakorlás után pihenteti a kártyát a következő táblázat szerint alakul:

doboz száma	pihentetési idő
2. doboz	1 nap
3. doboz	3 nap
4. doboz	7 nap
5. doboz	30 nap

Az első doboz nincs benne a táblázatban, hisz itt csak új, vagy sikertelenül gyakorolt szavak lehetnek, ezeket mindig kérdezi a program.

Hogy is néz ki?

Az alábbi 4 képen a Memori legfontosabb funckiói láthatók. Az 1. ábrán lévő listában minden leckéhez található egy diagram, ez hivatott mutatni a szavak dobozonkénti eloszlását. Az első oszlop felel meg az első doboznak, a második a másodiknak, és így tovább. Piros szín jelzi azokat a kártyákat, amelyeket gyakorolnunk kell, a barna szín az inaktív kártyákat mutatja. (Inaktívak azok, melyeket legutóbb sikeresen ismételtünk, de még nem telt le a dobozukhoz tartozó pihentetési idő.)

Gyakorlás során (4. kép) a felhasználó megnézi a kártya előlapját, megpróbálja felidézni a kifejezést, esetleg megnézi a hátoldalt ha szükséges, majd nyilatkozik, hogy tudta-e. Füllenteni nem érdemes, mert magunkat csapjuk be. :)

Abban az esetben, ha tudjuk, hogy egy iWiW-es ismerősünk már felvitt egy olyan leckét, melyet gyakorolni szeretnénk, a szavak begépelését is megspórolhatjuk. Az ismerőseim menüpontban (3. kép) megkeressük az emberünket, s lehetőségünk van átvenni a leckéjét.

1.kép - leckék listája	2. kép - lecke szerkesztése
3. kép - ismerősök leckéi	4. kép - lecke gyakorlása

Remélem, hogy sikerült egy hasznos alkalmazást összekalapálnom. Jó sok időmet elvitte a fejlesztés, ezúton is köszönöm pkitti véget nem érő türelmét, amivel tolerálta az éjszakai kódoló szeánszokat. :)

Rengeteg funkció implementálására már nem maradt idő, de ha a használati statisztika is úgy akarja majd, fogom még továbbfejleszteni a Memorit. Holnaptól a hibajavításé az elsődleges prioritás, ha bug-ot észleltek, jelezzétek itt a hozzászólásokban, vagy a memori kukac hiperkocka.hu email címen.

Mindenkinek kellemes tanulást! :)

Hiperkocka újra száguld

2008-11-15T00:00:00-08:00

A hiperkocka.hu első verziója nem volt túl hosszú életű. 3 nap alatt 3 poszt augusztusban. A Blogger.com jó választásnak tűnt, de mégsem vált be nálam. Nem bírtam megbarátkozni a böngészőben való szövegszerkesztéssel. Folyamatosan ment a copy-paste a Firefox és a desktop texteditor között. Ugyanez, ha a stylesheet-en akartam változtatni. Kissé nehézkes volt, így időlegesen abba is maradt az írás.

De csak időlegesen, mert az elmúlt egy hétben ismét kézbe vettem a dolgokat. Azért csak most, mert szeptember, október kissé fullosra sikerült. A napi nyolc órás meló mellé beütött egy ruby-s fejlesztés, amire cirka 1 hónapunk volt. Aztán szívtunk az üzembeállítással is pár hetet, de jelenleg vígan muzsikál a cucc. Csak annyit mondok: Merb IBM Websphere-en!!! Az első pénzes ruby-s meló, kötelező volt elvállalni. Lesz még róla szó itt.

Az újjászületést segítette: Webby

Az októberi Budapest.rb-n is volt szó a webby-ről, de már korábban felkeltette az érdeklődésemet eme frappáns megoldás. De miért is jó ez nekem?

a saját szövegszerkesztőmben írhatom a posztokat, faraghatom az oldalt
az egészet verziókezelőben tarthatom (a bejegyszéseket is!!!)
mivel a webby kimenetén statikus fájlok jönnek ki (html, css, js, xml), ezeket egy webszerverre felmásolva már megy is az oldal, nem kell se adatbázis, se ruby, se semmi a kiszolgáló gépre
használhatok template nyelveket tetszés szerint (sass-t a stylesheet-ekhez, haml-t, textile-t, erb-t a html-ekhez)
mert ruby, és szeretem :)

A külcsín egyszerű lett, még faragom, de a tartalomra kellene innentől fogva koncentrálni.

sqlplus command line history Linux alatt

2008-08-10T00:00:00-07:00

Fel kell installálnunk az rlwrap programot. Ubuntura például így:

$ sudo apt-get install rlwrap

Majd indítsuk az sqlplus-t az alábbi módon:

$ rlwrap sqlplus

Ha valaki lusta készíthet rá aliast a .bashrc-ben:

alias sqlplus='rlwrap sqlplus'

És készen is vagyunk. Have fun!

Jogosultságok Oracle DB-ben

2008-08-10T00:00:00-07:00

A minap szembesültem egy jogosultági problémával Oracle-ben, s mivel régen volt már az OCP vizsga, és én gyorsan felejtek, kénytelen voltam felfrissíteni ismereteimet a témában. Ha már így jártam, s mivel ketten is Oracle-ös posztokra nyilvánították ki igényüket a nyitóbejegyzés kommentjeiben, gondoltam írok a témáról.

Jogosultságok típusai

Két fajta jogosultság létezik Oracle-ben: objektum szintű (object privileges), és rendszer szintű (system privileges). A műveletet, amivel jogot adunk egy user-nek bizonyos dologra szép magyarul grantolásnak nevezzük, és meglepő mód a GRANT utasítással lehet elvégezni. Visszavonni a REVOKE-kal lehet.

Rendszer szintű privilégiumok: ilyen bizonyos műveletek végrehajtásának joga (pl.: csatlakozás az adatbázishoz, vagy táblatér létrehozása), és idetartoznak azon jogosultságok amik egy séma összes azonos típusú objektumára vonatkoznak (pl.: lekérdezés egy séma bármelyik táblájából).
Objektum szintű privilégiumok: egy bizonyos művelet végrehajtásának joga egy bizonyos séma egy bizonyos objektumán (pl.: sorok törlésének joga a HR user DEPARTMENTS tábláján). Bizonyos típusú objektumokhoz (CLUSTER, INDEX, TRIGGER, DATABASE LINK) nem tartoznak objektumszintű privilégiumok, hanem csak rendszer szintűek. Ha egy szinonímára grantolunk objektum szintű privilégiumot, akkor az egyenértékű azzal, mintha a szinoníma által hivatkozott objektumra grantolnánk. A szinoníma eldobása után a jog nem is fog elveszni.

Szerepek

Jogosultságokat adhatunk felhasználóknak (user) és szerepeknek (role). Mire jók a szerepek? Segítségükkel összefoghatunk privilégiumokat, és ezeket egyszerre oszthatjuk ki felhasználóknak, sőt akár más szerepeknek is, így egyszerűsíthetjük az adiminsztrációt.

Szerepek munkamenet (session) szinten lehetnek ki- és bekapcsolt állapotban. SET ROLE utasítással tudjuk ezt megtenni. Fontos tudni, hogy Oracle-ön belüli programoknak (függvények, eljárások, csomagok) közvetlenül kell kiosztani a jogosultságokat, szerepeken keresztül kiosztott jogosultságot nem használhatnak. Hiszen fordítási időben nem tudhatja az adatbázis, hogy mikor majd a program futni fog, a szükséges szerep aktív állapotban lesz-e.

with admin option, with grant option

Rendszer szintű privilégium és szerep esetén a WITH ADMIN OPTION megadásával megengedhetjük, hogy a felhasználó, aki kapta a jogot vagy szerepet, tovább is adhassa azt másoknak. Objektum szintű privilégiumok esetén a WITH GRANT OPTION-t kell használnunk, ha azt akarjuk, hogy tovább lehessen adni szerepeknek vagy felhasználóknak.

Ha WITH ADMIN OPTION-nel jogot adtunk Bobónak, majd visszavonjuk, de ő addigra már tovább grantolta Benőnek, akkor a továbbadott jogot Benő nem fogja elveszíteni. Viszont objektum szintű privilégium esetén, ha WITH GRANT OPTION-nel kiosztottuk Bobónak valami, aki továbbadta Benőnek, ezután visszavonjuk Bobótól, akkor ezzel a mozdulattal Benőtől is visszavontuk. Fincsi mi?

Jogosultságok kiosztása

Objektum szintű jogosultságot adunk Bobo nevű kollégának, hogy módosíthassa a departments tábla department_name oszlopát.

SQL> GRANT UPDATE (department_name) ON departments TO bobo;

A looser_privs szerepnek jogot adunk, hogy bármilyen táblát eldobhasson, majd Bobo megkapja a looser_privs-t.

SQL> GRANT DROP ANY TABLE TO looser_privs;
SQL> GRANT looser_privs TO bobo;

Majd rájövünk, hogy inkább visszavonunk mindent

SQL> REVOKE UPDATE ON departments FROM bobo;
SQL> REVOKE DROP ANY TABLE FROM looser_privs;

Jogosultságok lekérdezése

A következő nézetekből tudjuk lekérdezni, hogy kinek milyen jogosultságai vannak:

DBA_USERS: adatbázisban található felhasználók.
DBA_ROLES: adatbázisban található szerepek.
DBA_TAB_PRIVS: felhasználóknak és szerepeknek kiosztott objektum szintű jogosultságok. Ne zavarjon meg senkit a tábla neve, az összes
DBA_SYS_PRIVS: felhasználóknak és szerepeknek kiosztott rendszer szintű jogosultságok.
DBA_ROLE_PRIVS: felhasználóknak és szerepeknek kiosztott szerepek.

A végére pedig jöjjön három trükkös lekérdezés (forrás). Az első megadja, hogy egy user-nek, milyen szerepei vannak (rekurzívan) és a szerepeken keresztül milyen rendszerszintű privilégiumokkal rendelkezik.