Older blog entries for cactus (starting at number 155)

Not worth the paper it's printed on

We have all the Intentional coworkers (well, most of them, anyway) in Budapest all week, spending most of the time in meetings. Being the funny guy that I am, I try my best to shake things up with one-liners.

So Shane was showcasing us some new features, when, as it usually happens at demonstrations, our system crashed. Francois, at that point, was shredding some of his notes, but the paper he used was such that the shredding made a lot of noise. So I asked out loud:

Were those your stocks?

Judging by the full room laughing for over a minute, it's good to know that if programming doesn't work out, I can still look forward to a lucrative career as a comedian...

Syndicated 2007-11-14 18:03:00 from cactus.rulez.org

Diviánszky Péter for prezident!

Van ez a Be-ad beadandóprogram-kezelő webes rendszer, és ezen keresztül kellett az IA-32 assembly házifeladatot beadni. Igen ám, de nem csak a felvett kurzusok feladatait listázza ki a rendszer, hanem az összeset, amiről tud. Így hát amikor az assemblyt beadtam, megláttam hogy van egy Haskell kurzus is, feladatleírással mindennel, és just for fun beadtam arra is megoldást. Persze a félreértések elkerülése végett beleírtam az elejére egy kommentbe, hogy én igazából nem is járok arra a gyakorlatra. Kicsit egyébként számítottam arra, hogy majd jön egy levél hogy kinek a szabadidejével szórakozzak (hint: közeli felmenő nőrokonom).

Erre most veszem észre, hogy a tárgy oktatója, Diviánszky Péter (akit amúgy nem is ismerek), leellenőrizte, bevitte a rendszerbe hogy jó a megoldás, sőt, még el is küldte a kanonizált megoldás linkjét!

Syndicated 2007-11-10 12:50:00 from cactus.rulez.org

Nintendo a seggem

Kibaszott Super Paper Mario bazmeg, végigviszem a 100 szintes kurva dungeon-t ahol persze végig nem lehet save-elni, erre a végén megbasz a boss, és persze hogy game over, holnap kezdhetem előlről...

Eeez bazmeg ez a Nintendo, akik elvileg a játéktervezés meg a fun-csinálás csúcsa? Hogy egy órán keresztül nem lehet save-elni? Tán még majd vizet is melegítek, nem?!

Syndicated 2007-10-30 22:10:00 from cactus.rulez.org

Sapkakiválasztási axióma

Az egész egy ártatlannak tűnő fejtörővel kezdődött, amit András hozott a brigádnak. A feladat így szól:

Egy börtönben megszámlálhatóan végtelen rab raboskodik. Az unatkozó börtönőrök azt találják ki, hogy mindegyik rab fejére piros vagy kék sapkát húznak, úgy, hogy senki se lássa, a saját fejére milyen színű kerül, majd miután a rabok jól megnézték egymást (minden rab a sajátján kívül az összes többi rab sapkáját látja), mindegyiküktől megkérdezik, milyen színű sapka van a fején. Ha legfeljebb véges számosságú rossz válasz születik, a rabokat mind elengedik. Milyen stratégiát találjanak ki a rabok, hogy biztosan kijussanak?

Sajnos szerdán közölte a feladatot, és én először csütörtökön voltam dolgozni, úgyhogy addigra Encsének már volt egy (tudottan rossz) megoldás-vázlata. A következőek miatt fontos megismernünk ezt a megoldást, és azt is, hogy miért rossz.

Tegyük fel, hogy a rabok előre sorba rendeződnek, és megállapodnak egy algoritmusban, ami megszámlálhatóan végtelen hosszú piros/kék sorozatokat állít elő. Amikor minden rab fején sapka van már, mindegyik rab elkezdi futtatni az algoritmust, és megnézik, vajon az első, második, ... sorozatra igaz-e, hogy legfeljebb véges esetben adna hibás választ, ha az n. rab válasza az aktuális sorozat n. tagja lenne. A saját sapkájukat nem ismerve is mindannyian ugyanara a sorozatra fogják először megállapítani, hogy megfelelő. Ezekután valamennyi rab e szerint a sorozat szerint fogja a ráeső sapka-színt válaszolni.

Ha az őrök ki tudják kérdezni a rabokat, és meg is tudják állapítani, hogy legfeljebb véges rossz válasz született, akkor ezeket a műveleteket megengedettnek vehetjük (használhatjuk a börtönőrök algoritmusait), vagyis a végtelen sorozatok előállítását és egyes sorozatok ellenőrzését elvégezhetik a rabok.

