*hypf*

Die Skript-Sommerspiele 2009 werden heute eröffnet. Ich werde teilnehmen und versuchen, die einzelnen Probleme auch zu golfen.

Die Ankündigung der einzelnen Ereignisse ist leider etwas schwer zu finden, deswegen habe ich auch erst heute gemerkt, daß sie schon bei Event 5 sind. Aber eigentlich und offiziell beginnt das ganze heute.

Meine Lösungen liegen in meinem SVN-Repository.

Update (2009–08–06): Ich habe eine signierte Ausgabe von Windows Powershell: Step by Step gewonnen.

Zelluläre Automaten

Eindimensionale zelluläre Automaten lassen sich relativ einfach beschreiben: Letztlich hat man nur eine Kette von Zellen, die jeweils einen von zwei Zuständen haben: An oder Aus (0 oder 1, lebendig oder tot, wie auch immer man es bezeichnen will). Das kann man natürlich dann auch einfach mit Bits repräsentieren.

Zustände in allen zellulären Automaten ändern sich aufgrund der Nachbarschaft einer Zelle im jeweils vorhergehenden Zustand. Nehmen wir an, man hat eine lebendige Zelle (An, 1) und ihre Nachbarn in beide Richtungen sind tot (Aus, 0). Nehmen wir uns weiterhin eine Tabelle, in der steht, daß für exakt diese Konfiguration der Zelle und ihrer Nachbarn ihr Zustand zu tot wechselt (kann gut passieren, vielleicht starb sie ja aus Vereinsamung). In einer anderen Konfiguration sind die Nachbarn vielleicht nicht tot, sondern lebendig und in diesem Falle lebt die Zelle weiter. In noch einer anderen Konfiguration hat man vielleicht eine tote Zelle und egal, wie ihre Nachbarn aussehen, ändert sie ihren Zustand zu lebendig.

Zustandsübergänge

So eine Tabelle braucht im Grunde nicht viele Dinge: Der Zustand einer Zelle, die Zustände aller Nachbarzellen (nur zwei in diesem Fall) und der Zustand, den die Zelle in der nächsten Generation haben soll. Wir können das auch folgendermaßen darstellen:

In der oberen Zeile haben wir jeweils eine Zelle mit ihren zwei Nachbarn, links und rechts, also immer drei Zellen. Die untere Zeile liefert den jeweiligen Folgezustand für jede Konfiguration. Wie man vielleicht bemerkt hat, gibt es nur acht mögliche verschiedene Konfigurationen. Auf diesen können wir eine einfache Ordnung definieren, indem wir sie jeweils als drei Bits und damit als Zahl auffassen. Diese absteigende Ordnung habe ich hier auch verwendet. Haben wir diese Ordnung erst einmal, besteht diese komplette Regel nur noch aus acht Folgezuständen, die sich ebenfalls als Nullen und Einsen und damit als einzelne acht-bittige Binärzahl auffassen lassen. Diese Numerierung wurde vom britischen Mathematiker Stephen Wolfram erfunden und wird demzufolge auch als “Wolfram-Regel” bezeichnet.

Die Regel in obigem Bild ist Regel 30.

Darstellung

Nun wissen wir, daß so ein zellulärer Automat als einzelne Zahl beschrieben werden kann und daß er im Laufe der Generationen seinen Zustand ändert. Nur was bringt uns das?

Wir könnten zum Beispiel einen einzelnen Zustand dieses Automaten als eine Reihe von schwarzen und weißen Kästchen darstellen:

und dann könnten wir jede Generation under der jeweils vorhergehenden darstellen:

und siehe da, wir kriegen ein hübsches Bild. Ein wenig chaotisch, aber das ist nun mal bei der Regel so. Es gibt auch welche, die regelmäßigere Muster liefern.

Also war der Sinn und Zweck des Ganzen lediglich, ein merkwürdiges Bild zu erzeugen. Nun also zum spaßigen Teil: So etwas zu programmieren.

Der Quelltext

Es ist nicht gerade sonderlich schwer, das zu programmieren, also fangen wir einfach oben an:

Wir brauchen natürlich ein wenig Kontrolle darüber, wo das Programm aufhört zu berechnen. Ich setze eine einzelne Zelle mit Zustand 1 in die Mitte der ersten Generation (Anfangszustand), daher ist eine ungerade Breite nicht unsinnig, da sich viele Muster gleichmäßig nach links und rechts ausbreiten. Die Höhe hängt in ähnlicher Weise damit zusammen, da die Ergebnisse meist aufhören, sinnvoll zu werden, sobald ein sich ausbreitendes Muster den rechten und linken Rand erreicht.

