Wenn ich jemandem gegenüber erwähne, dass ich nach Feierabend gern das eine oder andere Programm schreibe, dann ernte ich regelmässig ein Paar hochgezogener Augenbrauen. Das kommt daher weil ich tagsüber mein Brot mit der Bedienung und Programmierung von EDV-Maschinen verdiene. Deswegen müsste ich eigentlich Abends etwas anderes tun, z.B. hm, mir fällt gerade nichts ein. Nun ist es aber so, dass ich schon in meiner Jugend gern programmiert habe, auch ohne damit Geld zu verdienen.
Als Warnung muss ich noch vorausschicken, dass ich die folgenden Programm nur für mich geschrieben habe und es deshalb sein kann, dass sie nicht allzu benutzerfreundlich sind.

Gut, los gehts:

JpgInfo

Gestelltes Problem
Angenommen, man hat ca. 10.000 Jpeg-Dateien unter denen sich viele Doppelte befinden. Diese Dubletten können sich in der Bildgrösse, in den Bildproportionen, der Helligkeit und auch der Farbverteilung unterscheiden.

Algorithmus
Das einfachste ist ein Vergleich der Dateigrössen. Damit hab' ich viele Dubletten gefunden, aber natürlich meine Anforderungen noch nicht erfüllen können. Die eine Hälfte des Algorithmus ist dadurch aber schon entstanden und zwar ist das eine Sortierung und eine anschliessende Anzeige von Dateien mit gleichem "Kennwert", zunächst eben der Dateigrösse. Ich habe mir den Quelltext für das Einlesen von Jpeg-Dateien von der "Independent JPEG Group" downgeloaded (wenn jemand mal erschreckend guten Quelltext sehen will, da ist er richtig) und somit Zugriff auf die Bilddaten. Zur Einbeziehung des Bildinhaltes werden die Jpeg-Dateien auf eine wahnsinnig schlechte Auflösung heruntergerechnet (8x8 Pixel). Dann werden sie in schwarz-weiss konvertiert, wobei ein Punkt dann schwarz ist, wenn er dunkler ist als die Durchschnittshelligkeit des Originalbildes, ansonsten weiss. Es ergibt sich also eine 64bit-Ganzzahl und nach diesem Wert werden die Bilder sortiert und dann Dateien mit gleichem Kennwert angezeigt. Dann kann der Anwender sich beide Versionen angucken und entscheiden ob die Bilder wirklich identisch sind.
Download jpginfo.exe (116 KB)

Screenshot:



FileTreeSync (Dateibackup)

Gestelltes Problem
An meinem Notebook sind zwei USB-Laufwerke angeschlossen. Auf dem Ersten befinden sich meine MP3-Dateien. Das Zweite wird zu Backupzwecken genutzt. Nun brauchte ich ein Programm, mit dem man zwei grosse Verzeichnisse mitsamt Unterverzeichnissen synchron halten kann. Mit dem Windows Explorer kam ich nämlich nicht weiter weil dieser beim Kopieren die schon vorhandenen Dateien erneut kopiert was bei grossen Dateianzahlen einfach zu lange dauert.

Algorithmus
Da ist nicht viel Algorithmus dabei, es wird ein Quellverzeichnis rekursiv durchsucht und geprüft, ob die dort liegenden Dateien im Zielverzeichnis mit gleicher Länge vorliegen. Falls nicht, werden sie kopiert. Nach dem Kopieren wird für jede Datei im Zielverzeichnisbaum geprüft, ob sie im Quellverzeichnisbaum vorhanden ist (sie könnte ja seit dem letzten Lauf gelöscht oder umbenannt worden sein). Falls sie dabei nicht gefunden wird, wird sie gelöscht.
Download FileTreeSync.exe (44 KB)

Screenshot:



Mühle

Gestelltes Problem
Brettspiele hab' ich schon viele gemacht, das ist das erste was funktioniert (bis auf eine kleine Endspielschwäche beim Springen, aber normalerweise kommt man nicht so weit).

Algorithmus
Minimax-Alpha-Beta.
Download Muehle.exe (84 KB)

Screenshot:



Raytracer

Gestelltes Problem
Anfang der Neunziger Jahre des letzten Jahrhunderts habe ich in der c't einen Artikel über die Erzeugung perspektivischer Bilder mit dem Verfahren des Ray-Tracing gelesen. Daraufhin hab' ich mich sofort an den Rechner gesetzt, denn ich wollte auch sowas machen.

Algorithmus
Das sprengt hier den Rahmen. Grundprinzip ist, dass man vom Auge des Betrachters aus durch jeden Bildpunkt einen "Lichtstrahl" schickt und ausrechnet, wohin dieser reflektiert wird. Die Farbe des getroffenen Punktes bestimmt dann die Farbe des Bildpunktes. Dafür braucht man jede Menge fiieeser Vektorrechnung. Es ist letzten Endes nicht trivial, auszurechnen wohin sich ein Strahl bewegt, der von einer Kugel reflektiert wird.
Download Ray.exe (120 KB)
Download Demo-Szenario (1 KB)

So sieht das dann aus:


Oder so:



Spekulant

Gestelltes Problem
Ein Bekannter, Besitzer eines Kreditinstituts, hatte die Idee, die Börsenkurse bekannter Gesellschaften auf kurzperiodische Regelmässigkeiten (im Bereich einiger Tage) zu untersuchen. War es vielleicht so, dass es bei einer Aktie, die an einem Tag um 5% gestiegen war, für den nächsten Tag eine grössere Wahrscheinlichkeit gab, dass sie wieder steigen würde? Zur Analyse hatte er die Kursdaten einiger Aktien für die letzten 10 Jahre zusammengestellt.

