ContentsFoundations to FrontierBezhig

cp/cp01/check.cpp

All lab code. Download this file.

// CP01 checks. Do not edit this file; edit drills.h.
// Build and run from this folder with   .\run.ps1      (every step)
//                                   or   .\run.ps1 3    (step 3 only)
// A failing check prints what your code returned, after "got".
#include <algorithm>
#include <chrono>
#include <cstdlib>
#include <exception>
#include <iostream>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

#include "drills.h"

static int failures = 0;

// How a returned value is printed after "got".
static std::string show(int x) { return std::to_string(x); }
static std::string show(long long x) { return std::to_string(x); }
static std::string show(bool b) { return b ? "true" : "false"; }
static std::string show(const std::vector<int>& v) {
    std::string s = "{";
    for (std::size_t i = 0; i < v.size(); ++i) s += (i ? ", " : "") + std::to_string(v[i]);
    return s + "}";
}
static std::string show(const std::unordered_map<int, int>& m) {
    std::vector<std::pair<int, int>> pairs(m.begin(), m.end());
    std::sort(pairs.begin(), pairs.end());  // sorted by key, so the printout is the same on every machine
    std::string s = "{";
    for (std::size_t i = 0; i < pairs.size(); ++i)
        s += (i ? ", " : "") + std::to_string(pairs[i].first) + ": " + std::to_string(pairs[i].second);
    return s + "}";
}

static void check(bool ok, const std::string& what, const std::string& got = "") {
    std::cout << (ok ? "ok     " : "WRONG  ") << what;
    if (!ok && !got.empty()) std::cout << "   (got " << got << ")";
    std::cout << "\n";
    if (!ok) ++failures;
}

template <class T, class U>
static void expect(const T& got, const U& want, const std::string& what) {
    check(got == want, what, show(got));
}

// A two-sum answer is right when it names two different positions, in order, that add up.
static bool validPair(const std::vector<int>& v, int target, const std::vector<int>& r) {
    return r.size() == 2 && 0 <= r[0] && r[0] < r[1] && r[1] < static_cast<int>(v.size()) &&
           static_cast<long long>(v[r[0]]) + v[r[1]] == target;
}

static void step1() {
    expect(countPositives({}), 0, "countPositives({}) is 0");
    expect(countPositives({-1, 0, 2}), 1, "countPositives({-1, 0, 2}) is 1 (zero is not positive)");
    expect(countPositives({5, 5, 5}), 3, "countPositives({5, 5, 5}) is 3");
    expect(countPositives({-3, -2}), 0, "countPositives({-3, -2}) is 0");
}

static void step2() {
    expect(countEach({}), std::unordered_map<int, int>{}, "countEach({}) is an empty map");
    expect(countEach({3, 1, 3, 3}), std::unordered_map<int, int>{{3, 3}, {1, 1}}, "countEach({3, 1, 3, 3}) is {1: 1, 3: 3}");
    expect(countEach({-2, -2}), std::unordered_map<int, int>{{-2, 2}}, "countEach({-2, -2}) is {-2: 2}");
    expect(countEach({0}), std::unordered_map<int, int>{{0, 1}}, "countEach({0}) is {0: 1}");
    std::vector<int> big;
    for (int i = 0; i < 1000; ++i) { big.push_back(i); big.push_back(i); }
    auto counts = countEach(big);
    bool allTwo = counts.size() == 1000;
    for (int i = 0; i < 1000 && allTwo; ++i) allTwo = counts.count(i) && counts[i] == 2;
    check(allTwo, "countEach(0..999, each twice) has 1000 keys, each counted 2",
          std::to_string(counts.size()) + " keys");
}

