From c79f7ea4ac93a9b11bff676d4174f5de46e0015b Mon Sep 17 00:00:00 2001 From: Syndamia Date: Thu, 29 Dec 2022 17:43:27 +0200 Subject: [SDP/P/exb] Solved exercise B --- .../Project/exb/City.cpp | 84 ++++++++++++++++++++++ 1 file changed, 84 insertions(+) create mode 100644 Year 2/Structures and data algorithms/Project/exb/City.cpp (limited to 'Year 2/Structures and data algorithms/Project/exb/City.cpp') 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 + +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 currPath, std::deque unique, int timeLeft, std::deque& 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 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 outLandmarks; + unsigned uniqueCount = 0; + visitTheMostInTimeRec(station, std::deque(), std::deque(), availableTime, outLandmarks, uniqueCount); + + std::deque out; + for (Landmark* l : outLandmarks) { + out.push_back(l->name); + } + return out; +} -- cgit v1.3.1-26-gb76a