Programming Praxis

5 Responses to “Tower Of Hanoi”

1. Dmitriy Borodiy said

   October 12, 2011 at 1:49 AM

   Here is my scheme solution:

   (define (hanoi n)
     (define (move-disks from to quantity)
       (if (eq? quantity 1) 
           (printf "Move disk from ~a to ~a~%" from to)
           (let ((aux (- 6 (+ from to))))
             (move-disks from aux (sub1 quantity))
             (move-disks from to 1)
             (move-disks aux to (sub1 quantity)))))
     (move-disks 1 3 n))
   
2. ardnew said

   October 12, 2011 at 4:19 PM

   purely iterative version with ASCII art in C:

   #include <stdio.h>
   #include <stdlib.h>
   #include <string.h>
   
   #define NUM_TOW 3
   #define NUM_RNG 5
   
   #define TOWER_1 0
   #define TOWER_2 1
   #define TOWER_3 2
   
   #define RING '='
   #define POST '|'
   
   int tower[NUM_TOW][NUM_RNG];
   
   void print_towers(int k)
   {
     int i, j, n, u, v;
     char *s;
   
     printf("\n\nStep (%d):\n\n", k);
   
     for (j = 0; j < NUM_RNG; ++j)
     {
       for (i = 0; i < NUM_TOW; ++i)
       {
         s = malloc(NUM_RNG * sizeof(*s));
         memset(s, 0, NUM_RNG);
   
         n  = NUM_RNG / 2;
   
         u = tower[i][j];
         v = !u;
   
         memset(s, ' ', n);
         memset(s + n, RING + v * (POST - RING), u + v - u * v);
         memset(s + n + u + v, ' ', n);
   
         printf("%*s", NUM_TOW + NUM_RNG + 1, s);
       }
       printf("\n");
     }
     printf("\n");
   }
   
   void init_towers()
   {
     int i, j;
   
     for (i = 0; i < NUM_TOW; ++i)
       for (j = 0; j < NUM_RNG; ++j)
         tower[i][j] = (j + 1) * !i;
   }
   
   int top(int t)
   {
     int i = NUM_RNG;
     while (tower[t][i - 1] && --i);
     return i;
   }
   
   int top_ring(int t)
   {
     int n = top(t);
     return tower[t][n - !(n - NUM_RNG)];
   }
   
   void swap(int *a, int *b)
   {
     *a ^= *b;
     *b ^= *a;
     *a ^= *b;
   }
   
   void move(int a, int b)
   {
     int ar = top_ring(a);
     int br = top_ring(b);
   
     if (ar && (!br || (br > ar))) swap(&a, &b);
   
     tower[a][top(a) - 1] = top_ring(b);
     tower[b][top(b)]     = 0;
   }
   
   void hanoi()
   {
     int x, n = 0;
     while (top(TOWER_3))
     {
       x = ++n % NUM_TOW;
       move(!x, 1 + !(x >> 1));
       print_towers(n);
     }
   }
   
   int main(void)
   {
     init_towers();
     print_towers(0);
     hanoi();
     return 0;
   }
   
3. Mike said

   October 14, 2011 at 3:25 AM

   Here’s an iterative solution in Python 3.

   The way I remember it is:
   1. Consider pairs of towers according to a repeating pattern.
   2. The pattern for an even number of disks is the same as for 2 disks;
   the pattern for an odd number of disks is reversed.
   3. For any pair of towers, make the legal move.

   from collections import deque
   from itertools import cycle
   
   def hanoi(ndisks):
       '''Generate moves to solve the Tower of Hanoi.
   
       input  - number of disks
       output - sequence of tuples of the form (disk, from, to)
       '''
       
       tower = [deque(range(ndisks)), deque(), deque()]
   
       pattern = ((0,1),(0,2),(1,2)) if ndisks&1 != 1 else ((0,2),(0,1),(1,2))
   
       for fm, to in cycle(pattern):
           if not tower[fm] or tower[to] and tower[to] < tower[fm]:
               fm, to = to, fm
               
           yield tower[fm][0], fm, to
           
           tower[to].appendleft(tower[fm].popleft())
           
           if len(tower[2]) == ndisks:
               break
   
   
   # test
   format_header = "Solution for {}-disk Towers of Hanoi:".format
   format_step = "Move disk {} from tower {} to tower {}.".format
   
   for ndisks in range(1,5):
       print(format_header(ndisks))
       
       for disk, fm, to in hanoi(ndisks):
           print(format_step(disk, 'ABC'[fm], 'ABC'[to]))
   
       print()
       
   
4. Jos Koot said

   November 30, 2011 at 3:50 PM

   #lang racket

   #|
   Shortest path of moving a Hanoian tower from one needle to another one.
   Non recursive algorithm.

   n : exact non-negative integer number
   h : number of disks.
   m : number of the move to be made counting from 1.
   d : disk, identified in increasing order by 0 up to but not including h.
   f : Position of the full tower at the start of the path (0, 1 or 2)
   t : Position of the full tower after completion of the path (0, 1 or 2)

   f and t must be different.

   mcnt : number of moves made with disk d after m moves.
   onto : needle a disk is moved to during move m.
   from : needle a disk is taken from during move m.
   thrd : needle not involved in move m.
   posi : needle disk d is positioned at after m moves.
   disk : disk being moved during move m.
   |#

   (require (only-in (lib “60.ss” “srfi”) log2-binary-factors))

   (define (exp2 n ) (expt 2 n))
   (define (mod2 n ) (modulo n 2))
   (define (mod3 n ) (modulo n 3))
   (define (pari n ) (add1 (mod2 (add1 n))))
   (define (rotd h d f t) (mod3 (* (- t f) (pari (- h d)))))
   (define (rot3 h f t) (rotd h 0 f t))
   (define (mcnt m d ) (quotient (+ m (exp2 d)) (exp2 (add1 d))))
   (define (thrd m h f t) (mod3 (- f (* m (rot3 h f t)))))
   (define (onto m h f t) (mod3 (- (thrd m h f t) (rotd h (disk m) f t))))
   (define (from m h f t) (mod3 (+ (thrd m h f t) (rotd h (disk m) f t))))
   (define (posi m h d f t) (mod3 (+ f (* (rotd h d f t) (mcnt m d)))))
   (define disk log2-binary-factors)

   #| compute the distribution of the disks of a tower of 100 disks after
   (expt 10 30) moves starting from needle 0 and going to needle 1.
   |#

   (time
   (let ((m (expt 10 30)) (h 100) (f 0) (t 1))
   (for/list ((d (in-range 0 h))) (posi m h d f t))))

   ; cpu time: 0 real time: 0 gc time: 0

   ; (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 0 0 2 1 0 2 1 1 1 1 2 0 0 2 1 1 1 0 0 1 2 0 0 0 1 1 0 0 1 1 1 2 0 0 0 0 0 1 2 0 0 2 2 0 0 0 1 1 0 2 2 0 0 2 1 0 0 1 1 1 1 1 2 2 1 0 0 1 1)

   Jos
5. Controlling What Lies Beneath said

   April 6, 2012 at 6:35 AM

   […] to the Tower of Hanoi puzzle, especially compared to the other languages: https://programmingpraxis.com/2011/10/11/tower-of-hanoi/ Tags: code, control, hacker, hacking, programming, […]

Leave a Reply

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out /  Change )

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s

Notify me of new comments via email.

Notify me of new posts via email.

Δ