Send More Money in PHP programmiert

Im Dezember 2012 ist mir das alte „Send More Money“-Problem mal wieder in die Finger geraten. Darüber habe ich dann im Artikel 6502 Assembler Programmierung geschrieben.

Schon im Dezember habe ich überlegt, wie das wohl in PHP auf einem Webserver laufen würde. Da ich im Augenblick sowieso gerade mit PHP herumexperimentiere (siehe auch Orthografie Schieber – Deutsch in der 7. Klasse Gymnasium), lag es auf der Hand, nun auch das liegengebliebene Send More Money Thema erneut aufzugreifen.

Besonders intelligent ist das Programm nicht.

Im ersten Ansatz durchlief es einfach alle Möglichkeiten für alle Buchstaben, die es gibt, also 10^8 Schleifendurchläufe = 100 Mio. Das dauerte dann schon mal schlappe xx Minuten. (Anmerkung: konnte die Laufzeit noch nicht ermitteln … es dauert Stunden!)

Da der Buchstabe M ein Übertrag aus zwei Ziffern ist, kann er maximal die Ziffer 1 darstellen. 0 ginge auch noch, aber das ist prinzipiell bei Alfametiken nicht zugelassen. Die Zahlen dürfen keine führenden Nullen aufweisen. Auf jeden Fall konnte ich die Anzahl der Schleifendurchläufe auf diese Weise von 100 Mio auf 20 Mio reduzieren, das entspricht einer Verkürzung der Laufzeit auf 1/5 der ursprünglichen Zeit. Gemessen habe ich: xx Minuten. (Anmerkung: konnte die Laufzeit noch nicht ermitteln … es dauert Stunden!)

Eine weitere Beschleunigung ergab sich aus der Tatsache, dass zumindest die letzte Stelle der Summe, also der Buchstabe Y, nicht jede beliebige Ziffer annehmen konnte, sondern immer eine Summe aus dem Buchstaben D und dem Buchstaben E darstellte. Somit musste Y nicht 10mal iteriert werden, sondern konnte schlicht und ergreifend für gegebene D und E berechnet werden. Statt 10 Schleifen nur noch eine Berechnung.

Nachdem die Lösungen gefunden waren, musste ich das Skript nur noch etwas mit CSS aufhübschen. Und hier ist das Ergebnis:

noch größer wird der Screenshot mit einem Mausklick

Leider kann ich euch nicht auf das Skript selber weiterleiten, weil es nur lokal bei mir auf dem XAMPP-Server läuft, aber nicht auf meinem Webserver. Da wird es nach 10 CPU Sekunden abgeschossen. 🙁

Gerne würde ich das Programm weiter beschleunigen. Vielleicht würde eine Rekursion etwas bringen. Ansonsten muss sich das wohl ein Mathematiker vorknöpfen. Es wäre mal interessant, auf welche Laufzeit man das Skript beschleunigen könnte.

Falls jemand schnellere Entwürfe hat, würde ich mich über eine Diskussion darüber sehr freuen!

Update 31.07.2013:
Ich konnte den Algorithmus durch früher greifende Ausschlüsse (letztendlich Constraints und Backtracking) weiter beschleunigen und benötige jetzt nur noch 381.170 Schleifendurchgänge. Das Skript läuft nun weniger als 1 Sekunde und ist damit auch auf dem Webserver ablauffähig: PHP-Skript SMM starten.

Ich habe es auch mal mit einem evolutionären Algorithmus probiert, aber der braucht ebenfalls sehr lange. Dadurch, dass die Chromosomen per Zufall mutiert werden, sind die Laufzeiten aber völlig unterschiedlich. Einmal war das Skript mit gerade mal 188 Generationen in 0,002 Sekunden fertig. Mal schauen, ob ich die Qualität der Mutationen noch verbessern kann.

Update 02.08.2013:
Nun habe ich mir das Thema auch noch einmal in Perl vorgenommen. Bei PHP werden Ausgaben auf dem Client (normalerweise) erst dann angezeigt, wenn das Skript komplett fertig ist. Das hat den Nachteil, dass ich während eines langlaufenden Skriptes keine hilfreichen Infos anzeigen kann. Mit Perl als Standalone-Programmiersprache kann ich grundsätzlich den Webserver und den Webbrowser weglassen und das Programm direkt in einer DOS-Box (=Kommandozeile cmd.exe) ablaufen lassen. Die Bildschirmausgaben erfolgen stets unmittelbar.

Obwohl sich PHP und Perl sehr ähnlich sehen, ist die Syntax von Perl doch deutlich anspruchsvoller.

Folgende Programm-Optimierungen konnte ich erreichen:

1. Brute Force Methode

