## Enumeration Basics

0 likes • Nov 18, 2022 • 0 views
C++

## More C++ Posts

#### Daily: Cutting a Wall

0 likes • Dec 20, 2021 • 0 views
C++
```/*Good morning! Here's your coding interview problem for today.
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 12 3 3 25 54 4 21 3 3 31 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;}```

#### CSCE 1040 Lab 9

0 likes • Nov 18, 2022 • 2 views
C++
```#include <iostream>#include "PlaylistNode.h"using namespace std;void PrintMenu(string title);
int main() {   string plTitle;   cout << "Enter playlist's title:" << endl;   getline(cin, plTitle);   PrintMenu(plTitle);   return 0;}
void PrintMenu(string title) {   Playlist list;   string id;   string sname;   string aname;   int length;   int oldPos;   int newPos;   char choice;      while(true) {      cout << endl << title << " PLAYLIST MENU" << endl;      cout << "a - Add song" << endl;      cout << "d - Remove song" << endl;      cout << "c - Change position of song" << endl;      cout << "s - Output songs by specific artist" << endl;      cout << "t - Output total time of playlist (in seconds)" << endl;      cout << "o - Output full playlist" << endl;      cout << "q - Quit" << endl << endl;            cout << "Choose an option:" << endl;      cin >> choice;      cin.ignore();            if (choice == 'q') {         exit(1);      }      else if (choice == 'a') {         cout << "\nADD SONG" << endl;         cout << "Enter song's unique ID: ";         cin >> id;         cin.ignore();         cout << "Enter song's name: ";         getline(cin,sname);         cout << "Enter artist's name: ";         getline(cin,aname);         cout << "Enter song's length (in seconds): ";         cin >> length;         list.AddSong(id, sname, aname, length);      }      else if (choice == 'd') {         cout << "\nREMOVE SONG" << endl;         cout << "Enter song's unique ID: ";         cin >> id;         list.RemoveSong(id);      }      else if (choice == 'c') {         cout << "\nCHANGE POSITION OF SONG" << endl;         cout << "Enter song's current position: ";         cin >> oldPos;         cout << "Enter new position for song: ";         cin >> newPos;         list.ChangePosition(oldPos, newPos);      }      else if (choice == 's') {         cout << "\nOUTPUT SONGS BY SPECIFIC ARTIST" << endl;         cout << "Enter artist's name: ";         getline(cin, aname);         list.SongsByArtist(aname);      }      else if (choice == 't') {         cout << "\nOUTPUT TOTAL TIME OF PLAYLIST (IN SECONDS)" << endl;         cout << "Total time: " << list.TotalTime() << " seconds" << endl;      }      else if (choice == 'o') {         cout << endl << title << " - OUTPUT FULL PLAYLIST" << endl;         list.PrintList();      }      else {         cout << "Invalid menu choice! Please try again." << endl;      }   }}```

#### Daily: Find missing array value

0 likes • Dec 24, 2021 • 18 views
C++
```/*Good morning! Here's your coding interview problem for today.
This problem was asked by Stripe.
Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.
For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.
You can modify the input array in-place.*/#include <iostream>using namespace std;
int calcMissing(int* input, int size){	int sum = 0;	int n = 1; //add one to account for missing value	for(int i = 0; i < size; i++)	{	if(input[i] > 0)	{	sum += input[i];	n++;	}	}
//If no numbers higher than 0, answer is 1	if(sum == 0)	return 1;
return (n*(n+1)/2) - sum; //Formula is expectedSum - actualSum	/* expectedSum = n*(n+1)/2, the formula for sum(1, n) */}
int main(){
cout << calcMissing(new int[4]{3, 4, -1, 1}, 4) << endl;	cout << calcMissing(new int[3]{1, 2, 0}, 3) << endl;
//No positive numbers	cout << calcMissing(new int[1]{0}, 1) << endl;}```

#### GCD using Stein's Algorithm

0 likes • Jun 30, 2023 • 2 views
C++
```// Iterative C++ program to// implement Stein's Algorithm//#include <bits/stdc++.h>#include <bitset>using namespace std;
// Function to implement// Stein's Algorithmint 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 codeint main(){    int a = 12, b = 780;    printf("Gcd of given numbers is %d\n", gcd(a, b));    return 0;}```

#### Egg Problem Template

