(25) MASTER MIND

[Thomas Klemm]

This program was extracted from DISPLAY-V4N5&6 p.12:

D.KREJTSCHA (537) Wrote:Ein grundsätzliches Problem für den HP-25 Besitzer ist immer wieder die auf 49 Schritte beschränkte Programmkapazität.
Selbst mit einer ausgefeilten Programmiertechnik stößt er schnell an die Grenzen dieses Rechners.
Das Fehlen einer Unterprogramm-Möglichkeit und indirekter Adressierung macht sich schmerzlich bemerkbar.
Deshalb spielt die Auswahl eines geeigneten Algorithmus zur Lösung der jeweiligen Aufgabe eine überragende Rolle.
Leider kann er nie sicher sein, den bestmöglichen Algorithmus gefunden zu haben, sonst müßte er nicht laufend die Verbesserung seiner für optimal gehaltenen Programme erleben.

Die bei dem vorliegenden Programm angewandte Methode wurde mir von Mr. K.E.PLAMBECK vorgeschlagen.

Die im Register R4 bzw. R5 gespeicherte Zahl soll durch systematisches Probieren gefunden werden.
Die Versuchszahl wird in die Register R6 und R7 geladen.
Der Vergleich auf positionsrichtige Ziffern erfolgt zwischen R6 und R5.
Der Vergleich auf positionsfalsche Ziffern erfolgt zwischen R5 und R7.
Bei Übereinstimmung wird die jeweilige Ziffer in R7 gelöscht.
Damit wird verhindert, daß sie ein zweites mal an einem (erfolgreichen) Vergleich teilnimmt.
Da bei positionsrichtigen Ziffern bei beiden Vergleichen eine Übereinstimmung festgestellt wird, wird einmal die 9 und später noch die 1 in das Ergebnisregister R2 addiert.
Das entspricht einer Erhöhung der Zehnerstelle um 1.
Ist die gerade untersuchte Ziffer in der gesuchten Zahl nicht vorhanden, so findet überhaupt keine Addition statt.
In den Registern R5 und R6 nimmt jede Position nur einmal an einem Vergleich (bzw. Vergleichsreihe) teil.
Die Positionen in R7 werden jedesmal alle verglichen.

Die Instruktion f MEANx in Schritt 29 ersetzt bekanntlich die Befehlsfolge RCL 7, RCL 3, /.

Das Programm läßt im wesentlichen zwei Wünsche offen:

1. Zulassung der Null
2. Erzeugung der zu erratenden Zahl durch einen Zufallszahlengenerator.
   

Der erste Wunsch läßt sich unter Verzicht auf Bedienungskomfort verwirklichen.
Statt 10 muß 100 in das Register R1 geladen werden.
Jede Ziffer muß noch mit einer "Kontrollziffer" versehen werden, d.h., statt z.B. 8050 muß 81015101 eingegeben werden.
Das Programm selbst bleibt unverändert!
Die Realisation des zweiten Wunsches gelang mir bisher nicht, obwohl sich das Programm, bei weiteren Abstrichen, um (mindestens) 8 Schritte kürzen läßt.

Registerbelegung:
R0: -frei-
R1: 10
R2: belegt   (SCORE)
R3: belegt   (FACTOR)
R4: belegt   (GOAL)
R5: belegt   (GOAL WORK)
R6: belegt   (HIT)
R7: belegt   (MISSED)

Spielziel:
Ermitteln einer unbekannten Zahl Z durch systematisches Probieren.

Spielablauf:

1. Programm eingeben.
2. f PRGM
3. f FIX 0
4. Register R1 laden.
5. Eine n-stellige negative Zahl Z eingeben lassen. (Üblich ist n = 4) Z darf keine Null enthalten. Die Ziffern 1 bis 9 dürfen mehrfach auftreten. Anhand des Vorzeichens unterscheidet das Programm zwischen Initialisierung (-) und Rateversuch.
      Eingabe: Z, CHS, R/S.
      Anzeige: 0.
6. N-stellige Versuchszahl V nach obigen Bedingungen eingeben.
      Eingabe: V, R/S.
      Anzeige: ij.
   Zehnerstelle i = positionsrichtige Ziffern.
   Einerstelle j = positionsfalsche Ziffern.
   Ist V = Z, so wird nach R/S wieder V angezeigt (nicht 40).
7. Weiterraten: Gehe nach 6.
   Neues Spiel: Gehe nach 5.
   

This listing works with this HP-25 emulator:

Code:

