1. Stephen Tanner
  2. romensio_c

Commits

Stephen Tanner  committed 0a25a4f

Finished

  • Participants
  • Parent commits 5fa9e43
  • Branches default

Comments (0)

Files changed (4)

File Debug/romensio_c

Binary file modified.

File Debug/src/main.o

Binary file modified.

File input.txt

View file
 4
-1 2 3 4
-5 6 7 8 
-9 1 2 3
-4 5 6 7
+1 3 1 2
+4 5 8 2
+3 2 1 4
+1 9 6 5

File src/main.c

View file
 //function prototypes
 bool oldNeighbor(Node I[], Node n);
 bool hasNeighbor(Node P[], Node n);
-
-void print(int **A, int n);
+bool skip(Node fail[], Node n, int f_count);
+void print(int **A, int n, int moves);
 void removePosition(int **A, int n, int i, int j);
 void solve(int **A, int n);
 void getPath(int **A, Node Q[], int *q_count, int n, Node I[], int i_count);
+bool inQ(Node Q[], Node n);
+void sortPath(Node Q[], int q_count);
+void clearFail(Node fail[], int f_count);
 
 int main (int argc, char *argv[]) {
 
 	int **A;
 
 
+
 	if (argc == 2 ) {
 		fp = fopen(argv[1], "r");
 		if (fp == NULL) {
 			}
 		}
 
-		print(*&A, n);
+		//print(*&A, n);
 
 		//removePosition(*&A, n, 3, 3);
 
 		solve(*&A, n);
 
-		print(*&A, n);
+
+
 
 		//Game over
 		return 0;
 	}
 }
 