Algorithmus
Ich verwarf zunächst den Ansatz, aus dem vorhandenen Datenbestand Regeln abzuleiten, da ich der Meinung war, dass eine Prognose für den Folgetag sich aus den Daten der vorhergehenden Tage unter direkter Einbeziehung der Datenbasis ergeben müsste.
Ich möchte den Algorithmus kurz an einem Beispiel demonstrieren. Geladen wurden die Kursdaten der Oracle-Aktie von 1993 bis 2002. Sie sind im oberen Fenster dargestellt. Die Pfeile geben die Kurstendenz wieder. Am 15.4.2002 ist die Aktie um 1,8% gefallen. Versetzen wir uns nun an diesen Tag zurück. Durch Klicken auf die entsprechende Zeile im oberen Fenster wird dieser Tag markiert, dann drücken wir auf Rechnen. Das Programm sucht sich nun die Daten vom aktuellen Tag, dem Vortag und dem Vorvortag zusammen, da eine Samplelänge von drei Tagen eingestellt ist. Es ergibt sich also dieses Sample: (-1,83/5,21/-5,28). Das Programm nimmt nun dieses Sample und legt es über die Kursdaten der letzten zehn Jahre und sucht dabei nach ähnlichen Samples. Diese werden absteigend nach der Ähnlichkeit sortiert und im unteren Fenster dargestellt. Das Sample mit der grössten Ähnlichkeit ist vom 22.2.2002. Damals ist der Kurs am nächsten Tag um 1,57% gestiegen. Das zweitähnlichste ist vom 14.6.1994, mit einem Anstieg von 1,42%. Beim drittähnlichsten Sample, der 16.2.2003 trat ein Verlust von 0,21% auf. Insgesamt sehen wir im unteren Fenster überwiegend Pfeile, die nach oben zeigen. Wenn wir uns also entscheiden die Aktie zu kaufen, dann würden wir am 16.4.2002 mit einem Gewinn von 6,74% belohnt werden. Über den Knopf "Spekulieren" kann der Auswahlvorgang automatisiert werden. Dabei wählt man ein Datum aus, welches z.B. ein Jahr in der Vergangenheit liegt. Das Programm erstellt dann für diesen Tag eine Prognose und entscheidet sich im positiven Fall, die Aktie zu kaufen. Dann prüft es, ob es Gewinn oder Verlust gemacht hätte und nimmt sich den Folgetag vor und entscheidet anhand einer erneuten Prognose, ob es die Aktie halten oder verkaufen soll und so weiter. Bei solchen Testspekulationen erzielt das Programm jährliche Profite im zweistelligen Prozentbereich. Es gibt also tatsächlich kurzperiodische Regelmässigkeiten in Aktienkursen. Trotzdem bin ich nicht reich geworden, da für den Kauf und den Verkauf einer Aktie jeweils Transaktionskosten anfallen. Da das Programm sehr viele Transaktionen macht, werden die Kursgewinne von den Transaktionskosten mehr als aufgefressen. Spass hats trotzdem gemacht.

Screenshot:



MP3CleanUp

Gestelltes Problem
Meine Kumpels und ich digitalisieren unsere CDs. Wir tauschen nur zu Backupzwecken und völlig unkommerziell. Bei einer MP3-Sammlung stellt sich ab einer gewissen Grösse die Frage, ob man ein bestimmtes Lied nicht schon irgendwo hat. Manuelle Abgleiche sind zeitaufwendig.

Algorithmus
Das Programm scannt einen Verzeichnisbaum auf MP3-Dateien, liest diese ein, und erzeugt eine Informationsdatei mit einem Extrakt aus den ersten 15 Musiksekunden sowie anderen Dateiinformationen. Diese Dateien werden in einem zweiten Schritt wieder eingelesen und dem Anwender in Form einer Liste präsentiert. In dieser Liste werden Dateien mit gemeinsamen Merkmalen zusammengefasst. Die Liste wird zunächst sortiert und dann Dateien mit gemeinsamen Merkmalen markiert. Folgende Sortierkriterien sind bis jetzt implementiert:
Dateiname (ohne Verzeichnis), Dateiname "tolerant" (Ziffern und Sonderzeichen entfernt), Dateigrösse, Dateigrösse "tolerant" (Dateilängen, die sich um maximal 100 Byte unterscheiden, gelten als identisch), Bitrate der MP3-Datei (alles unter 160 kBit/s ist schlecht), Samplingfrequenz (normal 44 kHz) und die Position des Lautstärkemaximums der ersten 15 Musiksekunden.
Damit kann man schon viele Doppelte erkennen, trotzdem muss bei der Verarbeitung der eigentlichen Musikdaten noch etwas getan werden.

Screenshot:



Faller-AMS-Steuerung (Prototyp)

Gestelltes Problem
Seit meinem 12. Lebensjahr bin ich begeisterter Besitzer einer Faller-AMS-Auto-Rennbahn. Ich hatte jedoch immer Probleme, Gegner zu finden, da sich meine Freunde meistens nur auf ein Rennen einliessen. Letztes Jahr habe ich eine Webcam erworben. Nun stellte sich mir die Frage, wie man eine PC-Steuerung eines Rennautos bewerkstelligen könnte.

