Weakest calculator/pocket computer that can do Tower of Hanoi?

[Dave Britten]

Very nice code, Thomas. I'll have to see if I can use any of that algorithm to improve my clumsy Casio fx-7000g version.

(N.B.: I've used the more standard ^ symbol for the x^y key, and (10^) to represent the small "10" that corresponds to 10^x.)

Prog 0

Code:

Mcl
Range 1,95,0,1,64,0
"N"?→N
2Frac (N÷2→O
2^N-1→M
9→P:9→Q:9→R
N→U:9→V:18→W
U→I
Lbl 0
N-I+1→D
Prog 2
Dsz I:Goto 0
1→B
Prog 3
Lbl 1
B→F
B+1+O→G
G>3⇒G-3→G
B+2-O→B
B>3⇒B-3→B
T[F→I:Prog 1
D→C
T[G→I:Prog 1
C<D⇒Goto 2
D→C:F→S:G→F:S→G
Lbl 2
0→D:T[F→I:Prog 2
Dsz T[F]:Ans
Isz T[G]
C→D:T[G→I:Prog 2
Prog 3
Dsz M
Goto 1

Prog 1 - This is a register-packing "get" routine.

Code:

P[Int(I÷9→Z
9Frac (I÷9→E
10Frac (Int (Z÷(10^)E)÷10→D

Prog 2 - And this is the corresponding "put" routine.

Code:

D→H
Prog 1
Z-D(10^)E+H(10^)E→P[Int (I÷9)]

Prog 3 - Display routine. There's no way to selectively erase parts of the screen, so the entire screen must be cleared and redrawn after each move.

Code:

Cls
-14→J
0→I
Lbl 1
J+16→J
0→K
Lbl 2
Prog 1
D=0⇒Goto 3
K+2→K
Plot J+8-D,K
Plot J+7+D,K
Line
Lbl 3
Isz I
0≠Frac (I÷9⇒Goto 2
I<27⇒Goto 1

[SlideRule]

(08-13-2018 11:47 AM)Thomas Klemm Wrote:  I've used from Binary solution of Tower of Hanoi:
Another formulation is from peg (m - (m & -m)) % 3 to peg (m + (m & -m)) % 3
And then from A006519:
Highest power of 2 dividing n.
FORMULA
a(n) = n AND -n (where "AND" is bitwise).
But I went the other way round: first I've generated the from and to sequences and looked them up in OEIS. Only when I figured out the formulas I found them in Wikipedia.

from Martin Gardner's [attachment=6205] chapter 6, page 67 …

Quote:The isomorphism of the Tower ofHanoi’s solution and the Hamil-
tonian path on cubes and hypercubes is perhaps not so startling
when we realize that in both cases the sequence of moves is a pattern
familiar to anyone working with binary computers. We first
write the binary numbers from 1 to 8 and label the columns A, B,
C, D as shown in Figure 27. We then write opposite each row the
letter that identifies the “1” that is farthest to the right on each row.
The sequence of these letters from top down will be the pattern in
question.

bold & italic my emphasis

BEST!
SlideRule

yet another reference [attachment=6206]

[Thomas Klemm]

(08-12-2018 06:07 PM)Thomas Okken Wrote:  As far as I'm aware, that behavior is a bug in the HP-25 (and 25C), not found in other HP models. See http://www.hpmuseum.org/forum/thread-9566.html

Thanks for the link. That was an interesting read.
I was happily watching the blinkenlichten while the HP-25 emulator was calculating.

So I tried to maximise the duration by using \(2^{33}=8,589,934,592\) but was slightly disappointed by the result:
Only disk 5?
Whereas I've expected 34.

Turned out the given result was \(8,589,934,605\) which is off by \(13\).
So I've entered the correct value manually.

Those of you who wonder how an odd number could lead to disk 5 may notice that all the values are rounded to 10 digits.

So that's a limitation of the program: \(0<n\leqslant10^{9}\).

[Thomas Klemm]

(08-13-2018 01:31 PM)SlideRule Wrote:  yet another reference

Thank you for all of your references. I've always loved the books by Martin Gardner.

Kind regards
Thomas

[Thomas Klemm]

(08-13-2018 11:47 AM)Thomas Klemm Wrote:  There are 12 lines left that could be used for a loop or a fancy display or what not.

Meanwhile I was able to remove another step.
This allows to output a single line in an infinite loop:

Code:

01 1           ; 1
02 STO 0       ; n=1
03▸RCL 0       ; k=n
04 1           ; 1 k
05 STO 1       ; a=1 k
06 STO 2       ; m=1 k
07▸R↓          ; k
08 2           ; 2 k
09 ÷           ; k/2
10 FRAC        ; {k/2}
11 x≠0         ; k % 2 ≠ 0 ?
12 GTO 20      ; done
13 LASTx       ; k'=k/2
14 2           ; 2 k'
15 STO × 1     ; a'=2a
16 R↓          ; k'
17 1           ; 1 k'
18 STO + 2     ; m'=m+1
19 GTO 07      ; while
20▸RCL 0       ; n
21 RCL 1       ; a n
22 +           ; n+a
23 3           ; modulo 3
24 ÷           ;
25 FRAC        ;
26 4           ;
27 ×           ;
28 INT         ; to=(n+a)%3
29 1           ;
30 0           ; 10 to
31 ÷           ; 0.to
32 RCL 0       ; n 0.to
33 RCL 1       ; a n 0.to
34 -           ; n-a 0.to
35 3           ; modulo 3
36 ÷           ;
37 FRAC        ;
38 4           ;
39 ×           ;
40 INT         ; from=(n-a)%3 0.to
41 +           ; from.to
42 1           ; 1
43 STO + 0     ; n=n+1
44 10^x        ; 10 from.to
45 ÷           ; 0.from-to
46 RCL 2       ; disk 0.from-to
47 +           ; disk.from-to
48 R/S         ; show move
49 GTO 03      ; next n

Make sure to have the display set to FIX 2 which is the default after starting up the calculator.

Example:

GTO 00
R/S
X: 1.02
R/S
X: 2.01
R/S
X: 1.21
R/S
X: 3.02
R/S
X: 1.10
…


Thus:

1. move disk 1 from peg 0 to peg 2
2. move disk 2 from peg 0 to peg 1
3. move disk 1 from peg 2 to peg 1
4. move disk 3 from peg 0 to peg 2
5. move disk 1 from peg 1 to peg 0
6. …
   

Cheers
Thomas

[Paul Dale]

Nice! I can stop looking now


Pauli

[Jake Schwartz]

For what it is worth, the earliest Tower of Hanoi program I could find in the PPC Journal is Harry Bertuccelli's HP-41C 164-step version, which appeared in Volume 8 Number 3 Page 22 (from May 1981). It also utilized four PPC ROM routines (HD, UD, LR, SR).

Jake

[Dave Britten]

(08-15-2018 03:49 PM)Jake Schwartz Wrote:  For what it is worth, the earliest Tower of Hanoi program I could find in the PPC Journal is Harry Bertuccelli's HP-41C 164-step version, which appeared in Volume 8 Number 3 Page 22 (from May 1981). It also utilized four PPC ROM routines (HD, UD, LR, SR).

Jake

Interesting, I would have expected there would be something for the 65 or 67, since the problem can clearly be handled with a 25. I should rummage through scans of PPC Notes to see if it was done on the TI-59 (or its kin).

EDIT: Here's a massive 559-step TI-59 version, though it seems to have more features than just a solver (you can play interactively, and print the state of the game to an attached printer). Search for program 918122 on this page.

http://www.rskey.org/CMS/index.php/the-library/15

[Gene]

Couple of other TI-59 Hanoi programs.

Recursive - 88 steps: 88 steps

Another one - 275 steps but prints each move showing towers!: Hanoi with print out

and the 560 step TI-59 version: 560 steps

[Thomas Klemm]

Now that we know that binary operations and remainder are useful in an iterative solution here's a version for the HP-16C:

Code:

01 RCL I
02 ENTER
03 ENTER
04 CHS
05 AND
06 -
07 RCL I
08 LSTx
09 +
10 3
11 RMD
12 x<>y
13 3
14 RMD
15 ISZ

Initialisiation

DEC
1
STO I
RTN

Endless Loop

R/S
Y: to
X: from


Example:

R/S
0
R↓
2

R/S
0
R↓
1

R/S
2
R↓
1

R/S
0
R↓
2

…

Thus:

1. move disk from peg 0 to peg 2
2. move disk from peg 0 to peg 1
3. move disk from peg 2 to peg 1
4. move disk from peg 0 to peg 2
5. …
   

It doesn't tell you which disk to move but that's not needed.

Kind regards
Thomas

[SlideRule]

OK, it took a while BUT I finally retrieved the source listing for the PC-2 (1500) HHC.

Code:

7 "HANOI TOWERS
8 "KEYS : $%& 
9 "SHARPENTIERS #8
10 " "CLEAR :DIM B(7,3):E=85,U=24,B(0,1)=99,B(0,2)=99,B(0,3)=99
20 PAUSE " *** HANOI TOWERS ***":INPUT "How many discs (1-7)? ";Q:Q=INT Q:IF Q<1OR Q>7THEN 20
30 B=Q,F=2*Q+1:FOR I=1TO Q:B(I,1)=F,F=F-2:NEXT I
40 CLS :WAIT 0:FOR I=0TO Q-1:GCURSOR E-Q+I:V=V+2^(6-I):GPRINT V:NEXT I
50 FOR I=7-QTO 6:GCURSOR E+I-6+Q:GPRINT V:V=V-2^I:NEXT I:GCURSOR E:GPRINT &7F:GCURSOR E+U:GPRINT &7F:GCURSOR E+2*U:GPRINT &7F
60 S=ASC INKEY$ :IF S<20OR S>22THEN 60
70 Z=S-19:IF @(Z+1)=0THEN 110
80 BEEP 1:K=30,H=Z:GOSUB 200:GPRINT "001010103810000006520E00"
90 S=ASC INKEY$ :IF S<20OR S>22THEN 90
100 X=S-19:IF Z<>XAND B(@(Z+1),Z)<B(@(X+1),X)THEN 120
110 GCURSOR 30:GPRINT "06520E00":BEEP 3:GOTO 60
120 BEEP 1:K=42,H=X:GOSUB 200
130 L=E+U*(Z-1)-INT (B(@(Z+1),Z)/2),T=L+U*(X-Z)
140 FOR M=0TO B(@(Z+1),Z)-1:N=L+M:GCURSOR N:GPRINT POINT NAND (127-2^(7-@(Z+1))):GCURSOR E+U*(Z-1)
150 GPRINT &7F:R=2^(6-@(X+1)),N=M+T:GCURSOR N:GPRINT POINT NOR R:NEXT M
160 B(@(X+1)+1,X)=B(@(Z+1),Z),B(@(Z+1),Z)=0
170 @(Z+1)=@(Z+1)-1,@(X+1)=@(X+1)+1,A=A+1
180 IF D=QCLS :WAIT :PRINT "BRAVO !!!";USING "####";A;" MOVES.":END
190 K=0,W$=STR$ A:FOR I=1TO LEN W$:H=VAL (MID$ (W$,I,1)):GOSUB 200:K=K+4:NEXT I:GPRINT "7848480040":GOTO 60
200 GCURSOR K:RESTORE 210+10*H:READ A$:GPRINT A$,:RETURN 
210 DATA "7C447C
220 DATA "487C40
230 DATA "74545C
240 DATA "54547C
250 DATA "1C7010
260 DATA "5C5474
270 DATA "7C5474
280 DATA "04047C
290 DATA "7C547C
300 DATA "5C547C

I think my initial response was on the PRIME sub-Forum but it seemed appropriate to post the BASIC listing here.

BEST!
SlideRule

[Dave Britten]

(08-29-2018 11:32 PM)SlideRule Wrote:  OK, it took a while BUT I finally retrieved the source listing for the PC-2 (1500) HHC.

I think my initial response was on the PRIME sub-Forum but it seemed appropriate to post the BASIC listing here.

BEST!
SlideRule

Cool! Thanks for posting the listing. I'll have to dig out my PC-2 and give it a try. I tend to prefer the Casios over the Sharps, largely because of the separate program spaces making them more convenient standalone systems, but there's no denying that the PC-2/PC-1500 was the most powerful of its contemporaries. I should really hunt down a cassette interface for it some day.

[SlideRule]

NOT the original Tower of Hanoi program for the ZX81 but …
[attachment=6266]
… enjoy.

BEST!
SlideRule

[SlideRule]

Even longer still …

Turing's sword
See you our server farm that hums
And serves HTTP?
It's spun its disk and done its sums
Ever since Berners-Lee.

See you our mainframe spewing out
The Towers of Hanoi?
It's moved recursive disks about
Since Babbage was a boy.

See you our ZX81
That prints the ABCs?
That very program used to run
With Lovelace at the keys.

Magnetic floppy disks and hard,
And tape with patience torn,
And eighty columns on a card,
And so was England born!

She is not any common thing,
Water or Wood or Air,
But Turing's Isle of Programming,
Where you and I will fare.

from Time Blew Away Like Dandelion Seed,
Thomas Thurman

… but finally found it.

BEST!
SlideRule