Skip to main content
Loading...

More C++ Posts

#include <iostream>
#include <vector>
#include <limits>

#define DEBUG_TRIAL false

class Trial{
    public:
        const size_t HEIGHT;
        std::string record;
        
        //Breaking height is the index of the floor, so 0 is the bottom floor, height-1 is the top floor.
        //Eggs is the eggs remaining.
        //Start is the bottom floor.
        //End is one above the top floor.
        const size_t BREAKING_HEIGHT;
        size_t eggs;
        size_t start;
        size_t end;
        
        
        size_t floorsLeft(){
            return (end-start);
        }
        
        size_t middle(){
            return start + (floorsLeft()/2UL);
        }
        
        size_t drops = 0;
        Trial(const size_t BREAKING_HEIGHT, size_t eggs, size_t start, size_t end): BREAKING_HEIGHT(BREAKING_HEIGHT), eggs(eggs), start(start), end(end), HEIGHT(end), record(end, '_'){
            record[BREAKING_HEIGHT] = 'B'; //Marking the breaking point
        }
        
        bool foundAnswer(){
            return ((record[0] == 'X') || (record.find("OX")!=std::string::npos));
        }
        
        //returns true if the egg broke.
        //height is the index of the floor, so 0 is the bottom floor, height-1 is the top floor.
        bool drop(size_t height){
            
            #if DEBUG_TRIAL
                std::cout << "Start: " << start << ". End: " << end << ". Floors Left: " << floorsLeft() << ". Middle Index: " << middle() << std::endl;
            #endif
            
            drops++;
            bool cracked = height >= BREAKING_HEIGHT;
            if(cracked) --eggs;
            
            //Update the record
            record[height] = (height >= BREAKING_HEIGHT)? 'X' : 'O';
            
            #if DEBUG_TRIAL
                //Print the record
                std::cout << record << std::endl;
            #endif
        
            return cracked;
        }
        
        size_t nowWhat(){
            if(foundAnswer()){
                return drops;
            }else if(eggs <= 0){ //Ran out of eggs
                throw "Algorithm failed! No more eggs!";
                return 1UL;
            }else if(eggs > 1){
                return wrecklessSearch();
            }else{
                return safeSearch();
            }
        }
        
        size_t safeSearch(){
            if(drop(start)){
                --end;
            }else{
                ++start;
            }
            
            return nowWhat();
        }
        
        size_t wrecklessSearch(){
            //If the egg breaks
            if(drop(middle())){
                end -= (floorsLeft()/2UL);
            }else{ //egg doesn't crack
                start += (floorsLeft()/2UL);
            }
            
            return nowWhat();
        }
        
        //returns the amount of drops needed to find the answer
        size_t search(){
            return nowWhat();
        }
};

//Height is the height of the building in floors.
//Breaking height is the index of the floor, so 0 is the bottom floor, height-1 is the top floor.
//Eggs is the eggs given.
//returns the amount of drops needed to find the answer
size_t search(const size_t height, const size_t BREAKING_HEIGHT, size_t eggs){
    Trial trial(BREAKING_HEIGHT, eggs, 0, height);
    return trial.search();
}

class TrialStats {
    public:
        size_t min = std::numeric_limits<size_t>::max();
        size_t max = 0;
        double mean = -1.0;
        
        void printStats(){
            // Print the results
            std::cout << "Minimum drops: " << min << std::endl;
            std::cout << "Maximum drops: " << max << std::endl;
            std::cout << "Mean drops: " << mean << std::endl;
        }
};

//Benchmarks all the possible breaking points of a single building height with a number of eggs.
TrialStats trial(const size_t HEIGHT, const size_t eggs){
    
    TrialStats stats;
    int totaldrops = 0;

    //Test every possible breaking point
    //Breaking height is the index of the floor, so 0 is the bottom floor, height-1 is the top floor.
    for (int breakingHeight = 0; breakingHeight < HEIGHT; ++breakingHeight) {
        size_t drops = search(HEIGHT, breakingHeight, eggs);

        stats.min = std::min(stats.min, drops);
        stats.max = std::max(stats.max, drops);
        totaldrops += drops;
    }

    // Calculate the mean number of drops
    stats.mean = static_cast<double>(totaldrops) / HEIGHT;
    
    return stats;
}

//Benchmarks a single building height from 1 egg to MAX_EGGS
void testTower(const size_t height, const size_t MAX_EGGS){
    //Drop every amount of eggs that you'd need.
    for (int eggs = 1; eggs <= MAX_EGGS; ++eggs) {
        std::cout << "Building height: " << height << ". Num eggs: " << eggs << std::endl;
        
        TrialStats stats = trial(height, eggs);
        stats.printStats();
        
        std::cout << std::endl << std::endl;
    }
}

//Benchmarks all buildings from 0 to MAX_HEIGHT
void benchmark(const size_t MAX_HEIGHT){
    const size_t MAX_EGGS = 2;
    //Test every building
    for (size_t height = 1; height <= MAX_HEIGHT; ++height) {
        testTower(height, std::min(height, MAX_EGGS));
    }
}