Algorithmus
Mir schwebt vor, mehrmals pro Sekunde eine Aufnahme der Rennstrecke zu erzeugen. Durch Differenzbildung zwischen der aktuellen und der vorherigen Aufnahmen würde eine schwarze Bitmap entstehen, die an zwei Stellen weiss wäre, dem Standort des Fahrzeuges zum Zeitpunkt der ersten Aufnahme und dem Standpunkt des Fahrzeuges zum Zeitpunkt der zweiten Aufnahme. In einer Kalibrierungsphase wäre es möglich, den Bereich zu bestimmen, in dem sich das computer-gelenkte Fahrzeug bewegt. Dadurch entfällt also eine separate Erfassung der Streckenparameter, sicherlich könnte man eine Anwendung erstellen, bei der dem Computer die einzelnen Streckenabschnitte, enge Kurve 90 Grad, Gerade, normale Kurve, 45 Grad... bekannt gemacht würden, aber dieser Ansatz erscheint mir nicht sehr elegant. Stattdessen soll der Rechner seinen Wagen einige langsame Runden drehen lassen und so ein Abbild der durchfahrenen Strecke erstellen. Die so erfasste Strecke wird dann in Sektoren eingeteilt, die Länge eines solchen Sektors ergibt sich aus dem zeitlichen Abstand zwischen zwei Aufnahmen. Nun muss für jeden Sektor die Maximalgeschwindigkeit bestimmt werden. Diese ist nur experimentell zu erfassen. Das bedeutet, dass der Rechner den Wagen schrittweise immer schneller fahren lassen muss, bis er an einer bestimmten Stelle "rausfliegt". Anhand der so erfassten Sektorparameter kann dann ein sicheres und schnelles Rennen gefahren werden. Bevor ich nun die erforderliche Hardware für die Geschwindigkeitssteuerung des Fahrzeugs besorge, mir schwebt eine Steuerung durch ein am Gasgriff angebrachtes Servo vor, ist zunächst einmal ein Prototyp zu erstellen, der die Machbarkeit belegt. Dabei ist der komplette Ablauf im Rechner zu simulieren. Einen ersten Schritt stellt ein Streckeneditor dar. Hier habe ich alle bekannten zweispurigen AMS-Schienen in Form eigener Klassen realisiert. Bis jetzt kann er die jeweilige Strecke nur darstellen. Der nächste Schritt wird sein, Fahrzeuge hinzuzufügen und diese dann auf der Strecke fahren zu lassen. Die dabei entstehenden Streckenbilder werden dem zuvor erklärten Programm zugeführt. Wenn sich zeigt, dass eine Echtzeitsteuerung möglich ist, werden als Input die Aufnahmen der Digitalkamera verwendet.
Mehr zu diesem Projekt hier.

Screenshot:



Scanner-Anbindung mit ActiveX-Control

Jetzt möchte ich noch eine Anwendung, die ich als Freelancer erstellt habe, vorstellen.
Gestelltes Problem
Eine Tochter eines grossen, deutschen Luftfahrtkonzerns brauchte zur Klärung von Sonderfällen bei der Ticketabrechnung eine Anwendung, mit der mehrere Flugtickets mit einem an den PC des Bearbeiters angeschlossenen Scanner aus einer ABAP-Anwendung heraus eingescannt und per FTP in das dortige Image-Archiv übertragen werden können.

Algorithmus
Da es sich um manuelle Einzelscans handelte, kam die TWAIN-Schnittstelle zum Einsatz. Damit die Anwendung aus SAP heraus gesteuert werden konnte, musste sie in Form eines ActiveX-Controls realisiert werden. Der Scanvorgang per TWAIN geschieht normalerweise in zwei Schritten, es wird zunächst ein Preview in niedriger Auflösung gemacht, dann wird vom mitgelieferten, scannerspezifischen TWAIN-GUI (Graphical User Interface) in der gescannten Seite eine Suche nach den zu scannenden Objekten durchgeführt, wobei der Anwender noch eine Korrekturmöglichkeit hat. Erst danach wird dann der finale Scan durchgeführt.
Dieses Verfahren erschien mir aus den folgenden Gründen nicht praktikabel:
a) verschiedene Scanner-Modelle würden unterschiedliche GUIs haben, womit sich eine uneinheitliche Benutzerführung ergäbe
b) durch das doppelte Scannen, zusammen mit der mittendrin notwendigen Benutzerinteraktion würde zuviel Zeit verbraucht werden.
Deshalb entschloss ich mich, jeweils eine DIN A4-Seite komplett einzuscannen und die Tickets in der eingescannten Seite selbst zu lokalisieren. Es wurde ein Kontrasterkennungsalgorithmus implementiert, der eine gescannte Seite auf "Kanten" untersuchte. Die gefundenen Tickets wurden dann dem Anwender dargestellt und mit einer Markierung zur Durchführung eventueller Korrekturen (die aber im Praxisbetrieb selten notwendig sind) versehen. Die Scanzeit für drei Tickets inklusive Bereichssuche liegt mit einem aktuellen HP-Scanner bei vorgewärmter Lampe bei 11 Sekunden.

Screenshot:

(Noch eine Anmerkung zu den etwas blassen Farben. Erstens hat man mir zum Testen einen alten Schrottscanner auf den Schreibtisch gestellt und zweitens werden die extrahierten Images vor dem Speichern selbstredend noch kontrastoptimiert)


Freecell-Solver

Gestelltes Problem
Freecell macht mich immer ganz kirre, da hat man dann mit dem falschen Stapel angefangen und auf einmal ist nichts mehr frei, Statistik: "30%, aktuell 17-mal verloren". Das ist Stress pur!
Warum kostbare Freizeit verschwenden, wenn man solche Probleme per Programm lösen kann?