static void step3() {
    expect(mostFrequent({4}), 4, "mostFrequent({4}) is 4");
    expect(mostFrequent({3, 1, 3, 3}), 3, "mostFrequent({3, 1, 3, 3}) is 3");
    expect(mostFrequent({1, 2, 2, 1}), 1, "mostFrequent({1, 2, 2, 1}) is 1 (a tie goes to the smaller value)");
    expect(mostFrequent({2, 1, 1, 2}), 1, "mostFrequent({2, 1, 1, 2}) is 1 (a tie goes to the smaller value)");
    expect(mostFrequent({9, 8, 8, 9, 7, 7}), 7, "mostFrequent({9, 8, 8, 9, 7, 7}) is 7 (three-way tie)");
    expect(mostFrequent({-5, -5, 7}), -5, "mostFrequent({-5, -5, 7}) is -5");
    expect(mostFrequent({-1, -2, -2, -1}), -2, "mostFrequent({-1, -2, -2, -1}) is -2 (smaller, not closer to zero)");
}

static void step4() {
    expect(firstUnique({}), -1, "firstUnique({}) is -1");
    expect(firstUnique({2, 3, 2}), 1, "firstUnique({2, 3, 2}) is 1");
    expect(firstUnique({1, 1}), -1, "firstUnique({1, 1}) is -1");
    expect(firstUnique({5}), 0, "firstUnique({5}) is 0");
    expect(firstUnique({4, 5, 4, 5, 6}), 4, "firstUnique({4, 5, 4, 5, 6}) is 4");
    expect(firstUnique({7, 7, 8, 9, 8}), 3, "firstUnique({7, 7, 8, 9, 8}) is 3 (an index, not the value 9)");
    expect(firstUnique({-1, 2, -1}), 1, "firstUnique({-1, 2, -1}) is 1");
    expect(firstUnique({1, 9}), 0, "firstUnique({1, 9}) is 0 (both are unique: the first position wins)");
    expect(firstUnique({9, 1}), 0, "firstUnique({9, 1}) is 0 (both are unique: the first position wins)");
}

static void step5() {
    expect(containsDuplicate({}), false, "containsDuplicate({}) is false");
    expect(containsDuplicate({1}), false, "containsDuplicate({1}) is false");
    expect(containsDuplicate({1, 2, 1}), true, "containsDuplicate({1, 2, 1}) is true");
    expect(containsDuplicate({-1, 1}), false, "containsDuplicate({-1, 1}) is false");
    expect(containsDuplicate({0, 0}), true, "containsDuplicate({0, 0}) is true");
    std::vector<int> big;
    for (int i = 0; i < 10000; ++i) big.push_back(i);
    expect(containsDuplicate(big), false, "containsDuplicate(0..9999) is false");
    big.push_back(9999);
    expect(containsDuplicate(big), true, "containsDuplicate(0..9999 plus one more 9999) is true");
}

static void step6() {
    expect(isAnagram("listen", "silent"), true, "isAnagram(\"listen\", \"silent\") is true");
    expect(isAnagram("a", "aa"), false, "isAnagram(\"a\", \"aa\") is false");
    expect(isAnagram("aa", "a"), false, "isAnagram(\"aa\", \"a\") is false (b is shorter)");
    expect(isAnagram("listen", "silen"), false, "isAnagram(\"listen\", \"silen\") is false (b is missing a letter)");
    expect(isAnagram("ab", "bb"), false, "isAnagram(\"ab\", \"bb\") is false");
    expect(isAnagram("aab", "abb"), false, "isAnagram(\"aab\", \"abb\") is false (same letters, different counts)");
    expect(isAnagram("", ""), true, "isAnagram(\"\", \"\") is true");
    expect(isAnagram("Aa", "aA"), true, "isAnagram(\"Aa\", \"aA\") is true");
    expect(isAnagram("Aa", "aa"), false, "isAnagram(\"Aa\", \"aa\") is false (case matters)");
    expect(isAnagram("ab", "ba "), false, "isAnagram(\"ab\", \"ba \") is false (spaces count)");
    expect(isAnagram("dormitory", "dirtyroom"), true, "isAnagram(\"dormitory\", \"dirtyroom\") is true");
}