Wenn die Regel als Parameter für das Programm gegeben wird, brauchen wir nicht danach fragen, lediglich, wenn sie außerhalb des zulässigen Bereiches (0–255) liegt. Gefragt wird so lange bis eine korrekte Regel eingegeben wurde (ja, hier kann man noch hilfreiche Hinweise geben, aber da hatte ich keine Lust zu).

Ich habe hier ein kleines Unterprogramm geschrieben, welches die Regel in ihre acht Einzelkonfigurationen zerlegt:

Hiernach haben wir acht Variablen, wolfram_x mit x zwischen 0 und 7, die jeweils die Folgezustände für jede Konfiguration beinhalten.

Danach initialisieren wir den Bereich, wo die Zustände jeder Zelle für jede Generation gespeichert werden:

Im Prinzip wird nur jede Zelle mit 0 initialisiert und eine einzelne 1 in der Mitte der ersten Generation hinzugefügt.

Wir haben allerdings noch ein kleines Problem mit diesem Ansatz: Wenn folgende Generationen berechnet werden, braucht jede Zelle eine Nachbarschaft. Nur wie sieht diese Nachbarschaft für die jeweils ersten und letzten Zellen einer Generation aus? Anfangs habe ich einfach nur eine weitere Null links und rechts an jede Zeile gehängt. Das funktioniert gut für die meisten Regeln und wir belassen es erstmal dabei. Wie man das nun in obigem Quelltext umsetzt, lasse ich als Übung für den Leser.

Was auch praktisch wäre, ist ein Unterprogramm, welches das komplette Bild ausgibt:

Es sind tatsächlich sogar zwei Unterprogramme, diese werden später noch praktisch.

Was natürlich immer noch fehlt, ist die Berechnung der Folgezustände. Also tun wir dies mal:

Nichts außeregwöhnliches hier, wir delegieren lediglich die Berechnung einer einzelnen Zelle an ein weiteres Unterprogramm. Wie vielleicht auffällt, zeige ich die Zeile sofort nachdem sie berechnet worden ist, was das Zuschauen während das Programm läuft, etwas weniger langweilig macht, da wir dann alle paar Sekunden eine neue Zeile sehen (ja, das Ganze ist so langsam).

Hier wird der neue Zustand einer einzelnen Zelle berechnet unter Zuhilfenahme eines weiteren Unterprogramms, welches den spezifischen Fall aus der Tabelle sucht. Wir machen uns hier die Tatsache zunutze, daß die Zelle und ihre Nachbarn im Grunde eine drei-Bit-Zahl ist und die Tabelle auch zugreifbar ist, indem wir diese drei Bit in eine Dezimalzahl zwischen 0 und 7 überführen. Der Code dafür ist leider ein wenig unschön, da viel Escaping nötig ist (die Klammern habe ich jedoch lediglich aus Vorsicht so behandelt, da Klammern gern etwas kaputt machen, besonders, wenn man anfängt, Strukturen zu schachteln).

Aber das war eigentlich schon alles. Führt man diese Batchdatei nun ohne Argumente aus, kommt die folgende Abfrage:

geben wir hier nun sagen wir 54 ein, kommt das folgende Bild zustande:

Der eigentliche Quelltext der Batchdatei ist ein wenig länger, da ich inzwischen auch eine Option anbiete, was mit dem linken und rechten Rand geschehen soll (alles null, alles eins, zylinderförmig und kopieren, letzteres ist nun die Standardeinstellung, da zum Beispiel Regeln wie 169 sehr merkwürdig aussehen, wenn sie mit Null-Kanten berechnet werden).

Momentan arbeite ich noch an SVG-Export aus dieser Batch-Datei (der Grund, warum ich die eigentlich geschrieben habe) und hoffe, inzwischen alle größeren Bugs gefunden zu haben. Die erste funktionierende Version hatte übrigens nur 54 Zeilen. Ich denke, hätte ich Java benutzt (was hier gerade die einzige andere Alternative war), hätte ich deutlich mehr gebraucht.

UPDATE (2008–12–26 16:21): SVG-Export ist fertig und werkelt nun auch wie er soll. Momentan lasse ich den Terminal Server in der Uni an allen 256 Automaten gleichzeitig rechnen:

