cp/cp01/drills.h

#pragma once
// CP01 lab: arrays, loops, and the frequency map. You write every function body in this file.
//
// Each comment is a contract, and check.cpp tests exactly that contract.
// Work through the lab steps in the book (CP01, section 3) in order, and after
// finishing step N run, from this folder in PowerShell:
//     .\run.ps1 N
// With no number, run.ps1 runs every step.
//
// Ground rules
// - Read the signature first: what goes in, and what type must come out?
// - Above every loop, write one comment line saying what is true after each pass
//   (its invariant). Make sure it is already true before the loop starts.
// - Standard library only: the headers below are all you need.
// - Each body starts as a `throw` that says "not written yet". Delete that line when
//   you write the step; check.cpp reports a step that still throws.

#include <cstddef>
#include <stdexcept>
#include <string>
#include <unordered_map>
#include <vector>

// STEP 1 (worked example). Return how many values in v are greater than 0.
// Zero is not positive. An empty v has 0 positive values.
inline int countPositives(const std::vector<int>& v) {
    throw std::logic_error("step 1, countPositives: not written yet");
}

// STEP 2 (partly filled). Return a map from each value in v to the number of times it
// appears. An empty v gives an empty map. This is your day02 countEach, finished.
inline std::unordered_map<int, int> countEach(const std::vector<int>& v) {
    throw std::logic_error("step 2, countEach: not written yet");
}

// STEP 3 (partly filled). Return the value that appears most often in v.
// If several values tie for most often, return the smallest of them.
// v always holds at least one value.
inline int mostFrequent(const std::vector<int>& v) {
    throw std::logic_error("step 3, mostFrequent: not written yet");
}

// STEP 4. Return the INDEX of the first value in v that appears exactly once,
// or -1 if no value appears exactly once (including when v is empty).
inline int firstUnique(const std::vector<int>& v) {
    throw std::logic_error("step 4, firstUnique: not written yet");
}

// STEP 5. Return true if some value appears at least twice in v, and false otherwise.
inline bool containsDuplicate(const std::vector<int>& v) {
    throw std::logic_error("step 5, containsDuplicate: not written yet");
}

// STEP 6. Return true if b uses exactly the same characters as a, each one the same
// number of times. Upper and lower case are different characters, and spaces count.
inline bool isAnagram(const std::string& a, const std::string& b) {
    throw std::logic_error("step 6, isAnagram: not written yet");
}

// STEP 7. Return two indices {i, j} with i < j and v[i] + v[j] == target.
// If several pairs work, return any one of them. If none does, return {}, an empty vector.
// Every value, and target, lies between -1'000'000'000 and 1'000'000'000.
inline std::vector<int> twoSum(const std::vector<int>& v, int target) {
    throw std::logic_error("step 7, twoSum: not written yet");
}

// STEP 8. Return the sum of every value in v, exactly, even when it does not fit in an int.
// Values can be as large as 2'000'000'000 and as small as -2'000'000'000.
inline long long exactSum(const std::vector<int>& v) {
    throw std::logic_error("step 8, exactSum: not written yet");
}

// STEP 9. Return how many index pairs (i, j) with i < j have v[i] + v[j] == target.
// Every value, and target, lies between -1'000'000'000 and 1'000'000'000.
// It must stay fast for 300'000 values: one pass with a map, not two nested loops.
inline long long countPairsWithSum(const std::vector<int>& v, int target) {
    throw std::logic_error("step 9, countPairsWithSum: not written yet");
}