A megoldás mégsem helyes, mivel könnyen látható (közvetlenül Cantor módszerével, vagy pl. a sapka-sorozatokat kettedesjegy-bitsorozatként értelmezve, a [0,1]-beli valós számokkal azonosítva), hogy a lehetséges sapkasorozatok kontinuum számosságúak, ezért nem sorolhatóak fel, vagyis egy mégoly erős algoritmus, amelyet a feladat, mint láttuk, implicit megenged, és könnyedén előállít végtelen bitsorozatokat, sem tudná valamennyi lehetséges sorozatot előállítani.

De vajon szükség van-e valamennyi sorozat előállítására? Nyilván nem, hiszen sok olyan sorozat van, amelyek közül egy adott sapka-leosztás esetén bármelyikre is jutnak a rabok az algoritmust futtava, a rossz válaszok száma legfeljebb véges. Definiáljunk ugyanis egy olyan binér relációt a megszámlálhatóan végtelen hosszú bitsorozatok felett, amelyben két sorozat relációban van, ha van olyan index, amelytől megegyeznek, vagyis legfeljebb véges tagjuk tér el. Ez a reláció nyilván ekvivalencia-reláció, és a raboknak elegendő egy olyan algoritmus, amely minden ekvivalencia-osztályból előbb-utóbb előállít legalább egy sorozatot.

Mármost vizsgáljuk meg az ekvivalencia-osztályok számát! Sajnos azt kapjuk, hogy ezek továbbra sem megszámlálhatóak, hiszen egy-egy osztálya úgy áll elő, hogy vesszük egy reprezentánsát, majd hozzávesszük azokat az egyéb sorozatokat, amelyek tőle egy tagban térnek el (ilyenből nyilván megszámlálhatóan végtelen van), amelyek két tagban (szintén), és így tovább. Megszámlálhatóan végtelen darab megszámlálhatóan végtelen halmaz uniója azonban még mindig csak megszámlálhatóan végtelen. Mivel az osztályok uniója, vagyis az összes sorozat megszámlálhatatlan, nyilván az osztályok száma is az.

A fenti gondolatmenet alapján tehát bárki meggyőzhető, hogy az ismeretett megoldás hibás. Csakhogy András egy ehhez nagyon hasonló megoldást ismertetett kanonizáltként (mint kiderült, a feladatot, és a megoldását ő matek-szakos hallgatóktól hallotta): a rabok megállapodnak ekvivalenciaosztályonként egy-egy reprezentánsban, és amikor az őrök kikérdezik őket, mindannyian a látott sapkák által meghatározott osztály reprezentánsának tagjaival válaszolnak.

Persze amikor ezt András előadta, kitört a pokol, mert átverve éreztük magunkat. Ugyan hogyan tudnának megállapodni a rabok az ehhez szükséges ℝ→ℝ függvényben, ha általában még a valós számok egy részhalmazára sem adható kiszámítható szelektorfüggvény? Mint kiderült, a forrásnak számító matekhallgatókat ez a részlet egyáltalán nem zavarta.

Aztán rákerestünk a neten, és kiderült, amit már akkor éreztem a zsigereimben, amikor a "megoldást" hallottuk: a megoldás valójában a kiválasztási axiómán függ, nem is lehetne konstruktív. Persze a linkelt oldallal ellentétben én nem gondolom, hogy ebből a kiválasztási axióma valamiféle értékelését vonhatjuk le, viszont szerintem az eredeti feladatban szereplő rabokon fikarcnyit sem segít bármilyen, nem-konstruktív módszer.

És innentől válik a kérdés filozófiaivá, és itt dobom be a gyeplőt a leendő kommentelők közé: szerintetek mi a helyzet?

Syndicated 2007-10-27 20:38:00 from cactus.rulez.org

Jönnek a letölthető Wii demók?

Az előbb vettem észre, hogy jött a Nintendotól egy üzenet a Wii-mre, hogy a Shop Channel-en keresztül letölthető a Metroid Prime 3-hoz egy preview videó. Hogy maga a videó milyen, azt még nem tudom, mert ahogy egész Európa rácuppant a témára, a Shop Channel hihetetlenül laaaaaaaaaaaasssúúúúú lett. Viszont azt érdekes lesz meglátni, hogy rámegy-e a Nintendo az X-Box Live-vonalra, lesznek-e később játszható letölthető demók.

Persze az is lehet, hogy az egésznek az lesz a vége, hogy a Nintendo csúnyán megbánja, hogy csak fél gigányi tárolókapacitást tervezett a konzolba, és egyetlen játszható demót sem fognak tudni megjelentetni, ever.

Syndicated 2007-10-15 20:42:00 from cactus.rulez.org

K stands for Kwality

Meg nem nevezett (mert egyébként semmi bajom vele) EAF4 gyakorlatvezető a következő példakódot prezentálta arra, hogy hogyan egyszerű új elemnek elsődleges kulcsként szolgáló azonosítószámot generálni, az amúgy SQL adatbázisra épülő programban:

