Post Reply 
Weakest calculator/pocket computer that can do Tower of Hanoi?
08-13-2018, 11:47 AM (This post was last modified: 09-10-2018 04:08 PM by Thomas Klemm.)
Post: #20
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


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.
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: Weakest calculator/pocket computer that can do Tower of Hanoi? - Thomas Klemm - 08-13-2018 11:47 AM



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