Weakest calculator/pocket computer that can do Tower of Hanoi?
08-11-2018, 05:26 PM
Post: #1
 Dave Britten Senior Member Posts: 2,143 Joined: Dec 2013
Weakest calculator/pocket computer that can do Tower of Hanoi?
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?
08-11-2018, 06:42 PM
Post: #2
 Thomas Okken Senior Member Posts: 1,816 Joined: Feb 2014
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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...
08-11-2018, 06:52 PM
Post: #3
 Dave Britten Senior Member Posts: 2,143 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
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.
08-11-2018, 08:35 PM
Post: #4
 Thomas Okken Senior Member Posts: 1,816 Joined: Feb 2014
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
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
08-12-2018, 01:46 AM (This post was last modified: 08-12-2018 02:14 AM by Thomas Okken.)
Post: #5
 Thomas Okken Senior Member Posts: 1,816 Joined: Feb 2014
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
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.
08-12-2018, 01:52 AM
Post: #6
 Dave Britten Senior Member Posts: 2,143 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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.
08-12-2018, 07:16 AM (This post was last modified: 08-12-2018 01:19 PM by Thomas Klemm.)
Post: #7
 Thomas Klemm Senior Member Posts: 1,773 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
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.
08-12-2018, 07:46 AM
Post: #8
 Thomas Okken Senior Member Posts: 1,816 Joined: Feb 2014
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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.
08-12-2018, 08:10 AM
Post: #9
 Thomas Klemm Senior Member Posts: 1,773 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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
08-12-2018, 09:35 AM (This post was last modified: 08-12-2018 09:48 AM by Thomas Klemm.)
Post: #10
 Thomas Klemm Senior Member Posts: 1,773 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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
08-12-2018, 01:16 PM (This post was last modified: 08-12-2018 01:20 PM by Thomas Klemm.)
Post: #11
 Thomas Klemm Senior Member Posts: 1,773 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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
08-12-2018, 01:19 PM (This post was last modified: 08-12-2018 01:34 PM by Thomas Okken.)
Post: #12
 Thomas Okken Senior Member Posts: 1,816 Joined: Feb 2014
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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.
08-12-2018, 01:32 PM
Post: #13
 Thomas Klemm Senior Member Posts: 1,773 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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
08-12-2018, 05:08 PM
Post: #14
 Thomas Klemm Senior Member Posts: 1,773 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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?
08-12-2018, 06:07 PM
Post: #15
 Thomas Okken Senior Member Posts: 1,816 Joined: Feb 2014
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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
08-13-2018, 12:45 AM
Post: #16
 SlideRule Senior Member Posts: 1,325 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
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
08-13-2018, 01:38 AM
Post: #17
 Paul Dale Senior Member Posts: 1,762 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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
08-13-2018, 03:40 AM
Post: #18
 Thomas Okken Senior Member Posts: 1,816 Joined: Feb 2014
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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.
08-13-2018, 07:03 AM
Post: #19
 Paul Dale Senior Member Posts: 1,762 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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
08-13-2018, 11:47 AM (This post was last modified: 09-10-2018 04:08 PM by Thomas Klemm.)
Post: #20
 Thomas Klemm Senior Member Posts: 1,773 Joined: Dec 2013
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
(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

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.
 « Next Oldest | Next Newest »

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