Skip to main content

Simple Greedy sort C++

Jun 30, 2023Iceman_71
Loading...

More C++ Posts

Daily: Cutting a Wall

Dec 20, 2021aedrarian

0 likes • 0 views

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

Hash Table Example

Nov 18, 2022AustinLeath

0 likes • 0 views

using namespace std;
class Hash
{
int BUCKET; // No. of buckets
// Pointer to an array containing buckets
list<int> *table;
public:
Hash(int V); // Constructor
// inserts a key into hash table
void insertItem(int x);
// deletes a key from hash table
void deleteItem(int key);
// hash function to map values to key
int hashFunction(int x) {
return (x % BUCKET);
}
void displayHash();
};
Hash::Hash(int b)
{
this->BUCKET = b;
table = new list<int>[BUCKET];
}
void Hash::insertItem(int key)
{
int index = hashFunction(key);
table[index].push_back(key);
}
void Hash::deleteItem(int key)
{
// get the hash index of key
int index = hashFunction(key);
// find the key in (inex)th list
list <int> :: iterator i;
for (i = table[index].begin();
i != table[index].end(); i++) {
if (*i == key)
break;
}
// if key is found in hash table, remove it
if (i != table[index].end())
table[index].erase(i);
}
// function to display hash table
void Hash::displayHash() {
for (int i = 0; i < BUCKET; i++) {
cout << i;
for (auto x : table[i])
cout << " --> " << x;
cout << endl;
}
}
// Driver program
int main()
{
// array that contains keys to be mapped
int a[] = {15, 11, 27, 8, 12};
int n = sizeof(a)/sizeof(a[0]);
// insert the keys into the hash table
Hash h(7); // 7 is count of buckets in
// hash table
for (int i = 0; i < n; i++)
h.insertItem(a[i]);
// delete 12 from hash table
h.deleteItem(12);
// display the Hash table
h.displayHash();
return 0;
}

Two Letter Combinations

Nov 18, 2022AustinLeath

0 likes • 0 views

#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
using namespace std;
//This program makes a new text file that contains all combinations of two letters.
// aa, ab, ..., zy, zz
int main(){
string filename = "two_letters.txt";
ofstream outFile;
outFile.open(filename.c_str());
if(!outFile.is_open()){
cout << "Something's wrong. Closing..." << endl;
return 0;
}
for(char first = 'a'; first <= 'z'; first++){
for(char second = 'a'; second <= 'z'; second++){
outFile << first << second << " ";
}
outFile << endl;
}
return 0;
}

Infection Simulation

Nov 18, 2022AustinLeath

0 likes • 2 views

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

Bit arithmetic + and -

Sep 1, 2023LeifMessinger

0 likes • 2 views

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

SAM 5 words with bitmaps

Oct 23, 2022LeifMessinger

0 likes • 1 view

//Leif Messinger
//Finds all sets of 5 5 letter words that don't have duplicate letters in either themselves or each other.
//First it reads the words in and puts them in groups of their bitmasks
//After that, we recurse on each group. Before doing that, we remove the group from the set of other groups to check it against.
#include <cstdio> //getchar, printf
#include <cassert> //assert
#include <vector>
#include <set>
#include <algorithm> //std::copy_if
#include <iterator> //std::back_inserter
#define CHECK_FOR_CRLF true
#define MIN_WORDS 5
#define MAX_WORDS 5
#define WORD_TOO_LONG(len) (len != 5)
const unsigned int charToBitmask(const char bruh){
assert(bruh >= 'a' && bruh <= 'z');
return (1 << (bruh - 'a'));
}
void printBitmask(unsigned int bitmask){
char start = 'a';
while(bitmask != 0){
if(bitmask & 1){
putchar(start);
}
bitmask >>= 1;
++start;
}
}
//Pointer needs to be deleted
const std::set<unsigned int>* getBitmasks(){
std::set<unsigned int>* bitmasksPointer = new std::set<unsigned int>;
std::set<unsigned int>& bitmasks = (*bitmasksPointer);
unsigned int bitmask = 0;
unsigned int wordLength = 0;
bool duplicateLetters = false;
for(char c = getchar(); c >= 0; c = getchar()){
if(CHECK_FOR_CRLF && c == '\r'){
continue;
}
if(c == '\n'){
if(!(WORD_TOO_LONG(wordLength) || duplicateLetters)) bitmasks.insert(bitmask);
bitmask = 0;
wordLength = 0;
duplicateLetters = false;
continue;
}
if((bitmask & charToBitmask(c)) != 0) duplicateLetters = true;
bitmask |= charToBitmask(c);
++wordLength;
}
return bitmasksPointer;
}
void printBitmasks(const std::vector<unsigned int>& bitmasks){
for(unsigned int bruh : bitmasks){
printBitmask(bruh);
putchar(','); putchar(' ');
}
puts("");
}
//Just to be clear, when I mean "word", I mean a group of words with the same letters.
void recurse(std::vector<unsigned int>& oldBitmasks, std::vector<unsigned int> history, const unsigned int currentBitmask){
//If there's not enough words left
if(oldBitmasks.size() + (-(history.size())) + (-MIN_WORDS) <= 0){
//If there's enough words
if(history.size() >= MIN_WORDS){
//Print the list
printBitmasks(history);
}
return;
//To make it faster, we can stop it after 5 words too
}else if(history.size() >= MAX_WORDS){
//Print the list
printBitmasks(history);
return;
}
//Thin out the array with only stuff that matches the currentBitmask.
std::vector<unsigned int> newBitmasks;
std::copy_if(oldBitmasks.begin(), oldBitmasks.end(), std::back_inserter(newBitmasks), [&currentBitmask](unsigned int bruh){
return (bruh & currentBitmask) == 0;
});
while(newBitmasks.size() > 0){
//I know this modifies 'oldBitmasks' too. It's intentional.
//This makes it so that the word is never involved in any of the child serches or any of the later searches in this while loop.
const unsigned int word = newBitmasks.back(); newBitmasks.pop_back();
std::vector<unsigned int> newHistory = history;
newHistory.push_back(word);
recurse(newBitmasks, newHistory, currentBitmask | word);
}
}
int main(){
const std::set<unsigned int>* bitmasksSet = getBitmasks();
std::vector<unsigned int> bitmasks(bitmasksSet->begin(), bitmasksSet->end());
delete bitmasksSet;
recurse(bitmasks, std::vector<unsigned int>(), 0);
return 0;
}