Weakest calculator/pocket computer that can do Tower of Hanoi?
08-13-2018, 01:07 PM
Post: #21
 Dave Britten Senior Member Posts: 2,154 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
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
08-13-2018, 01:31 PM (This post was last modified: 08-13-2018 01:39 PM by SlideRule.)
Post: #22
 SlideRule Senior Member Posts: 1,325 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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]
08-13-2018, 03:58 PM
Post: #23
 Thomas Klemm Senior Member Posts: 1,804 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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

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}$$.
08-13-2018, 04:02 PM
Post: #24
 Thomas Klemm Senior Member Posts: 1,804 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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
08-14-2018, 12:47 AM (This post was last modified: 09-10-2018 04:09 PM by Thomas Klemm.)
Post: #25
 Thomas Klemm Senior Member Posts: 1,804 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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

Cheers
Thomas
08-14-2018, 04:18 AM
Post: #26
 Paul Dale Senior Member Posts: 1,766 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
Nice! I can stop looking now

Pauli
08-15-2018, 03:49 PM
Post: #27
 Jake Schwartz Senior Member Posts: 330 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
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
08-15-2018, 04:39 PM (This post was last modified: 08-15-2018 04:46 PM by Dave Britten.)
Post: #28
 Dave Britten Senior Member Posts: 2,154 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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
08-15-2018, 05:31 PM
Post: #29
 Gene Moderator Posts: 1,290 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
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
08-15-2018, 08:12 PM
Post: #30
 Thomas Klemm Senior Member Posts: 1,804 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
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

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

Kind regards
Thomas
08-29-2018, 11:32 PM
Post: #31
 SlideRule Senior Member Posts: 1,325 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
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
08-30-2018, 03:36 PM
Post: #32
 Dave Britten Senior Member Posts: 2,154 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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.
08-30-2018, 11:57 PM
Post: #33
 SlideRule Senior Member Posts: 1,325 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
NOT the original Tower of Hanoi program for the ZX81 but …
[attachment=6266]
… enjoy.

BEST!
SlideRule
10-29-2018, 02:15 PM
Post: #34
 SlideRule Senior Member Posts: 1,325 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
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?
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
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)