01: 15 41    : g x<0
02: 13 47    : GTO 47
03: 23 06    : STO 6
04: 23 07    : STO 7
05: 24 04    : RCL 4
06: 14 71    : f x=y
07: 13 00    : GTO 00
08: 23 05    : STO 5
09: 34       : CLx
10: 23 02    : STO 2
11: 01       : 1
12: 23 03    : STO 3
13: 24 01    : RCL 1
14: 23 71 05 : STO / 5
15: 23 71 06 : STO / 6
16: 24 06    : RCL 6
17: 15 01    : g FRAC
18: 23 41 06 : STO - 6
19: 24 05    : RCL 5
20: 15 71    : g x=0
21: 13 45    : GTO 45
22: 15 01    : g FRAC
23: 23 41 05 : STO - 5
24: 14 61    : f x<>y
25: 13 29    : GTO 29
26: 09       : 9
27: 23 51 02 : STO + 2
28: 22       : Rv
29: 14 21    : f mean
30: 14 01    : f INT
31: 15 71    : g x=0
32: 13 11    : GTO 11
33: 24 01    : RCL 1
34: 23 61 03 : STO * 3
35: 71       : /
36: 15 01    : g FRAC
37: 14 61    : f x<>y
38: 13 28    : GTO 28
39: 24 03    : RCL 3
40: 61       : *
41: 23 41 07 : STO - 7
42: 01       : 1
43: 23 51 02 : STO + 2
44: 13 11    : GTO 11
45: 24 02    : RCL 2
46: 13 00    : GTO 00
47: 15 03    : g ABS
48: 23 04    : STO 4
49: 34       : CLx

Example

f CLEAR PRGM
f FIX 0
10 STO 1

-4711 R/S
0.

1234 R/S
2.

5126 R/S
1.

7813 R/S
11.

3919 R/S
10.

4711 R/S
4711.

---

D.KREJTSCHA (537) Wrote:A fundamental problem for the HP-25 owner is always the limited program capacity of 49 steps.
Even with a sophisticated programming technique, he quickly reaches the limits of this computer.
The lack of a subroutine option and indirect addressing is painfully noticeable.
That is why the selection of a suitable algorithm to solve the respective task plays a paramount role.
Unfortunately, he can never be sure that he has found the best possible algorithm, otherwise he would not have to experience the continuous improvement of his programs, which he considers to be optimal.

The method used in this program was suggested to me by Mr. K.E.PLAMBECK.

The number stored in register R4 or R5 is to be found by systematic trial and error.
The test number is loaded into registers R6 and R7.
The comparison for digits in the correct position takes place between R6 and R5.
The comparison for digits in the wrong position takes place between R5 and R7.
If there is a match, the respective digit in R7 is deleted.
This prevents it from participating in a (successful) comparison a second time.
As a match is found in both comparisons when the digits are in the correct position, the 9 is added once and then the 1 is added to the result register R2.
This corresponds to an increase in the tens digit by 1.
If the digit just examined is not present in the number being searched for, no addition takes place at all.
In registers R5 and R6, each position only participates in a comparison (or comparison series) once.
The positions in R7 are all compared each time.

The instruction f MEANx in step 29 replaces the command sequence RCL 7, RCL 3, /.

The program essentially leaves two wishes unfulfilled:

1. Allowing zero
2. Generating the number to be guessed using a random number generator.
   

The first wish can be realized without compromising on user convenience.
Instead of 10, 100 must be loaded into register R1.
Each digit must be provided with a "check digit", i.e., instead of 8050, for example, 81015101 must be entered.
The program itself remains unchanged!
I have not yet been able to realize the second wish, although the program can be shortened by (at least) 8 steps with further cuts.

Register assignment:
R0: -free-
R1: 10
R2: occupied   (SCORE)
R3: occupied   (FACTOR)
R4: occupied   (GOAL)
R5: occupied   (GOAL WORK)
R6: occupied   (HIT)
R7: occupied   (MISSED)

Game goal:
Determine an unknown number Z by systematic trial and error.

How to play:

1. Enter the program.
2. f PRGM
3. f FIX 0
4. Load register R1.
5. Have the user enter an n-digit negative number Z. (n = 4 is usual) Z must not contain a zero. The numbers 1 to 9 may appear multiple times. The program uses the sign to distinguish between initialization (-) and guessing attempts.
      Enter: Z, CHS, R/S.
      Display: 0.
6. Enter the N-digit attempt number V according to the above conditions.
      Enter: V, R/S.
      Display: ij.
   Tens digit i = digits in the correct position.
   Units digit j = digits in the wrong position.
   If V = Z, V is displayed again after R/S (not 40).
7. Continue guessing: Go to 6.
   New game: Go to 5.