Algorithmus
Vor der Frage nach dem Algorithmus stand die nach dem Aussehen der Anwendung. Einfach nur Text "Zug von Stapel drei nach vier." erschien mir nicht ausreichend. Deswegen habe ich erst einmal alle Karten bei Freecell geklaut und als einzelne .bmp-Dateien abgelegt. Da ich mittlerweile auch ganz gern mal den Borland-C++-Compiler benutze, ging der Teil mit der Anzeige der Karten auf einem grünen Spieltisch relativ schnell. Wie in Freecell aus der ausgewählten Spielnummer die Anfangsstellung entsteht, habe ich noch nicht ergründen können. Deshalb wurde das Spiel 21145 fest im Programm verdrahtet. Jetzt mussten ja nur noch zu einer Stellung alle möglichen Züge ermittelt und dann für jeden Zug rekursiv das Gleiche getan werden, bis man auf eine Stellung stiess, wo alle Karten abgelegt waren. Pustekuchen. Die ersten Läufe dieser Version schafften über 100.000 Stellungen, ohne zu einer Lösung zu kommen. Bei Freecell gibt es nämlich reversible Züge. Deshalb wurde eine Liste der schon besuchten Positionen hinzugefügt. Damit konnten auch andere Formen der Stellungswiederholung ausgeschlossen werden. Trotzdem hatte ich ein Programm welches es schaffte in 10 Sekunden 200-mal zu verlieren, aber trotzdem nicht zur Lösung fand. Das lag daran dass es bei Freecell sehr viele Stellungen gibt. Es war notwendig, dem Programm auf der Ebene der möglichen Züge eine Richtung vorzugeben. Statt alle Zugmöglichkeiten wahllos durchzuprobieren, wurde für jeden Zug eine Bewertung berechnet. Die Züge mit der besten Bewertung wurden dann als erste ausprobiert. Eine gute Stellung hat folgende Eigenschaften: möglichst viele freie Plätze, möglichst gut sortierte Stapel, keine eingeklemmten Karten mit kleinem Wert. Damit gings dann. Hat ja auch immerhin fünf Tage gebraucht.
So sieht das dann aus:

(451 Positionen getestet, Rekursionstiefe 318, gemerkt 450 Stellungen, bis jetzt 38-mal verloren)


PlotR2R3

Gestelltes Problem
Da ich zum Ausmalen (siehe Computergrafik) gerne Bitmaps mit möglichst vielen Einzelflächen als Ausgangsbasis nehme, dachte ich daran, dass doch zur Abwechslung einmal 3-dimensionale Objekte interessant wären. Solche Programme hab' ich schon früher geschrieben, allerdings in Turbo-Pascal, einer Sprache die damals auf IBM-kompatiblem PC's mit MS-DOS wirklich unschlagbar war, den Sprung zu Windows aber nicht geschafft hat. Mitte der 80er war das für mich an der Uni als Darstellung von Elektronenorbitalen (Kugelfunktionen) eine Übungsaufgabe in theoretischer Physik. Entweder die Darstellung der Kugelfunktionen am PC oder eine "schriftliche Aufgabe". Damals hab' ich mich in drei Millisekunden für die Programmieraufgabe entschieden. Der Professor meinte dann übrigens zu meinen Ausdrucken "Das ist die beste Darstellung der Kugelfunktionen, die ich jemals gesehen habe. Wie haben Sie das gemacht?"
Es ging jetzt also darum, diese Darstellung in C++ zu implementieren.

Algorithmus
Die Koordinaten der Fläche werden durch drei Funktionen X(s,t), Y(s,t), Z(s,t) berechnet. Die Intervalle für s und t werden vom Benutzer gewählt, ebenso eine Anzahl Schritte, in die die Intervalle eingeteilt werden. Das Programm durchläuft das Intervall und ermittelt für je drei Punkte aus dem Intervall drei Punkte im Raum, die dann ein Dreieck ergeben. Diese Dreiecke werden in einer Liste abgelegt. Nach der Berechnung wird die Dreiecksliste so sortiert, dass die vom Betrachter am weitesten entfernten Flächen an den Anfang der Liste kommen. Dann wird die Liste gezeichnet, wobei jedes Dreieck mit der Hintergrundfarbe gefüllt wird. Dadurch verdecken die vorderen Flächen die hinteren.

Screenshot (20.000 Flächen):



Mastermind

Gestelltes Problem
Ursprünglich ging es um eine Wette mit einem Kumpel, wer wohl das bessere Programm für das Spiel Mastermind schreiben könne. Das Schwierige dabei war, dass der Computer die Kombination erraten musste. Ich habe fast zwei Wochen gebraucht, bis ich einen Algorithmus fand. Wer damals (1988) die Wette gewann wird nur per Mail verraten.
1997 habe ich dann das Programm in Java erneut geschrieben. Auch die Grafiken sind alle selbst gemacht (Applet auf alter Homepage).

Algorithmus
Ist eigentlich enttäuschend einfach. Es werden alle möglichen Kombinationen in einem Feld gespeichert. Die erste Kombination aus diesem Feld, im Screenshot (hier weiss, schwarz, blau, gelb) wird dem Benutzer angeboten. Dann gibt der Benutzer seine Bewertung (hier zwei weisse Stecker). Nun kommt der Trick. Das Programm nimmt jede Kombination aus dem Feld und prüft, welche Bewertung der Benutzer der eben angebotenen Kombination gegeben hätte, wenn es die Kombination des Benutzers wäre. Wenn der Benutzer also die Kombination (weiss, schwarz, blau, gelb) hätte, dann würde er für die angebotene Kombination (weiss, schwarz, blau, gelb) vier schwarze Stecker vergeben. Er vergab aber zwei weisse Stecker. Also wird diese Kombination gestrichen. Übrig bleiben die Kombinationen, die zusammen mit (weiss, schwarz, blau, gelb) zwei weisse Stecker ergeben. Jetzt wird die erste der übrigen Kombinationen (schwarz, weiss, grün, rot) angeboten. Nach maximal sechs Zügen ist die Kombination erraten.

Screenshot:



Sudoku

Gestelltes Problem
Ein Programm zum Lösen von Kreuzworträtseln habe ich eigentlich schon lange auf meiner ToDo-Liste. Dabei bin ich aber immer vor den notwendigen Wörterbüchern zurückgeschreckt. Bei den japanischen Zahlenrätseln ist die erforderliche Datenbasis viel schmaler. In Zukunft muss ich jedenfalls keine wertvolle Freizeit für das Lösen dieser Dinger mehr aufwenden.

Algorithmus
Erst einmal die Regeln: in jeder Zeile, in jeder Spalte und in jedem der markierten 3x3-Kästchen darf jede Ziffer nur einmal vorkommen.
Der Algorithmus ist nicht besonders knifflig, für die jeweils erste freie Zelle werden die Ziffern von 1 bis 9 ausprobiert. Falls das Rätsel dabei noch erfüllt ist, wird rekursiv mit der nächsten freien Zelle fortgesetzt.

