/*******************************************************************/
/*                                                                 */
/* This program is free to copy !                                  */
/*                                                                 */
/* Program: hanoi.c                                                */
/*                                                                 */
/* Description:                                                    */
/*                                                                 */
/* This program solves and print the "Tower of Hanoi" problem      */
/* for n <= 9.                                                     */
/*                                                                 */
/* Algrorithm from the swedish book "Programmeringsmetodik med     */
/* abstrakta datatyper" by Goeran Eriksson and Jan Karlsson,       */
/* Lund 1986.                                                      */
/*                                                                 */
/*                                                                 */
/* Program by: Stefan Spaennare, Lund, Sweden                      */
/*                                                                 */
/* E-mail:      stefan@spaennare.se                                */
/*                                                                 */
/* Latest update: 2003-02-19                                       */
/*                                                                 */
/*******************************************************************/

/********************************************************************************/
/*                                                                              */
/* Notice                                                                       */
/* ======                                                                       */
/*                                                                              */
/* I make no warranties that this program is (1) free of errors, (2) consistent */
/* with any standard merchantability, or (3) meeting the requirements of a      */
/* particular application. This software shall not, partly or as a whole,       */
/* participate in a process, whose outcome can result in injury to a person or  */
/* loss of property. It is solely designed for analytical work. Permission to   */
/* use, copy and distribute is hereby granted without fee, providing that the   */
/* header above including this notice appears in all copies.                    */
/*                                                                              */
/*                                                            Stefan Spaennare  */
/*                                                                              */
/********************************************************************************/


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

double timetic=(double)(CLOCKS_PER_SEC);

int n0;

int nr[4];

int peg[4][201];

char ss[101];

void printpeg()
{
   int i,j,p,pp,pp2;

   for (i=n0; i>=1; i--) {
       for (j=0; j<=79; j++) {
          ss[j]=' ';
       } /* for j */

       p=peg[1][i];

       if (p == 0) {
          pp=0;
          pp2=0;
       }
       else {
          pp=n0-p+1;
          pp2=2*pp-1;
       } /* if */ 

       for (j=1; j<=pp2; j++) {
          ss[j-pp+20]='#';
       } /* for j */

       p=peg[2][i];

       if (p == 0) {
          pp=0;
          pp2=0;
       }
       else {
          pp=n0-p+1;
          pp2=2*pp-1;
       } /* if */ 

       for (j=1; j<=pp2; j++) {
          ss[j-pp+40]='#';
       } /* for j */

       p=peg[3][i];

       if (p == 0) {
          pp=0;
          pp2=0;
       }
       else {
          pp=n0-p+1;
          pp2=2*pp-1;
       } /* if */ 

       for (j=1; j<=pp2; j++) {
          ss[j-pp+60]='#';
       } /* for j */


       ss[80]='\0';

       printf("%s\n",ss);

    } /* for i */

    for (j=0; j<=79; j++) {
       ss[j]='=';
    } /* for j */

    ss[80]='\0';

    printf("%s\n\n",ss);


} /* printpeg */




void smod(fpeg,tpeg)
int fpeg,tpeg;
{

   nr[tpeg]++;
   peg[tpeg][nr[tpeg]]=peg[fpeg][nr[fpeg]];
   peg[fpeg][nr[fpeg]]=0;
   nr[fpeg]--;

   printpeg();

} /* smod */


void smd(fpeg,vpeg,tpeg,n)
int fpeg,vpeg,tpeg;
int n;
{
   if (n == 1) {
      smod(fpeg,tpeg);
   }
   else {
      smd(fpeg,tpeg,vpeg,n-1);
      smod(fpeg,tpeg);
      smd(vpeg,fpeg,tpeg,n-1);
   } /* if */
} /* smd */


int main(argc,argv) 
int argc;
char *argv[];

{
  
   int i,n; 
   int fpeg,vpeg,tpeg;

   clock_t time1,timediff;

   if (argc != 2) {
      printf("Usage: %s ni (ni <= 9)\n",argv[0]);
      exit(0);
   } /* if */

   n=atoi(argv[1]);

   if (n > 9) {
      n=9;
   } /* if */

   n0=n;

   fpeg=1;
   vpeg=2;
   tpeg=3;

   for (i=1; i<=n; i++) {
      peg[fpeg][i]=i;
      peg[vpeg][i]=0;
      peg[tpeg][i]=0;
   } /* for i */ 

   nr[fpeg]=n;
   nr[vpeg]=0;
   nr[tpeg]=0;

   printpeg();

   time1=clock();

   smd(fpeg,vpeg,tpeg,n);

   timediff=clock()-time1;


 
} /* End */