hw(AT/1): Cleaned up implementation

1 files changed, 56 insertions, 56 deletions

diff --git a/Year 4/Artificial Intelligence/hw01/main.cpp b/Year 4/Artificial Intelligence/hw01/main.cpp
index 46f2c6d..87e6167 100644
--- a/Year 4/Artificial Intelligence/hw01/main.cpp
+++ b/Year 4/Artificial Intelligence/hw01/main.cpp
@@ -20,20 +20,16 @@ struct Node {
 	int currentDepth;
 	int remainingDepth;
 
-	void update() {
-		this->currentDepth++;
-		this->remainingDepth = this->manhattan_dist();
-	}
+	Node() : board(), change(), zero(), currentDepth(), remainingDepth() {}
 
-	Node& operator=(const Node& other) {
-		if (this != &other) {
-			this->change = other.change;
-			this->board = other.board;
-			this->zero = other.zero;
-			this->currentDepth = other.currentDepth;
-			this->remainingDepth = other.remainingDepth;
+	void update_zero() {
+		for (this->zero = 0; this->zero < this->board.size(); this->zero++) {
+			if (this->board[this->zero] == 0) return;
 		}
-		return *this;
+	}
+
+	void update_remainingDepth() {
+		this->remainingDepth = this->manhattan_dist();
 	}
 
 	bool solved() {
@@ -53,14 +49,11 @@ struct Node {
 		return false;
 	}
 
-	friend bool operator==(const Node& left, const Node& right) {
-		return left.board == right.board;
-	}
-
-	void find_zero() {
-		for (this->zero = 0; this->zero < this->board.size(); this->zero++) {
-			if (this->board[this->zero] == 0) return;
-		}
+	void increment(int new_zero) {
+		swap(this->board[new_zero], this->board[this->zero]);
+		this->zero = new_zero;
+		this->currentDepth++;
+		this->update_remainingDepth();
 	}
 
 private:
@@ -78,9 +71,26 @@ private:
 		}
 		return total;
 	}
+
+public:
+	Node& operator=(const Node& other) {
+		if (this != &other) {
+			this->change = other.change;
+			this->board = other.board;
+			this->zero = other.zero;
+			this->currentDepth = other.currentDepth;
+			this->remainingDepth = other.remainingDepth;
+		}
+		return *this;
+	}
+
+	friend bool operator==(const Node& left, const Node& right) {
+		return left.board == right.board;
+	}
 };
 
 #define SOLVED -1
+#define SKIP_J_IF(condition) if (condition) { delete j; continue; }
 
 int dfs(vector<Node*>& path, int maxDepth) {
 	Node* i = path.back();
@@ -92,55 +102,41 @@ int dfs(vector<Node*>& path, int maxDepth) {
 	for (int dir = 0; dir < 4; dir++) {
 		Node* j = new Node(*i);
 
+		int new_zero = 0;
 		switch (dir) {
 			case 0: // left
-				if (j->zero % N == 0) {
-					delete j;
-					continue;
-				}
-				swap(j->board[j->zero - 1], j->board[j->zero]);
+				SKIP_J_IF(j->zero % N == 0);
+
+				new_zero = j->zero - 1;
 				j->change = "right";
-				j->zero--;
 				break;
 			case 1: // right
-				if (j->zero % N == N - 1) {
-					delete j;
-					continue;
-				}
-				swap(j->board[j->zero + 1], j->board[j->zero]);
+				SKIP_J_IF(j->zero % N == N - 1);
+
+				new_zero = j->zero + 1;
 				j->change = "left";
-				j->zero++;
 				break;
 			case 2: // up
-				if (j->zero / N == 0) {
-					delete j;
-					continue;
-				}
-				swap(j->board[j->zero - N], j->board[j->zero]);
+				SKIP_J_IF(j->zero / N == 0);
+
+				new_zero = j->zero - N;
 				j->change = "down";
-				j->zero -= N;
 				break;
 			case 3: // down
-				if (j->zero / N == N - 1) {
-					delete j;
-					continue;
-				}
-				swap(j->board[j->zero + N], j->board[j->zero]);
+				SKIP_J_IF(j->zero / N == N - 1);
+
+				new_zero = j->zero + N;
 				j->change = "up";
-				j->zero += N;
 				break;
 		}
-		j->update();
+		j->increment(new_zero);
 
 		// Don't go back a step
-		if (j->equals_any_in(path)) {
-			delete j;
-			continue;
-		}
+		SKIP_J_IF(j->equals_any_in(path));
 
 		path.push_back(j);
-		int val = dfs(path, maxDepth);
 
+		int val = dfs(path, maxDepth);
 		if (val == SOLVED) return SOLVED;
 		if (val < min) min = val;
 
@@ -162,10 +158,14 @@ bool solvable(Node* root) {
 		}
 	}
 
+	// n is even, an n-by-n board is solvable
+	// iff the number of inversions + the row of the blank square is odd
 	if (board.size() % 2 == 0) {
-		inversions += root->zero % N;
-		return inversions % 2 == 1;
+		inversions += root->zero / N;
+		return (inversions % 2) == ((I / N) % 2);
 	}
+	// when n is odd, an n-by-n board is solvable
+	// iff its number of inversions is even
 	else {
 		return inversions % 2 == 0;
 	}
@@ -186,9 +186,7 @@ int main() {
 	N = sqrt(N + 1);
 
 	/* Prepare */
-	root->find_zero();
-	root->update();
-	root->currentDepth = 0;
+	root->update_zero();
 
 	if (!solvable(root)) {
 		std::cout << -1 << std::endl;
@@ -196,11 +194,13 @@ int main() {
 		return 0;
 	}
 
+	root->update_remainingDepth();
+
 	vector<Node*> path;
 	path.push_back(root);
 
 	/* IDA* */
-	int bound = 1;
+	int bound = 3;
 	while(bound != SOLVED) {
 		bound = dfs(path, bound);
 	}