Screenshot:



Sudoku II

Gestelltes Problem
Das Sudoku war also prinzipiell gelöst. Es zeigte sich jedoch, dass für manche Rätsel recht viele Kombinationen ausprobiert werden mussten. Bei einem Rätsel waren es 45253, was für die heutige Hardware ein Witz ist, aber in Zusammenhang mit der Ausgabe jeder Position auf dem Monitor dann doch zu Laufzeiten von über 10 Minuten führte. Da kann man dann natürlich tricksen und nur jede fünfte oder zehnte Position ausgeben. Es zeigte sich jedoch dass bei einer vertikal gespiegelten Version des obigen Rätsels statt 45253 Versuchen nur noch 199 nötig waren. Die Methode, die jeweils erste freie Zelle von links oben durchzuiterieren war offensichtlich suboptimal.

Algorithmus
Der Grundalgorithmus blieb gleich, freie Zelle suchen und für jede mögliche Ziffer Rekursion mit der nächsten freien Zelle. Geändert wurde lediglich das Auffinden dieser Zelle. Unter allen noch freien Zellen wird die genommen, deren Kasten, Zeile und Spalte am meisten gefüllt sind. Bei der Optimierung von rekursiven Programmen habe ich immer eine gewisse Scheu, zusätzliche Anweisungen einzufügen, aber letzten Endes hängt die Gesamtlaufzeit nur von einer möglichst niedrigen Anzahl Rekursionen ab. Mein Referenzrätsel wird jetzt jedenfalls mit 315 Versuchen gelöst.

Screenshot:



Bindup

Gestelltes Problem
Hier eine Platte, da eine Platte, Datensicherungen vom Arbeits-PC. Diverse Rechnerwechsel. Irgendwann waren meine Datenbestände wirklich komplett durcheinander, alles mehrfach irgendwo abgelegt. Deshalb brauchte ich mal wieder ein Programm zum Auffinden von Duplikaten. Es sucht in einem Verzeichnisbaum rekursiv nach identischen Dateien. Die gefundenen Gruppen von Dateien gleichen Inhaltes werden dann in einem Tree-Control angezeigt und können gelöscht werden.

Algorithmus
Zunächst alle Dateien auffinden. Dabei prüfen, ob es Dateien mit identischer Länge gibt. Für diese eine Checksumme bilden. Dateien mit gleicher Länge und gleicher Checksumme werden gruppenweise verglichen. Es ergibt sich also eine Liste mit Gruppen von identischen Dateien.

Screenshot:



Anna

Gestelltes Problem
Man hat ein Amateurteleskop mit einer Digitalkamera dahinter und möchte Langzeitbelichtungen von Himmelsobjekten machen. Die Belichtungszeiten liegen dabei im Bereich von 15 Sekunden bis 15 Minuten. Zur späteren Verringerung des Bildrauschens werden dabei pro Belichtungszeit gleich mehrere Aufnahmen gemacht. Die kann man dann von Hand per Drahtauslöser steuern. Es macht aber keinen Spass, eine Serie, z.B. 10x30 Sekunden, 10x60 Sekunden, 5x90 Sekunden und 5x120 Sekunden manuell zu steuern.
Weiterhin besteht bei Langzeitaufnahmen das Problem der Abweichung des Teleskops. Mit meinem Refraktor von 900mm Brennweite entspricht ein Bildpunkt der EOS 350 1/5000 Grad Bildwinkel. Wenn also das Fernrohr während der Aufnahme um nur 1/500 Grad abweicht, hat man auf der Aufnahme statt eines Sterns einen Strich mit einer Länge von 10 Pixel. Die Lösung diese Problems besteht darin, dass man parallel zum Aufnahmeteleskop noch ein zweites meist kleineres Fernrohr, ein "Leitrohr" anbringt. Damit sucht man sich einen Stern in der Nähe des aufzunehmenden Objektes, bringt ihn in Bildmitte und hält ihn dort während der Aufnahme, indem man Abweichungen durch kleinere Teleskopbewegungen korrigiert. Das kann händisch mit einem Fadenkreuzokular gemacht werden. Natürlich kann man an das Leitrohr auch eine Webcam anbringen und über das Webcambild "guiden". Dann könnte man auch noch ein Programm machen, welches das Nachführen automatisch durchführt, einen "Autoguider". Sowas wollte ich.

Name
Das Programm trägt den Namen meiner Nichte Anna, weil ich mir gern vorstelle, wie sie draussen auf dem Balkon gewissenhaft Kamerabedienung und Nachführung erledigt, während ich mich drinnen, in dem Wissen, dass sie einen guten Job macht, mit den Problemen der Zeitgeschichte befasse.

Algorithmus
Bei den Belichtungsserien musste ich zunächst etwas Hardware basteln. Dafür habe ich meinen Drahtauslöser zerlegt und ein Kabel drangelötet, welches mit einem über meine USB-Karte ansteuerbaren Relais verbunden ist. Dann eine Liste von acht Belichtungszeiten (in Sekunden) mit zugehöriger Bildanzahl. Damit die Kamera das gerade gemachte Bild auf ihrer Speicherkarte ablegen kann, gabs noch eine Wartezeit zwischen den Aufnahmen. Wenn man dann eine Serie startet, werden die Belichtungszeiten über entsprechend gesetzte Timer von oben nach unten abgearbeitet.
Für die Nachführung brauchte ich ebenfalls zunächst eine PC-Anbindung, diesmal für die Teleskopmotoren. In der ersten Version habe ich das über Relais, mit denen ich die Richtungstasten meiner Handsteuerung überbrückte, gelöst, später kam noch eine serielle Anbindung über das "LX200"-Protokoll an meine "Littlefoot"-Teleskopsteuerung hinzu. Der Algorithmus ist recht trivial, nimm ein Webcam-Bild, filtere alle Pixel, die oberhalb eines Schwellwertes liegen, heraus und bilde den Schwerpunkt der restlichen Pixel. Zeichne um diesen Punkt ein diagonales Fadenkreuz. Wenn sich der gefundene Punkt nicht in Bildmitte befindet, setze den jeweiligen Teleskopmotor in Gang. Das klappt gut und ehrlich gesagt fand' ich die ganze Sache beim ersten Mal etwas unheimlich, als ich danebenstand und die Kamera klicken hörte und die Nachführung brav ihren Stern zentrierte.

