Answers/Solutions to Exercises in Chapter 5, Exercise 12
E12: Repeat the exercise 11 for the Hanoi Towers puzzle program listed in the Appendix A.
S12: Below is the modified program and its output for a 4 disks run. Note, that we "store" the tracing messages in a linked list and display them only at the end of the program, so it does not get mixed up with the display of the moving disks.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define HEIGHT 10
typedef int PEG[HEIGHT];
PEG A, B, C;
void set_pegs(int nofdisks);
void ht(int nofdisks,PEG origin,PEG help,PEG destination);
int remove_top(PEG peg);
void put_top(PEG peg,int disk);
void move(PEG from,PEG to);
void show_pegs(void);
char *make_disk(int disk);
#define TRACE(a) trace_enter(#a)
#define RETURN(a,b) return(trace_exit(#a,b))
#define RETURN2(a,b) return((char*) trace_exit(#a,(int) b))
#define RETURN1(a) {trace_exit(#a,1); return;}
#define EXIT(a,b) exit(trace_exit(#a,b))
void trace_enter(char*);
int trace_exit(char*,int);
char indent[300]="";
int indi=0;
struct Trace_struct {
char* message;
struct Trace_struct* next;
};
typedef struct Trace_struct Trace;
Trace *trace=NULL;
Trace *last=NULL;
char line[300];
/* function main -------------------------------------------- */
int main(int argc,char* argv[])
{
TRACE(main);
if (argc != 2) {
printf("usage - call <nofdisks>\n");
EXIT(main,1);
}
if (sscanf(argv[1],"%d",&nofdisks) != 1) {
printf("number of disks must be 2 - %d\n",HEIGHT);
EXIT(main,0);
}
if (nofdisks < 2 || nofdisks > HEIGHT) {
printf("number of disks must be 2 - %d\n",HEIGHT);
EXIT(main,0);
}
set_pegs(nofdisks);
show_pegs();
ht(nofdisks,A,B,C);
printf("done\n");
trace_exit("main",0);
for(last=trace; last!=NULL; last=last->next)
printf("%s",last->message);
return(0);
}/*end main*/
/* function set_pegs ---------------------------------- */
void set_pegs(int nofdisks)
{
TRACE(set_pegs);
int i;
if (nofdisks > HEIGHT) {
printf("too many disks (%d) for the height of the pegs (%d)\n",
nofdisks,HEIGHT);
EXIT(set_pegs,1);
}
for(i = 0; i < HEIGHT; i++)
A[i] = B[i] = C[i] = -1;
for(i = 0; i < nofdisks; i++)
A[i] = nofdisks-1-i;
RETURN1(set_pegs)
}/* end set_pegs */
/* function ht ------------------------------------------ */
void ht(int nofdisks,PEG origin,PEG help,PEG destination)
{
TRACE(ht);
if (nofdisks == 2) { // base case
move(origin,help);
show_pegs();
move(origin,destination);
show_pegs();
move(help,destination);
show_pegs();
RETURN1(ht)
}
// recursion
ht(nofdisks-1,origin,destination,help);
move(origin,destination);
show_pegs();
ht(nofdisks-1,help,origin,destination);
RETURN1(ht)
}/* end ht */
/* function remove_top ------------------------------------ */
int remove_top(PEG peg)
{
TRACE(remove_top);
int i, res;
for(i = 0; i < HEIGHT; i++)
if (peg[i] == -1) break;
if (i == 0) {
printf("peg is empty\n");
EXIT(remove_top,0);
}
i--;
res = peg[i];
peg[i] = -1;
RETURN(remove_top,res);
}/* end remove_top */
/* function put_top --------------------------------------- */
void put_top(PEG peg,int disk)
{
TRACE(put_top);
int i;
for(i = 0; i < HEIGHT; i++)
if (peg[i] == -1) break;
if (i == HEIGHT) {
printf("peg is full\n");
EXIT(put_top,1);
}
peg[i] = disk;
RETURN1(put_top)
}/* end put_top */
/* function move ---------------------------------------------- */
void move(PEG from,PEG to)
{
TRACE(move);
int disk;
disk = remove_top(from);
put_top(to,disk);
RETURN1(move)
}/* end move */
/* function show_pegs ----------------------------------------- */
void show_pegs(void)
{
TRACE(show_pegs);
int i;
for(i = HEIGHT-1; i >= 0; i--) {
printf("%s",make_disk(A[i]));
printf(" %s",make_disk(B[i]));
printf(" %s\n",make_disk(C[i]));
}
printf("%s",make_disk(-2));
printf(" %s",make_disk(-2));
printf(" %s\n",make_disk(-2));
fflush(stdout);
getchar();
fflush(stdin);
RETURN1(show_pegs)
}/* end show_pegs */
/* function make_disk -------------------------------------- */
char *make_disk(int disk)
{
TRACE(make_disk);
static char buf[26];
int i, j;
if (disk == -2) /* make base */
strcpy(buf,"HHHHHHHHHHHHHHHHHHHHHHHHH");
else if (disk == -1) /* make peg */
strcpy(buf," | ");
else{
for(j = 0; j < 1+HEIGHT-disk; buf[j++] = ' ');
for(i = 0; i <= disk; buf[j++] = '=',i++);
buf[j++] = '|';
for(i = 0; i <= disk; buf[j++] = '=',i++);
for(i = 0; i < 1+HEIGHT-disk; buf[j++] = ' ',i++);
buf[j] = '\0';
}
RETURN2(make_disk,&buf[0]);
}/* end make_disk */
/* function trace_enter ------------------------------------------------ */
void trace_enter(char* fce)
{
Trace* p;
indent[indi++]=' ';
indent[indi]='\0';
sprintf(line,"%sentering %s\n",indent,fce);
p=(Trace*)malloc(sizeof(Trace));
p->message=(char*)malloc(strlen(line)+1);
strcpy(p->message,line);
p->next=NULL;
if (trace==NULL) {
trace=last=p;
return;
}else{
last->next=p;
last=p;
return;
}
}/* end trace_enter */
/* function trace_exit ------------------------------------------------ */
int trace_exit(char* fce,int ret)
{
Trace* p;
sprintf(line,"%sexiting %s\n",indent,fce);
p=(Trace*)malloc(sizeof(Trace));
p->message=(char*)malloc(strlen(line)+1);
strcpy(p->message,line);
p->next=NULL;
if (trace==NULL) {
trace=last=p;
}else{
last->next=p;
last=p;
}
indent[--indi]='\0';
return(ret);
}/* end trace_enter */
| | |
| | |
| | |
| | |
| | |
| | |
=|= | |
==|== | |
===|=== | |
====|==== | |
HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH
| | |
| | |
| | |
| | |
| | |
| | |
| | |
==|== | |
===|=== | |
====|==== =|= |
HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
===|=== | |
====|==== =|= ==|==
HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
===|=== | =|=
====|==== | ==|==
HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | =|=
====|==== ===|=== ==|==
HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
=|= | |
====|==== ===|=== ==|==
HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
=|= ==|== |
====|==== ===|=== |
HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| =|= |
| ==|== |
====|==== ===|=== |
HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| =|= |
| ==|== |
| ===|=== ====|====
HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| ==|== =|=
| ===|=== ====|====
HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | =|=
==|== ===|=== ====|====
HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
=|= | |
==|== ===|=== ====|====
HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
=|= | ===|===
==|== | ====|====
HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | ===|===
==|== =|= ====|====
HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH
| | |
| | |
| | |
| | |
| | |
| | |
| | |
| | ==|==
| | ===|===
| =|= ====|====
HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH
| | |
| | |
| | |
| | |
| | |
| | |
| | =|=
| | ==|==
| | ===|===
| | ====|====
HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH HHHHHHHHHHHHHHHHHHHHHHHHH
done
entering main
entering set_pegs
exiting set_pegs
entering show_pegs
exiting show_pegs
entering ht
entering ht
entering ht
entering move
entering remove_top
exiting remove_top
entering put_top
exiting put_top
exiting move
entering show_pegs
exiting show_pegs
entering move
entering remove_top
exiting remove_top
entering put_top
exiting put_top
exiting move
entering show_pegs
exiting show_pegs
entering move
entering remove_top
exiting remove_top
entering put_top
exiting put_top
exiting move
entering show_pegs
exiting show_pegs
exiting ht
entering move
entering remove_top
exiting remove_top
entering put_top
exiting put_top
exiting move
entering show_pegs
exiting show_pegs
entering ht
entering move
entering remove_top
exiting remove_top
entering put_top
exiting put_top
exiting move
entering show_pegs
exiting show_pegs
entering move
entering remove_top
exiting remove_top
entering put_top
exiting put_top
exiting move
entering show_pegs
exiting show_pegs
entering move
entering remove_top
exiting remove_top
entering put_top
exiting put_top
exiting move
entering show_pegs
exiting show_pegs
exiting ht
exiting ht
entering move
entering remove_top
exiting remove_top
entering put_top
exiting put_top
exiting move
entering show_pegs
exiting show_pegs
entering ht
entering ht
entering move
entering remove_top
exiting remove_top
entering put_top
exiting put_top
exiting move
entering show_pegs
exiting show_pegs
entering move
entering remove_top
exiting remove_top
entering put_top
exiting put_top
exiting move
entering show_pegs
exiting show_pegs
entering move
entering remove_top
exiting remove_top
entering put_top
exiting put_top
exiting move
entering show_pegs
exiting show_pegs
exiting ht
entering move
entering remove_top
exiting remove_top
entering put_top
exiting put_top
exiting move
entering show_pegs
exiting show_pegs
entering ht
entering move
entering remove_top
exiting remove_top
entering put_top
exiting put_top
exiting move
entering show_pegs
exiting show_pegs
entering move
entering remove_top
exiting remove_top
entering put_top
exiting put_top
exiting move
entering show_pegs
exiting show_pegs
entering move
entering remove_top
exiting remove_top
entering put_top
exiting put_top
exiting move
entering show_pegs
exiting show_pegs
exiting ht
exiting ht
exiting ht
exiting main
Back to Answers/Solutions Index Back to Answers/Solutions for Chapter 5 Index