Die stellt den Ausgangs-Algortihmus dar und ist in keiner Weise optimiert. Es werden einfach sämtliche möglichen Werte (0 bis 9) für alle Buchstaben ausprobiert. Jede dieser Möglichkeiten wird anschließend daraufhin untersucht, ob Doppelungen vorkommen. Der Buchstabe „s“ darf beispielsweise nicht durch dieselbe Ziffer ersetzt werden wie irgendeiner der anderen 7 Buchstaben. Danach wird überprüft, ob die Addition aufgeht. Es wird nicht berücksichtigt, dass „M“ eigentlich nur eine „1“ sein kann.

Insgesamt ergeben sich 24 Lösungen mit M=0 und 1 Lösung mit M=1.

Das Programm durchläuft 100 Mio Schleifen und benötigt auf meinem alten Notebook 19:50 Minuten (=100%).

2. Berücksichtigung von Einschränkungen für M

Danach habe ich berücksichtigt, dass M entweder 0 oder 1 ist, da es sich um einen Übertrag aus der Addtion der beiden Tausenderstellen handeln kann. Bei der Addtion zweier Zahlen ist ein Übertrag>1 nicht möglich.

Entsprechend reduzierte sich die Anzahl der Schleifendurchläufe von 10*10 Mio auf 2*10 Mio = 20 Millionen.

Das Programm benötigte mit 4:04 Minuten nur noch etwa 21% der ursprünglichen Laufzeit.

3. Berechnung von Y

Für den Buchstaben Y müssen keine beliebigen Werte ausprobiert werden, denn er lässt sich immer aus den bereits zugewiesenen Buchstaben D und E errechnen. Dabei muss nur beachtet werden, dass der Buchstabe keinen Wert>9 annehmen darf.

Auf diese Weise können alle Schleifen für Y entfallen, also ein Faktor von 10, so dass 2 Mio Schleifen übrig bleiben.

Das Skript benötigte nun noch 26,42 Sekunden (2,21% des Brute-Force Algorithmus).

4. Einführung von Backtracking

Nun habe ich die Schleifen so früh wie möglich beendet, indem ich je nach Stufe der Schleifenkaskade überprüft habe, ob ein Buchstabe sich von den bereits zugewiesenen der höheren Schleifenlevel unterschied. Dadurch entfielen natürlich jedes Mal eine ganze Reihe von inneren (tiefer liegenden) Schleifen.

Insgesamt reduzierte sich die Anzahl der Schleifen nun auf 40.320.

Und entsprechend spielte die Laufzeit mit 0,49 Sekunden kaum noch eine Rolle.

5. Zahlen beginnen nicht mit Null

Anschließend habe ich die Regel implementiert, dass Zahlen nicht mit einer Null beginnen dürfen, die Buchstaben S und M also nicht gleich Null sein dürfen. Das reduzierte die Anzahl der Schleifen auf nur noch 14.760 und die Laufzeit auf 0,19 Sekunden.

Aber auch die Anzahl der Lösungen verringerte sich auf 1, nämlich auf die einzig valide.

Schlussbemerkung

Weitere logische Überlegungen habe ich nicht mehr implementiert, denn dann kann ich das Puzzle auch gleich ohne Computer lösen.

Interessant finde ich, dass ich durch ganz einfache zusätzliche Verbesserungen des Ausgangs-Algorithmus wirklich dramatische Laufzeitverbesserungen erreichen konnte. Von ursprünglich 100.000.000 Schleifendurchgängen ging es runter auf 14.760 Durchgänge. Und die Laufzeit verbesserte sich von etwa 20 Minuten auf einen kaum mehr messbaren Wert unterhalb 1 Sekunde.

Update 03.08.2013:
Ich habe mir auch noch einmal den evolutionären (=genetischen) Algorithmus vorgeknüpft und konnte ihn unter Perl verbessern. Eigentlich funktionierte der schon ganz gut, aber leider blieb er in einem lokalen Maximum hängen. Die guten Gene altern jetzt und können ebenfalls mutieren, wenn sie ein bestimmtes Alter überschritten haben. Dadurch erhalte ich zwar kurzfristig wieder schlechtere Lösungen, aber eben auch die Chance, dass das globale Maximum gefunden wird.

Nachdem das in Perl klappte, habe ich es auf PHP übertragen. Starten des evolutionären PHP-Skrips.

Üblicherweise ist es sehr schnell. Natürlich variiert die Laufzeit in Abhängigkeit von den erzeugten Generationen sehr stark. Die Mutationen werden ja zufällig erzeugt. Es wird auch nur noch die einzig valide Lösung ausgegeben. Die anderen Lösungen mit M=0 könnt ihr euch mit dem ersten Skript ansehen: Normales PHP-Skript SMM starten.