hw(AI/1): Fix solution

2 files changed, 218 insertions, 1 deletions

diff --git a/Year 4/Artificial Intelligence/hw01/main.cpp b/Year 4/Artificial Intelligence/hw01/main.cpp
new file mode 100644
index 0000000..46f2c6d
--- /dev/null
+++ b/Year 4/Artificial Intelligence/hw01/main.cpp
@@ -0,0 +1,215 @@
+#include <iostream>
+#include <utility>
+#include <vector>
+#include <string>
+#include <math.h>
+#include <climits>
+#include <cassert>
+
+// #include "graph.h"
+
+using namespace std;
+
+int I, N = 0;
+
+struct Node {
+	vector<int> board;
+	string change;
+	int zero;
+
+	int currentDepth;
+	int remainingDepth;
+
+	void update() {
+		this->currentDepth++;
+		this->remainingDepth = this->manhattan_dist();
+	}
+
+	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;
+	}
+
+	bool solved() {
+		return this->remainingDepth == 0;
+	}
+
+	int depth() {
+		return this->currentDepth + this->remainingDepth;
+	}
+
+	bool equals_any_in(vector<Node*>& arr) {
+		for (int i = 0; i < arr.size(); i++) {
+			if (*arr[i] == *this) {
+				return true;
+			}
+		}
+		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;
+		}
+	}
+
+private:
+	pair<int, int> to_2D(int i) {
+		return { i / N, i % N };
+	}
+	int manhattan_dist() {
+		int total = 0;
+		for (int i = 0; i < this->board.size(); i++) {
+			if (this->board[i] == 0) continue;
+
+			auto curr = to_2D(i);
+			auto goal = to_2D(this->board[i] - 1 + (this->board[i] > I));
+			total += abs(curr.first - goal.first) + abs(curr.second - goal.second);
+		}
+		return total;
+	}
+};
+
+#define SOLVED -1
+
+int dfs(vector<Node*>& path, int maxDepth) {
+	Node* i = path.back();
+
+	if (i->solved()) return SOLVED;
+	if (i->depth() > maxDepth) return i->depth();
+
+	int min = INT_MAX;
+	for (int dir = 0; dir < 4; dir++) {
+		Node* j = new Node(*i);
+
+		switch (dir) {
+			case 0: // left
+				if (j->zero % N == 0) {
+					delete j;
+					continue;
+				}
+				swap(j->board[j->zero - 1], j->board[j->zero]);
+				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]);
+				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]);
+				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]);
+				j->change = "up";
+				j->zero += N;
+				break;
+		}
+		j->update();
+
+		// Don't go back a step
+		if (j->equals_any_in(path)) {
+			delete j;
+			continue;
+		}
+
+		path.push_back(j);
+		int val = dfs(path, maxDepth);
+
+		if (val == SOLVED) return SOLVED;
+		if (val < min) min = val;
+
+		path.pop_back();
+		delete j;
+	}
+	return min;
+}
+
+bool solvable(Node* root) {
+	vector<int> &board = root->board;
+
+	int inversions = 0;
+	for (int i = 0; i < board.size(); i++) {
+		if (board[i] == 0) continue;
+		for (int j = i; j < board.size(); j++) {
+			if (board[j] == 0) continue;
+			inversions += board[i] > board[j];
+		}
+	}
+
+	if (board.size() % 2 == 0) {
+		inversions += root->zero % N;
+		return inversions % 2 == 1;
+	}
+	else {
+		return inversions % 2 == 0;
+	}
+}
+
+int main() {
+	/* Input */
+	cin >> N >> I;
+	if (I == -1) { I = N; }
+	N++;
+
+	Node* root = new Node;
+	int temp;
+	for (int i = 0; i < N; i++) {
+		cin >> temp;
+		root->board.push_back(temp);
+	}
+	N = sqrt(N + 1);
+
+	/* Prepare */
+	root->find_zero();
+	root->update();
+	root->currentDepth = 0;
+
+	if (!solvable(root)) {
+		std::cout << -1 << std::endl;
+		delete root;
+		return 0;
+	}
+
+	vector<Node*> path;
+	path.push_back(root);
+
+	/* IDA* */
+	int bound = 1;
+	while(bound != SOLVED) {
+		bound = dfs(path, bound);
+	}
+
+	/* Output */
+	cout << (path.size() - 1) << endl;
+	for (int i = 1; i < path.size(); i++) {
+		cout << path[i]->change << endl;
+		delete path[i];
+	}
+	delete root;
+}
diff --git a/Year 4/Artificial Intelligence/shell.nix b/Year 4/Artificial Intelligence/shell.nix
index 5fe3be2..cbb734b 100644
--- a/Year 4/Artificial Intelligence/shell.nix
+++ b/Year 4/Artificial Intelligence/shell.nix
@@ -1,9 +1,11 @@
 let
-  nixpkgs = fetchTarball "https://github.com/NixOS/nixpkgs/tarball/nixos-24.05";
+  nixpkgs = fetchTarball "https://github.com/NixOS/nixpkgs/tarball/nixos-24.11";
   pkgs = import nixpkgs { config = {}; overlays = []; };
 in
 pkgs.mkShellNoCC {
   packages = with pkgs; [
     cargo
+    gcc
+    valgrind
   ];
 }