Die Taskleiste liegt üblicherweise (zumindest für 98,4 % der Benutzer) am unteren Rand des Bildschirms. Nun werden Bildschirme im Breitbildformat (16∶10 zumeist) immer häufiger (und ich habe oft ohnehin so viele Fenster offen, daß der Fenstertitel in der Taskleiste auf wenige Buchstaben reduziert wird), daß es verlockend scheint, die Taskleiste einfach an den linken oder rechten Rand zu kleben. Das hat den Vorteil, daß man mehr vom Fenstertitel sieht, gerade wenn viele Fenster offen sind. Und zumindest für mich bringt ein Bildschirm in dem Format auch nicht so unglaublich viel, da das meiste, was ich mache (Webseiten lesen oder Code schreiben) eher vertikale Aktivitäten sind und nicht ganz so viel Platz in horizontaler Richtung benötigen. Zugegeben, in Eclipse oder Visual Studio ist mehr Platz immer gut, aber ich nehme lieber mehr Gesamtauflösung anstelle von mehr horizontaler Auflösung.

In der Taskleiste werden nun Tooltips angezeigt, wenn der Fenstertitel nicht komplett auf die Schaltfläche paßt:

Gleiches passiert auch bei einer vertikalen Taskleiste:

Nun ergibt sich hier ein Problem. Der Tooltip bei der horizontalen Taskleiste wird nie wirklich im Weg sein. Am unteren Rand von Fenstern befindet sich meist allenfalls eine Statusleiste aber nichts wirklich Wichtiges. Der Tooltip einer vertikalen Taskleiste hingegen erscheint an einer Position und Höhe, wo im Normalfall keine Statusinformationen eines Programms sind, sondern Inhalt, den man erfassen möchte.

Das ist besonders nervig, wenn man ein Fenster wiederherstellt, welches vorher maximiert war. Der Fensterinhalt fängt also gleich neben der Taskleiste an und der Tooltip erscheint ungefähr zu dem Zeitpunkt wo das Fenster fertig gezeichnet wurde und man gerade anfangen könnte, darin etwas zu suchen.

Webseiten zumindest werden üblicherweise in einem F-Muster abgesucht. Daher ist bei vielen Websites die Navigation auf der linken Seite. Bei normalen Programmen ist dies zuweilen auch zu beobachten: Die Liste der Mailordner in meinem E-Mail-Programm ist links und üblicherweise ist es genau diese, die mich interessiert, wenn ich das Programm wiederherstelle, da dort hervorgehoben wird, wo ich neue Mails habe. Da ist ein Tooltip, der mir bis zu zwei Order verdeckt, nervig, da es zum Einen meine Aufmerksamkeit ablenkt und zum Anderen brauche ich einen Moment, um das Ding wieder loszuwerden. Das mag nicht nach allzu viel verlorener Zeit klingen, ist es wohl auch nicht, aber wenn man das zum wiederholten Male am Tag bewußt feststellt, ist es schon unschön.

Wahrscheinlich wird das sogar noch schlimmer, wenn man Aero aktiviert, da dort der Tooltip erst auftaucht, nachdem schon eine Miniaturansicht des Fensters gezeigt wurde. Und diese verdeckt im Normalfall sogar noch mehr.

Vielleicht wäre es auch besser, die Taskleiste an den rechten Bildschirmrand zu verlegen, da dort selten Informationen sind, die man sofort nach dem Wiederherstellen eines Fensters sucht (zumindest nehme ich das an und mir fällt momentan auch kein Gegenbeispiel ein).

UPDATE (2008–11–08 13:55): Ist Aero aktiviert, ist die Situation eher besser, denn schlimmer, die Miniaturansicht taucht gar nicht erst auf, wenn man ein Fenster wiederherstellt und der Tooltip wartet nach dem Klick noch mal die normale Zeit, ehe er erscheint (dann allerdings witzigerweise unter der Taskleiste).

Nachdem ich gestern auf meinem anderen Rechner wieder ein System aufgesetzt habe, habe ich mich dazu entschieden, mal wieder Winamp als Audio-Player zu verwenden. Ich hatte ihn zu meinen Windows-2000-Zeiten benutzt, bin allerdings nach dem Umstieg auf Windows Vista zum Windows Media Player gewechselt. Ich mochte die Medienbibliothek mit den Albencovern und daß ich nicht länger alle Dateien im Dateisystem in Ordnung halten mußte. Aber WMP war etwas langsam auf meinem schon leicht angegrauten Pentium 4 mit 2.53 GHz.

