Skip to main content

Simple Greedy sort C++

Jun 30, 2023Iceman_71
Loading...

More C++ Posts

C++ Range Slicer

Oct 31, 2023LeifMessinger

0 likes • 3 views

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

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

Heapify a vector

Nov 19, 2022CodeCatch

0 likes • 0 views

#include <iostream>
#include <vector>
using namespace std;
void swap(int *a, int *b)
{
int temp = *b;
*b = *a;
*a = temp;
}
void heapify(vector<int> &hT, int i)
{
int size = hT.size();
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < size && hT[l] > hT[largest])
largest = l;
if (r < size && hT[r] > hT[largest])
largest = r;
if (largest != i)
{
swap(&hT[i], &hT[largest]);
heapify(hT, largest);
}
}
void insert(vector<int> &hT, int newNum)
{
int size = hT.size();
if (size == 0)
{
hT.push_back(newNum);
}
else
{
hT.push_back(newNum);
for (int i = size / 2 - 1; i >= 0; i--)
{
heapify(hT, i);
}
}
}
void deleteNode(vector<int> &hT, int num)
{
int size = hT.size();
int i;
for (i = 0; i < size; i++)
{
if (num == hT[i])
break;
}
swap(&hT[i], &hT[size - 1]);
hT.pop_back();
for (int i = size / 2 - 1; i >= 0; i--)
{
heapify(hT, i);
}
}
void printArray(vector<int> &hT)
{
for (int i = 0; i < hT.size(); ++i)
cout << hT[i] << " ";
cout << "\n";
}
int main()
{
vector<int> heapTree;
insert(heapTree, 3);
insert(heapTree, 4);
insert(heapTree, 9);
insert(heapTree, 5);
insert(heapTree, 2);
cout << "Max-Heap array: ";
printArray(heapTree);
deleteNode(heapTree, 4);
cout << "After deleting an element: ";
printArray(heapTree);
}

minimum matrix values

Nov 18, 2022AustinLeath

0 likes • 4 views

#include <iostream>
using namespace std;
int main() {
const int ROW_SIZE = 2;
const int COLUMN_SIZE = 5; //establish all variables
int matrix[ROW_SIZE][COLUMN_SIZE];
int minVal;
for (int i = 0; i < ROW_SIZE; ++i) // for loop to ask user to enter data.
{
for (int h = 0; h < COLUMN_SIZE; ++h) {
cout << "Enter data for row #" << i + 1 << " and column #" << h + 1 << ": ";
cin >> matrix[i][h];
}
}
cout << "You entered: " << endl;
for (int i = 0; i < ROW_SIZE; ++i) //for statements to output the array neatly
{
for (int h = 0; h < COLUMN_SIZE; ++h) {
cout << matrix[i][h] << "\t";
}
cout << endl;
}
cout << "Minimum for each row is: {";
for (int i = 0; i < ROW_SIZE; i++) //for statements to find the minimum in each row
{
minVal = matrix[i][0];
for (int h = 0; h < COLUMN_SIZE; h++) {
if (matrix[i][h] < minVal) // if matrix[i][h] < minVal -> minVal = matrix[i][h];
{
minVal = matrix[i][h];
}
}
cout << minVal << ", ";
}
cout << "}" << endl;
cout << "Minimum for each column is: {";
for (int i = 0; i < COLUMN_SIZE; i++) //for statements to find the minimum in each column
{
minVal = matrix[0][i];
for (int h = 0; h < ROW_SIZE; h++) {
if (matrix[h][i] < minVal) //replaces minVal with array index for that column that is lowest
{
minVal = matrix[h][i];
}
}
cout << minVal << ", ";
}
cout << "}" << endl;
return 0;
}

C++ SigFigs

Sep 7, 2022LeifMessinger

0 likes • 0 views

#include <iostream>
#include <cstring>
int main(int argc, char** argv){
//With decimal
if(strstr(argv[1], ".") != nullptr){
int i = 0;
//Skip i to first non 0 digit
while(argv[1][i] < '1' || argv[1][i] > '9') ++i;
//If digit comes before decimal
if((argv[1] + i) < strstr(argv[1], ".")){ //Good example of pointer arithmetic
std::cout << strlen(argv[1] + i) - 1 << std::endl; //Another good example
}else{
//If digit is after decimal
std::cout << strlen(argv[1] + i) << std::endl;
}
}else{
//Without decimal
int m = 0;
int i = 0;
while(argv[1][i] < '1' || argv[1][i] > '9') ++i; //In case of some number like 0045
for(; argv[1][i] != '\0'; ++i){
if(argv[1][i] >= '1' && argv[1][i] <= '9') m = i + 1;
}
std::cout << m << std::endl;
}
return 0;
}