Screenshot:



Minesweeper Löseprogramm

Gestelltes Problem
Ich glaube, ich bin ein komischer Typ. Komisch hier im Sinne von merkwürdig. Ich denke mir nämlich gern Lösungen für Probleme aus. So kam mir unlängst in einer Rätselzeitschrift meiner Mutter ein "Finde die zehn Unterschiede"-Bilderrätsel unter. Das habe ich dann mit der Digiknipse fotografiert. Jetzt müssten, in der einfachen Lösungsvariante, nur beide Bilder aus dem Gesamtbild ausgeschnitten und dann abwechselnd angezeigt werden. Dabei würden dann die Unterschiede "blinken". Die etwas fortgeschrittenere Variante würde direkt eine Bildsubtraktion durchführen.
Meine Mutter fand diesen rechnergestützten Lösungsansatz unmoralisch und vielleicht bewegt mich auch Faulheit dazu, Probleme abschliessend lösen zu wollen.
Dieses Mal war es Minesweeper. Mir ging schon länger im Kopf herum, dass und wie man da etwas machen könnte. Ich wollte ein Programm schreiben, welches Minesweeper fernsteuert.

Algorithmus
Zunächst musste ich ein Minesweeperfenster finden und mir das Spielfeld kopieren. Dieses wurde dann nach diesen Bitmaps:

durchsucht. Damit hatte ich also in meinem Programm ein Abbild der aktuellen Spielsituation. Diese wurde auf zwei verschiedene Weisen analysiert.
1. Dumm
Dabei wird nach Zahlen-Zellen gesucht, die genau so viele geschlossene Zellen in ihrer Umgebung haben, wie es ihrem Zahlenwert entspricht. Wenn also eine 1er-Zelle nur ein geschlossenes Feld in ihrer Umgebung hat, wird dieses markiert. Das Markieren geschieht, indem ein rechter Mausklick mit den passenden Koordinaten an das Minesweeper-Fenster geschickt wird. Danach wird für alle Zahlenzellen ein Klick mit beiden Maustasten, der alle offensichtlich gelösten Felder aufdeckt, geschickt.
2. Schlau
Hier wird ein Ausschnitt von 4x4 Zellen über das Spielfeld bewegt. Es werden dann für alle geschlossenen Zellen alle Belegungsmöglichkeiten durchiteriert. Die Iteration sieht so aus:
int NextIt( int pos )
{
    if ( pos >= ITW * ITW )
      return false;

    if ( IterationsZellen[ pos / ITW ][ pos % ITW ].ZelleOrig == CVALZU )
    {
      // Wenn sie 0 ist, auf 1 und raus
      if ( IterationsZellen[ pos / ITW ][ pos % ITW ].AktWert == 0 )
      {
         IterationsZellen[ pos / ITW ][ pos % ITW ].AktWert = 1;

         return true;
      }
      // Sonst auf 0 und nächsthöhere erhöhen
      IterationsZellen[ pos / ITW ][ pos % ITW ].AktWert = 0;
    }

    return NextIt( pos + 1 );
}
Rekursion muss nicht immer sein, aber hier ist sie echt lecker. Es werden dann alle möglichen Belegungen anhand der Zahlenfelder bewertet, wobei entschieden wird, ob sie eine gültige Minenverteilung darstellen. Wenn ein Feld bei allen gültigen Minenverteilungen leer ist, wird es geöffnet. Ein Feld, welches bei allen gültigen Minenverteilungen eine Mine hat, wird markiert.

Tja, trotz der Massen an Mausklicks und der vielen Bildschirmabzüge ist das Programm dann doch relativ schnell. Wieder ein Problem gelöst...

Screenshots:




Ameis

Gestelltes Problem
Schwarmintelligenz verstehe ich so, dass ein Erfolgsrezept darin besteht, das nachzumachen, was erfolgreiche Individuen getan haben. Damit partizipiert man an von anderen gemachter Erfahrung. Ein Teilbereich ist dabei die Optimierung von Wegen, wie finden z.B. Ameisen den kürzesten Weg zur Futterquelle und zurück? Sie verwenden Pheromone, mit denen sie einen Weg markieren. Der kürzeste Weg ist der, den die meisten Ameisen benutzen (hier deutet sich eine Rekursion an, die mir noch etwas zu Schaffen macht).
Mein Ansatz unterschied sich vom dem, was ich im Internet gefunden hatte, insoweit als ich versuchte, einen "richtigen" Ameisenhaufen nachzumachen. Dabei sollte es keine vorgegebenen Wege, keine vorgegebene Richtung und auch keine nachträgliche Vergabe von Duftstoffen (Ameise findet Futter und markiert dann den von ihr gegangenen Weg) geben, weil ich das unrealistisch fand.