-void print (int **A, int n) {
+void print (int **A, int n, int moves) {
 	//Print out the matrix
 	int i;
 	int j;
+	int left = 0;
 	for (i = 0; i < n; i++) {
 		for (j = 0; j < n; j++) {
 
 			}
 			else {
 				printf("%d ", A[i][j]);
+				left++;
 			}
 
 		}
 		printf("\n");
 	}
-	for (i = 0; i < (n * 2) - 1; i++) {
-		printf("-");
-	}
-	printf("\n");
+
+	printf("Numbers left: %d\n", left);
+	printf("Number of moves: %d\n", moves);
 }
 
 void removePosition(int **A, int n, int i, int j) {
 	Node L;
 	Node Q[10];
 	Node I[100];
-
-	int q_count = 0;
-	int i_count = 0;
+	Node *fail = (Node *) malloc (sizeof(Node) * n * n);
+	int f_count = 0;
+	int moves = 0;
 
 	int i;
 	int j;
 	clear.j = 0;
 	clear.value = 0;
 
-	for (i = 0; i < 10; i++) {
-		Q[i] = clear;
-	}
-	for (i = 0; i < 100; i++) {
-		I[i] = clear;
+
+	int a;
+	for (a = 0; a < n*n; a++) {
+		L.i = 0;
+		L.j = 0;
+		L.value = A[0][0];
+
+		for (i = 0; i < n; i++) {
+			for (j = 0; j < n; j++) {
+				Node t;
+				t.i = i;
+				t.j = j;
+				t.value = A[i][j];
+				if (A[i][j] > L.value && !skip(fail, t, f_count)) {
+					L.i = i;
+					L.j = j;
+					L.value = A[i][j];
+				}
+			}
+		}
+		if (L.value == 0) {
+			break;
+		}
+
+		for (i = 0; i < 10; i++) {
+			Q[i] = clear;
+		}
+		for (i = 0; i < 100; i++) {
+			I[i] = clear;
+		}
+		int q_count = 0;
+		int i_count = 0;
+		Q[0] = L;
+		q_count++;
+		getPath(*&A, Q, &q_count, n, I, i_count);
+		//So now Q Should either have a path or be null
+		sortPath(Q, q_count);
+		if (q_count > 1) {
+			for (i = 0; i < q_count; i++) {
+				removePosition(*&A, n, Q[i].i, Q[i].j);
+				clearFail(fail, f_count);
+			}
+			moves++;
+		}
+		else {
+
+			fail[f_count] = L;
+			f_count++;
+		}
+		//print(*&A, n, moves);
+			//Now We need to find a new L and start the recusive search again
+
 	}
 
-
-	L.i = 0;
-	L.j = 0;
-	L.value = A[0][0];
-
-	for (i = 0; i < n; i++) {
-		for (j = 0; j < n; j++) {
-			if (A[i][j] > L.value) {
-				L.i = i;
-				L.j = j;
-				L.value = A[i][j];
-			}
-		}
-	}
-	Q[0] = L;
-	q_count++;
-
-	//getPath(*&A,Q, q_count, n, I, i_count);
-	getPath(*&A, Q, &q_count, n, I, i_count);
-
-	//So now Q Should either have a path or be null
-
-	if (q_count > 0) {
-		for (i = 0; i < 10; i++) {
-			//For all the nodes in Q, we can remove them from the game board
-			removePosition(*&A, n, Q[i].i, Q[i].j);
-			print(*&A, n);
-		}
-	}
-
-	//Now We need to find a new L and start the recusive search again
-
+	print(*&A, n, moves);
 
 }
 
-//void getPath(int **A, Node *Q, int q_count, int n, Node *I, int i_count) {
+void sortPath(Node Q[], int q_count) {
+	int i;
+	Node tmp;
+	for (i = 0; i < q_count; i++) {
+		int j;
+		for (j = i; j < q_count; j++) {
+			if(Q[i].i >= Q[j].i) {
+				tmp = Q[i];
+				Q[i] = Q[j];
+				Q[j] = tmp;
+			}
+		}
+
+	}
+}
+void clearFail(Node fail[], int f_count) {
+
+	int i;
+	Node clear;
+	clear.value = 0;
+	clear.i = 0;
+	clear.j = 0;
+
+	for (i = 0; i < f_count; i++) {
+		fail[i] = clear;
+	}
+}
+
 void getPath(int **A,Node Q[], int *q_count, int n, Node I[], int i_count) {
 
 
 	//base case if q is empty
-
 	if (*q_count == 0) {
 		return;
 	}
 
-
 	int n_count = 0;
 
 	Node P[100];
 			NW.i = Q[i].i - 1;
 			NW.j = Q[i].j - 1;
 			NW.value = A[NW.i][NW.j];
-			if (!hasNeighbor(P, NW) && !oldNeighbor(I, NW)) {
+			if (!hasNeighbor(P, NW) && !oldNeighbor(I, NW) && NW.value && !inQ(Q, NW)) {
 				P[n_count] = NW;
 				n_count++;
 			}
 			N.i = Q[i].i - 1;
 			N.j = Q[i].j;
 			N.value = A[N.i][N.j];
-			if (!hasNeighbor(P, N) && !oldNeighbor(I, N)) {
+			if (!hasNeighbor(P, N) && !oldNeighbor(I, N) && N.value && !inQ(Q, N)) {
 				P[n_count] = N;
 				n_count++;
 			}
 		}
 
+		//S
+		if (Q[i].i + 1 < n) {
+			Node S;
+			S.i = Q[i].i + 1;
+			S.j = Q[i].j;
+			S.value = A[S.i][S.j];
+			if (!hasNeighbor(P, S) && !oldNeighbor(I, S) && S.value && !inQ(Q, S)) {
+				P[n_count] = S;
+				n_count++;
+			}
+		}
+
 		//NE
 		if (Q[i].i - 1 >= 0 && Q[i].j + 1 < n) {
 
 			NE.i = Q[i].i - 1;
 			NE.j = Q[i].j + 1;
 			NE.value = A[NE.i][NE.j];
-			if (!hasNeighbor(P, NE) && !oldNeighbor(I, NE)) {
+			if (!hasNeighbor(P, NE) && !oldNeighbor(I, NE) && NE.value && !inQ(Q, NE)) {
 				P[n_count] = NE;
 				n_count++;
 			}
 			W.i = Q[i].i;
 			W.j = Q[i].j - 1;
 			W.value = A[W.i][W.j];
-			if (!hasNeighbor(P, W) && !oldNeighbor(I, W)) {
+			if (!hasNeighbor(P, W) && !oldNeighbor(I, W) && W.value && !inQ(Q, W)) {
 				P[n_count] = W;
 				n_count++;
 			}
 			E.i = Q[i].i;
 			E.j = Q[i].j + 1;
 			E.value = A[E.i][E.j];
-			if (!hasNeighbor(P, E) && !oldNeighbor(I, E)) {
+			if (!hasNeighbor(P, E) && !oldNeighbor(I, E) && E.value && !inQ(Q, E)) {
 				P[n_count] = E;
 				n_count++;
 			}
 		}
 
 		//SW
-		if (Q[i].i + 1 >= 0 && Q[i].j - 1 >= 0) {
+		if (Q[i].i + 1 < n && Q[i].j - 1 >= 0) {
 
 			Node SW;
 			SW.i = Q[i].i + 1;
 			SW.j = Q[i].j - 1;
 			SW.value = A[SW.i][SW.j];
-			if (!hasNeighbor(P, SW) && !oldNeighbor(I, SW)) {
+			if (!hasNeighbor(P, SW) && !oldNeighbor(I, SW) && SW.value && !inQ(Q, SW)) {
 				P[n_count] = SW;
 				n_count++;
 			}
 			SE.i = Q[i].i + 1;
 			SE.j = Q[i].j + 1;
 			SE.value = A[SE.i][SE.j];
-			if (!hasNeighbor(P, SE) && !oldNeighbor(I, SE)) {
+			if (!hasNeighbor(P, SE) && !oldNeighbor(I, SE) && SE.value && !inQ(Q, SE)) {
 				P[n_count] = SE;
 				n_count++;
 			}
 	}
 	//Now P is populated with all the Neighbors of the Nodes in Q
 
-	Node T = P[0];
+	Node T;
+	T.value = 10;
 
 	//Pick the smallest T
 	for (i = 1; i < n_count; i++) {
-		if (T.value > P[i].value) {
+		if (T.value > P[i].value && P[i].value != 0) {
 			T = P[i];
 		}
 	}
 
+	if (T.value == 10) {
+		return;
+	}
+
 	//get the weight of Q
 	int q_weight = 0;
 	for (i = 0; i < *q_count; i++ ) {
 	}
 
 	//Check the new weight
-	int W = q_weight + T.value;
-	if (W < 10) {
+	int t_weight = q_weight + T.value;
+	if (t_weight < 10) {
 		Q[*q_count] = T;
-		q_count++;
+		*q_count = *q_count + 1;
 		return getPath(A, Q, q_count, n, I, i_count);
 	}
-	else if (W > 10) {
-		q_count--;
+	else if (t_weight > 10) {
+		*q_count = *q_count - 1;
 		Node last = Q[*q_count];
 		I[i_count] = last;
 		i_count++;
 	}
 	else {
 		Q[*q_count] = T;
-		q_count++;
+		*q_count = *q_count + 1;
 		return;
 	}
 
 	return false;
 }
 
+bool inQ(Node Q[], Node n) {
+	int i;
+	for (i = 0; i < 10; i++) {
+		Node c = Q[i];
+		if (c.i == n.i && c.j == n.j && c.value == n.value) {
+			return true;
+		}
+	}
+	return false;
+}
+
+bool skip(Node fail[], Node n, int f_count) {
+	int i;
+	if (!f_count) {
+		return false;
+	}
+	for (i = 0; i < f_count; i++) {
+		if (fail[i].value == n.value && fail[i].i == n.i && fail[i].j == n.j) {
+			return true;
+		}
+	}
+	return false;
+}
+
 //search the sed of old neighbors for exisiting ones.
 bool oldNeighbor(Node I[], Node n) {
 	int i;