int create_index (QSqlTable table)
{
  for (int id = 0; ; ++id)
  {
    bool found = false;
    for (int i = 0; i < table.rowsNum() && !found; ++i)
    {
      if (id == table.getRow(i)["id"])
        found = true;
    }

    if (!found)
      return id;
  }
}

Kész bazmeg, ilyen nincs, kifekvés meghalás megkészülés. Kérdezem tőle, tudja-e, hogy ezt meg lehet csinálni jobban (maximumkeresés) és jól (rábízni az egészet az adatbázismotorra)? Erre azt mondja, hogy igen, lehet ezt az adatbázisban is megoldani: felveszünk egy egysoros, egyoszlopos táblát, amiben a legutóbb kiosztott azonosító van, és ezt mindig növeljük egyel, amikor valamelyik táblába új elemet rakunk be.

Erre meg már tényleg nem tudtam mit lépni. Mit lépni, szaladni ki a világból!

Syndicated 2007-10-12 19:16:00 from cactus.rulez.org

Egy jó doboz bármit elad

Ez igazából a NooBTooB eheti adását nézve jutott eszembe: az egyik betelefonáló arról mesél, hogy milyen vicces is az, amikor valaki, aki egyáltalán nincs képben a számítógépes játékokat illetően, rácsodálkozik az ötéves "modern" játékokra.

Szóval történt három éve, hogy Milánnal egy Media Marktban vagy Electroworldben vagy ilyesmiben voltunk, és én éppen a Playstation 2-kínálatot böngésztem. Milán akkoriban kapott rá a számítógépes játékokra (későn érő típus, ugye), úgyhogy ő a PC-s polcokat nézte. Egyszer csak odajön hozzám egy dobozzal a kezében, hogy nézzem meg, mit gondolok róla, mert a doboz alapján egész jó lehet, ilyen kommandós izé, meg mintha hasonlítana Rainbow Six-re, amivel éppen akkoriban játszott.

És hogy mi volt az a játék, ami 2004-ben felkeltette Milán érdeklődését, és amiről megkérdezte, hogy véletlenül nem hallottam-e már róla hogy milyen?

2004-ben?

Az eredeti Counter-Strike.

Syndicated 2007-10-07 16:52:00 from cactus.rulez.org

Valós halál

Organikus károkozás — ezzé bagatellizálódott a gyilkosság Richard Morgan regényének világában. A könyvben felvázolt jövőben az emberi tudatot ugyanis egy erre alkalmas, tarkóba épített elektronikus berendezés (a tudattok) tárolja, és nem jelent gondot bármikor újraburkolni, átültetni másik—akár szintetikus—testbe. Problémát tehát csak a címadó valós halál, a tudattok megsemmisülése jelent.

Richard Morgan: Valós halál

Morgan sci-fi krimije alaposan körbejárja az alapötlet felvetette kérdéseket. Hogyan viszonyulnak a néhány generáció óta jelen lévő, a tudatot és a testet teljesen elválasztó technikai bravúrhoz az életösztönt milliárd év alatt internalizált emberi lények? Mit jelent a társadalom számára, ha a tehetősebbek megannyi testet és klónt tarthatnak fenn a maguk számára, és az alsóbb osztályok emberöltőinek életét nézhetik végig, gyakorlatilag tetszőleges ideig? Mennyire fontos a testek, és mennyire a személyiségek vonzódása a párkapcsolatokban?

Takeshi Kovácsnak, egy katonai speciális osztag, a Küldöttek veteránjának magánnyomozása jelenti a történetet, amolyan oldschool Philip Marlowe-stílben. Morgan az általa teremtett világról mindig csak apró részleteket mutat, sosem tol az olvasó arcába szájbarágó magyarázatokat arról, ami a XXI. és a XXVI. század között történt. Szerintem ez pozitív.

Ami viszont nem tetszett, illetve inkább csak nem felelt meg a prekoncepciómnak, az az, hogy sokkal modernebb sci-fire számítottam. A magyar kiadás borítója büszkén hirdeti, hogy a regény "Philip K. Dick-díjas", bármit is jelentsen ez, de pont Dick ugyanezt a regényt negyven évvel ezelőtt simán megírhatta volna, mondjuk azzal együtt, hogy az biztos egy kevésbé követhető könyv lenne.

A centrális kérdést jelentő test-tudat dualitást pedig bár körbejárja, de leglényegesebb pontjára mintha félne kitérni. A történetben ugyanis többször szerepel a távtárolás technikája, sőt, a bonyodalmat is ez adja: vagyis hogy egyesek tudatáról időnként biztonsági másolatot készítenek, és szükség esetén, ha a tudattok megsemmisül, innen visszaállítható egy pár órával a halált megelőző állapot. Igen ám, de mennyiben tekinthető ez örök életnek, mennyire jelenti azt a szubjektív én számára, hogy nem kell félnem a (valós) haláltól? Vajon miért érezném súlytalannak a valós öngyilkosságot csak azért, mert halálom után pár órával már újra beburkolnak egy testbe valakit, aki a regénybeli logika szerint én vagyok? Hiszen nyilvánvaló, hogy én én, aki meghúzom a ravaszt, ez a tudat, a maga folytonosságában megszűnik létezni. Akkor hogy is van ez? Az ikertestvérem nem én vagyok...

