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

[Dave Britten]

What's the weakest (least RAM, sparsest programming capabilities) handheld that can do Tower of Hanoi solutions? I know it's been done on the 42S, but that has a spacious 8 KB RAM. I've pulled it off on my Casio fx-7000g, which gives you a little over 400 bytes for your program, and 26 variables/registers. It'll handle up to 8 discs (which takes quite a long time to run). Has anybody managed to do it on a 32S?

[Thomas Okken]

(08-11-2018 05:26 PM)Dave Britten Wrote:  What's the weakest (least RAM, sparsest programming capabilities) handheld that can do Tower of Hanoi solutions? I know it's been done on the 42S, but that has a spacious 8 KB RAM. I've pulled it off on my Casio fx-7000g, which gives you a little over 400 bytes for your program, and 26 variables/registers. It'll handle up to 8 discs (which takes quite a long time to run). Has anybody managed to do it on a 32S?

If you implement the iterative solution, you can do it on almost anything. I did it on the 19C, but that was ages ago, and that program is lost in the mists of time and I don't remember any of the implementation details. I'll take a shot at doing it on the HP-25 tonight...

[Dave Britten]

Now that would be impressive to see it running on a 25. I'm assuming you'd have to simply display the moves in "from.to" format or similar.

I used the iterative method for the 1st-gen Casio program, and it just barely fits in memory (and uses nearly all the variables, even with packing the stacks into a single variable each). But it also shows the discs graphically. There's no doubt plenty of opportunities to shrink and optimize it.

[Thomas Okken]

Doing it on the 25 does seem a bit ambitious. When I started writing the code, it turned out quite a bit longer than I thought. Devil in the details... It does fit in the 19C/29C, though:

Code:

01▸LBL 0
02 STO 0
03 2
04 ÷
05 FRAC
06 X≠0?
07 9
08 ENTER
09 1
10 2
11 3
12 +
13 STO 2
14 RCL 0
15 10↑X
16 9
17 ÷
18 INT
19 STO 3
20 CLX
21 STO 4
22 STO 5
23▸LBL 1
24 RCL 2
25 1
26 0
27 ÷
28 INT
29 LASTX
30 FRAC
31 EEX
32 3
33 ×
34 X<>Y
35 +
36 STO 2
37 LASTX
38 RCL 3
39 RCL 4
40 X>Y?
41 GTO 2
42 +
43 1
44 GTO 3
45▸LBL 2
46 +
47 X<>Y
48 1
49 0
50 ÷
51 INT
52 LASTX
53 FRAC
54 EEX
55 2
56 ×
57 +
58 X<>Y
59 1
60 CHS
61▸LBL 3
62 X<>Y
63 X=0?
64 RTN
65 LOG
66 INT
67 10↑X
68 ×
69 STO- 3
70 STO+ 4
71 R↓
72 R/S
73 RCL 3
74 RCL 4
75 RCL 5
76 STO 3
77 R↓
78 STO 5
79 R↓
80 STO 4
81 GTO 1

[Thomas Okken]

A bit smarter algorithm, taking advantage of the fact that if you're not displaying the towers anyway, and only showing the sequence of moves, you don't have to keep track of where the discs are:

Code:

01▸LBL 0
02 STO 0
03 CLX
04 STO 1
05▸LBL 1
06 1
07 STO+ 1
08 RCL 0
09 STO 2
10 RCL 1
11▸LBL 2
12 2
13 ÷
14 ENTER
15 INT
16 X≠Y?
17 GTO 3
18 1
19 STO- 2
20 R↓
21 GTO 2
22▸LBL 3
23 RCL 2
24 X=0?
25 RTN
26 2
27 ÷
28 FRAC
29 2
30 ×
31 1
32 +
33 ×
34 ENTER
35 ENTER
36 LASTX
37 +
38 ENTER
39 ENTER
40 3
41 ÷
42 INT
43 3
44 ×
45 -
46 X<>Y
47 ENTER
48 ENTER
49 3
50 ÷
51 INT
52 3
53 ×
54 -
55 1
56 0
57 ×
58 +
59 1
60 1
61 +
62 R/S
63 GTO 1

Better, but still too long for the HP-25. Not having MOD really hurts.

[Dave Britten]

(08-12-2018 01:46 AM)Thomas Okken Wrote:  A bit smarter algorithm, taking advantage of the fact that if you're not displaying the towers anyway, and only showing the sequence of moves, you don't have to keep track of where the discs are:

