# Wing Project 1 | C++

## aedrarian

### 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 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;

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++;
}
}

{
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++;
}
}
}
```