Syndicated 2007-10-03 18:22:00 from cactus.rulez.org

(cross-posted from here)

Queueing timeouts in JavaScript

I wanted to create a simple animation to illustrate sorting algorithms, using SVG and JavaScript. The basic idea was to present a simple JavaScript API that sorting implementations could use. It turned out I had to implement my own timeout queueing contraption for this.

I was aiming for being able to write something like the following code:

function bubble ()
{
    for (var i = array.length - 1; i != 0; --i)
    {
        for (var j = 0; j != i; ++j)
        {
            if (less (j + 1, j))
                swap (j + 1, j);
        }
        mark_as_done (i);
    }
    mark_as_done (0);
}

Looks pretty straight-forward, doesn't it? One just needs to write less(), swap() and mark_as_done() to change/animate certain SVG objects, and it's all done, right? Well, I'm certainly no Javascript wizard, so that's what I thought too.

However, since JavaScript is not run in a thread separate from the browser, you can't just implement animation by modifying values and wait()'ing for a couple of milliseconds. In fact, it turns out, there's no explicit way to wait for a given time at all. What you can, and should, do, is set up a callback to be executed after a certain amount of time. The JavaScript API for this is a function called setTimeout(), and there's also a separate function called setInterval() that sets up the callback to be run every n milliseconds.

The APIs are string-based, that is, callback functions and arguments are passed as JavaScript text. That alone calls for some quite un-intentional coding, for example, check out the source code for this SVG file:

function start_animation()
{        
    setTimeout("anim_down('subject', 10)", 25);
}


function anim_down (id, n) { var elem = document.getElementById(id); translate (elem, 0, 10);

if (n) setTimeout("anim_down('" + id + "'," + (n - 1) + ")", 25); else setTimeout("anim_left('" + id + "', 20)", 25); }

As you can see, it's a pain in the ass to make sure everything is nicely representable as a string -- e. g., XML element ID's are passed around instead of pointers to the actual elements. But you can always store state in some global variable, that's not the real problem. To see what the problem is, try clicking repeatedly on the button and see how the animation gets deformed. It's not hard to guess what's happening: a second timeout-cascade is set up before the first one had time to finish.

So in the bubble() function defined above, all swapping animations would start simultaneously. And there's no way to select() or join() or whatever until a certain timeout has run. We need to create a timeout queue.

Look at the code below for a minimalistic approach. Timeouts that register timeouts themselves should set/clear current_timeout, like in this example.

var timeout_queue = [];
var timeout_queue_timeout = 0;
var current_timeout = null; 
var timeout_queue_freq = 100;


function pop_timeout () { if (!timeout_queue.length) { clearInterval(timeout_queue_timeout); timeout_queue_timeout = 0; return; } if (!current_timeout) { var timeout = timeout_queue.shift(); timeout.run (); } }

function queue_timeout(timeout) { timeout_queue.push(timeout); if (!timeout_queue_timeout) timeout_queue_timeout = setInterval("pop_timeout()", timeout_queue_freq);

pop_timeout (); }

Try clicking multiple times in quick succession in the second example: you won't see any corruption in the animation this time. Also, if you look at the code, thanks to the pseudo-synchronization, the animation can be expressed more intentionally:

function start_animation()
{
    animate('subject', 0, 10, 10);
    animate('subject', 10, 0, 20);
    animate('subject', 0, -10, 10);
}
25 Nov 2005 (updated 25 Nov 2005 at 20:11 UTC) »
Porting Guikachu to Windows

After surveying what needs to be done to get Guikachu on Windows, it turned out it's not going to be a difficult task. The only libraries that are not readily available for MinGW are libgnomeui, gnome-vfs and GConf. Of these three, making libgnomeui and GConf optional is straighforward, but Gnome-VFS is used throughout the IO code, which in turn is used throughout the whole codebase.

So what I first did was creating new implementations of load_uri/save_uri that use POSIX open/read/write/close calls.

Then I looked at GTKmm for Windows. At this point, I should point out that GTK+ doesn't work on Windows 98. It would have saved me a lot of frustration, have I known this in advance.

All in all, the port is coming along nicely, with some ugly hacking inside Automake-generated Makefiles, I've got it to compile today. It still has problems at link-time, however: ld is complaining about missing VTables of some GTKmm classes. I hope to sort these out by tomorrow.

Update: It's alive! (click here for screenshot)

146 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!