//Constant prefix notation solver using bruh
//Could make it infix or postfix later
#include<string>
#include<vector>
#include<iostream>

std::vector<long double> bruhBuff;

long double operator ""bruh(long double a){
    bruhBuff.push_back(a);
    return a;
}

long double operator ""bruh(const char op){
    if(bruhBuff.size() < 2) throw "Bruh weak";
    
    long double b = bruhBuff.back();
    bruhBuff.pop_back();
    long double a = bruhBuff.back();
    bruhBuff.pop_back();
    
    
    switch(op){
        case (int)('+'):
            return a + b;
        case (int)('-'):
            return a - b;
        case (int)('*'):
            return a * b;
        case (int)('/'):
            return a / b;
    }
    return 69l;
}
 
int main(){
    1.0bruh;
    2.0bruh;
    std::cout << '+'bruh << std::endl;
    
    return 0;
}

#include <bits/stdc++.h>
#define MAXSIZE 50000
#define INF 100000

using namespace std;

vector<int> adj[MAXSIZE]; //Adjacency List

bool visited[MAXSIZE]; //Checks if a node is visited or not in BFS and DFS
bool isConnected = true; //Checks if the input graph is connected or not

int dist[MAXSIZE], discover[MAXSIZE], finish[MAXSIZE]; //Distance for BFS, in time and out time for DFS
int t = 1; //Time used for DFS
int u, v, i, j, k, N = 0;

stack<int> st; //Stack for TopSort

multiset<pair<int, int>> s; //collection of pairs to sort by distance
pair<int, int> current; //pointer variable to a position in the multiset

void BFS()
{
	queue<int> q; //queue for BFS
	q.push(1); //pushing the source
	dist[1] = 0; //assign the distance of source as 0
	visited[1] = 1; //marking as visited
	
	while(!q.empty())
	{
	u = q.front();
	q.pop();

	for(i=0; i < adj[u].size(); i++)
	{
	v = adj[u][i]; //Adjacent vertex

	if(!visited[v]) //if not visited, update the distance and push onto queue
	{
	visited[v] = 1;
	dist[v] = dist[u]+1;
	q.push(v);
	}

	}

	}
	
	for(i = 1; i <= N; i++)
	{
	s.insert(make_pair(dist[i], i)); //for sorted distance
	}
	
	cout << "BFS results:" << endl;
	
	//prints BFS results and checks if the graph is connected
	while(!s.empty())
	{
	current = *s.begin(); 
	s.erase(s.begin());

	i = current.second; 
	j = current.first;

	if(j == INF) //if any infinite value, graph is not connected
	{
	cout << i << " INF" << endl;
	isConnected = false;
	}
	else
	{
	cout << i << " " << j << endl;
	}

	}

	//marks blocks of memory as visited
	memset(visited, 0, sizeof visited);
}


void dfsSearch(int s)
{
	visited[s] = 1; //marking it visited
	discover[s] = t++; //assigning and incrementing time

	int i, v;

	for(i = 0; i < adj[s].size(); i++)
	{
	v = adj[s][i];

	if(!visited[v]) //if vertex is not visited then visit, else continue
	{
	dfsSearch(v);
	}

	}

	st.push(s); //pushed onto stack for TopSort if it was called
	finish[s] = t++; //out time
}

void DFS()
{

	for(i = 1; i <= N; i++)
	{
	if(visited[i]) //if visited continue, else visit it with DFS
	{
	continue;
	}

	dfsSearch(i); //embedded function to actually perform DFS
	}

	for(i=1;i<=N;i++)
	{
	s.insert(make_pair(discover[i], i)); //minheap for sorted discovery time
	}
	
	cout << "DFS results:" << endl;

	while(!s.empty()) //Prints DFS results as long as the multiset is not empty
	{
	current = *s.begin(); //duplicates the pointer to first object in the multiset
	s.erase(s.begin()); //erases the first object in multiset

	i = current.second;
	cout << i << " " << discover[i] << " " << finish[i] << endl; //prints discover times and finish times
	}

}

void TopSort()
{
	//call DFS so we can have a sorted stack to print
	for(i=1;i<=N;i++)
	{
	if(visited[i])
	{
	continue;
	}

	dfsSearch(i);
	}

	cout<<"Topological Sort results:"<<endl;

	//print sorted results from DFS
	while(!st.empty())
	{
	i = st.top(); 
	st.pop();

	cout << i << endl;
	}

	//declare blocks of memory as visited
	memset(visited, 0, sizeof visited);

}