Algorithmus
Es gibt zwei Pheromone:
"Ich komme vom Haufen, suche Futter."
"Ich komme vom Futter, suche den Haufen."
Eine Ameise, die Futter hat, muss sich also in der Richtung bewegen, aus der Ameisen kommen, die Futter suchen, damit also vom Bau losgelaufen sind. Umgekehrt muss eine Ameise, die Futter sucht, sich in die Richtung bewegen, aus der die meisten Ameisen mit Futter zurückkehren. Ich habe drei Typen von Feldern verwendet, Ameisenhaufen (blau), Futter (grün) und Hindernis (grau). Die Ameisen selbst sind schwarze Punkte. Sie geben ihren jeweiligen Duftstoff ab, der Vorrat ist begrenzt, damit kurze Wege entstehen. Wenn eine Ameise einen Bildpunkt verlässt, dann geht sie in die Richtung, aus der die meisten Ameisen mit dem Gegenduft gekommen sind. Dabei ist noch ein gewisses Zufallselement im Spiel. Die Düfte verfliegen mit der Zeit, damit sich neue Wege bilden können. Im Screenshot sieht man die Situation nach 14260 Durchläufen mit 5000 Ameisen. Sie haben links oben und rechts unten Futter gefunden. Die 219884 Statuswechsel sind die Anzahl der Futterabgabe plus Futteraufnahme. Ameisen auf Futtersuche hinterlassen ein gelbes Pheromon, Rückkehrer eins der Farbe Lila. Die Wege sind noch nicht so optimal, wie ich mirs wünschen würde, aber trotzdem machen die Ameisen ihren Job, holen Futter und bringen es zum Haufen zurück, ein nettes Feierabendprojekt.

Screenshot:


Hmja, dann dachte ich mir, eigentlich müssten die Ameisen nicht dahin gehen wo die Meisten herkommen, sondern dahin, wo die Erfolgreichsten, also die mit dem kürzesten Weg vom Futter oder Bau herkommen. Ausserdem ist der Weg zurück zum Bau doch eigentlich unveränderlich, weswegen die Rückkehrpheromone nicht verfliegen sollten. Nach diesen Programmänderungen verwandelten sich die Ameisen in noch gefrässigere Biester.

Screenshots:




Pong

Gestelltes Problem
Ich hab' ein Handy. Das Handy kann Java. Es hat nur ein paar Jahre gedauert, bis ich auf die Idee gekommen bin dass ich doch mal ein Programm schreiben könnte welches auf dem Handy läuft. Also erst einmal etwas Kleines für den Anfang, Pong.

Programm
Zunächst musste ich mir Java ME besorgen, und ein paar Beispiele angucken. Dann ein kleines Hello-World zum Üben und dann gings auch schon los. Besonders schwierig wars nicht, ich musste mich lediglich wieder in Java einfühlen.


Screenshot:



MiniMax

Gestelltes Problem
Für Spiele mit voller Information gibts den MiniMax-Algorithmus. Der Rechner probiert alle möglichen Zugmöglichkeiten aus, mehrere Halbzüge im Voraus und als Mensch verliert man dann. Der Computer ist deswegen nicht intelligent, man kann ihm nur beibringen, gewisse Spiele recht gut zu spielen. Sowas hatte ich schon früher programmiert, dabei aber jedes Spiel für sich. Diesmal sollte es Java sein, fürs Handy und der Findedenbestenzug-Programmteil von den jeweiligen Spielregeln getrennt ausgeführt werden. Ausserdem sollten die Züge animiert werden.

Programm
Ich weiss nicht, wie andere Leute Programmieren, aber bei mir ists so, dass ich eigentlich von Fehler zu Fehler stolpere. Man schreibt den Code und dann hauts nicht hin, das geht mir dann im Kopf rum, warum geht das nicht, kann doch eigentlich nicht sein. Kann aber doch sein, und wenn ich dann so einen Fehler gefunden hab', dann freue ich mich und alles ist wieder im Lot.

Es entstand dann also eine "MiniMax-Engine" und gleichzeitig ein VierGewinnt-Spiel. Als das dann lief, hab' ich mit "Mühle" weitergemacht. Das ist beides in einem einzigen Programm vereinigt, einen Einstellungsdialog gibts auch.


Screenshots:


Das Viergewinnt hab' ich dann gegen zwei im Internet gefundene Viergewinnts antreten lassen. Bei gleicher Halbzugtiefe waren die dann doch eher nicht so gut. Ich weiss auch warum.

Als nächstes hab' ich dann Dame und Räuberdame gemacht. Und Halma, 3x3. Und Schach. Und Hase und Jäger.



SameGame

Gestelltes Problem
Um 2000 herum stiess ich auf ein Spiel namens "Clickomania", das ein Klon von SameGame ist. Dabei muss man Gruppen aneinandergrenzender Spielsteine gleicher Farbe "sprengen". Darüberliegende Steine fallen in die entstandene Lücke und am Ende sollte möglichst kein Stein mehr übrig bleiben. Das machte Spass! Da bei mir immer so viele Steine übrig blieben, grübelte ich schon damals darüber, wie man wohl für eine gegebene Stellung eine optimale Lösung finden könnte. Als ich dann mit den Handyspielen anfing, dachte ich mir, dass es interessant sein könne, einen SameGame-Solver fürs Handy zu schreiben.

Programm
Bevor ich mit dem Solver anfangen konnte, musste ich erst einmal das Spiel selbst programmieren. Das war nicht schwer, deshalb legte ich einen Schwerpunkt auf eine saubere Animation und verschiedene Designs der Spielsteine. Dazu sollte die Anzahl der noch vorhandenen Spielsteine als Siebensegmentanzeige ausgegeben werden. Dafür besorgte ich mir eine technische Zeichnung einer solchen Anzeige und übertrug die Koordinaten der einzelnen Segmente in eine Java-Klasse. Wie immer alles Handarbeit (in den untigen Screenshots aus einem Nokia 6260-Emulator ist die Anzeige etwas zu gross, auf meinem Nokia 6300 ist das besser).

Solver habe ich dann zwei gemacht, erstmal einen dummen, der einfach nur Stellen sucht, wo man klicken kann. Danach dann einen, der für jede anklickbare Gruppe den "Nachher"-Zustand ermittelt und dann zählt wieviele "verwaiste" Steine es gibt. Die Gruppe, bei der die wenigsten Waisen anfallen, wird dann geklickt. Das ist schon recht passabel aber noch nicht optimal.


