Hanoi towers recursive and iterative solution

hanoi-iter.py

#!/usr/bin/env python3
# vim: ts=4 expandtab
import sys

class Peg:
    """ Stack representing one Hanoi peg. """
    def __init__(self, n=0):
        self.stack = []
        self.stack.extend(range(1,n+1))

    def count(self):
        return len(self.stack)

    def empty(self):
        return self.count()==0

    def top(self):
        return self.stack[-1] if not self.empty() else 0

    def pop(self):
        return self.stack.pop() if not self.empty() else 0

    def push(self, disc):
        if disc < self.top():
            raise Exception("Game rules violated")
        self.stack.append(disc)

    def __repr__(self):
        return str(self.stack)

class Pegs():
    """ Class representing three Hanoi pegs. """

    def __init__(self, n, src=1, dst=3):
        self.n = n
        self.dst = dst
        self.pegs = [None] #First non-peg to make indexing start from 1
        for i in range(3):
            self.pegs.append(Peg(n if i==src-1 else 0))

    def simplemove(self, src, dst):
        disc = self.pegs[src].pop()
        print("from {} to {}.".format(src, dst))
        self.pegs[dst].push(disc)
        print(self)

    def legalmove(self, first, second):
        """Performs the only legal move between two pegs."""
        d1 = self.pegs[first].top()
        d2 = self.pegs[second].top()
        if d1 > d2:
            self.simplemove(first, second)
        else:
            self.simplemove(second, first)

    def finished(self):
        return self.pegs[self.dst].count() == self.n

    def __repr__(self):
        return str(self.pegs[1:])


def hanoj(n, src=1, dst=3, tmp=2):
    if n % 2 == 0: # Even disc flow
        flow = ((src, tmp), (src, dst), (dst, tmp))
    else: #Odd disc flow
        flow = ((src, dst), (src, tmp), (dst, tmp))

    p = Pegs(n, src)
    step = 0
    while not p.finished():
        print("Step {:03}: ".format(step+1), end="")
        p.legalmove(*flow[step % 3])
        step += 1


if __name__ == "__main__":
    hanoj(int(sys.argv[1]))

hanoi-rec.c

#include <stdio.h>
#include <stdlib.h>
int step = 0;

void hanoj(int n, int src, int dst, int tmp) {
	if (n>0) {
		hanoj(n-1, src, tmp, dst);
		printf("Step %3d: from %d to %d.\n", ++step, src, dst);
		hanoj(n-1, tmp, dst, src);
	}
}

int main(int argc, char *argv[]) {
	if (argc == 2) {
		hanoj(atoi(argv[1]), 1, 3, 2);
	}
	return 0;
}

hanoi-rec.py

#!/usr/bin/env python3
# vim: ts=4 expandtab
import sys
step = 0

def hanoj(n, src=1, dst=3, tmp=2):
    global step
    if n>0:
        hanoj(n-1, src, tmp, dst)
        step += 1
        print("Step {:03}: from {} to {}.".format(step, src, dst))
        hanoj(n-1, tmp, dst, src)


if __name__ == "__main__":
    hanoj(int(sys.argv[1]))

honoi-bin.c

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void hanoj(int n) {
	int steps, step, from, to;
	steps = pow(2,n);
	for (step=1; step < steps; step++) {
		from = (step & (step-1)) % 3;
		to = (1 + (step | (step-1))) % 3;
		printf("Step %3d: from %d to %d.\n", step, from+1, to+1);
	}
}

int main(int argc, char *argv[]) {
	if (argc == 2) {
		hanoj(atoi(argv[1]));
	}
	return 0;
}