I kind of suspected it might be possible to squeeze an optimization like that out of the problem. Hadn't experimented with the idea myself, though.

(08-12-2018 01:46 AM)Thomas Okken Wrote:  Not having MOD really hurts.

Yeah, that was definitely getting in my way doing the Casio version, particularly the section that chooses the next pair of pegs to operate on. I think doing stunts with Int and Frac would outweigh the savings of a few otherwise viable optimizations.

[Thomas Klemm]

This program for the HP-11C implements A001511:

Code:

01▸LBL A
02 1
03▸LBL 0
04 x<>y
05 2
06 ÷
07 FRAC
08 x≠0
09 GTO 1
10 R↓
11 LSTx
12 x<>y
13 1
14 +
15 GTO 0
16▸LBL 1
17 R↓
18 RTN

Quote:a(n) = number of disk to be moved at n-th step of optimal solution to Towers of Hanoi problem

It uses the following method to calculate \(a(n)\):

Quote:a(n) is the number of digits that must be counted from right to left to reach the first 1 in the binary representation of n.

Example with 3 disks

Hint: Move odd disks to the right and even disks to the left.

1 [A] → 1 ; move disk 1 to the right
2 [A] → 2 ; move disk 2 to the left
3 [A] → 1 ; move disk 1 to the right
4 [A] → 3 ; move disk 3 to the right
5 [A] → 1 ; (…)
6 [A] → 2
7 [A] → 1

(08-11-2018 08:35 PM)Thomas Okken Wrote:  Doing it on the 25 does seem a bit ambitious.

It should be possible to convert this program for the HP-25.

Cheers
Thomas

---

Edit: Fixed typo in line 08 of the program.

[Thomas Okken]

(08-12-2018 07:16 AM)Thomas Klemm Wrote:  This program for the HP-11C implements A001511:

Code:

01▸LBL A
02 1
03▸LBL 0
04 x<>y
05 2
06 ÷
07 FRAC
08 x≠y
09 GTO 1
10 R↓
11 LSTx
12 x<>y
13 1
14 +
15 GTO 0
16▸LBL 1
17 R↓
18 RTN

That program always returns 1, for any input.

Even if it did do what you say it should do, it would still be only a partial solution, because all it would tell you is which disc should be moved at any given step. The reason why my (second) program is so much longer is because it works out from from which to which position the disc is moved.

[Thomas Klemm]

(08-11-2018 05:26 PM)Dave Britten Wrote:  What's the weakest (least RAM, sparsest programming capabilities) handheld that can do Tower of Hanoi solutions?

On the HP-35 you could do the following to calculate \(a(n)\) from A001511:

1. Fill the stack with \(\frac{1}{2}\):

.5
ENTER
ENTER
ENTER

2. Enter the number \(n\):

CLx
\(n\)

3. Count how often you have to hit the [×] key until the number ends with .5.

[×]
[×]
…

4. Continue at step 2 with the next number.

Kind regards
Thomas

[Thomas Klemm]

(08-12-2018 07:46 AM)Thomas Okken Wrote:  That program always returns 1, for any input.

That's weird. Are you sure that you've entered these lines?

Code:

13 1
14 +

Quote:Even if it did do what you say it should do, it would still be only a partial solution, because all it would tell you is which disc should be moved at any given step. The reason why my (second) program is so much longer is because it works out from from which to which position the disc is moved.

It depends on how a solution is specified. You could give the sequence A001511 to someone and without understanding the rules it would be possible to play the game. You'd have to know how to move odd and even disk numbers differently but you could colour the disks accordingly which would give them a nice touch.

If you desperately need to know the positions they could be calculated from \(n\) and \(a(n)\):

Here's a Python program:

Code:

def hanoi(n):
    k, a = n, 1
    while not k % 2:
        k /= 2
        a += 1
    p = n / 2**a
    q, r = (p % 3, (p+1) % 3) if a % 2 else ((-p) % 3, (-p-1) % 3)
    return a, q, r

for i in range(1, 2**5):
    print hanoi(i)

And this is the generated output:

Code:

(disk, from, to)
(1, 0, 1)
(2, 0, 2)
(1, 1, 2)
(3, 0, 1)
(1, 2, 0)
(2, 2, 1)
(1, 0, 1)
(4, 0, 2)
(1, 1, 2)
(2, 1, 0)
(1, 2, 0)
(3, 1, 2)
(1, 0, 1)
(2, 0, 2)
(1, 1, 2)
(5, 0, 1)
(1, 2, 0)
(2, 2, 1)
(1, 0, 1)
(3, 2, 0)
(1, 1, 2)
(2, 1, 0)
(1, 2, 0)
(4, 2, 1)
(1, 0, 1)
(2, 0, 2)
(1, 1, 2)
(3, 0, 1)
(1, 2, 0)
(2, 2, 1)
(1, 0, 1)

