Untitled

mail@pastecode.io avatar
unknown
abap
2 years ago
6.7 kB
5
Indexable
#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;
}