int main() {
    constexpr size_t MAX_HEIGHT = 36;
    
    benchmark(MAX_HEIGHT);

    return 0;
}
/*
this program will simulate the spreading of a disease through a 
grid of people, starting from a user-defined person. It will count
the number of turns taken before everyone on the grid is immunized
to the disease after having caught it once.
This program will user the SIR model (Susceptible, Infectious, Recovered)
 and cellular automata to simulate the people in the grid.
*/
#include <iostream>
using namespace std;

/* Any and all global variables */
const int SIZE = 8; //Size of the square person array

/* Any and all functions */
void gridDefaultify(char[][SIZE], int);
	//Purpose: Sets each item in the person array to 's'
	//Parameters: A square, two-dimensional array
	//            The size of that array's bounds
void gridDisplay(char[][SIZE], int);
	//Purpose: Formats and prints the information in the person grid
	//Parameters: A square, two-dimensional array
	//            The value of the current day
void nextTurn(char[][SIZE], char[][SIZE], int&);
	//Purpose: Updates the grid of people, and the current day
	//Parameters: Two square, two-dimensional arrays
	//            A reference to the current day (so that it can be updated)
int countInfected(char[][SIZE], int);
	//Purpose: Counts the number of infectious people on the grid
	//Parameters: A square, two-dimensional array
	//            The size of that array's bounds


int main(){
	int currentDay = 0; //Infection begins on day 0, and ends one day after the last person is Recovered
	char gridCurrent[SIZE][SIZE]; //Grid of all people
	char gridUpdate[SIZE][SIZE]; //Where the user chooses to start the infection
	int xToInfect;
	int yToInfect; //Set of coordinates for the initial infection position, given by user
	
	//Initializes the grids to all 's'
	gridDefaultify(gridCurrent, SIZE);
	gridDefaultify(gridUpdate, SIZE);
	
	//The below block gets the initial infection coordinates from the user
	cout << "Please enter a location to infect: ";
	while(true){
		cin >> xToInfect >> yToInfect;

		xToInfect--;
		yToInfect--;
		
		if(xToInfect < 0 || yToInfect < 0 || xToInfect >= SIZE || yToInfect >= SIZE){
			cout << "Those coordinates are outside the bounds of this region." << endl;
			cout << "Please enter another location to infect: ";
			continue;
		} else {
			gridCurrent[xToInfect][yToInfect] = 'i';
			break;
		}
	}
	
	//Displays the initial state of the grid
	gridDisplay(gridCurrent, currentDay);
	
	//The below block will display and update the grid until the infection is done.
	while(true){
		nextTurn(gridCurrent, gridUpdate, currentDay);
		gridDisplay(gridCurrent, currentDay);
		if(countInfected(gridCurrent, SIZE) == 0) break; //Once there are no more infected, the game is done
	}
	
	//Displays the number of days taken for the infection to end
	cout << "It took " << currentDay + 1 << " days for the outbreak to end";
	
	cout << endl;
	return 0;
}

void gridDefaultify(char arr[][SIZE], int arrSize){
	for(int x = 0; x < arrSize; x++){
		for(int y = 0; y < arrSize; y++){
			arr[x][y] = 's'; //Sets all items in the passed-in array to 's'
		}
	}
	return;
}

void gridDisplay(char arr[][SIZE], int day){
	cout << "Day " << day << endl; //Prints the current day
	for(int x = 0; x < SIZE; x++){
		for(int y = 0; y < SIZE; y++){
			cout << arr[x][y] <<" "; //Prints the array's contents
		}
		cout << endl; //Formats with newlines
	}
	cout << endl; //Some spacing
	return;
}

void nextTurn(char today[][SIZE], char update[][SIZE], int& day){
	day++; //Updates the day
	int xCheck; //X coordinate to be checked
	int yCheck; //Y coordinate to be checked
	
	for(int x = 0; x < SIZE; x++){
		for(int y = 0; y < SIZE; y++){
			//Sets all 'i' to 'r' in the new grid
			if(today[x][y] == 'i' || today[x][y] == 'r'){
				update[x][y] = 'r'; //Updates all infectious to recovered, and keeps current recovered
			}
			if(today[x][y] == 's'){									// If the person is susceptible...
				for(int xCheck = x-1; xCheck <= x+1; xCheck++){		// Check all x coordinates around the person
					for(int yCheck = y-1; yCheck <= y+1; yCheck++){	// Check all y coordinates around the person
						if(xCheck == x && yCheck == y){
																	// Don't check at the person because there is no need to check there
						} else {
							if(xCheck >= 0 && yCheck >= 0 && xCheck < SIZE && yCheck < SIZE){ // Make sure the checked coordinates are in bounds
								if(today[xCheck][yCheck] == 'i'){	//Is the person at the checked coordinates infected?
									update[x][y] = 'i';				//If so, update the 's' to 'i' in the new grid
								}
							}
						}
					}
				}
			}
		}
	}
	
	for(int x = 0; x < SIZE; x++){
		for(int y = 0; y < SIZE; y++){
			today[x][y] = update[x][y]; //Updates today's grid with the new values
		}
	}
}

int countInfected(char arr[][SIZE], int arrSize){
	int count = 0;
	
	for(int x = 0; x < arrSize; x++){
		for(int y = 0; y < arrSize; y++){
			if(arr[x][y] == 'i') count++; //Increments count for each infected person in the grid
		}
	}
	
	return count;
}
#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;
}