Yesterday i was out of home so could not give this a try. Here is my piece of code for the given problem.
#include "stdio.h"
#define TRUE 1
#define FALSE 0
/*
* Defining a structure and data type for representing each tower
* tower is pointer to elements of tower
* size represent number of elements in tower
*/
typedef struct {
int *tower;
int size;
} tower_t;
/* Display the move */
void display_move(tower_t* tt1, tower_t* tt2, tower_t* t1, tower_t* t2, tower_t* t3) {
int from = 0;
int to = 0;
if(tt1->tower == t1->tower) {
from = 1;
} else if(tt1->tower == t2->tower) {
from = 2;
} else {
from = 3;
}
if(tt2->tower == t1->tower) {
to = 1;
} else if(tt2->tower == t2->tower) {
to = 2;
} else {
to = 3;
}
printf("Move from %d to %d\n", from, to);
}
/* Display current state of all towers */
void display_towers(tower_t t1, tower_t t2, tower_t t3, int tower_size) {
int i = 0;
printf("Towers:\n");
for(i = (tower_size - 1); i >= 0; i--) {
printf("%d %d %d\n", t1.tower[i], t2.tower[i], t3.tower[i]);
}
printf("\n");
}
/* Moves elemet fro tt1 to tt2 using tt3 as buffer */
void move(tower_t* tt1, tower_t* tt2, tower_t* tt3, tower_t* t1, tower_t* t2, tower_t* t3, int tower_size) {
int move_to_tt2 = FALSE;
int move_count = 0;
int i = 0;
//determining number of elements that can be moved from tt1
for(i = (tt1->size - 1); i >= 0; i--) {
if(((tt2->size == 0) || (tt2->tower[tt2->size - 1] > tt1->tower[i]))
&& ((tt3->size == 0) || (tt3->tower[tt3->size - 1] > tt1->tower[i]))) {
move_count++;
} else {
break;
}
}
//if number of elements is odd, move first element to tt2
//else move first element to tt3
if(move_count % 2) {
move_to_tt2 = TRUE;
} else {
move_to_tt2 = FALSE;
}
//loop for moving each element till count of moveable element is not 0 in tt1
while(move_count != 0) {
if(move_to_tt2) {
//display the current move
display_move(tt1, tt2, t1, t2, t3);
//move element from tt1 to tt2
tt2->tower[tt2->size++] = tt1->tower[--tt1->size];
tt1->tower[tt1->size] = 0;
//toggle flag to move next element to tt3
move_to_tt2 = FALSE;
//display current state of all towers after move
display_towers(*t1, *t2, *t3, tower_size);
//move pegs from tower tt3 to tt2
move(tt3, tt2, tt1, t1, t2, t3, tower_size);
} else {
//display the current move
display_move(tt1, tt3, t1, t2, t3);
//move element from tt1 to tt3
tt3->tower[tt3->size++] = tt1->tower[--tt1->size];
tt1->tower[tt1->size] = 0;
//toggle flag to move next element to tt2
move_to_tt2 = TRUE;
//display current state of all towers after move
display_towers(*t1, *t2, *t3, tower_size);
//move pegs from tower tt2 to tt3
move(tt2, tt3, tt1, t1, t2, t3, tower_size);
}
//one more element moved, decrementing count
move_count--;
}
}
int main() {
tower_t t1 = {0};
tower_t t2 = {0};
tower_t t3 = {0};
int tower_size = 0;
int i = 0;
//taking tower size as input
scanf("%d", &tower_size);
//validating tower size
if(tower_size <= 0) {
printf("Invalid tower size\n");
return 0;
}
//allocating memory for each tower
t1.tower = (int*)malloc(sizeof(int) * tower_size);
t2.tower = (int*)malloc(sizeof(int) * tower_size);
t3.tower = (int*)malloc(sizeof(int) * tower_size);
//initializing elements of t1 with the peg it contains
//initializing elements of t2 and t3 with 0 as they are initially empty
for(i = 0; i < tower_size; i++) {
t1.tower[i] = tower_size - i;
t2.tower[i] = t3.tower[i] = 0;
}
//initializing size of t1 with current tower size as it contain all pegs
//initializing size t2 and t3 with 0 as they are initially empty
t1.size = tower_size;
t2.size = t3.size = 0;
//display the initial state of all towers
display_towers(t1, t2, t3, tower_size);
//moving complete tower 1 to tower 2 using tower 3 as buffer
move(&t1, &t2, &t3, &t1, &t2, &t3, tower_size);
//free the memory previously allocated for each tower
free(t1.tower);
free(t2.tower);
free(t3.tower);
return 0;
}
Compile the file with above code and run as:
a.exe < input.txt > output.txt [on windows]
a.out < input.txt > output.txt [on linux]
Here,
a.exe or a.out are the executables generated after compilation
input.txt is the file containing input, e.g., for tower of size (or height) 4, input.txt will be:
4
output.txt is the output file containing result, for given example output.txt will contain
Towers:
1 0 0
2 0 0
3 0 0
4 0 0
Move from 1 to 3
Towers:
0 0 0
2 0 0
3 0 0
4 0 1
Move from 1 to 2
Towers:
0 0 0
0 0 0
3 0 0
4 2 1
Move from 3 to 2
Towers:
0 0 0
0 0 0
3 1 0
4 2 0
Move from 1 to 3
Towers:
0 0 0
0 0 0
0 1 0
4 2 3
Move from 2 to 1
Towers:
0 0 0
0 0 0
1 0 0
4 2 3
Move from 2 to 3
Towers:
0 0 0
0 0 0
1 0 2
4 0 3
Move from 1 to 3
Towers:
0 0 0
0 0 1
0 0 2
4 0 3
Move from 1 to 2
Towers:
0 0 0
0 0 1
0 0 2
0 4 3
Move from 3 to 2
Towers:
0 0 0
0 0 0
0 1 2
0 4 3
Move from 3 to 1
Towers:
0 0 0
0 0 0
0 1 0
2 4 3
Move from 2 to 1
Towers:
0 0 0
0 0 0
1 0 0
2 4 3
Move from 3 to 2
Towers:
0 0 0
0 0 0
1 3 0
2 4 0
Move from 1 to 3
Towers:
0 0 0
0 0 0
0 3 0
2 4 1
Move from 1 to 2
Towers:
0 0 0
0 2 0
0 3 0
0 4 1
Move from 3 to 2
Towers:
0 1 0
0 2 0
0 3 0
0 4 0
Let me know if any item need clarification.
P.S.:
1. If you want to see only move statement and don't want to see towers state after each move, remove "display_towers" function call from code.
2. If you want to see only towers state after every move and don't want to move statement, remove "display_move" function call from code.
-Pradeep