add Sem03

9 files changed, 537 insertions, 1 deletions

diff --git a/README.md b/README.md
index 5d9ad8e..aa06d3e 100644
--- a/README.md
+++ b/README.md
@@ -1,3 +1,3 @@
-# Код от семинариe по СДП - Компютърни науки
+# Код от семинаритe по СДП - Компютърни науки
 * Тема 1: Технически преговор - указатели и памет. Дефиниция на структура от данни. Сложност.
 * Тема 2: Стек.
\ No newline at end of file
diff --git a/Seminar03/Linked-Queue.hpp b/Seminar03/Linked-Queue.hpp
new file mode 100644
index 0000000..d11dc11
--- /dev/null
+++ b/Seminar03/Linked-Queue.hpp
@@ -0,0 +1,162 @@
+#ifndef LINKED_QUEUE_IMPL
+#define LINKED_QUEUE_IMPL
+
+#include<cstddef>
+
+template<class T>
+class LinkedQueue {
+private:
+    struct LinkedNode {
+        T data;
+        LinkedNode* next;
+
+        LinkedNode(const T& argData, LinkedNode* argNext = nullptr) : data {argData}, next{argNext} {} 
+    };
+
+    LinkedNode* head;                   // Последния добавен елемент в опашката
+    LinkedNode* tail;                   // Първия добавен елемент в опашката
+    size_t queueSize;
+
+    void copy(const LinkedQueue<T>&);
+    void free();
+
+public:
+    LinkedQueue();
+    
+    LinkedQueue(const LinkedQueue<T>&);
+    LinkedQueue& operator=(const LinkedQueue<T>&);
+
+    LinkedQueue(LinkedQueue<T>&&) noexcept;
+    LinkedQueue& operator=(LinkedQueue<T>&&) noexcept;
+
+    void push(const T&);
+    void pop();
+    const T& front() const;
+
+    bool empty() const;
+
+    size_t size() const;
+
+    ~LinkedQueue();
+};
+
+template<class T>
+LinkedQueue<T>::LinkedQueue() : head {nullptr}, tail{nullptr}, queueSize{0} {}
+
+template<class T>
+LinkedQueue<T>::LinkedQueue(const LinkedQueue<T>& other) {
+    copy(other);
+}
+
+template<class T>
+LinkedQueue<T>& LinkedQueue<T>::operator=(const LinkedQueue<T>& other) {
+    if(this != &other){
+        free();
+        copy(other);
+    }
+
+    return *this;
+}
+
+template<class T>
+LinkedQueue<T>::LinkedQueue(LinkedQueue<T>&& other) noexcept {
+    head = other.head;
+    tail = other.tail;
+    size = other.size;
+
+    other.head = nullptr;
+    other.tail = nullptr;
+}
+
+template<class T>
+LinkedQueue<T>& LinkedQueue<T>::operator=(LinkedQueue<T>&& other) noexcept {
+    if(this != &other) {
+        head = other.head;
+        tail = other.tail;
+        size = other.size;
+
+        other.head = nullptr;
+        other.tail = nullptr;
+    }
+    return *this;
+}
+
+template<class T>
+void LinkedQueue<T>::copy(const LinkedQueue<T>& other) {
+    LinkedNode* iter = other.head;
+
+    while(iter) {
+        push(iter->data);
+        iter = iter->next;
+    }
+}
+
+template<class T>
+void LinkedQueue<T>::free() {
+    LinkedNode* iter = head;
+    while(iter) {
+        LinkedNode* removeMe = iter;
+        iter = iter->next;
+        delete removeMe;
+    }
+}
+
+template<class T>
+bool LinkedQueue<T>::empty() const {
+    return head == nullptr;
+}
+
+template<class T>
+size_t LinkedQueue<T>::size() const {
+    return queueSize;
+}
+
+template<class T>
+void LinkedQueue<T>::push(const T& elem) {
+    LinkedNode* toPush = new LinkedNode(elem);
+    if(empty()) {
+        tail = toPush;
+        head = toPush;
+    }
+    else {
+        tail->next = toPush;
+        tail = toPush;
+    }
+
+    ++queueSize;
+}
+
+template<class T>
+void LinkedQueue<T>::pop() {
+    if(empty()) {
+        throw "Empty queue";
+    }
+    else if(head == tail) {
+        delete head;
+        head = nullptr;
+        tail = nullptr;
+    }
+    else {
+        LinkedNode* deleteMe = head;
+        head = head->next;
+        delete deleteMe;
+    }
+
+    --queueSize;
+}
+
+template<class T>
+const T& LinkedQueue<T>::front() const {
+    if(empty()){
+        throw "Empty queue";
+    }
+
+    return head->data;
+}
+
+template<class T>
+LinkedQueue<T>::~LinkedQueue() {
+    free();
+}
+
+#endif
\ No newline at end of file
diff --git a/Seminar03/QueueTests.cpp b/Seminar03/QueueTests.cpp
new file mode 100644
index 0000000..221a09a
--- /dev/null
+++ b/Seminar03/QueueTests.cpp
@@ -0,0 +1,28 @@
+#include"Linked-Queue.hpp"
+#include<cassert>
+#include<iostream>
+
+void runTest() {
+    LinkedQueue<int> q;
+
+    for (size_t i = 0; i < 1000; i++)
+        q.push(i);
+
+    std::cout << "Passed size test" << std::endl;
+    assert(q.size() == 1000);
+
+    for (size_t i = 0; i < 1000; i++) {
+        assert(q.front() == i);
+        q.pop();
+    }
+
+    std::cout << "Push, pop and top working as expected" << std::endl;
+
+    assert(q.empty() && q.size() == 0);
+
+    std::cout << "Passed empty test" << std::endl;
+}
+
+int main() {
+    runTest();
+}
diff --git a/Seminar03/README.md b/Seminar03/README.md
new file mode 100644
index 0000000..3dad403
--- /dev/null
+++ b/Seminar03/README.md
@@ -0,0 +1,185 @@
+# Опашка
+Опашката е линейна структура от данни, която работи на принципа FIFO (first in first out). Опашката отговаря точно на представата за реална опашка. 
+Операции:
+* Enqueue (или push) - добавя елемент в края на опашката
+* Dequeue (или pop)  - премахва първия добавен елемент в опашката
+* Front              - връща първия елемент в опашката
+  
+Опционални операции към интерфейса:
+* empty() - Връща дали опашката е празна или не
+* size()  - Връща размера на опашката
+
+В STL имаме готова реализация на опашка. Тя се намира в библиотеката \<queue> и се създава чрез std::queue\<T>. 
+Пример:
+```cpp
+#include<iostream>
+#include<queue>
+
+int main() {
+    std::queue<int> q;
+
+    q.push(1);
+    q.push(2);
+    q.push(3);
+    q.push(4);
+
+    std::cout << q.front();             // Извежда 1
+    q.pop()                             // Премахва 1 от опашката
+    std::cout << q.front();             // Извежда 2
+    q.pop();                            // Премахва 2 от опашката
+    q.pop();                            // Премахва 3 от опашката
+}
+```
+
+## Приложения
+Едно от основните приложения на опашката е използването ѝ в различни алгоритми за обхождане на графи, като най - ясен пример за това би бил алгоритъма BFS. Други алгоритми върху графи също използват опашка (или нейни разновидности) за да обхождат графа и да решават различни задачи върху него. 
+Опашките също намират голямо приложение в операционните системи и компютърните мрежи.
+
+## Начини за реализация
+### Свързани компоненти
+
+Представяме елемента на опашката по следния начин:
+```cpp
+template<class T>
+struct QueueNode {
+    T data;
+    QueueNode<T>* next;
+}
+```
+В класа представящ опашка пазим два указателя, head и tail:
+```cpp
+template<class T>
+class LinkedQueue {
+    QueueNode<T>* head;                 // Представлява първия елемент, който е добавен.
+    QueueNode<T>* tail;                 // Представлява последния елемент, който е добавен.
+}
+```
+![](media/qexample.png)
+При такова представяне как биха изглеждали алгоритмите за добавяне и премахване?
+
+### Чрез масив
+Можем да представим опашката чрез статичен или динамичен масив и два индекса - към първия  и последния елемент добавен към опашката.
+![](media/arr-queue.png)
+
+При такова представяне как биха изглеждали алгоритмите за добавяне и премахване? Дали след като запълним последната клетка на масива повече няма да можем да добавим елемент в опашката?
+
+# Декове
+Декът или deque (от double ended queue) е линейна структура от данни, за която можем да си мислим като опашка, позволяваща добавяне и премахване на елементи и от двете страни.
+
+Операции:
+* push_front(x) - Добавя x в началото
+* push_back(x)  - Добавя х в края
+* pop_back()    - Премахва последния елемент
+* pop_front()   - Премахва първия елемент
+
+*A deque ("double ended queue") is a linear list for which all insertions and deletions (and usually all accesses) are made at the ends of the list*.
+
+Стандартната библиотека ни предлага реализация на дек. Тази реализация обаче трябва да се използва внимателно. Примерно, std::deque ни позволява достъп на произволен елемент в колекцията. Това, дори да изглежда като функционалност, която не бихме отказали, често може да доведе до различен тип грешки.
+
+Пример:
+```cpp
+#include<deque>
+
+int main() {
+    std::deque<int> dq;
+
+    dq.push_front(1);
+    dq.push_back(2);
+
+    dq[0] = 10; 
+    // Позволява промяна, но доста често такава промяна е безсмислена.
+    // Наложи ли ви се да правите такава промяна
+    // вероятно използвате грешната структура от данни.
+    dq[3] = 1;
+    // Какво става когато такъв елемент няма?
+    // Отговорът е зависи - недефинирано поведение (undefined behaviour).
+}
+```
+
+# Неща, които използвам в решението на задачите
+
+## Статични масиви и std::array
+Всички знаем, че статичният масив е бърза и удобна структура от данни. STL ни предлага готова реализация на статичен масив. Тя се намира в библиотеката \<array>.
+Пример:
+```cpp
+#include<array>
+
+int main() {
+    std::array<int, 10> arr;
+    arr[0] = 42;
+}
+```
+В случая arr се държи като нормален статичен масив, но идва с допълнителни помощни функции и поддържа логика за итератори.
+
+## Нетипови параметри
+Нетиповите параметри често се използват за определяне на някакви максимуми, минимуми или константи свързани с класа. Примерно, нека имаме следния код:
+
+```cpp
+const size_t MAX_SIZE = 100;
+
+template<class T>
+class staticArray {
+    T data[MAX_SIZE];
+}
+```
+Това върши работа до момента в който не ни потрябват два различни варианта на staticArray - един с максимум елемента 100 а втория с максимум 50. Този проблем се решава чрез нетипови параметри по следния начин:
+```cpp
+template<class T, size_t maxSize>
+class staticArray {
+    T data[maxSize];
+}
+```
+Сега много лесно мога да си направя два статични масива с различна горна граница:
+
+```cpp
+int main() {
+    staticArray<int, 50> fst;
+    staticArray<int, 100> snd;
+}
+```
+Тук компилаторът няма да ни се скара, понеже maxSize задължително трябва да е константа.
+Едно хубаво свойство на нетиповите параметри е, че staticArray<T, 50> и staticArray<T, 100> са два различни типа.
+
+# Задачи
+
+## Задача първа
+Да се напише функция, която генерира всички двоични числа от 1 до n, използвайки опашка.
+
+Пример:
+> n = 10 ➡ 1 10 11 100 101 110 111 1000 1001 1010
+
+## Задача втора
+Конче стои върху шахматна дъска NxN. За начална и крайна позиция да се изведе с колко най - малко хода можем да стигнем от началната до крайната.
+
+Пример:
+> {(0, 0), (2, 1)} -> 1
+> 
+> {(0, 0), (7, 7)} -> 6
+
+## Задача трета - Sliding window maximum
+Даден е масив от цели числа. Представяме си, че имаме прозорец с дължина *k* който се движи отляво надясно. Единственото което можем да видим са числата в прозореца. Да се изведе максимумът на всеки такъв прозорец.
+
+Пример:
+
+> Вход:  **[1, 3, -1, -3, 5, 3, 6, 7]**, k = 3
+> 
+> Output: [3, 3, 5, 5, 6, 7]
+
+Обяснение:
+> 
+> **[1  3  -1]** -3  5  3  6  7      => 3
+> 
+> 1 **[3  -1  -3]** 5  3  6  7       => 3
+>
+> 1  3 **[-1  -3  5]** 3  6  7       => 5
+>
+> 1  3  -1 **[-3  5  3]** 6  7       => 5
+>
+> 1  3  -1  -3 **[5  3  6]** 7       => 6
+>
+> 1  3  -1  -3  5 **[3  6  7]**      => 7
+
+Като бонус можете да направите втора задача да не извежда само минималния път, но и клетките през които сме минали.
+
+Алтернативни решения на задачи 1 и 2 както и още задачи за упражнение можете да намерите на:
+https://github.com/ivanahristova/data-structures-fmi/tree/main/sem04
\ No newline at end of file
diff --git a/Seminar03/media/arr-queue.png b/Seminar03/media/arr-queue.png
new file mode 100644
index 0000000..ba4e1fe
--- /dev/null
+++ b/Seminar03/media/arr-queue.png
diff --git a/Seminar03/media/qexample.png b/Seminar03/media/qexample.png
new file mode 100644
index 0000000..b43a02c
--- /dev/null
+++ b/Seminar03/media/qexample.png
diff --git a/Seminar03/task01.cpp b/Seminar03/task01.cpp
new file mode 100644
index 0000000..2a2eff3
--- /dev/null
+++ b/Seminar03/task01.cpp
@@ -0,0 +1,27 @@
+#include<iostream>
+#include<queue>
+#include<string>
+
+// Сложност по време: ?
+// Сложност по памет: ?
+void printAllBinaryNumbers(size_t n) {
+    std::queue<std::string> q;
+    
+    q.push("1");
+
+    while(n) {
+        std::string currentNumber = q.front();
+        q.pop();
+
+        std::cout << currentNumber << " ";
+
+        q.push(currentNumber + "0");
+        q.push(currentNumber + "1");
+        
+        n--;
+    }
+}
+
+int main() {
+    printAllBinaryNumbers(10);
+}
\ No newline at end of file
diff --git a/Seminar03/task02.cpp b/Seminar03/task02.cpp
new file mode 100644
index 0000000..e5ab8a7
--- /dev/null
+++ b/Seminar03/task02.cpp
@@ -0,0 +1,93 @@
+#include <iostream>
+#include <array>
+#include <queue>
+
+template<unsigned boardSize = 8>
+class minMoves {
+    using position = std::pair<int, int>;
+    using positionAndSteps = std::pair<position, int>;
+    using board = std::array<std::array<bool, boardSize>, boardSize>;
+
+    board playground;
+
+    void cleanPlayground() {
+        for (auto &col : playground)
+            for (auto &pos : col)
+                pos = false;
+    }
+
+    static bool equalPositions(const position &fst, const position &snd) {
+        return fst.first == snd.first && fst.second == snd.second;
+    }
+
+    static bool isValidPos(const position &p) {
+        return p.first >= 0 && p.second >= 0 && p.first < boardSize && p.second < boardSize;
+    }
+
+    void mark(const position &toMark) {
+        playground[toMark.first][toMark.second] = true;
+    }
+
+    bool isMarked(const position &pos) const {
+        return playground[pos.first][pos.second];
+    }
+
+    void pushAndMarkIfValid(std::queue<positionAndSteps> &q, const position &toPush, int steps) {
+        if (isValidPos(toPush) && !isMarked(toPush)) {
+            q.push({toPush, steps});
+            mark(toPush);
+        }
+    }
+
+    int process(const position &startPos, const position &endPos) {
+        std::queue<positionAndSteps> q;
+
+        q.push({startPos, 0});
+
+        while (!q.empty()) {
+            positionAndSteps currentPosition = q.front();
+
+            q.pop();
+
+            if (equalPositions(currentPosition.first, endPos))
+                return currentPosition.second;
+
+            int x = currentPosition.first.first;
+            int y = currentPosition.first.second;
+            int moves = currentPosition.second + 1;
+
+            pushAndMarkIfValid(q, {x + 1, y + 2}, moves);
+            pushAndMarkIfValid(q, {x - 1, y - 2}, moves);
+            pushAndMarkIfValid(q, {x + 1, y - 2}, moves);
+            pushAndMarkIfValid(q, {x - 1, y + 2}, moves);
+            pushAndMarkIfValid(q, {x + 2, y - 1}, moves);
+            pushAndMarkIfValid(q, {x + 2, y + 1}, moves);
+            pushAndMarkIfValid(q, {x - 2, y + 1}, moves);
+            pushAndMarkIfValid(q, {x - 2, y - 1}, moves);
+        }
+        return -1;
+    }
+
+public:
+    minMoves() { cleanPlayground(); }
+
+    int getMinMoves(const position &start, const position &end) {
+        cleanPlayground();
+
+        return process(start, end);
+    }
+};
+
+int main() {
+    minMoves m;
+
+    std::cout << m.getMinMoves({0, 0}, {5, 3}) << std::endl;
+
+    minMoves<12> ms;
+
+    std::cout << ms.getMinMoves({0, 0}, {11, 11}) << std::endl;
+
+    minMoves<2> mt;
+
+    std::cout << mt.getMinMoves({0, 0}, {12, 212});
+}
\ No newline at end of file
diff --git a/Seminar03/task03.cpp b/Seminar03/task03.cpp
new file mode 100644
index 0000000..eef4cf4
--- /dev/null
+++ b/Seminar03/task03.cpp
@@ -0,0 +1,41 @@
+#include<iostream>
+#include<deque>
+#include<vector>
+
+std::vector<int> maxSlidingWindow(const std::vector<int>& v, size_t k) {
+    std::deque<int> window;
+    std::vector<int> result;
+
+    for (size_t i = 0; i < k; i++) {
+        while(!window.empty() && window.back() < v[i]) {
+            window.pop_back();
+        }
+        window.push_back(v[i]);
+    }
+
+    result.push_back(window.front());
+
+    for (size_t i = k; i < v.size(); i++) {
+        if(window.front() == v[i - k]) {
+            window.pop_front();
+        }
+
+        while(!window.empty() && window.back() < v[i]) {
+            window.pop_back();
+        }
+
+        window.push_back(v[i]);
+        result.push_back(window.front());
+    }
+    
+    return result;
+}
+
+int main() {
+    std::vector<int> example = {1, 3, -1, -3, 5, 3, 6, 7};
+
+    std::vector<int> result = maxSlidingWindow(example, 3);
+
+    for(auto elem : result)
+        std::cout << elem << " ";
+}
\ No newline at end of file