#include <stdio.h>
#include <stdlib.h>
#define tank_x 5
#define tank_y 6
#define tank_z 10
#define maxlength 100
#define goal 8
#define empty 0
typedef struct {
int x;
int y;
int z;
}State;
void makenullState (State *state){
state->x = 0;
state->y = 0;
state->z = 0;
}
void printState (State state){
printf("X:%d \t Y:%d \t Z: %d", state.x, state.y, state.z);
}
const char* action[] = {"1st state", "pour water X to Y", "pour water X to Z",
"pour water Y to X","pour water Y to Z", "pour water Z to X","pour water Z to Y"};
int goalcheck (State state){
return (state.x == goal || state.y == goal || state.z == goal);
}
int min (int a, int b){
return a < b ? a:b;
}
int max (int a, int b){
return a > b ? a:b;
}
int pourWaterX_Z (State cur_state, State *result){
if(cur_state.x > 0 && cur_state.z != tank_z){
result->z = min((cur_state.x + cur_state.z),tank_z);
result->x = max((cur_state.x - (tank_z - cur_state.z)),0);
result->y = cur_state.y;
return 1;
}
return 0;
}
int pourWaterX_Y (State cur_state, State *result){
if(cur_state.x > 0 && cur_state.y != tank_y){
result->y = min((cur_state.y + cur_state.x),tank_y);
result->x = max((cur_state.x - (tank_y - cur_state.y)),0);
result->z = cur_state.z;
return 1;
}
return 0;
}
int pourWaterY_Z (State cur_state, State *result){
if(cur_state.y > 0 && cur_state.z != tank_z){
result->z = min ((cur_state.y + cur_state.z),tank_z);
result->y = max((cur_state.y - (tank_z - cur_state.z)),0);
result->x = cur_state.x;
return 1;
}
return 0;
}
int pourWaterY_X (State cur_state, State *result){
if(cur_state.y > 0 && cur_state.x != tank_x){
result->x = min((cur_state.x + cur_state.y),tank_x);
result->y = max ((cur_state.y - (tank_x - cur_state.x)),0);
result->z = cur_state.z;
return 1;
}
return 0;
}
int pourWaterZ_X (State cur_state, State *result){
if(cur_state.z > 0 && cur_state.x != tank_x){
result->x = min ((cur_state.x + cur_state.z), tank_x);
result->z = max((cur_state.z - (tank_x - cur_state.x)),0);
result->y = cur_state.y;
return 1;
}
return 0;
}
int pourWaterZ_Y (State cur_state, State *result){
if(cur_state.z > 0 && cur_state.y != tank_y){
result->y = min ((cur_state.z + cur_state.y),tank_y);
result->z = max((cur_state.z - (tank_y - cur_state.y)),0);
result->x = cur_state.x;
return 1;
}
return 0;
}
int call_op (State cur_state, State *result, int opt){
switch(opt){
case 1: return pourWaterX_Y(cur_state, result);
case 2: return pourWaterX_Z(cur_state, result);
case 3: return pourWaterY_X (cur_state, result);
case 4: return pourWaterY_Z (cur_state, result);
case 5: return pourWaterZ_X (cur_state, result);
case 6: return pourWaterZ_Y (cur_state, result);
default: printf("Error");
}
}
typedef struct Node {
State state;
struct Node* Parent;
int no_function;
}Node;
typedef struct {
Node* Elements [maxlength];
int top_idx;
}Stack;
void makenullStack (Stack *stack){
stack->top_idx = maxlength;
}
int empty_stack (Stack stack){
return stack.top_idx == maxlength;
}
int full_stack (Stack s){
return s.top_idx == 0;
}
Node* top (Stack stack){
if(!empty_stack(stack))
return stack.Elements[stack.top_idx];
return NULL;
}
void push (Node* x, Stack *stack){
if(full_stack(*stack))
printf("Error! Stack full");
else{
stack->top_idx -= 1;
stack->Elements[stack->top_idx] = x;
}
}
void pop (Stack *stack){
if(!empty_stack(*stack))
stack->top_idx += 1;
else printf("Error! Stack rong");
}
int compareState (State s1, State s2){
return (s1.x == s2.x && s1.y == s2.y);
}
int find_state (State s, Stack openStack){
while (!empty_stack(openStack)){
if(compareState(top(openStack)->state,s))
return 1;
pop(&openStack);
}
return 0;
}
//Node* DFS (State state){
// Stack open ;
// Stack close;
// makenullStack(&open);
// makenullStack(&close);
//
// Node* root = (Node*) malloc (sizeof(Node));
// root->state = state;
// root->Parent = NULL;
// root->no_function = 0;
// push(root, &open);
//
// while(!empty_stack(open)){
// Node* node = top (open);
// pop(&open);
// push(node, &close);
//
// if(goalcheck(node->state))
// return node;
// int opt;
// for(opt = 1; opt <= 6; opt++){
// State newstate;
// makenullState(&newstate);
// if(call_op(node->state, &newstate, opt)){
// if(find_state(newstate, close) || find_state(newstate, open))
// continue;
//
// Node* newNode = (Node*) malloc (sizeof(Node));
// newNode->state = newstate;
// newNode->Parent = node;
// newNode->no_function = opt;
// push(newNode, &open);
// }
// }
// }
// return NULL;
//}
Node* DFS (State s){
Stack open;
Stack close;
makenullStack(&open);
makenullStack(&close);
Node* root = (Node*) malloc (sizeof(Node));
root->state = s;
root->Parent = NULL;
root->no_function = 0;
push(root, &open);
while(!empty_stack(open)){
Node* node = top(open);
pop(&open);
push(node, &close);
if(goalcheck(node->state))
return node;
int opt;
for(opt = 1; opt <= 6; opt++){
State newState;
makenullState(&newState);
if(call_op(node->state,&newState,opt)){
printf("c");
if(find_state(newState, open) || find_state(newState, close));
continue;
Node* newNode = (Node*) malloc (sizeof(Node));
newNode->state = newState;
newNode->Parent = node;
newNode->no_function = opt;
push(newNode, &open);
}
}
}
return NULL;
}
//void print_Ways (Node* node){
// Stack stackPrint;
// makenullStack(&stackPrint);
//
// while(node->Parent != NULL){
// push(node, &stackPrint);
// node = node->Parent;
// }
// push(node , &stackPrint);
// int no_action = 0;
// while (!empty_stack(stackPrint)){
// printf("\nAction %d: %s \n", no_action, action[top(stackPrint)->no_function]);
// printState(top(stackPrint)->state);
// pop(&stackPrint);
// no_action++;
// }
//}
void print_Ways (Node* node){
Stack stackPrint;
makenullStack(&stackPrint);
while(node->Parent != NULL){
push(node, &stackPrint);
node = node->Parent;
}
push(node , &stackPrint);
int no_action = 0;
while (!empty_stack(stackPrint)){
printf("\nAction %d: %s \n", no_action, action[top(stackPrint)->no_function]);
printState(top(stackPrint)->state);
pop(&stackPrint);
no_action++;
}
}
int main (){
State cur_state = {0,0,10};
Node* p = DFS(cur_state);
printState(p->state);
//print_Ways(p);
return 0;
}