Added my solutions to todays programming introduction exam

1 files changed, 114 insertions, 0 deletions

diff --git a/Year 1/Programming introduction/Exams/Exam1/prob3.cpp b/Year 1/Programming introduction/Exams/Exam1/prob3.cpp
new file mode 100644
index 0000000..07a21f2
--- /dev/null
+++ b/Year 1/Programming introduction/Exams/Exam1/prob3.cpp
@@ -0,0 +1,114 @@
+#include <iostream>
+
+using namespace std;
+
+const int MAX_SIZE = 1024;
+
+int deletedFromStartToSubset(char src[], int srcLen, char toCheck[], int toCheckLen) {
+	for (int i = 0, j = 0; i <= srcLen - toCheckLen; i++) {
+		/* Check if values from toCheck correspond to those of src with offset */
+
+		for (j = 0; j < toCheckLen; j++) {
+			if (src[j + i] != toCheck[j])
+				break;
+		}
+
+		if (j == toCheckLen)
+			return i;
+	}
+	return -1;
+}
+
+int deletedAndRotationIsSubset(char src[], int srcLen, char toCheck[], int toCheckLen) {
+	for (int rot = 0; rot < toCheckLen; rot++) {
+		/* Check if subset */
+
+		int deleted = deletedFromStartToSubset(src, srcLen, toCheck, toCheckLen);
+		if (deleted >= 0)
+			return deleted;
+
+		/* Rotate toCheck */
+
+		char lastVal = toCheck[toCheckLen - 1];
+		for (int i = toCheckLen - 2; i >= 0; i--) {
+			toCheck[i + 1] = toCheck[i];
+		}
+		toCheck[0] = lastVal;
+	}
+	return -1;
+}
+
+/* Bonus */
+
+int validRotationByDelSrc(char src[], int srcLen, char toCheck[], int toCheckLen, int deletedIndexes[]) {
+	char common[MAX_SIZE];
+
+	int di = 1;
+	for (int i = 0, ci = 0; i < srcLen; i++) {
+		for (int j = 0; j < toCheckLen; j++) {
+			if (src[i] == toCheck[j]) {
+				common[ci++] = toCheck[j];
+				deletedIndexes[di++] = i; // I know this is wrong, but I didn't have time to fix it :D
+				break;
+			}
+		}
+	}
+	deletedIndexes[0] = di; // Length at position 0
+
+	return deletedAndRotationIsSubset(common, toCheckLen, toCheck, toCheckLen);
+}
+
+int main() {
+
+
+	/* Get input */
+
+	cout << "size1: ";
+	int size1;
+	cin >> size1;
+	cout << "size2: ";
+	int size2;
+	cin >> size2;
+
+	cout << "firstArr: ";
+	char firstArr[MAX_SIZE];
+	for (int i = 0; i < size1; i++)
+		cin >> firstArr[i];
+
+	cout << "secondArr: ";
+	char secondArr[MAX_SIZE];
+	for (int i = 0; i < size2; i++)
+		cin >> secondArr[i];
+
+	/* Output result */
+
+	int deleted = deletedAndRotationIsSubset(firstArr, size1, secondArr, size2);
+
+	if (deleted == -1) {
+		int deletedIndexes[MAX_SIZE];
+		deleted = validRotationByDelSrc(firstArr, size1, secondArr, size2, deletedIndexes);
+
+		if (deleted == -1)
+			cout << "No rotations found!" << endl;
+		else {
+			cout << "Rotation \"";
+
+			for (int i = 0; i < size2; i++)
+				cout << secondArr[i];
+
+			cout << "\" found after deleting characters: ";
+
+			for (int i = 1; i < deletedIndexes[0]; i++)
+				cout << deletedIndexes[i] << " ";
+			cout << endl;
+		}
+	}
+	else {
+		cout << "Rotation \"";
+
+		for (int i = 0; i < size2; i++)
+			cout << secondArr[i];
+
+		cout << "\" found after deleting " << deleted << " characters from the start and " << (size1 - size2 - deleted) << " characters from the end." << endl;
+	}
+}