[SDP/P/exb] Solved exercise B

5 files changed, 155 insertions, 0 deletions

diff --git a/Year 2/Structures and data algorithms/Project/exb/City.cpp b/Year 2/Structures and data algorithms/Project/exb/City.cpp
new file mode 100644
index 0000000..daf9b5c
--- /dev/null
+++ b/Year 2/Structures and data algorithms/Project/exb/City.cpp
@@ -0,0 +1,84 @@
+#include "CityVisit.h"
+#include <iostream>
+
+CityVisit::Landmark* CityVisit::find(const std::string& name) {
+	for (Landmark* l : landmarks) {
+		if (l->name == name)
+			return l;
+	}
+	return nullptr;
+}
+
+void CityVisit::pushLandmarks(const std::string& from, const std::string& to, unsigned time) {
+	Landmark* a = find(from);
+	if (a == nullptr) {
+		a = new Landmark(from);
+		landmarks.push_back(a);
+	}
+	Landmark* b = find(to);
+	if (b == nullptr) {
+		b = new Landmark(to);
+		landmarks.push_back(b);
+	}
+
+	a->visitable.push_back({ b, time });
+	b->visitable.push_back({ a, time });
+}
+
+void CityVisit::parse(std::ifstream& inFile) {
+	unsigned k = 0, r = 0;
+	inFile >> k >> r;
+
+	std::string name1;
+	std::string name2;
+	unsigned time = 0;
+	while (r-- > 0) {
+		inFile >> name1 >> name2 >> time;
+		pushLandmarks(name1, name2, time);
+	}
+	inFile >> availableTime;
+}
+
+void CityVisit::visitTheMostInTimeRec(Landmark* currentLandmark, std::deque<Landmark*> currPath, std::deque<Landmark*> unique, int timeLeft, std::deque<Landmark*>& bestPath, unsigned& uniqueCount) {
+	if (timeLeft < 0) return;
+
+	bool currentExists = false;
+	for (const Landmark* l : unique) {
+		if (l == currentLandmark) {
+			currentExists = true;
+			break;
+		}
+	}
+	if (!currentExists)
+		unique.push_back(currentLandmark);
+
+	currPath.push_back(currentLandmark);
+
+	if (currentLandmark->name == "Railstation" && unique.size() > uniqueCount) {
+		bestPath = currPath;
+		uniqueCount = unique.size();
+	}
+
+	for (auto lp : currentLandmark->visitable) {
+		visitTheMostInTimeRec(lp.first, currPath, unique, timeLeft - lp.second, bestPath, uniqueCount);
+	}
+}
+
+std::deque<std::string> CityVisit::visitTheMostInTime(std::ifstream& inFile) {
+	landmarks.clear();
+	parse(inFile);
+
+	Landmark* station = find("Railstation");
+	if (station == nullptr)
+		throw std::logic_error("No landmark named Railstation exists!");
+
+	std::deque<Landmark*> outLandmarks;
+	unsigned uniqueCount = 0;
+	visitTheMostInTimeRec(station, std::deque<Landmark*>(), std::deque<Landmark*>(), availableTime, outLandmarks, uniqueCount);
+
+	std::deque<std::string> out;
+	for (Landmark* l : outLandmarks) {
+		out.push_back(l->name);
+	}
+	return out;
+}
diff --git a/Year 2/Structures and data algorithms/Project/exb/CityVisit.h b/Year 2/Structures and data algorithms/Project/exb/CityVisit.h
new file mode 100644
index 0000000..c513542
--- /dev/null
+++ b/Year 2/Structures and data algorithms/Project/exb/CityVisit.h
@@ -0,0 +1,30 @@
+#ifndef CITY
+#define CITY
+
+#include <string>
+#include <deque>
+#include <utility> // използвам само pair
+#include <fstream>
+
+class CityVisit {
+	struct Landmark {
+		std::string name;
+		std::deque<std::pair<Landmark*, unsigned>> visitable;
+
+		Landmark(const std::string& name) : name(name), visitable() {}
+	};
+
+	std::deque<Landmark*> landmarks;
+	unsigned availableTime;
+
+	Landmark* find(const std::string& name);
+	void visitTheMostInTimeRec(Landmark* currentLandmark, std::deque<Landmark*> currPath, std::deque<Landmark*> unique, int timeLeft, std::deque<Landmark*>& bestPath, unsigned& uniqueCount);
+
+public:
+	void pushLandmarks(const std::string& from, const std::string& to, unsigned time);
+
+	void parse(std::ifstream& inFile);
+	std::deque<std::string> visitTheMostInTime(std::ifstream& inFile);
+};
+
+#endif
diff --git a/Year 2/Structures and data algorithms/Project/exb/Plovdiv.txt b/Year 2/Structures and data algorithms/Project/exb/Plovdiv.txt
new file mode 100644
index 0000000..7270347
--- /dev/null
+++ b/Year 2/Structures and data algorithms/Project/exb/Plovdiv.txt
@@ -0,0 +1,10 @@
+6 8
+Railstation ArtGallery 26
+Railstation RomanStadium 20
+ArtGallery DzhumayaSquare 5
+ArtGallery HistoricalMuseum 14
+ArtGallery AntiqueTheatre 7
+RomanStadium DzhumayaSquare 2
+DzhumayaSquare HistoricalMuseum 18
+HistoricalMuseum AntiqueTheatre 12
+68
diff --git a/Year 2/Structures and data algorithms/Project/exb/Sofia.txt b/Year 2/Structures and data algorithms/Project/exb/Sofia.txt
new file mode 100644
index 0000000..f252f6e
--- /dev/null
+++ b/Year 2/Structures and data algorithms/Project/exb/Sofia.txt
@@ -0,0 +1,12 @@
+12 10
+Railstation G 1
+G D 1
+G F 1
+G E 1
+G B 1
+F B 1
+F E 1
+E B 1
+E D 1
+D B 1
+42
diff --git a/Year 2/Structures and data algorithms/Project/exb/main.cpp b/Year 2/Structures and data algorithms/Project/exb/main.cpp
new file mode 100644
index 0000000..118c79b
--- /dev/null
+++ b/Year 2/Structures and data algorithms/Project/exb/main.cpp
@@ -0,0 +1,19 @@
+#include "CityVisit.h"
+#include <iostream>
+
+int main() {
+	std::cout << "Име на град: ";
+	std::string fileName;
+	std::cin >> fileName;
+
+	std::ifstream inFile(fileName + ".txt");
+	if (!inFile.is_open())
+		throw std::logic_error("The given city has no .txt file!");
+
+	CityVisit cv;
+	std::deque<std::string> visited = cv.visitTheMostInTime(inFile);
+	inFile.close();
+	for (std::string v : visited)
+		std::cout << v << " ";
+	std::cout << std::endl;
+}