0 likes • Jul 10, 2023 • 3 views
C++
```#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 answersize_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_EGGSvoid 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_HEIGHTvoid 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;}```

#### Command line game

0 likes • Nov 19, 2022 • 1 view
C++
```#include <iostream>#include <vector>#include <utility>#include <algorithm>#include <chrono>using namespace std;
#include <stdio.h>#include <Windows.h>
int nScreenWidth = 120;			// Console Screen Size X (columns)int nScreenHeight = 40;			// Console Screen Size Y (rows)int nMapWidth = 16;				// World Dimensionsint nMapHeight = 16;
float fPlayerX = 14.7f;			// Player Start Positionfloat fPlayerY = 5.09f;float fPlayerA = 0.0f;			// Player Start Rotationfloat fFOV = 3.14159f / 4.0f;	// Field of Viewfloat fDepth = 16.0f;			// Maximum rendering distancefloat fSpeed = 5.0f;			// Walking Speed
int main(){	// Create Screen Buffer	wchar_t *screen = new wchar_t[nScreenWidth*nScreenHeight];	HANDLE hConsole = CreateConsoleScreenBuffer(GENERIC_READ | GENERIC_WRITE, 0, NULL, CONSOLE_TEXTMODE_BUFFER, NULL);	SetConsoleActiveScreenBuffer(hConsole);	DWORD dwBytesWritten = 0;
// Create Map of world space # = wall block, . = space	wstring map;	map += L"#########.......";	map += L"#...............";	map += L"#.......########";	map += L"#..............#";	map += L"#......##......#";	map += L"#......##......#";	map += L"#..............#";	map += L"###............#";	map += L"##.............#";	map += L"#......####..###";	map += L"#......#.......#";	map += L"#......#.......#";	map += L"#..............#";	map += L"#......#########";	map += L"#..............#";	map += L"################";
auto tp1 = chrono::system_clock::now();	auto tp2 = chrono::system_clock::now();		while (1)	{		// We'll need time differential per frame to calculate modification		// to movement speeds, to ensure consistant movement, as ray-tracing		// is non-deterministic		tp2 = chrono::system_clock::now();		chrono::duration<float> elapsedTime = tp2 - tp1;		tp1 = tp2;		float fElapsedTime = elapsedTime.count();

// Handle CCW Rotation		if (GetAsyncKeyState((unsigned short)'A') & 0x8000)			fPlayerA -= (fSpeed * 0.75f) * fElapsedTime;
// Handle CW Rotation		if (GetAsyncKeyState((unsigned short)'D') & 0x8000)			fPlayerA += (fSpeed * 0.75f) * fElapsedTime;				// Handle Forwards movement & collision		if (GetAsyncKeyState((unsigned short)'W') & 0x8000)		{			fPlayerX += sinf(fPlayerA) * fSpeed * fElapsedTime;;			fPlayerY += cosf(fPlayerA) * fSpeed * fElapsedTime;;			if (map.c_str()[(int)fPlayerX * nMapWidth + (int)fPlayerY] == '#')			{				fPlayerX -= sinf(fPlayerA) * fSpeed * fElapsedTime;;				fPlayerY -= cosf(fPlayerA) * fSpeed * fElapsedTime;;			}					}
// Handle backwards movement & collision		if (GetAsyncKeyState((unsigned short)'S') & 0x8000)		{			fPlayerX -= sinf(fPlayerA) * fSpeed * fElapsedTime;;			fPlayerY -= cosf(fPlayerA) * fSpeed * fElapsedTime;;			if (map.c_str()[(int)fPlayerX * nMapWidth + (int)fPlayerY] == '#')			{				fPlayerX += sinf(fPlayerA) * fSpeed * fElapsedTime;;				fPlayerY += cosf(fPlayerA) * fSpeed * fElapsedTime;;			}		}
for (int x = 0; x < nScreenWidth; x++)		{			// For each column, calculate the projected ray angle into world space			float fRayAngle = (fPlayerA - fFOV/2.0f) + ((float)x / (float)nScreenWidth) * fFOV;
// Find distance to wall			float fStepSize = 0.1f;		  // Increment size for ray casting, decrease to increase													float fDistanceToWall = 0.0f; //                                      resolution
bool bHitWall = false;		// Set when ray hits wall block			bool bBoundary = false;		// Set when ray hits boundary between two wall blocks
float fEyeX = sinf(fRayAngle); // Unit vector for ray in player space			float fEyeY = cosf(fRayAngle);
// Incrementally cast ray from player, along ray angle, testing for 			// intersection with a block			while (!bHitWall && fDistanceToWall < fDepth)			{				fDistanceToWall += fStepSize;				int nTestX = (int)(fPlayerX + fEyeX * fDistanceToWall);				int nTestY = (int)(fPlayerY + fEyeY * fDistanceToWall);								// Test if ray is out of bounds				if (nTestX < 0 || nTestX >= nMapWidth || nTestY < 0 || nTestY >= nMapHeight)				{					bHitWall = true;			// Just set distance to maximum depth					fDistanceToWall = fDepth;				}				else				{					// Ray is inbounds so test to see if the ray cell is a wall block					if (map.c_str()[nTestX * nMapWidth + nTestY] == '#')					{						// Ray has hit wall						bHitWall = true;
// To highlight tile boundaries, cast a ray from each corner						// of the tile, to the player. The more coincident this ray						// is to the rendering ray, the closer we are to a tile 						// boundary, which we'll shade to add detail to the walls						vector<pair<float, float>> p;
// Test each corner of hit tile, storing the distance from						// the player, and the calculated dot product of the two rays						for (int tx = 0; tx < 2; tx++)							for (int ty = 0; ty < 2; ty++)							{								// Angle of corner to eye								float vy = (float)nTestY + ty - fPlayerY;								float vx = (float)nTestX + tx - fPlayerX;								float d = sqrt(vx*vx + vy*vy); 								float dot = (fEyeX * vx / d) + (fEyeY * vy / d);								p.push_back(make_pair(d, dot));							}
// Sort Pairs from closest to farthest						sort(p.begin(), p.end(), [](const pair<float, float> &left, const pair<float, float> &right) {return left.first < right.first; });												// First two/three are closest (we will never see all four)						float fBound = 0.01;						if (acos(p.at(0).second) < fBound) bBoundary = true;						if (acos(p.at(1).second) < fBound) bBoundary = true;						if (acos(p.at(2).second) < fBound) bBoundary = true;					}				}			}					// Calculate distance to ceiling and floor			int nCeiling = (float)(nScreenHeight/2.0) - nScreenHeight / ((float)fDistanceToWall);			int nFloor = nScreenHeight - nCeiling;
// Shader walls based on distance			short nShade = ' ';			if (fDistanceToWall <= fDepth / 4.0f)			nShade = 0x2588;	// Very close				else if (fDistanceToWall < fDepth / 3.0f)		nShade = 0x2593;			else if (fDistanceToWall < fDepth / 2.0f)		nShade = 0x2592;			else if (fDistanceToWall < fDepth)				nShade = 0x2591;			else											nShade = ' ';		// Too far away
if (bBoundary)		nShade = ' '; // Black it out						for (int y = 0; y < nScreenHeight; y++)			{				// Each Row				if(y <= nCeiling)					screen[y*nScreenWidth + x] = ' ';				else if(y > nCeiling && y <= nFloor)					screen[y*nScreenWidth + x] = nShade;				else // Floor				{									// Shade floor based on distance					float b = 1.0f - (((float)y -nScreenHeight/2.0f) / ((float)nScreenHeight / 2.0f));					if (b < 0.25)		nShade = '#';					else if (b < 0.5)	nShade = 'x';					else if (b < 0.75)	nShade = '.';					else if (b < 0.9)	nShade = '-';					else				nShade = ' ';					screen[y*nScreenWidth + x] = nShade;				}			}		}
// Display Stats		swprintf_s(screen, 40, L"X=%3.2f, Y=%3.2f, A=%3.2f FPS=%3.2f ", fPlayerX, fPlayerY, fPlayerA, 1.0f/fElapsedTime);
// Display Map		for (int nx = 0; nx < nMapWidth; nx++)			for (int ny = 0; ny < nMapWidth; ny++)			{				screen[(ny+1)*nScreenWidth + nx] = map[ny * nMapWidth + nx];			}		screen[((int)fPlayerX+1) * nScreenWidth + (int)fPlayerY] = 'P';
// Display Frame		screen[nScreenWidth * nScreenHeight - 1] = '\0';		WriteConsoleOutputCharacter(hConsole, screen, nScreenWidth * nScreenHeight, { 0,0 }, &dwBytesWritten);	}
return 0;}```