Rosetta Code

Towers of Hanoi: Difference between revisions

Page Discussion

Towers of Hanoi (view source)

Revision as of 14:23, 15 June 2011

669 bytes added ,  13 years ago
Fixed second D version
(Simpler first D version)
(Fixed second D version)
Line 229:
 
===Iterative===
refFast 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 const n = (args.length > 1) ? to!(int)(args[1]) : 3 ;
Hanoi(n, "L","M" size_t i,"R") j;
size_t[3] p;
▲ int nn p[0] = (1 << n) - 1;
printf("\n|");
▲ for (xi = 1 n; x <i nn> 0; x++i--){
printf(" %d", i);
printf("\n|\n|\n");
foreach (size_t x; 1 .. (1 << n)) {
i = x & (x - 1);
▲ i = x & x - 1 const ;size_t fr = (i + i / 3) & 3 ;
i = (x | (x - 1)) + 1;
▲ i = (x | xconst - 1) + 1 ;size_t to = (i + i / 3) & 3 ;
▲ for (i = x, j = 1; !(i&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}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/14243"