Is that what you want?

Not sure if we can squeeze that into the 49 lines of a HP-25 though.

(08-12-2018 01:46 AM)Thomas Okken Wrote:  Not having MOD really hurts.

Agreed.

Cheers
Thomas

[Thomas Klemm]

(08-12-2018 07:46 AM)Thomas Okken Wrote:  That program always returns 1, for any input.

Oops, found the typo in line 08.
It should be x≠0 instead of x≠y:

Code:

08 x≠0

Thanks for notifying it.

Cheers
Thomas

[Thomas Okken]

(08-12-2018 09:35 AM)Thomas Klemm Wrote:  

(08-12-2018 07:46 AM)Thomas Okken Wrote:  That program always returns 1, for any input.

That's weird. Are you sure that you've entered these lines?

Code:

13 1
14 +

I am. Are you sure you have even tested this program? Those two lines are never reached. Here's what happens:

Code:

01▸LBL A   X:n
02 1       X:1 Y:n
03▸LBL 0
04 x<>y    X:n Y:1
05 2       X:2 Y:n Z:1
06 ÷       X:n/2 Y:1
07 FRAC    X:0 or 0.5 Y:1
08 x≠y     always true, see above!
09 GTO 1
16▸LBL 1
17 R↓      X:1 T:0 or 0.5
18 RTN

UPDATE: Ah, we posted at the same time -- never mind.

However,

(08-12-2018 09:35 AM)Thomas Klemm Wrote:  If you desperately need to know the positions they could be calculated from n and a(n)

I wouldn't call myself particularly desperate, but merely specifying which disc is moved at each step, without saying from where to where, looks like only half a solution to me. If you had read my second program more carefully, you would have noticed that it performs the same calculation that yours does, and then it works out the exact move. All your program accomplishes is to amputate two thirds of the logic. What's left certainly fits in an HP-25, but I wouldn't call that sequence a solution to the Towers of Hanoi puzzle, but merely an interesting property of such a solution.

[Thomas Klemm]

(08-12-2018 01:19 PM)Thomas Okken Wrote:  Are you sure you have even tested this program?

Unfortunately I can't run the Nonpareil emulator at the moment. So no, the program as it was typed wasn't tested. However it was tested on the real hardware. But from there I can't transfer programs to a computer.

Based on the behaviour you described I imagined what could have gone wrong. Missing a key happens to me all the time so I thought I give it a try.

Kind regards
Thomas

[Thomas Klemm]

(08-12-2018 07:16 AM)Thomas Klemm Wrote:  It should be possible to convert this program for the HP-25.

Here's what I came up with:

Code:

01 ENTER
02 1
03 x<>y
04 2
05 ÷
06 FRAC
07 x≠0
08 GTO 15
09 R↓
10 LASTx
11 x<>y
12 1
13 +
14 GTO 03
15 R↓

I've used this online HP-25 emulator to test it.
I hope I didn't make typos again.

Cheers
Thomas

PS: I wasn't aware that the ENTER in the first line is needed.
Otherwise 1 will just be appended to the number in the display.
Does anybody know with which model this behaviour changed?

[Thomas Okken]

(08-12-2018 05:08 PM)Thomas Klemm Wrote:  PS: I wasn't aware that the ENTER in the first line is needed.
Otherwise 1 will just be appended to the number in the display.
Does anybody know with which model this behaviour changed?

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

[SlideRule]

I found [attachment=6204]a most useful reference.

example: Chapter 2; the Classical Tower of Hanoi, pgs 94-05

Quote:As in the case of the CR it is clear that in an optimal solution disc 1 has to
be moved in the first step and then in every second move. Hence it will move
in every odd numbered move

BEST!
SlideRule

[Paul Dale]

(08-12-2018 05:08 PM)Thomas Klemm Wrote:  PS: I wasn't aware that the ENTER in the first line is needed.

Specify that the program is run after ENTER has been pressed. To expand this to a complete solution the oddness of the input is required, so a STO as the first step avoids the issue.
I wonder if the sign of the output could indicate the direction of the move rather than calculating the final position?