static void step7() {
    std::vector<int> v = {2, 7, 11, 15};
    auto r = twoSum(v, 9);
    check(validPair(v, 9, r), "twoSum({2, 7, 11, 15}, 9) gives a valid pair", show(r));
    v = {3, 2, 4};
    r = twoSum(v, 6);
    check(validPair(v, 6, r), "twoSum({3, 2, 4}, 6) gives a valid pair (not 3 + itself)", show(r));
    v = {3, 3};
    r = twoSum(v, 6);
    check(validPair(v, 6, r), "twoSum({3, 3}, 6) gives {0, 1}", show(r));
    v = {-3, 4, 3, 90};
    r = twoSum(v, 0);
    check(validPair(v, 0, r), "twoSum({-3, 4, 3, 90}, 0) gives a valid pair", show(r));
    expect(twoSum({1, 2}, 10), std::vector<int>{}, "twoSum({1, 2}, 10) is {} (no pair)");
    expect(twoSum({}, 5), std::vector<int>{}, "twoSum({}, 5) is {}");
    expect(twoSum({5}, 10), std::vector<int>{}, "twoSum({5}, 10) is {} (one value cannot pair with itself)");
}

static void step8() {
    expect(exactSum({}), 0LL, "exactSum({}) is 0");
    expect(exactSum({1, 2, 3}), 6LL, "exactSum({1, 2, 3}) is 6");
    expect(exactSum({2000000000, 2000000000}), 4000000000LL, "exactSum({2e9, 2e9}) is 4000000000 (too big for an int)");
    expect(exactSum({-2000000000, -2000000000, -2000000000}), -6000000000LL, "exactSum({-2e9, -2e9, -2e9}) is -6000000000");
    expect(exactSum({2000000000, -2000000000, 7}), 7LL, "exactSum({2e9, -2e9, 7}) is 7");
}

static void step9() {
    expect(countPairsWithSum({1, 1, 1}, 2), 3LL, "countPairsWithSum({1, 1, 1}, 2) is 3");
    expect(countPairsWithSum({1, 5, 7, -1}, 6), 2LL, "countPairsWithSum({1, 5, 7, -1}, 6) is 2");
    expect(countPairsWithSum({}, 0), 0LL, "countPairsWithSum({}, 0) is 0");
    expect(countPairsWithSum({3, 3, 3, 3}, 6), 6LL, "countPairsWithSum({3, 3, 3, 3}, 6) is 6");
    expect(countPairsWithSum({1, 2, 3}, 10), 0LL, "countPairsWithSum({1, 2, 3}, 10) is 0");
    expect(countPairsWithSum({0, 0, 0}, 0), 3LL, "countPairsWithSum({0, 0, 0}, 0) is 3");
    expect(countPairsWithSum({2, 4, 3, 3}, 6), 2LL, "countPairsWithSum({2, 4, 3, 3}, 6) is 2");
    // 300'000 values: at 100'000 a compiler-vectorized pair of nested loops can finish in under a second.
    std::vector<int> ones(300000, 1);
    auto start = std::chrono::steady_clock::now();
    long long got = countPairsWithSum(ones, 2);
    double seconds = std::chrono::duration<double>(std::chrono::steady_clock::now() - start).count();
    expect(got, 44999850000LL, "countPairsWithSum(300000 ones, 2) is 44999850000 (too big for an int)");
    check(seconds < 1.5, "countPairsWithSum on 300000 values finishes in under 1.5 s (took " +
                             std::to_string(seconds) + " s)");
}

int main(int argc, char** argv) {
    int only = argc > 1 ? std::atoi(argv[1]) : 0;
    void (*steps[])() = {step1, step2, step3, step4, step5, step6, step7, step8, step9};
    for (int s = 1; s <= 9; ++s) {
        if (only != 0 && only != s) continue;
        std::cout << "-- step " << s << " --\n";
        try {
            steps[s - 1]();
        } catch (const std::exception& e) {
            std::cout << "WRONG  threw: " << e.what() << "\n";
            ++failures;
        }
    }
    std::cout << (failures == 0 ? "\nAll checks passed.\n" : "\nSome checks failed.\n");
    return failures == 0 ? 0 : 1;
}