Screenshots:



SlotCount(Android)

Gestelltes Problem
Ich hatte mich ja schon häufiger mit der Erstellung von Software im Umfeld meiner Faller-Rennbahn beschäftigt. Nachdem ich dann ein Android-Handy hatte, reifte in mir die Idee, dass man vielleicht einen Rundenzähler machen könnte. Die eingebaute Kamera würde die Strecke filmen und erkennen wenn eines der beiden Autos über die Ziellinie fährt.

Programm
Die erforderlichen Elemente hatte ich in irgendeiner Form alle schon einmal gemacht, die Bewegungserkennung, das Ermitteln des Bereichs in dem sich ein Fahrzeug aufhalten kann und auch das Zuordnen einer erkannten Bewegung zu einem der beiden Fahrzeuge. Die Möglichkeiten, die man für die Android-Entwicklung mit Eclipse hat, sind schon recht umfangreich und so kam ich schnell voran.
Mittendrin beschloss ich die Anwendung auch im Android Appstore zu veröffentlichen, was dann noch einigen Zusatzaufwand z.B. für die Internationalisierung bedeutete.
Die Benutzung der Anwendung besteht aus drei Phasen, als Erstes das Einstellen des Erkennungsalgorithmus, Wert für die Empfindlichkeit und die ungefähre Grösse der zu erkennenden Objekte. Dann musste die Anwendung lernen, wo die Fahrzeugspuren verlaufen. Danach konnten dann Rennen gefahren werden. Nachdem die Anwendung gelernt hatte, wo die Spuren verlaufen, durfte das Smartphone nicht mehr bewegt werden, so dass ich sämtliche Abläufe über Sprachausgaben des Handys steuerte.


Screenshots:

Das Menü (englische Version)


Einstellung der Erkennungsparameter. Auf die grüne Anzeige unten Rechts bin ich ein bisschen stolz. Sie zeigt an den Stellen weiss, wo im Kamerabild eine Bewegung (hier der Bleistift) erkannt wurde.


Nach Abschluss der Spurkalibrierung. Die Rechtecke geben die Bereiche vor, in denen das Fahrzeug detektiert wurde. Die Farbe der Rechtecke ist automatisch aus der Fahrzeugfarbe bestimmt worden. Die Pfeile deuten die erkannte Fahrtrichtung an.


Rennview. Es werden für jedes Fahrzeug die Runden gezählt, die Rundenzeit und die schnellste Runde ermittelt. Für den Start gibt es einen Countdown. Dabei werden auf Wunsch auch Fehlstarts erkannt. Wer zuerst die eingestellte Rundenanzahl erreicht, wird als Gewinner ausgerufen. Falls beide Fahrzeuge im gleichen Kamerabild die Ziellinie überqueren, gewinnt der Fahrer, dessen Auto am weitesten ins Kamerabild reingefahren ist.


CasaTest(Android)

Gestelltes Problem
Weil ich meine Heizkörper gern automatisch regeln wollte, hatte ich mir eine Steuerung "CasaControl" der Firma Pearl gekauft. Damit kann man per App Heizkörperventile, Steckdosen und mehr steuern. Mit der vom Hersteller bereitgestellten App war ich nicht so zufrieden, so dass ich lieber selbst eine machen wollte.

Programm
Ist halt eine App, war ein bisschen fummelig herauszufinden wie man die Temperatur- und Schaltbefehle an die Steuerung schickt. Aber dann ging das was ich wollte, nämlich einen Heizkörper auf eine bestimmte Temperatur zu stellen oder eine Funksteckdose ein- und auszuschalten ganz gut.


Screenshot:






Msudoku(Android)

Gestelltes Problem
Lange nichts mit anspruchsvollem Algorithmus programmiert. Um zu gucken ob ichs noch kann entschied ich mich einen Sudoku-Löser für Androd zu schreiben. Dieses Mal aber mit einem mehr an die menschliche Denkweise angelehnten Algorithmus.

Programm
Man sieht das Sudoku in der Anzeige und kann die Zellenwerte verändern (die Anzeige könnte man noch etwas aufhübschen, mir war das nicht so wichtig).
Dann kann man für jede Zelle eine Liste von möglichen Kandidaten generieren und anzeigen lassen. Es ist dann möglich sich Tipps geben zu lassen, dabei werden Zellen mit schon bestimmtem Inhalt gelb unterlegt. Für diese Hints werden auch Zweier- und Dreiergruppen bestimmt (wenn also in einem Block zwei Zellen mit den Kandidaten 2/7 und 2/7 vorkommen, dann kann weder 2 noch 7 als Kandidat in den anderen Zellen des Blocks vorkommen).
Schliesslich gibt es auch einen automatischen Lösemodus bei dem das Sudoku komplett gelöst wird. Das ist im Vergleich zu meinem weiter oben beschriebenen Brute-Force-Sudoku sehr schnell. Ich hatte hier bisher die Lösung stets in unter einer Sekunde Rechenzeit. Das alte Programm hat durchaus auch mal 10 Minuten (und das auf einem Desktop) gebraucht.
Es kann jetzt sein dass es ein Sudoku gibt, bei dem die Betrachtung von 3er-Gruppen nicht ausreicht, so dass man dann z.B. 4er-Gruppen ins Programm einbauen oder doch noch eine rekursive Brute-Force-Lösung (die dann aber nur noch auf das schon teilweise gelöste Sudoku angewendet würde und damit schneller wäre als komplett Brute-Force) ergänzen müsste.
Da habe ich aber aktuell garnicht so grosses Interesse weil ich die App an sechs Abenden relativ entspannt ohne grössere Irrwege oder lange Fehlersuchen (und auch ohne Konzept oder Skizzen) runterprogrammieren konnte und damit dann festgestellt habe dass ichs noch kann B-) .


Screenshot: