//===============Header File==================
#include <iostream>
#include <sstream> //stringbuf
#include <utility> //exchange

//Couple rules:
//Characters given through the getter functions have to be removed from the buffer.
    //This is so that bufferEmpty() == buffer.in_avail() > 0 basically always.
    //skipWhitespace doesn't remove the text from the buffer, but it does return the number of characters.
//nextWord will trim whitespace before the word
//nextInt will trim non-numbers before the number
//hasNextInt and hasNextWord will trim the whitespace. If you think you need it, you should get nextWhitespace before doing any of those.
//Whitespace after a word or an int is left on the buffer.
//nextWhitespace will (get and) remove whitespace until the end of the line, including the newline character, but stops before the next line.
    //nextWhitespace won't read the next line when called before the end of the line, and it won't prompt the user for the next line if interactive.
        //If nextWhitespace is called after reading the end of the line, then it will read a new line into the buffer, which will prompt the user.
    //It acts like nextLine, but if there's something non-whitespace on the current line it stops there.
class Scanner {
    public:
        std::stringbuf buffer;
        std::istream& input;
        
        Scanner(std::istream& in = std::cin) : buffer(), input(in) {}
        
    //Buffer debugging
        bool fillBuffer();
    
        bool bufferEmpty();
        void printBufferEmpty();
        std::string getBuffer();
        size_t bufferLength();
        void printBufferStats();
    
    //Int
        bool hasNextInt();
        int nextInt();
    
    //Word
        bool hasNextWord();
        std::string nextWord();
    
    //Line
        bool hasNextLine();
    
    //Whitespace
        size_t skipWhitespace();    //Prob should be private, but I don't believe in that private shit.
        bool hasNextWhitespace();
        std::string nextWhitespace();
        std::string nextWhitespaceAll();
        std::string nextLine();
};

//===============Source File==================
bool Scanner::fillBuffer() {    //Returns if it had to get the next line from the input.
    const bool badInput = input.eof() || input.bad();
    const bool shouldFillBuffer = bufferEmpty() && !badInput;
    if (shouldFillBuffer) {
        std::string line;
        if (std::getline(input, line)) {
            buffer.str(buffer.str() + line + "\n");
        }
    }
    return shouldFillBuffer;
}

bool Scanner::bufferEmpty(){
    return buffer.str() == "";
}
void Scanner::printBufferEmpty(){
    std::cout << "The buffer is " << (bufferEmpty()? "" : "not") << " empty." << std::endl;
}

std::string Scanner::getBuffer(){
    return buffer.str();
}
size_t Scanner::bufferLength(){
    return buffer.str().length();
}
void Scanner::printBufferStats(){
    if(bufferEmpty()){
        std::cout << "The buffer is \"\"" << std::endl;
        return;
    }
    std::cout << "The length of the buffer is " << bufferLength() << std::endl;
    if(buffer.sgetc() == '\r'){
        std::cout << "The buffer is \\r\\n" << std::endl;
    }else if(buffer.sgetc() == '\n'){
        std::cout << "The buffer is \\n" << std::endl;
    }
}

bool Scanner::hasNextInt() {
    return hasNextWord() && (std::isdigit(buffer.sgetc()) || buffer.sgetc() == '-');
}

int Scanner::nextInt() {
    if (!hasNextInt()) {   //Will fill the buffer if not filled. Will also trim whitespace.
        return 0;
    }
    
    std::string num;
    size_t charactersRead = 0;
    while (buffer.in_avail() > 0 && (std::isdigit(buffer.sgetc()) || buffer.sgetc() == '-')) {
        num += buffer.sbumpc();
        ++charactersRead;
    }
    buffer.str(buffer.str().erase(0, charactersRead));
    return std::stoi(num);
}

bool Scanner::hasNextWord() {
    nextWhitespaceAll();
    return buffer.in_avail() > 0;
}

std::string Scanner::nextWord() {
    if (!hasNextWord()) {   //Will fill the buffer if not filled. Will also trim whitespace.
        return "";
    }
    
    std::string word;
    size_t charactersRead = 0;
    while (buffer.in_avail() > 0 && !std::isspace(buffer.sgetc())) {
        word += buffer.sbumpc();
        ++charactersRead;
    }
    buffer.str(buffer.str().erase(0, charactersRead));
    return word;
}

bool Scanner::hasNextLine() {
    return (!bufferEmpty()) || fillBuffer();
}