Also Winamp. Auf einem Windows Vista. Der erste Start zeigt einen netten Dialog, der mit ermöglicht, ein Skin auszuwählen (Warum eigentlich? Ich habe keine Skins mitinstalliert), Dateiverknüpfungen zu ändern sowie die Entscheidung zu treffen, ob ich anonyme Nutzungsstatistiken verschicken möchte.

Das Lustige kam danach: Nachdem ich mich durch den Dialog gekämpft habe, wollte Winamp Administratorrechte (UAC und so). Zweimal! Und jedesmal, wenn man Winamp startet fragt er noch einmal nach (stört sich aber netterweise nicht daran, wenn man es ihm verwehrt). Ich frage mich allerdings, warum. Weder Dateiverknüpfungen noch irgendwas anderes, was ich in den Optionen gefunden hätte, erfordert Administratorrechte. Nichts. Dem Gebettel nachzugeben und es einfach zu erlauben, ändert auch nichts (anders als bei Eclipse 3.3, wo man Eclipse einmalig als Admin ausführen mußte, damit es lief). Winamp fragt dennoch fröhlich bei jedem Start weiter nach Adminrechten. seufz

Andere Sache: Da ich nur eine Tastatur, eine Maus und einen Monitor habe, muß ich entweder alle naselang Maus und Tastatur umstecken oder aber die Remotedesktopverbindung nutzen. Momentan mal wieder letzteres. Ich dachte mir, da ich auf dem anderen Rechner eh gerade nicht viel anderes mache als ein paar Widerlichkeiten auf der Kommandozeile und Musik hören, brauche ich nicht ganz so viele Farben und hab die RDP-Verbindung einfach mal auf 8 Bit runtergestellt.

Das mochte Winamp nicht so wirklich. Das war quasi gleich der Schocktod beim entsetzten Anblick von nur 256 Farben oder so. Ich frage mich zwar, ob die Musik so farbenfroh ist, daß ihm das nicht reicht, aber er starb sehr schön reproduzierbar gleich beim Starten. Ich ash den UAC-Dialog und im Hintergrund dann gleich das Windows Error Reporting. Unschön. Bei höheren Farbtiefen ging es dann wieder.

Randnotiz: Die Medienbibliothek von Winamp ist (zumindest für mich) deutlich verwirrender als die vom Windows Media Player und irgendwie auch nicht sonderlich viel schneller. Ich werd Winamp also möglicherweise wieder wegtun.

UPDATE (2008–09–04 18:24): Die Sache mit UAC ist behoben. Es gibt eine gut versteckte Option “Restore file associations at Winamp start-up”, die dafür verantwortlich war. Nimmt man das Häkchen weg, so verschwindet die Nachfrage beim Start. Trotzdem, Dateiverknüpfungen ändern ist etwas, was auch ohne Adminrechte geht.

Ich gehe mal davon aus, daß einige den Norton Commander kennen oder zumindest einen der zahlreichen Klone desselben. Ich persönlich benutze Far täglich mehrfach. Eines der Dinge, die einen OFM so praktisch machen, ist die integrierte Kommandozeilenumgebung. Dies funktioniert allerdings in meinen Augen am besten in einem Textinterface, da man dort auch gleich die Resultate sieht (Total Commander geht hier ein wenig daran vorbei, finde ich).

Wäre es nicht schön, wenn man die gleiche Art von Kommandozeilenintegration auch im Windows-Explorer hätte? Ein Kommilitone erwähnte die Idee vor kurzem und ich war sofort überzeugt, daß es nützlich sein kann und würde und habe mal schnell ein Bild gebastelt, wie sowas aussehen könnte (siehe Anhang).

Ich fand nach einigem Suchen tatsächlich etwas, das so etwas bereitstellt: Command Prompt Explorer Bar, allerdings in C# geschrieben. Raymond Chen zitierte einmal Jesse Kaplan, einen Manager für die Common Language Runtime (CLR): Man sollte keine Shell-Erweiterungen in Managed Code schreiben.

Also wird das oben erwähnte Projekt, wie auch die Verwendung einzelner Teile davon wohl keine brauchbare Option sein. Insofern werde ich wohl vielleicht irgendwann das Ding so bauen, wie ich es mir vorstelle, nur dann in C++.