feat(Week12): Add solutions to most exercises

6 files changed, 745 insertions, 0 deletions

diff --git a/Week12/Exercise01.cpp b/Week12/Exercise01.cpp
new file mode 100644
index 0000000..12a2375
--- /dev/null
+++ b/Week12/Exercise01.cpp
@@ -0,0 +1,111 @@
+#include <iostream>
+
+bool isLetter(char x) {
+	return ('A' <= x && x <= 'Z') || ('a' <= x && x <= 'z');
+}
+
+// Отмества един път на дясно всяка буква по шифъра на цезар.
+// Тоест, а става b, b става c, ..., z става a
+void caesarShift(char* str, unsigned int size) {
+	for (unsigned int i = 0; i < size; i++) {
+		if (isLetter(str[i])) {
+			str[i]++;
+
+			// Тази логика може да се пренапише с модулно деление
+			if ('z' < str[i])
+				str[i] = 'a';
+			else if ('Z' < str[i] && str[i] < 'a')
+				str[i] = 'A';
+		}
+	}
+}
+
+char toLower(char x) {
+	if ('A' <= x && x <= 'Z')
+		return x + ('a' - 'A');
+	return x;
+}
+
+// Дали първия низ започва с цялото съдържание на втория низ,
+// игнорирайки дали букви са главни или малки.
+bool isSubstr(const char* str, unsigned int size, const char* substr, unsigned int subsize) {
+	if (size < subsize)
+		return false;
+
+	for (unsigned int i = 0; i < subsize; i++)
+		if (toLower(str[i]) != toLower(substr[i]))
+			return false;
+
+	return !isLetter(str[subsize]);
+}
+
+char* getInput(unsigned &allocated, unsigned &size) {
+	allocated = 8;
+	size = 0;
+
+	char* input = new char[allocated];
+
+	char curr;
+	std::cin.get(curr);
+	while (curr != '\n') {
+		input[size++] = curr;
+		std::cin.get(curr);
+
+		// Реоразмеряване
+		if (size >= allocated) {
+			allocated *= 2;
+			char* newSentenceArray = new char[allocated];
+
+			for (unsigned i = 0; i < size; i++)
+				newSentenceArray[i] = input[i];
+
+			delete[] input;
+			input = newSentenceArray;
+		}
+	}
+	input[size] = '\0';
+
+	return input;
+}
+
+// Ще зачетем едно съобщение за дешифрирано ако съдържа една от често-срещаните думи.
+// На теория може би е възможно шифрирано съобщение да съдържа някоя от тях, но това е
+// извън обхвата на задачата.
+//
+// Алгоритъма е следния: проверяваме дали съобщението е дешифрирано, ако не е,
+// отместваме всяка буква с една позиция (a -> b, b -> c, ..., z -> a) и пробваме пак.
+bool bruteforceCaesar(char* text, unsigned int size) {
+	for (unsigned int shift = 0; shift < 26; shift++) {
+		for (unsigned int i = 0; i < size; i++) {
+			// По-добра реализация е да обикалеме масив от низове.
+			// Обаче, така ми се стурва по-лесно за разбиране.
+			if (isSubstr(text + i, size - i, "the", 3) ||
+			    isSubstr(text + i, size - i, "be",  2) ||
+			    isSubstr(text + i, size - i, "to",  2) ||
+			    isSubstr(text + i, size - i, "of",  2) ||
+			    isSubstr(text + i, size - i, "and", 3))
+			{
+				return true;
+			}
+		}
+
+		caesarShift(text, size);
+	}
+	return false;
+}
+
+int main() {
+	unsigned int allocated, size;
+	char* text = getInput(allocated, size);
+
+	if (bruteforceCaesar(text, size)) {
+		std::cout << text << std::endl;
+	}
+	else {
+		std::cout << "Couldn't bruteforce the message!" << std::endl;
+	}
+
+	delete[] text;
+
+	return 0;
+}
diff --git a/Week12/Exercise02.cpp b/Week12/Exercise02.cpp
new file mode 100644
index 0000000..1b884a5
--- /dev/null
+++ b/Week12/Exercise02.cpp
@@ -0,0 +1,89 @@
+#include <iostream>
+
+unsigned int findSpace(const char* text, unsigned int start, unsigned int size) {
+	for (unsigned int i = start; i < size; i++)
+		if (text[i] == ' ')
+			return i;
+	return size;
+}
+
+void fitToColumns(char* text, unsigned int size, unsigned int columns) {
+	unsigned indexInColumn = 0;
+	unsigned int lastSpace = size;
+
+	for (unsigned int i = 0; i < size; i++) {
+		if (text[i] == ' ')
+			lastSpace = i;
+
+		if (indexInColumn == columns) {
+			// Ако следващия знак е шпация, разделяме реда на него,
+			// вместо на предходна шпация (ако има такава).
+			// Това побира по-добре нашите полета и оправя пример 3.
+			if (i + 1 < size && text[i + 1] == ' ')
+				lastSpace = i + 1;
+			else if (i + 1 == size)
+				return;
+
+			if (lastSpace >= size)
+				lastSpace = findSpace(text, i, size);
+
+			if (lastSpace >= size)
+				return;
+
+			text[lastSpace] = '\n';
+			i = lastSpace + 1;
+
+			indexInColumn = 0;
+			lastSpace = size;
+		}
+		else {
+			indexInColumn++;
+		}
+	}
+}
+
+char* getInput(unsigned &allocated, unsigned &size);
+
+int main() {
+	unsigned int allocated, size;
+	char* text = getInput(allocated, size);
+
+	unsigned int columns;
+	std::cin >> columns;
+
+	fitToColumns(text, size, columns - 1);
+	std::cout << text << std::endl;
+
+	delete[] text;
+
+	return 0;
+}
+
+char* getInput(unsigned &allocated, unsigned &size) {
+	allocated = 8;
+	size = 0;
+
+	char* input = new char[allocated];
+
+	char curr;
+	std::cin.get(curr);
+	while (curr != '\n') {
+		input[size++] = curr;
+		std::cin.get(curr);
+
+		// Реоразмеряване
+		if (size >= allocated) {
+			allocated *= 2;
+			char* newSentenceArray = new char[allocated];
+
+			for (unsigned i = 0; i < size; i++)
+				newSentenceArray[i] = input[i];
+
+			delete[] input;
+			input = newSentenceArray;
+		}
+	}
+	input[size] = '\0';
+
+	return input;
+}
diff --git a/Week12/Exercise03.cpp b/Week12/Exercise03.cpp
new file mode 100644
index 0000000..59228fc
--- /dev/null
+++ b/Week12/Exercise03.cpp
@@ -0,0 +1,81 @@
+#include <iostream>
+
+void printRepeat(char x, unsigned int repeat) {
+	while (repeat-- > 0)
+		std::cout << x;
+}
+
+char* getField(unsigned &allocated, unsigned &size);
+
+int main() {
+	unsigned int allocated1, size1;
+	char* field1 = getField(allocated1, size1);
+
+	unsigned int allocated2, size2;
+	char* field2 = getField(allocated2, size2);
+
+	int columns;
+	std::cin >> columns;
+
+	columns = columns - size1 - size2;
+
+	if (columns <= 0) {
+		std::cout << field1 << field2 << std::endl;
+	}
+	else {
+		unsigned int sideSpaces = columns / 3, middleSpaces = columns / 3;
+		if (columns % 3 == 1)
+			middleSpaces++;
+		else if (columns % 3 == 2)
+			sideSpaces++;
+
+		// Алтернативно може да създадем низ с дадения брой шпации и
+		// да изкараме него, вместо да принтираме шпациите директно.
+
+		printRepeat(' ', sideSpaces);
+		std::cout << field1;
+		printRepeat(' ', middleSpaces);
+		std::cout << field2;
+		printRepeat(' ', sideSpaces);
+		std::cout << std::endl;
+	}
+
+	delete[] field1;
+	delete[] field2;
+
+	return 0;
+}
+
+// Тази функция е почти същата като getLine от задача 2, само че
+// разделителя (разделителите) между малко се различава.
+// По-точно, позволява да имаме произволен брой шпации между полетата
+// във входа, без това да влияе върху резултата.
+char* getField(unsigned &allocated, unsigned &size) {
+	allocated = 8;
+	size = 0;
+
+	char* input = new char[allocated];
+
+	char curr;
+	std::cin.get(curr);
+	while ((curr != ' ' || size == 0) && curr != '\n') {
+		if (curr != ' ')
+			input[size++] = curr;
+		std::cin.get(curr);
+
+		// Реоразмеряване
+		if (size >= allocated) {
+			allocated *= 2;
+			char* newSentenceArray = new char[allocated];
+
+			for (unsigned i = 0; i < size; i++)
+				newSentenceArray[i] = input[i];
+
+			delete[] input;
+			input = newSentenceArray;
+		}
+	}
+	input[size] = '\0';
+
+	return input;
+}
diff --git a/Week12/Exercise04.cpp b/Week12/Exercise04.cpp
new file mode 100644
index 0000000..b10ff9e
--- /dev/null
+++ b/Week12/Exercise04.cpp
@@ -0,0 +1,158 @@
+#include <iostream>
+
+// Функциите тук "консумират" входния низ, тоест не просто
+// превръщат буквите в някаква друга стойност, ами и инкрементират
+// указателя, така че да се пропуснат обработените букви.
+
+bool isDigit(char x) {
+	return '0' <= x && x <= '9';
+}
+
+bool digitsUntil(const char*& str, char end) {
+	bool hasAnyDigits = false;
+
+	while (*str != '\0' && *str != end) {
+		if (!isDigit(*str))
+			return false;
+		str++;
+		hasAnyDigits = true;
+	}
+
+	return hasAnyDigits && *str == end;
+}
+
+bool isInteger(const char* text) {
+	if (*text == '+' || *text == '-')
+		text++;
+
+	return digitsUntil(text, '\0');
+}
+
+bool isFloat(const char* text) {
+	if (*text == '+' || *text == '-')
+		text++;
+
+	if (!digitsUntil(text, '.'))
+		return false;
+	text++;
+	return digitsUntil(text, '\0');
+}
+
+bool isLetter(char x) {
+	return ('A' <= x && x <= 'Z') || ('a' <= x && x <= 'z');
+}
+
+bool isWord(const char* text) {
+	while (*text != '\0') {
+		if (!isLetter(*text))
+			return false;
+		text++;
+	}
+	return true;
+}
+
+// В тази функция донякъде има един проблем:
+// не проверяваме ако часа ни е 12-часов, дали часа е между 0 и 12 (вместо между 0 и 24).
+// Обаче, по условие не ни е казано да проверяваме за това, затова изпускам проверката.
+bool isTime(const char* text) {
+	if ((text[0] == 'A' || text[0] == 'P') && text[1] == 'M')
+		text += 2;
+
+	if (!isDigit(*text) && '0' <= *text && *text <= '2')
+		return false;
+	text++;
+
+	if (isDigit(*text))
+		text++;
+
+	if (*text != ':')
+		return false;
+	text++;
+
+	if (!isDigit(*text) && '0' <= *text && *text <= '5')
+		return false;
+	text++;
+
+	if (!isDigit(*text))
+		return false;
+	text++;
+
+	if ((text[0] == 'A' || text[0] == 'P') && text[1] == 'M')
+		text += 2;
+
+	return *text == '\0';
+}
+
+bool isPercentage(char* text, unsigned int size) {
+	if (!isDigit(*text))
+		return false;
+
+	if (text[size - 1] != '%')
+		return false;
+
+	text[size - 1] = '\0';
+
+	return isInteger(text) || isFloat(text);
+}
+
+char* getInput(unsigned &allocated, unsigned &size);
+
+int main() {
+	unsigned int allocated, size;
+	char* text = getInput(allocated, size);
+
+	if (size == 0) {
+		std::cout << "other" << std::endl;
+	}
+	else if (isInteger(text)) {
+		std::cout << "integer" << std::endl;
+	}
+	else if (isFloat(text)) {
+		std::cout << "float" << std::endl;
+	}
+	else if (isWord(text)) {
+		std::cout << "word" << std::endl;
+	}
+	else if (isTime(text)) {
+		std::cout << "time" << std::endl;
+	}
+	else if (isPercentage(text, size)) {
+		std::cout << "percentage" << std::endl;
+	}
+	else {
+		std::cout << "other" << std::endl;
+	}
+
+	delete[] text;
+
+	return 0;
+}
+
+char* getInput(unsigned &allocated, unsigned &size) {
+	allocated = 8;
+	size = 0;
+
+	char* input = new char[allocated];
+
+	char curr;
+	std::cin.get(curr);
+	while (curr != '\n') {
+		input[size++] = curr;
+		std::cin.get(curr);
+
+		// Реоразмеряване
+		if (size >= allocated) {
+			allocated *= 2;
+			char* newSentenceArray = new char[allocated];
+
+			for (unsigned i = 0; i < size; i++)
+				newSentenceArray[i] = input[i];
+
+			delete[] input;
+			input = newSentenceArray;
+		}
+	}
+	input[size] = '\0';
+
+	return input;
+}
diff --git a/Week12/Exercise06.cpp b/Week12/Exercise06.cpp
new file mode 100644
index 0000000..e0d3a72
--- /dev/null
+++ b/Week12/Exercise06.cpp
@@ -0,0 +1,303 @@
+#include <iostream>
+
+/* Менажиране на памет на текста */
+
+// Заделяне на памет
+void newText(char**& text, unsigned& size, unsigned& allocated) {
+	size = 0;
+	allocated = 8;
+	text = new char*[allocated];
+}
+
+// Реоразмеряване
+void enlargeText(char**& text, unsigned& size, unsigned& allocated) {
+	allocated *= 2;
+	char** largerText = new char*[allocated];
+
+	for (unsigned i = 0; i < size; i++)
+		largerText[i] = text[i];
+
+	delete[] text;
+	text = largerText;
+}
+
+// Освобождаване на памет
+void deleteText(char**& text, unsigned& size) {
+	for (unsigned i = 0; i < size; i++)
+		delete[] text[i];
+	delete[] text;
+	text = nullptr;
+}
+
+/* Обсег */
+//
+// Тези функции наричам "консуматори", защото приемат указател към низ,
+// който указател инкрементират.
+//
+// Тоест, ако указателя сочи към "1234Hello", след като го подадем на
+// consumeUnsigned, ще сочи към "Hello" (и value ще бъде 1234).
+//
+
+bool isDigit(char x) {
+	return '0' <= x && x <= '9';
+}
+
+bool consumeUnsigned(const char*& cmd, unsigned& value) {
+	value = 0;
+	bool consumedAnything = false;
+
+	while (isDigit(*cmd) && *cmd != '\0') {
+		value = value * 10 + (*cmd - '0');
+		cmd++;
+		consumedAnything = true;
+	}
+
+	return consumedAnything;
+}
+
+bool consumeLineAddress(const char*& cmd, unsigned current, unsigned lastLine, unsigned& address) {
+	bool consumedAnything = false;
+
+	if (*cmd == '.') {
+		address = current;
+		cmd++;
+		consumedAnything = true;
+	}
+	else if (*cmd == '$') {
+		address = lastLine;
+		cmd++;
+		consumedAnything = true;
+	}
+	else {
+		consumedAnything = consumeUnsigned(cmd, address);
+
+		// Ако не ни е подаден адрес
+		if (address == 0) {
+			address = current;
+		}
+		// Ако има числов адрес
+		else {
+			address--;
+			if (address > lastLine)
+				address = lastLine;
+		}
+	}
+
+	return consumedAnything;
+}
+
+// Обработва подадения обсег, като връща индекси rangeStart и rangeEnd,
+// т.е. автоматично превръща ред "5" на индекс 4.
+void consumeLineRange(const char*& cmd, unsigned current, unsigned lastLine, unsigned& rangeStart, unsigned& rangeEnd) {
+	bool consumedStart = consumeLineAddress(cmd, current, lastLine, rangeStart);
+
+	if (*cmd == ',') {
+		// Ако не въведем обсег, тогава обсега е текущия ред.
+		// Но, ако въведем обсег за няколко реда, без да има
+		// експлицитни начало и край (т.е. целия обсег е ","),
+		// тогава това трябва да е същото като "1,$".
+		if (!consumedStart)
+			rangeStart = 0;
+
+		cmd++;
+
+		if (!consumeLineAddress(cmd, current, lastLine, rangeEnd))
+			rangeEnd = lastLine;
+	}
+	else {
+		rangeEnd = rangeStart;
+	}
+}
+
+/* Команда */
+
+void printCommand(char** text, unsigned& textLines, unsigned selected) {
+	if (selected >= textLines)
+		std::cout << "(null text)" << std::endl;
+	else
+		std::cout << text[selected] << std::endl;
+}
+
+void enumerateCommand(char** text, unsigned& textLines, unsigned selected) {
+	if (selected >= textLines) {
+		std::cout << "(null text)" << std::endl;
+	}
+	else {
+		std::cout << (selected + 1) << ' ';
+		printCommand(text, textLines, selected);
+	}
+}
+
+void deleteCommand(char**& text, unsigned& textLines, unsigned selected) {
+	if (textLines < 1)
+		return;
+
+	delete[] text[selected];
+
+	// Отместваме всички редове под изтрития с една позиция нагоре
+	if (textLines > 1) {
+		for (unsigned l = selected; l < textLines - 1; l++)
+			text[l] = text[l + 1];
+	}
+
+	text[--textLines] = nullptr;
+}
+
+char* cpystr(const char* str) {
+	// Тази логика може да се изведе в strlen
+	unsigned length = 0;
+	while (str[length] != '\0')
+		length++;
+
+	char* copy = new char[length + 1];
+	// <= length, за да копираме терминиращата нула
+	for (unsigned i = 0; i <= length; i++)
+		copy[i] = str[i];
+
+	return copy;
+}
+
+void insertCommand(const char* argText, char**& text, unsigned& textLines, unsigned& textAllocated, unsigned selected) {
+	if (textAllocated <= textLines + 1)
+		enlargeText(text, textLines, textAllocated);
+
+	// Да вмъкнем текст преди даден ред е същото, като да
+	// измествим с един ред надолу всички редове от избрания до последния вкл.
+	// и да променим реда на който индекс оригинално беше избрания.
+	// Гаден случай: ако текста ни е празен, не трябва да правим преместването.
+	if (textLines > 0) {
+		for (unsigned i = textLines; i > selected; i--)
+			text[i] = text[i - 1];
+	}
+	textLines++;
+
+	text[selected] = cpystr(argText);
+}
+
+void appendCommand(const char* argText, char**& text, unsigned& textLines, unsigned& textAllocated, unsigned selected) {
+	// Да добавиш текст след подаден ред е същото, като
+	// да добавиш текст преди реда след подадения.
+	// Гаден случай: ако текста ни е празен, трябва задължително да
+	// вмъкнем на ред с индекс 0.
+	insertCommand(argText, text, textLines, textAllocated, selected + (textLines > 0));
+}
+
+bool evaluateCommand(const char* cmd, char**& text, unsigned& textLines, unsigned& textAllocated, unsigned& current) {
+	unsigned start, end;
+	consumeLineRange(cmd, current, textLines - (textLines > 1), start, end);
+
+	if (start > end) {
+		std::cout << "Start line in range cannot be after end line!" << std::endl;
+		return true;
+	}
+
+	for (unsigned selected = start; selected <= end; selected++) {
+		switch (*cmd) {
+			// Ако има само въведен обсег и няма въведена команда
+			case '\0':
+				current = selected;
+				break;
+
+			case 'p':
+				printCommand(text, textLines, selected);
+				break;
+
+			case 'n':
+				enumerateCommand(text, textLines, selected);
+				break;
+
+			case 'd':
+				deleteCommand(text, textLines, selected);
+
+				if (selected <= current && current > 0)
+					current--;
+
+				if (end > 0) {
+					end--;
+					// Тук се възползваме от факта, че (при unsigned int)
+					// 0 - 1 = 4294967295
+					// 4294967295 + 1 = 0
+					selected--;
+				}
+
+				break;
+
+			case 'i':
+				insertCommand(cmd + 1, text, textLines, textAllocated, selected);
+				current = selected;
+
+				end++;
+				selected++;
+				break;
+
+			case 'a':
+				appendCommand(cmd + 1, text, textLines, textAllocated, selected);
+				current = selected + (textLines > 1);
+
+				end++;
+				selected++;
+				break;
+
+			case 'q':
+				return false;
+
+			default:
+				std::cout << "Unknown command " << *cmd << "!" << std::endl;
+				return true;
+		}
+	}
+	return true;
+}
+
+void getInput(char*& input, unsigned &allocated, unsigned &size);
+
+int main() {
+	unsigned textAllocated, textSize;
+	char** text;
+	newText(text, textSize, textAllocated);
+
+	unsigned currentLine = 0;
+
+	unsigned cmdAllocated = 0, cmdSize = 0;
+	char* cmd;
+
+	getInput(cmd, cmdAllocated, cmdSize);
+	while (evaluateCommand(cmd, text, textSize, textAllocated, currentLine)) {
+		cmdSize = 0;
+		getInput(cmd, cmdAllocated, cmdSize);
+	}
+
+	deleteText(text, textSize);
+	delete[] cmd;
+
+	return 0;
+}
+
+void getInput(char*& input, unsigned &allocated, unsigned &size) {
+	if (allocated == 0) {
+		allocated = 8;
+		size = 0;
+
+		input = new char[allocated];
+	}
+
+	char curr;
+	std::cin.get(curr);
+	while (curr != '\n') {
+		input[size++] = curr;
+		std::cin.get(curr);
+
+		// Реоразмеряване
+		if (size >= allocated) {
+			allocated *= 2;
+			char* newSentenceArray = new char[allocated];
+
+			for (unsigned i = 0; i < size; i++)
+				newSentenceArray[i] = input[i];
+
+			delete[] input;
+			input = newSentenceArray;
+		}
+	}
+	input[size] = '\0';
+}
diff --git a/Week12/README.md b/Week12/README.md
new file mode 100644
index 0000000..141899a
--- /dev/null
+++ b/Week12/README.md
@@ -0,0 +1,3 @@
+# Задачи
+
+<https://syndamia.com/teaching/upp-2025/week12/>