exercises

/**
 * STL Algorithms - Exercises
 * Compile: g++ -std=c++17 -Wall exercises.cpp -o exercises
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>
using namespace std;

// ============================================================
// Exercise 1: Filter and Transform ⭐
// ============================================================

// TODO: Given vector of ints, return new vector with
// only positive numbers, squared

void exercise1() {
    // vector<int> v = {-3, 1, -4, 1, 5, -9, 2};
    // auto result = filterAndSquare(v);
    // result = {1, 1, 25, 4}
    cout << "(Implement filterAndSquare)" << endl;
}

// ============================================================
// Exercise 2: Find Duplicates ⭐⭐
// ============================================================

// TODO: Use algorithms to find all duplicate values in vector

void exercise2() {
    // vector<int> v = {1, 2, 3, 2, 4, 3, 5};
    // auto dups = findDuplicates(v);
    // dups = {2, 3}
    cout << "(Implement findDuplicates)" << endl;
}

// ============================================================
// Exercise 3: Partition ⭐⭐
// ============================================================

// TODO: Partition vector so evens come before odds
// Use partition algorithm

void exercise3() {
    // vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8};
    // partitionEvenOdd(v);
    // Evens before odds: {2, 8, 6, 4, 5, 3, 7, 1}
    cout << "(Implement partition)" << endl;
}

// ============================================================
// Exercise 4: Top K Elements ⭐⭐
// ============================================================

// TODO: Find top K largest elements using partial_sort

void exercise4() {
    // vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
    // auto top3 = topK(v, 3);
    // top3 = {9, 6, 5}
    cout << "(Implement topK)" << endl;
}

// ============================================================
// Exercise 5: Rotate to Target ⭐⭐
// ============================================================

// TODO: Rotate vector so target value is first

void exercise5() {
    // vector<int> v = {1, 2, 3, 4, 5};
    // rotateToFront(v, 3);
    // v = {3, 4, 5, 1, 2}
    cout << "(Implement rotateToFront)" << endl;
}

// ============================================================
// Exercise 6: Running Average ⭐⭐⭐
// ============================================================

// TODO: Calculate running average using partial_sum and transform

void exercise6() {
    // vector<double> v = {1, 2, 3, 4, 5};
    // auto avg = runningAverage(v);
    // avg = {1, 1.5, 2, 2.5, 3}
    cout << "(Implement runningAverage)" << endl;
}

// ============================================================
// Exercise 7: Merge Sorted Unique ⭐⭐⭐
// ============================================================

// TODO: Merge two sorted vectors, remove duplicates

void exercise7() {
    // vector<int> a = {1, 2, 3, 3, 4};
    // vector<int> b = {2, 4, 5, 5, 6};
    // auto result = mergeSortedUnique(a, b);
    // result = {1, 2, 3, 4, 5, 6}
    cout << "(Implement mergeSortedUnique)" << endl;
}

// ============================================================
// Exercise 8: Custom Sort ⭐⭐⭐
// ============================================================

// TODO: Sort strings by length, then alphabetically

void exercise8() {
    // vector<string> v = {"apple", "pie", "cat", "banana", "a"};
    // customSort(v);
    // v = {"a", "cat", "pie", "apple", "banana"}
    cout << "(Implement customSort)" << endl;
}

// ============================================================
// MAIN
// ============================================================

int main() {
    cout << "=== STL Algorithms Exercises ===" << endl;
    
    cout << "\nEx1: Filter and Square" << endl;
    exercise1();
    
    cout << "\nEx2: Find Duplicates" << endl;
    exercise2();
    
    cout << "\nEx3: Partition" << endl;
    exercise3();
    
    cout << "\nEx4: Top K" << endl;
    exercise4();
    
    cout << "\nEx5: Rotate to Front" << endl;
    exercise5();
    
    cout << "\nEx6: Running Average" << endl;
    exercise6();
    
    cout << "\nEx7: Merge Sorted Unique" << endl;
    exercise7();
    
    cout << "\nEx8: Custom Sort" << endl;
    exercise8();
    
    return 0;
}

// ============================================================
// ANSWERS
// ============================================================
/*
Ex1:
vector<int> filterAndSquare(const vector<int>& v) {
    vector<int> result;
    copy_if(v.begin(), v.end(), back_inserter(result), [](int x) { return x > 0; });
    transform(result.begin(), result.end(), result.begin(), [](int x) { return x * x; });
    return result;
}

Ex2:
vector<int> findDuplicates(vector<int> v) {
    sort(v.begin(), v.end());
    vector<int> dups;
    for (size_t i = 1; i < v.size(); i++) {
        if (v[i] == v[i-1] && (dups.empty() || dups.back() != v[i])) {
            dups.push_back(v[i]);
        }
    }
    return dups;
}

Ex3:
void partitionEvenOdd(vector<int>& v) {
    partition(v.begin(), v.end(), [](int x) { return x % 2 == 0; });
}

Ex4:
vector<int> topK(vector<int> v, int k) {
    partial_sort(v.begin(), v.begin() + k, v.end(), greater<int>());
    return vector<int>(v.begin(), v.begin() + k);
}

Ex5:
void rotateToFront(vector<int>& v, int target) {
    auto it = find(v.begin(), v.end(), target);
    if (it != v.end()) rotate(v.begin(), it, v.end());
}

Ex6:
vector<double> runningAverage(const vector<double>& v) {
    vector<double> sums(v.size()), result(v.size());
    partial_sum(v.begin(), v.end(), sums.begin());
    for (size_t i = 0; i < v.size(); i++) {
        result[i] = sums[i] / (i + 1);
    }
    return result;
}

Ex7:
vector<int> mergeSortedUnique(vector<int> a, vector<int> b) {
    a.erase(unique(a.begin(), a.end()), a.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    vector<int> result;
    set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(result));
    return result;
}

Ex8:
void customSort(vector<string>& v) {
    sort(v.begin(), v.end(), [](const string& a, const string& b) {
        if (a.length() != b.length()) return a.length() < b.length();
        return a < b;
    });
}
*/