Wing Project 1

Oct 31, 2021aedrarian

0 likes • 1 view

//Get data file at https://codecatch.net/post.php?postID=91e87d73
//Iteration 1 of Wing Project. Solution breaks down around n=35
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
using namespace std;
int getSum(map<int, int> list);
void readData(map<int, float>* data);
void lowestPrice();
void findSums(int n, vector<map<int, int>>* sumsList, map<int, float>* data);
//void findSum(map<int, int> currList, int x, int n, vector<map<int, int>>* sumsList);
void findSum(map<int, int> currList, int x, int n, vector<map<int, int>>* sumsList, map<int, float>* data);
float getPrice(map<int, int> set, map<int, float>* data);
template <typename S>
ostream& operator<<(ostream& os, const vector<S>& vector)
{
// Printing all the elements using <<
for (auto element : vector) {
os << element << " ";
}
return os;
}
bool operator==(map<int, int> m1, map<int, int> m2)
{
if(m1.size() != m2.size())
return false;
bool ret = true;
for(auto it = m1.begin(); it !=m1.end() && ret; it++)
{
if(ret && m1.count(it->first) != m2.count(it->first))
ret = false;
if(ret && m1.count(it->first) == 1)
{
if(m1.at(it->first) != m2.at(it->first))
ret = false;
}
}
return ret;
}
int main()
{
map<int, float> data;
readData(&data);
vector<map<int, int>> *sumsList;
sumsList = new vector<map<int, int>>;
findSums(40, sumsList, &data);
for(auto el : *sumsList)
{
for(auto it = el.begin(); it != el.end(); it++)
{
cout << it->first << "->" << it->second << " ";
}
cout << getPrice(el, &data) << endl;
}
return 0;
}
/* Returns the price of wings given a set of numbers of wings to buy.
* Returns -1 if the set contains a number that is not possible to buy.
*/
float getPrice(map<int, int> set, map<int, float>* data)
{
float price = 0;
for(auto it = set.begin(); it != set.end(); it++)
{
//If data doesn't contain an element of set, return -1
if(data->count(it->first) == 0)
return -1;
price += data->at(it->first) * it->second; //pricePerPacket * qtyOfPackets
}
return price;
}
/* Adds the elements of list.
* Suppose mapping is <num, qty>.
* Returns sum(num*qty)
*/
int getSum(map<int, int> list)
{
int sum = 0;
for(auto it = list.begin(); it != list.end(); it++)
sum += it->first * it->second;
return sum;
}
void findSums(int n, vector<map<int, int>>* sumsList, map<int, float>* data)
{
map<int, int> currList;
//Recur when currSum < n
auto it = data->begin();
while(it->first <= n && it != data->end())
{
findSum(currList, it->first, n, sumsList, data);
it++;
}
}
void findSum(map<int, int> currList, int x, int n, vector<map<int, int>>* sumsList, map<int, float>* data)
{
//Append x to currList
if(currList.count(x) == 0)
currList.emplace(x, 1);
else
{
int val = 1+ currList.at(x);
currList.erase(x);
currList.emplace(x, val);
}
//Determine current sum, check for return cases
int currSum = getSum(currList);
if(currSum > n)
return;
else if(currSum == n)
{
//Check to make sure no duplicates
for(auto list : *sumsList)
{
if(list == currList)
return;
}
sumsList->push_back(currList);
return;
}
//Recur when currSum < n
auto it = data->begin();
while(it->first <= n-x && it != data->end())
{
findSum(currList, it->first, n, sumsList, data);
it++;
}
}
void readData(map<int, float>* data)
{
ifstream file ("./data", ifstream::in);
if(file.is_open())
{
int i = 0;
while(!file.eof())
{
float wings, price;
string skipnl;
file >> wings;
file >> price;
data->emplace(wings, price);
getline(file, skipnl);
i++;
}
}
}