/*******************************************************************/
/*                                                                 */
/* This program is free to copy !                                  */
/*                                                                 */
/* Program: hanoi2.c                                               */
/*                                                                 */
/* Description:                                                    */
/*                                                                 */
/* This program solves but not print the "Tower of Hanoi"          */
/* problem.                                                        */
/*                                                                 */
/* 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                                       */
/*                                                                 */
/* Benchmark:                                                      */
/*                                                                 */
/* n=25                                                            */
/*                                                                 */
/* Computer:             CPU-time (s):           Compilation:      */
/*                                                                 */
/* Pentium 180 MHz           8.80                   gcc -O3        */
/*                                                                 */
/*******************************************************************/

/********************************************************************************/
/*                                                                              */
/* 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 nr[4];

int peg[4][201];

int nn;


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

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

} /* 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\n",argv[0]);
      exit(0);
   } /* if */

   n=atoi(argv[1]);

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

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

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

   nn=0;

   time1=clock();

   smd(fpeg,vpeg,tpeg,n);

   timediff=clock()-time1;


   printf("%12d\n\n",nn);

   printf("%12.2f\n",(double)(timediff)/timetic);

 
} /* End */