size_t Scanner::skipWhitespace() {   //Returns characters read
    size_t charactersRead = 0;
    while (buffer.in_avail() > 0 && std::isspace(buffer.sgetc())) {
        buffer.sbumpc();
        ++charactersRead;
    }
    return charactersRead;
}
bool Scanner::hasNextWhitespace(){
    fillBuffer();
    return buffer.in_avail() > 0 && std::isspace(buffer.sgetc());
}
std::string Scanner::nextWhitespace() {
    if (!hasNextWhitespace()) {   //Will fill the buffer if not filled
        return "";
    }
    const size_t charactersRead = skipWhitespace();
    std::string whitespace = buffer.str().substr(charactersRead);
    buffer.str(buffer.str().erase(0, charactersRead));
    return whitespace;
}
std::string Scanner::nextWhitespaceAll(){
    std::string whitespace;
    while(hasNextWhitespace()){
        std::string gottenWhiteSpace = nextWhitespace();
        whitespace += gottenWhiteSpace;
    }
    return whitespace;
}
std::string Scanner::nextLine(){
    if (!hasNextLine()) {
        return "";
    }
    
    fillBuffer();
    //Swap out the old buffer with an empty buffer, and get the old buffer as a variable.
    std::string line = std::exchange(buffer, std::stringbuf()).str();
    
    //Remove the newline.
    if(line[line.length() - 1] == '\n' || line[line.length() - 1] == '\r' ) line.pop_back();
    if(line[line.length() - 1] == '\r' || line[line.length() - 1] == '\n' ) line.pop_back();
    return line;
}


//=================Word and Int test=================
while(bruh.hasNextInt() || bruh.hasNextWord()){
    std::cout << "started loop" << std::endl;
    if(bruh.hasNextInt()){
        std::cout << "Int: " << bruh.nextInt() << " " << std::endl;
    }else{
        std::cout << "Word: " << bruh.nextWord() << " " << std::endl;
    }
    bruh.nextWhitespace();
}
//===================Line test======================
for(int count = 1; bruh.hasNextLine(); ++count){
    std::string line = bruh.nextLine();
    std::cout << "Line " << count << ": " << line << std::endl;
}

#define NUM_BITS 8

#include <iostream>


struct Number{
    int num : NUM_BITS;
    Number(){}
    Number(const int& bruh){
        num = bruh;
    }
    operator int() const { return num; }
    Number& operator=(const int& bruh){
        num = bruh;
        return (*this);
    }
};

using namespace std;

bool isNegative(const int& num){
    //This gets the bitwise and of num and 10000000000000000000000000000000
    //This implicit casts to bool, which means (num & (1 << 31)) != 0
    return (num & (1 << 31));
}

void printBinaryNumber(const int& num, const int numBits){
    for(int i = numBits; i > 0; --i){
        //8..1
        int bitMask = 1 << (i-1);
        if(num & bitMask){ //Test the bit
            cout << '1';
        }else{
            cout << '0';
        }
    }
}

void printCarryBits(const int& a, const int& b, const int numBits){
    int answer = 0;
    
    bool carry = false;
    for(int i = 0; i < numBits; ++i){
        //8..1
        int bitMask = 1 << i;
        bool aBit = a & bitMask;
        bool bBit = b & bitMask;
        if(aBit && bBit || aBit && carry || bBit && carry){ //Carry bit is true next
            if(carry)
                answer |= bitMask;
            carry = true;
        }else{
            if(carry)
                answer |= bitMask;
            carry = false;
        }
    }
    printBinaryNumber(answer, 8);
}


void printBorrowBits(const int& a, const int& b, const int numBits){
    int answer = 0;
    
    bool carry = false;
    for(int i = 0; i < numBits; ++i){
        //8..1
        int bitMask = 1 << i;
        bool aBit = a & bitMask;
        bool bBit = b & bitMask;
        if((!(aBit ^ carry)) && bBit){ //Carry bit is true next
            if(carry)
                answer |= bitMask;
            carry = true;
        }else{
            if(carry)
                answer |= bitMask;
            carry = false;
        }
    }
    printBinaryNumber(answer, 8);
}

void doProblem(const int& a, const int& b, const char& sign, const int& result, const int& numBits){
    if(sign == '+'){
        cout << ' '; printCarryBits(a, b, numBits); cout << endl;
    }else{
        cout << ' '; printBorrowBits(a, b, numBits); cout << endl;
    }
    cout << ' '; printBinaryNumber(a, numBits); cout << endl;
    cout << sign; printBinaryNumber(b, numBits); cout << endl;
    cout << "----------" << endl;
    cout << ""; printBinaryNumber(result, numBits + 1); cout << " = " << result;
    cout << endl;
}

int main(){
    
    Number a = 0b110;
    Number b = 0b011;
    cout<< a << endl << b << endl;
    
    doProblem(a, b, '+', a + b, NUM_BITS);
    doProblem(a, b, '-', a - b, NUM_BITS);
    doProblem(-a, b, '+', -a + b, NUM_BITS);
    doProblem(a, b, '-', -a - b, NUM_BITS);
    

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

#include<iostream>
using namespace std;

const int rows = 8;
const int cols = 8;
char chessboard[rows][cols];

void setBoard(char chessboard[][cols]);
void printBoard(char chessboard[][cols]);

void setBoard(char chessboard[][cols]) {
    for(int i = 0; i < rows; i++) {
        for(int j = 0; j < cols; j++) {
            if(i % 2 == 0 && j % 2 == 0) {
                chessboard[i][j] = 'x';
            } else {
                if(i % 2 != 0 && j % 2 == 1) {
                    chessboard[i][j] = 'x';
                } else {
                    chessboard[i][j] = '-';
                }
            }
        }
    }
    return;
}

void printBoard(char chessboard[][cols]) {
    for(int i = 0; i < rows; i++) {
        for(int j = 0; j < cols; j++) {
            cout << chessboard[i][j] << " ";
        }
        cout << endl;
    }
    return;
}

int main(int argc, char const *argv[])
{
    setBoard(chessboard);
    printBoard(chessboard);
    return 0;
}

/*
Good morning! Here's your coding interview problem for today.

This problem was asked by LinkedIn.

A wall consists of several rows of bricks of various integer lengths and uniform height. Your goal is to find a vertical line going from the top to the bottom of the wall that cuts through the fewest number of bricks. If the line goes through the edge between two bricks, this does not count as a cut.

For example, suppose the input is as follows, where values in each row represent the lengths of bricks in that row:

[[3, 5, 1, 1],
	[2, 3, 3, 2],
	[5, 5],
	[4, 4, 2],
	[1, 3, 3, 3],
	[1, 1, 6, 1, 1]]

The best we can we do here is to draw a line after the eighth brick, which will only require cutting through the bricks in the third and fifth row.

Given an input consisting of brick lengths for each row such as the one above, return the fewest number of bricks that must be cut to create a vertical line.

AUTHORS NOTE:
Makes following assumptions:
- Each row is same length
- Data is in file called "data.dat" and formatted in space-separated rows
- The cuts at the beginning and end of the wall are not solutions

This requires the following file named data.dat that is a space separated file, or similar formatted file:
----START FILE----
3 5 1 1
2 3 3 2
5 5
4 4 2
1 3 3 3
1 1 6 1 1
----END FILE----
*/

#include <algorithm>
#include <iostream>
#include <fstream>
#include <map>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

int main()
{
	vector<vector<int>> wall;

	ifstream in;
	in.open("data.dat");
	if(!in.good())
	{
	cout << "ERROR: File failed to open properly.\n";
	}

	/* Get input from space separated file */
	string line;
	while(!in.eof())
	{
	getline(in, line);

	int i;
	vector<int> currv;
	stringstream strs(line);
	while(strs >> i)
	currv.push_back(i);
	wall.push_back(currv);
	}

	

	/* Convert each value from "length of brick" to "position at end of brick" */
	for(int y = 0; y < wall.size(); y++)
	{
	wall.at(y).pop_back(); //Delet last val
	for(int x = 1; x < wall.at(y).size(); x++) //Skip the first bc data doesn't need change
	wall.at(y).at(x) += wall.at(y).at(x-1);
	}

	/* Check output. COMMENT OUT */
	// for(auto row : wall)
	// {
	// for(int pos : row)
	// cout << pos << " ";
	// cout << endl;
	// }

	/* Determine which ending position is most common, and cut there */
	//Exclude final position, which will be the size of the wall

	int mode = -1;
	int amt = -1;
	vector<int> tried;
	for(auto row : wall)
	{
	for(int pos : row) //For each pos in the wall
	{
	//Guard. If pos is contained in the list, skip pos
	if(find(tried.begin(), tried.end(), pos) != tried.end())
	continue;
	tried.push_back(pos);

	/* Cycle through each row to see if it contains the pos */
	int curramt = 0;
	for(auto currrow : wall)
	{
	if( find( currrow.begin(), currrow.end(), pos ) != currrow.end() )
	curramt++;
	}
	//cout << pos << " " << curramt << endl; 

	if(curramt > amt)
	{
	amt = curramt;
	mode = pos;
	}
	}
	}

	cout << "Please cut at position " << mode << endl;
	cout << "This will cut through " << (wall.size() - amt) << " bricks." << endl;

	return 0;
}