Commits

Stephen Tanner committed 5fa9e43

Now can loop through once, find largest, and search all its neighbors

Comments (0)

Files changed (5)

Binary file added.

Binary file added.

-3
-1 2 3
-4 5 6
-7 8 9
+4
+1 2 3 4
+5 6 7 8 
+9 1 2 3
+4 5 6 7
+3
+1 2 3
+4 5 6
+7 8 9
 
 #include <stdio.h>
 #include <stdlib.h>
+#include <stdbool.h>
 
+typedef struct {
+	int i;
+	int j;
+	int value;
+}Node;
 
 //function prototypes
+bool oldNeighbor(Node I[], Node n);
+bool hasNeighbor(Node P[], Node n);
+
 void print(int **A, int n);
-
+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);
 
 int main (int argc, char *argv[]) {
 
 
 		print(*&A, n);
 
+		//removePosition(*&A, n, 3, 3);
 
+		solve(*&A, n);
 
+		print(*&A, n);
 
 		//Game over
 		return 0;
 	for (i = 0; i < n; i++) {
 		for (j = 0; j < n; j++) {
 
+			if (A[i][j] == 0) {
+				printf("  ");
+			}
+			else {
+				printf("%d ", A[i][j]);
+			}
 
-			printf("%d ", A[i][j]);
 		}
 		printf("\n");
 	}
 	printf("\n");
 }
 
+void removePosition(int **A, int n, int i, int j) {
 
+	int p;
+	for (p = i; p > 0; p--) {
+		A[p][j] = A[p - 1][j];
+	}
+	A[p][j] = 0;
+
+}
+
+void solve(int **A, int n) {
+	Node L;
+	Node Q[10];
+	Node I[100];
+
+	int q_count = 0;
+	int i_count = 0;
+
+	int i;
+	int j;
+
+	Node clear;
+	clear.i = 0;
+	clear.j = 0;
+	clear.value = 0;
+
+	for (i = 0; i < 10; i++) {
+		Q[i] = clear;
+	}
+	for (i = 0; i < 100; i++) {
+		I[i] = clear;
+	}
+
+
+	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
+
+
+}
+
+//void getPath(int **A, Node *Q, int q_count, int n, Node *I, int i_count) {
+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];
+	int i;
+	for (i = 0; i < 100; i++) {
+		P[i].i = 0;
+		P[i].j = 0;
+		P[i].value = 0;
+	}
+
+	for (i = 0; i < *q_count; i++) {
+
+
+		//NW
+		if (Q[i].i - 1 >= 0 && Q[i].j - 1 >= 0 ) {
+
+			Node NW;
+			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)) {
+				P[n_count] = NW;
+				n_count++;
+			}
+		}
+
+		//N
+		if (Q[i].i - 1 >= 0) {
+
+			Node N;
+			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)) {
+				P[n_count] = N;
+				n_count++;
+			}
+		}
+
+		//NE
+		if (Q[i].i - 1 >= 0 && Q[i].j + 1 < n) {
+
+			Node NE;
+			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)) {
+				P[n_count] = NE;
+				n_count++;
+			}
+		}
+
+		//W
+		if (Q[i].j - 1 >= 0) {
+
+			Node W;
+			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)) {
+				P[n_count] = W;
+				n_count++;
+			}
+		}
+		//E
+		if (Q[i].j + 1 < n) {
+
+			Node E;
+			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)) {
+				P[n_count] = E;
+				n_count++;
+			}
+		}
+
+		//SW
+		if (Q[i].i + 1 >= 0 && 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)) {
+				P[n_count] = SW;
+				n_count++;
+			}
+		}
+
+		//SE
+		if (Q[i].i + 1 < n && Q[i].j + 1 < n) {
+
+			Node SE;
+			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)) {
+				P[n_count] = SE;
+				n_count++;
+			}
+		}
+	}
+	//Now P is populated with all the Neighbors of the Nodes in Q
+
+	Node T = P[0];
+
+	//Pick the smallest T
+	for (i = 1; i < n_count; i++) {
+		if (T.value > P[i].value) {
+			T = P[i];
+		}
+	}
+
+	//get the weight of Q
+	int q_weight = 0;
+	for (i = 0; i < *q_count; i++ ) {
+		q_weight = q_weight + Q[i].value;
+
+	}
+
+	//Check the new weight
+	int W = q_weight + T.value;
+	if (W < 10) {
+		Q[*q_count] = T;
+		q_count++;
+		return getPath(A, Q, q_count, n, I, i_count);
+	}
+	else if (W > 10) {
+		q_count--;
+		Node last = Q[*q_count];
+		I[i_count] = last;
+		i_count++;
+		Q[*q_count].i = 0;
+		Q[*q_count].j = 0;
+		Q[*q_count].value = 0;
+
+		return getPath(A, Q, q_count, n, I, i_count);
+
+	}
+	else {
+		Q[*q_count] = T;
+		q_count++;
+		return;
+	}
+
+
+}
+
+
+//Check the set of neighbors for existing ones
+bool hasNeighbor(Node P[], Node n) {
+	int i;
+	for (i = 0; i < 100; i++) {
+		Node c = P[i];
+		if (c.i == n.i && c.j == n.j && c.value == n.value) {
+			return true;
+		}
+	}
+	return false;
+}
+
+//search the sed of old neighbors for exisiting ones.
+bool oldNeighbor(Node I[], Node n) {
+	int i;
+	for (i = 0; i < 100; i++) {
+		Node c = I[i];
+		if (c.i == n.i && c.j == n.j && c.value == n.value) {
+			return true;
+		}
+	}
+	return false;
+}
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.