// Iterative C++ program to
// implement Stein's Algorithm
//#include <bits/stdc++.h>
#include <bitset>
using namespace std;

// Function to implement
// Stein's Algorithm
int gcd(int a, int b)
{
    /* GCD(0, b) == b; GCD(a, 0) == a,
    GCD(0, 0) == 0 */
    if (a == 0)
        return b;
    if (b == 0)
        return a;

    /*Finding K, where K is the
    greatest power of 2
    that divides both a and b. */
    int k;
    for (k = 0; ((a | b) & 1) == 0; ++k)
    {
        a >>= 1;
        b >>= 1;
    }

    /* Dividing a by 2 until a becomes odd */
    while ((a & 1) == 0)
        a >>= 1;

    /* From here on, 'a' is always odd. */
    do
    {
        /* If b is even, remove all factor of 2 in b */
        while ((b & 1) == 0)
            b >>= 1;

        /* Now a and b are both odd.
        Swap if necessary so a <= b,
        then set b = b - a (which is even).*/
        if (a > b)
            swap(a, b); // Swap u and v.

        b = (b - a);
    } while (b != 0);

    /* restore common factors of 2 */
    return a << k;
}

// Driver code
int main()
{
    int a = 12, b = 780;
    printf("Gcd of given numbers is %d\n", gcd(a, b));
    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.
	}

	}
	
}

//Leif Messinger
//Compile with C++ 20
#include <iostream>
#include <ranges>
#include <vector>
#include <functional>
#include <cctype> //toupper
#include <cxxabi.h>

template <typename T>
void printType(){
    std::cout << abi::__cxa_demangle(typeid(T).name(), NULL, NULL, NULL) << std::endl;
}

template <typename T>
class Slicer{
    public:
        T begin_;
        T end_;
        T trueEnd;
        Slicer(T begin, T end): begin_(begin), end_(begin), trueEnd(end){}
        template<typename U>
        Slicer(U&& vec) : begin_(vec.begin()), end_(vec.begin()), trueEnd(vec.end()){}
        Slicer& finish(){
            begin_ = end_;
            end_ = trueEnd;
            return (*this);
        }
        Slicer& to(long int index){
            begin_ = end_;
            if(index > 0){
                end_ = (begin_ + index);
            }else{
                index *= -1;
                end_ = (trueEnd - index);
            }
            return (*this);
        }
        Slicer& operator[](long int index){
            return to(index);
        }
        T begin(){
            return this->begin_;
        }
        T end(){
            return this->end_;
        }
        Slicer& operator()(std::function<void(decltype(*begin_))> func) {
            for(decltype(*begin_) thing : (*this)){
                func(thing);
            }
            return (*this);
        }
};
static_assert(std::ranges::range< Slicer<std::vector<int>::const_iterator> >);

int main(){
    std::string vec = "abcdefghijklmnopqrstuvwxyz";
    Slicer<std::string::const_iterator> bruh(vec);
    
    //printType<decltype(bruh)>();

    bruh.to(3)([](char yeet){
        std::cout << yeet;
    })
    .to(-1)([](char yeet){
        std::cout << char(std::toupper(yeet));
    }).finish()([](char yeet){
        std::cout << yeet << yeet << yeet << yeet << yeet;
    });
    
    std::cout << std::endl << std::endl;
    
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
    Slicer<int*> arrSlicer(arr, arr + (sizeof(arr)/sizeof(int)));
    
    std::cout << "[";
    arrSlicer.to(-1)([](int yeet){
        std::cout << yeet << ", ";
    }).finish()([](int yeet){
        std::cout << yeet << "]" << std::endl;
    });

    return 0;
}

#include <iostream>
#include <string>	//Should already be in iostream
#include <cstdlib>

//A word score adds up the character values. a-z gets mapped to 1-26 for the values of the characters.

//wordScore [wordValue]
//Pipe in the input into stdin, or type the words yourself.

//Lowercase words only
int characterValue(const char b){
	return ((b >= 'a') && (b <= 'z'))? ((b - 'a') + 1) : 0;
}

int main(int argc, char** argv){
    //The first argument specifies if you are trying to look for a certain word score
	int wordValue = (argc > 1)? std::atoi(argv[1]) : 0;

	std::string line;
	while(std::getline(std::cin, line)){
		int sum = 0;
		for(const char c : line){
			sum += characterValue(c);
		}
		if(wordValue){	//If wordValue is 0 or the sum is the correct value
			if(wordValue == sum){
				std::cout << line << std::endl;
			}
		} else {
			std::cout << sum << "\t" << line << std::endl;
		}
	}
	return 0;
}

//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 <iostream>
#include <cstring>
#include <unistd.h>
#include <sys/utsname.h>

int main() {
    char newHostname[] = "newhostname"; // Replace with the desired hostname

    if (sethostname(newHostname, strlen(newHostname)) == 0) {
        std::cout << "Hostname set to: " << newHostname << std::endl;

        // Optionally, update the /etc/hostname file to make the change permanent
        FILE *hostnameFile = fopen("/etc/hostname", "w");
        if (hostnameFile != NULL) {
            fprintf(hostnameFile, "%s\n", newHostname);
            fclose(hostnameFile);
        } else {
            perror("Failed to update /etc/hostname");
        }
    } else {
        perror("Failed to set hostname");
    }

    return 0;
}