Vor einigen Tagen kam mein Sohn im GesprÀch auf das Thema Programmierung . Das ganze GesprÀch will ich hier nicht wiedergeben, aber irgendwann sind wir bei dem legendÀren Send More Money Problem gelandet. Kennt das jemand?
Ein amerikanischer Student macht eine Weltreise. Als er gerade Europa besichtigt, geht ihm das Geld aus. Er schickt eine Postkarte nach Hause mit dem folgenden Inhalt:
SEND
+MORE
-----
MONEY
Wenn man jeden Buchstaben durch eine Ziffer ersetzt, erhĂ€lt man den Betrag, den sich der Student wĂŒnscht.
Diese Art von SymbolrĂ€tsel nennt man Alphametik. Dabei werden unterschiedliche Buchstaben durch unterschiedliche Ziffern so ersetzt, dass die mathematische Operation sinnvoll ist. Heutzutage findet man den richtigen Geldbetrag natĂŒrlich im Internet. (Schaut nicht nach đ Die Rechnung lautet 9567 + 1085 = 10652.)
Mein Sohn wollte wissen, wie man das RÀtsel mit dem Computer lösen kann. Ende der 1980er Jahre habe ich das mal in 6502 (bzw. 6510) Assembler gelöst. Der 6502 war der Mikroprozessor, der im Apple II+ und spÀter in modifizierter Form als 6510 im Commodore C-64 (von dem hatte ich damals 3, einer davon funktioniert auf jeden Fall heute noch) eingebaut war.
NatĂŒrlich konnte man auch diese Computer bereits in höheren Programmiersprachen programmieren. Ich entschied mich damals aus ZeitgrĂŒnden fĂŒr Assembler, da ich im ersten Ansatz einen ziemlich dummen Algorithmus umsetzen wollte, nĂ€mlich das stumpfsinnige Durchprobieren aller Möglichkeiten. Um die Laufzeiten möglichst niedrig zu halten, wollte ich direkt in Maschinensprache/Assembler programmieren.
Mich wĂŒrde einmal interessieren, ob es da drauĂen in der weiten Welt noch jemanden gibt, der mal in 6502-Assembler programmiert hat und möglichweise den folgenden Code noch halbwegs versteht? WĂŒrde mich ĂŒber eure Kommentare unterhalb des Artikels freuen!
Meine Lösung sieht als Hex-Dump folgendermaĂen aus (per Mausklick gibt es eine gröĂere Darstellung):
Das ist ein Originalausdruck mit Nadeln auf Rollenpapier (2 Streifen nebeneinander auf ein Blatt A4 geklebt.).
Wer genau hinsieht, entdeckt einen kleinen Rechtschreibfehler: ich habe das Problem damals immer „Sent More Money“ genannt, obwohl es natĂŒrlich „Send More Money“ heiĂen muss.
Ein biĂchen leichter lesbar ist das Programm in Assembler-Code:
Zugegeben: besonders elegant war das Programm nicht, aber es hat alle Lösungen ausgespuckt:
Letztendlich korrekt ist hierbei nur die letzte Lösung, denn eine 0 als erste Ziffer ist fĂŒr Alphametiken nicht zugelassen.
NatĂŒrlich zeigt auch das Disassembling oben nicht, wie ich das Programm entwickelt habe. Ăblicherweise arbeitet man nicht mit festen Speicheradressen fĂŒr Variablen und Unterprogramme, sondern mit Symbolen. Ein Unterprogramm hat zum Beispiel bei der Anzeige jeder neuen Lösung auf dem Bildschirm zusĂ€tzlich ein akustisches Signal ausgegeben. Das sah dann im Original so aus:
Aber auch das war nicht der Anfang. đ Davor habe ich fĂŒr jedes Unterprogramm einen Programmablaufplan entwickelt. Alles noch handgezeichnet:
Das kann aber jetzt dann jeder nachvollziehen, oder?
1989 habe ich das ganze Programm auch noch mal in Turbo-Pascal programmiert. Aber darauf gehe ich in diesem Artikel nicht weiter ein.
Sehr schön ist das Problem und ein progammtechnischer Ansatz in dem „Artikel Von Professor Urban“ (Hinweis 03.02.2019: Leider funktioniert der Link nicht mehr: http://www.hib-wien.at/leute/wurban/informatik/sendmoremoney.pdf.) dargestellt.
FĂŒr alle, die nun – wie ich – wieder Lust auf 6502-Assembler bekommen haben, habe ich noch eine Buch-Empfehlung: Programmierung des 6502 von Rodnay Zaks.
Das Buch steht bei mir seit 1983 im IT-BĂŒcherregal und ist sowohl fĂŒr Einsteiger als auch fĂŒr Fortgeschrittene wĂ€rmstens zu empfehlen.
Auch wenn heute kaum noch jemand direkt in Assembler programmiert, so macht es doch SpaĂ, sich auf diese Tiefe hinabzubegeben und kleinere Probleme damit zu lösen.
(Vielleicht, mein Sohn, ist das ja auch fĂŒr dich ein Anreiz!)