Towers of Hanoi: Difference between revisions

Content added Content deleted

Inline

@@ Line 229: / Line 229: @@
 ===Iterative===
-ref : [http://hanoitower.mkolar.org/shortestTHalgo.html The shortest and "mysterious" TH algorithm]
+Fast iterative version. See: [http://hanoitower.mkolar.org/shortestTHalgo.html The shortest and "mysterious" TH algorithm]
+<lang d>// Code found and then improved by Glenn C. Rhoads,
-<lang d>module hanoi;
+// then some more by M. Kolar (2000).
-import std.stdio;
-import std.conv ;
+import std.stdio, std.conv, std.typetuple;
-void Hanoi(int n , string L /* from */, string M /* to */, string R /* via */) {
-  string[3] Pegs = [L,R,M] ;
-  int nn = (1 << n) ;
-  int x, fr, to, i, j ;
-  for(x = 1 ; x < nn ; x++){
-    i =  x & x - 1       ; fr = (i + i/3) & 3 ;
-    i = (x | x - 1) + 1  ; to = (i + i/3) & 3 ;
-    for(i = x, j = 1; !(i&1) ; i >>=1, j++)
-        writefln("Move Disc %d from %s to %s", j, Pegs[fr], Pegs[to]) ;
-  }
-}
 void main(string[] args) {
-  int n = (args.length > 1) ? to!(int)(args[1]) : 3 ;
+    const n = (args.length > 1) ? to!int(args[1]) : 3;
-  Hanoi(n, "L","M","R") ;
+    size_t i, j;
+    size_t[3] p;
+    p[0] = (1 << n) - 1;
+    printf("\n|");
+    for (i = n; i > 0; i--)
+        printf(" %d", i);
+    printf("\n|\n|\n");
+    foreach (size_t x; 1 .. (1 << n)) {
+        i = x & (x - 1);
+        const size_t fr = (i + i / 3) & 3;
+        i = (x | (x - 1)) + 1;
+        const size_t to = (i + i / 3) & 3;
+        for (i = x, j = 1; ; i >>= 1, j <<= 1)
+            if (i & 1)
+                break;
+        // Now j is not the number of the disk to move,
+        // it contains the single bit to be moved:
+        p[fr] &= ~j;
+        p[to] |= j;
+        foreach (k; TypeTuple!(0, 1, 2)) {
+            printf("\n|");
+            j = 1 << n;
+            for (i = n; i > 0; i--) {
+                j >>= 1;
+                if (j & p[k])
+                    printf(" %d", i);
+            }
+        }
+        printf("\n");
+    }
 }</lang>
+Output:
+<pre>| 3 2 1
+|
+|
+| 3 2
+|
+| 1
+| 3
+| 2
+| 1
+| 3
+| 2 1
+|
+|
+| 2 1
+| 3
+| 1
+| 2
+| 3
+| 1
+|
+| 3 2
+|
+|
+| 3 2 1</pre>
 =={{header|Dc}}==