Wing Project 1 | C++

October 30th, 2021 06:20:44 PM

					
//Get data file at https://codecatch.net/post.php?postID=91e87d73 //Iteration 1 of Wing Project. Solution breaks down around n=35 #include <iostream> #include <fstream> #include <string> #include <vector> #include <map> using namespace std; int getSum(map<int, int> list); void readData(map<int, float>* data); void lowestPrice(); void findSums(int n, vector<map<int, int>>* sumsList, map<int, float>* data); //void findSum(map<int, int> currList, int x, int n, vector<map<int, int>>* sumsList); void findSum(map<int, int> currList, int x, int n, vector<map<int, int>>* sumsList, map<int, float>* data); float getPrice(map<int, int> set, map<int, float>* data); template <typename S> ostream& operator<<(ostream& os, const vector<S>& vector) { // Printing all the elements using << for (auto element : vector) { os << element << " "; } return os; } bool operator==(map<int, int> m1, map<int, int> m2) { if(m1.size() != m2.size()) return false; bool ret = true; for(auto it = m1.begin(); it !=m1.end() && ret; it++) { if(ret && m1.count(it->first) != m2.count(it->first)) ret = false; if(ret && m1.count(it->first) == 1) { if(m1.at(it->first) != m2.at(it->first)) ret = false; } } return ret; } int main() { map<int, float> data; readData(&data); vector<map<int, int>> *sumsList; sumsList = new vector<map<int, int>>; findSums(40, sumsList, &data); for(auto el : *sumsList) { for(auto it = el.begin(); it != el.end(); it++) { cout << it->first << "->" << it->second << " "; } cout << getPrice(el, &data) << endl; } return 0; } /* Returns the price of wings given a set of numbers of wings to buy. * Returns -1 if the set contains a number that is not possible to buy. */ float getPrice(map<int, int> set, map<int, float>* data) { float price = 0; for(auto it = set.begin(); it != set.end(); it++) { //If data doesn't contain an element of set, return -1 if(data->count(it->first) == 0) return -1; price += data->at(it->first) * it->second; //pricePerPacket * qtyOfPackets } return price; } /* Adds the elements of list. * Suppose mapping is <num, qty>. * Returns sum(num*qty) */ int getSum(map<int, int> list) { int sum = 0; for(auto it = list.begin(); it != list.end(); it++) sum += it->first * it->second; return sum; } void findSums(int n, vector<map<int, int>>* sumsList, map<int, float>* data) { map<int, int> currList; //Recur when currSum < n auto it = data->begin(); while(it->first <= n && it != data->end()) { findSum(currList, it->first, n, sumsList, data); it++; } } void findSum(map<int, int> currList, int x, int n, vector<map<int, int>>* sumsList, map<int, float>* data) { //Append x to currList if(currList.count(x) == 0) currList.emplace(x, 1); else { int val = 1+ currList.at(x); currList.erase(x); currList.emplace(x, val); } //Determine current sum, check for return cases int currSum = getSum(currList); if(currSum > n) return; else if(currSum == n) { //Check to make sure no duplicates for(auto list : *sumsList) { if(list == currList) return; } sumsList->push_back(currList); return; } //Recur when currSum < n auto it = data->begin(); while(it->first <= n-x && it != data->end()) { findSum(currList, it->first, n, sumsList, data); it++; } } void readData(map<int, float>* data) { ifstream file ("./data", ifstream::in); if(file.is_open()) { int i = 0; while(!file.eof()) { float wings, price; string skipnl; file >> wings; file >> price; data->emplace(wings, price); getline(file, skipnl); i++; } } }

Featured Posts