int main()
{
	string str, num, input;
	int selection, connectedChoice = 0;


	//get to input any file, more freedom than declaring file in command line
	cout << "Enter the exact name of your input file [case sensitive]: ";
	cin >> input;
	
	ifstream inputFile(input); //Read the input file

	//checks if the ifstream cannot open
	if(inputFile.fail())
	{
	cout << endl << "No input files matching that name. Terminating..." << endl;
	return 0;
	}

	//Read until the end of file
	while(!inputFile.eof())
	{
	getline(inputFile, str); //read the current line

	if(str == "")
	{
	continue;
	}

	if(!isdigit(str[0])) //checks to see if the first item in a line is a digit or not
	{
	cout << "Invalid file format. You have a line beginning with a non-digit. Terminating..." << endl;
	return 0;
	}

	stringstream ss;
	ss << str; //convert the line to stream of strings
	
	ss >> num; //read the line num
	stringstream(num) >> u;
	
	while(!ss.eof())
	{
	ss>>num;
	if(stringstream(num) >> v)
	{
	adj[u].push_back(v); //read the adjacent vertices
	}
	}

	N++; //calculate the number of vertices
	sort(adj[u].begin(), adj[u].end()); //sort the adjacency list in case it is not sorted
	}
	
	//creates arbitrary values for distance, will check later if INF remain
	for(i = 1; i <= N; i++)
	{
	dist[i] = INF;
	}

	cout << endl << "Valid Input file loaded!" << endl;

	while(selection != 4)
	{
	cout << "************************************************" << endl;
	cout << "What type of analysis would you like to perform?" << endl;
	cout << "1: Breadth-First Search" << endl;
	cout << "2: Depth-First Search" << endl;
	cout << "3: Topological Sort" << endl;
	cout << "4: Quit" << endl;
	cout << "************************************************" << endl;
	
	//read user input and execute selection
	cin >> selection;

	switch(selection)
	{
	case 1:
	cout << endl;
	BFS();
	cout << endl;
	cout << "Would you like to know if the graph is connected?" << endl;
	cout << "1: Yes" << endl;
	cout << "Any other key: No" << endl;
	cin >> connectedChoice;

	switch(connectedChoice)
	{
	case 1:
	if(!isConnected)
	{
	cout << "The graph is not connected." << endl << endl;
	}
	else
	{
	cout << "The graph is connected!" << endl << endl;
	}
	break;
	default:
	break;
	}
	break;
	case 2:
	cout << endl;
	DFS();
	cout << endl;
	break;
	case 3:
	cout << endl;
	TopSort();
	cout << endl;
	break;
	case 4:
	return 0;
	default:
	cout << endl << "Invalid selection." << endl; //loops the selection prompt until a valid selection is input.
	}

	}
	
}

#include <iostream>
using namespace std;

int main() {
  const int ROW_SIZE = 2;
  const int COLUMN_SIZE = 5;              //establish all variables
  int matrix[ROW_SIZE][COLUMN_SIZE];
  int minVal;

  for (int i = 0; i < ROW_SIZE; ++i)    // for loop to ask user to enter data.
  {
    for (int h = 0; h < COLUMN_SIZE; ++h) {
      cout << "Enter data for row #" << i + 1 << " and column #" << h + 1 << ": ";
      cin >> matrix[i][h];
    }
  }
  cout << "You entered: " << endl;
  for (int i = 0; i < ROW_SIZE; ++i) //for statements to output the array neatly
  {
    for (int h = 0; h < COLUMN_SIZE; ++h) {
      cout << matrix[i][h] << "\t";
    }
    cout << endl;
  }

  cout << "Minimum for each row is: {";
  for (int i = 0; i < ROW_SIZE; i++) //for statements to find the minimum in each row
  {
    minVal = matrix[i][0];

    for (int h = 0; h < COLUMN_SIZE; h++) {
      if (matrix[i][h] < minVal) // if matrix[i][h] < minVal -> minVal = matrix[i][h];
      {
        minVal = matrix[i][h];
      }
    }
    cout << minVal << ", ";
  }
  cout << "}" << endl;

  cout << "Minimum for each column is: {";
  for (int i = 0; i < COLUMN_SIZE; i++) //for statements to find the minimum in each column
  {
    minVal = matrix[0][i];
    for (int h = 0; h < ROW_SIZE; h++) {
      if (matrix[h][i] < minVal) //replaces minVal with array index for that column that is lowest
      {
        minVal = matrix[h][i];
      }
    }
    cout << minVal << ", ";
  }
  cout << "}" << endl;

  return 0;
}

#include <iostream>
using namespace std;

int main() {

cout << "Hello World!\n";
// Prints out "Hello World"
return 0;

}

/*
Algorithm:
Step 1: Get radius of the cylinder from the user and store in variable r
Step 2: Get height of the cylinder from the user and store in variable h
Step 3: Multiply radius * radius * height * pi and store in v
Step 4: Display the volume
*/

#include <iostream>
using namespace std;


int main()
{
        float r; //define variable for radius
        float h; //define variable for height
        float v;
        float pi;
        pi=3.1416;

        cout<<"Enter radius:";
        cin>>r;

        cout<<"Enter height:";
        cin>>h;

        v=r*r*h*pi;  //compute volume

        cout<<"Radius:"<<r<<"\tHeight:"<<h<<endl; //display radius and height

        cout<<"\n************************\n";

        cout<<"Volume:"<<v<<endl;//display volume

        return 0;
}

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