Skip to main content

Wing Project 1

Oct 31, 2021aedrarian
Loading...

More C++ Posts

Simple Greedy sort C++

Jun 30, 2023Iceman_71

0 likes • 7 views

#include <iostream>
using namespace std;
int main()
{
int arr[] = {5, 1, 4, 20, 10, 2, 13, 11, 6, 21};
int greed[] = {0, 0, 0, 0};
int k = 0;
int i;
int set_index;
while (k < 4)
{
i = 0;
while (i < 10)
{
if (arr[i] > greed[k])
{
greed[k] = arr[i];
set_index = i;
}
i++;
}
arr[set_index] = 0;
k++;
}
cout << greed[0] << " " << greed[1] << " " << greed[2] << " " << greed[3] << endl;
}

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

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

Egg Problem Template

Jul 10, 2023LeifMessinger

0 likes • 4 views

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

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

Untitled

Apr 15, 2025hasnaoui1

0 likes • 4 views

int main()