Anyway, here is a 49 step programme for the HP 25 that gives the solution to an n level Tower of Hanoi problem:

Code:

01  STO 4
02  1
03  2
04  STO 0
05  1
06  3
07  STO 1
08  2
09  3
10  STO 2
11  RCL 4
12  2
13  /
14  FRAC
15  x=0?
16  GTO 22
17  RCL 0
18  RCL 1
19  STO 0
20  Rv
21  STO 1
22  2
23  RCL 4
24  y^x
25  .
26  9
27  -
28  INT
29  RCL 0
30  PSE
31  Rv
32  1
33  -
34  x=0?
35  GTO 00
36  RCL 1
37  PSE
38  Rv
39  1
40  -
41  x=0?
42  GTO 00
43  RCL 2
44  PSE
45  Rv
46  1
47  -
48  x!=0?
49  GTO 29

To run:

1. GTO 00
2. Enter n
3. R/S
   

The program will display a sequence of two digits numbers that represent the poles moved between, pick the legal move in each case.

For a three high tower these are:

Code:

Display   Meaning
13        move the disc from pole 1 to 3
12        move the disc from pole 1 to 2
23        move the disc from pole 3 to 2
13        move the disc from pole 1 to 3
12        move the disc from pole 2 to 1
23        move the disc from pole 2 to 3
13        move the disc from pole 1 to 3

Pauli

[Thomas Okken]

(08-13-2018 01:38 AM)Paul Dale Wrote:  Anyway, here is a 49 step programme for the HP 25 that gives the solution to an n level Tower of Hanoi problem:

[...]

The program will display a sequence of two digits numbers that represent the poles moved between, pick the legal move in each case.

Lame. Why don't you just admit you don't know how to do this on the HP-25? Just like Thomas K., who also seems to think he's coded a solution even though he didn't, and like me, who coded a solution that is complete but is too long to fit.

[Paul Dale]

(08-13-2018 03:40 AM)Thomas Okken Wrote:  Lame. Why don't you just admit you don't know how to do this on the HP-25? Just like Thomas K., who also seems to think he's coded a solution even though he didn't, and like me, who coded a solution that is complete but is too long to fit.

I'm happy to admit that I've not come up with a complete solution for the HP-25 but this is a solution for somebody manually moving discs around. Okay, the single PSE is too fast and R/S would be needed instead but that's trivial. Regardless, I'm not yet ready to admit that a complete solution is totally impossible (I'm close but not quite yet).


Pauli

[Thomas Klemm]

(08-13-2018 07:03 AM)Paul Dale Wrote:  Regardless, I'm not yet ready to admit that a complete solution is totally impossible (I'm close but not quite yet).

Here's a program for the HP-25:

Code:

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

For a move \(n\) it returns:

Z: to
Y: from
X: disk

Example:

12 R/S
Z: 1
Y: 2
X: 3

Thus move disk 3 from peg 2 to peg 1.

It's the translation of the following Python program:

Code:

def hanoi(n):
    k = n
    a = m = 1
    while not k % 2:
        k /= 2
        a *= 2
        m += 1
    return m, (n - a) % 3, (n + a) % 3

This is the list for all moves for 5 disks:

Code:

>>> for n in range(1, 2**5):
...     print n, hanoi(n)
...
1 (1, 0, 2)
2 (2, 0, 1)
3 (1, 2, 1)
4 (3, 0, 2)
5 (1, 1, 0)
6 (2, 1, 2)
7 (1, 0, 2)
8 (4, 0, 1)
9 (1, 2, 1)
10 (2, 2, 0)
11 (1, 1, 0)
12 (3, 2, 1)
13 (1, 0, 2)
14 (2, 0, 1)
15 (1, 2, 1)
16 (5, 0, 2)
17 (1, 1, 0)
18 (2, 1, 2)
19 (1, 0, 2)
20 (3, 1, 0)
21 (1, 2, 1)
22 (2, 2, 0)
23 (1, 1, 0)
24 (4, 1, 2)
25 (1, 0, 2)
26 (2, 0, 1)
27 (1, 2, 1)
28 (3, 0, 2)
29 (1, 1, 0)
30 (2, 1, 2)
31 (1, 0, 2)

There are 12 lines left that could be used for a loop or a fancy display or what not.

Cheers
Thomas

---

Addendum:
I've used from Binary solution of Tower of Hanoi:

Quote:Another formulation is from peg (m - (m & -m)) % 3 to peg (m + (m & -m)) % 3

And then from A006519:

Quote: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.