psychic-model.cpp

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <random>

using namespace std;

typedef vector<vector<int>> vector_2d_t;
typedef vector<vector<vector<int>>> vector_3d_t;

std::ostream &operator<<(std::ostream &o, vector_2d_t vv) {
    for (auto v : vv) {
        for (auto item : v) {
            o << "[" << item << "]";
        }
        o << '\n';
    }

    return o;
}

std::ostream &operator<<(std::ostream &o, vector_3d_t& vvv) {
    for (auto vv : vvv) {
        o << "Set: ";

        for (auto v : vv) {
            o << "[";

            for (int i = 0; i < v.size(); i++) {
                o << v[i];

                if (i != v.size() - 1) {
                    o << " ";
                }
            }

            o << "]";
        }

        o << '\n';
    }

    return o;
}

std::ostream &operator<<(std::ostream &o, vector<int> v) {
    for (auto item : v) {
        o << item << " ";
    }

    return o;
}

int n_choose_k(int n, int k) {
    if (k == 0) {
        return 1;
    }

    return (n * n_choose_k(n - 1, k - 1)) / k;
}

void recurse(vector_2d_t& subsets, vector<int>& subset, vector<int>& nums, int start, int n, int k) {
    if (k == 0) {
        subsets.push_back(subset);
        return;
    }

    for (int i = start; i < nums.size(); i++) {
        subset.push_back(nums[i]);

        recurse(subsets, subset, nums, i + 1, n, k - 1);

        subset.pop_back();
    }
}

vector_2d_t combine(int n, int k) {
    vector_2d_t subsets;
    vector<int> subset;

    vector<int> nums;
    for (int i = 1; i <= n; i++) {
        nums.push_back(i);
    }

    recurse(subsets, subset, nums, 0, n, k);
    return subsets;
}

int count_false_bits(vector<bool> v) {
    return std::count(v.begin(), v.end(), false);
}

vector<int> sample_k_subset(int N, int k) {
    static std::random_device rd;
    static std::mt19937 gen(rd());
    static std::uniform_int_distribution<> dis(1, N);

    unordered_set<int> elems;

    while (elems.size() < k) {
        elems.insert(dis(gen));
    }

    vector<int> result(elems.begin(), elems.end());
    sort(result.begin(), result.end());

    return result;
}

int sample_k_number(int k) {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(1, k);

    return dis(gen);
}

/* s1, s2 must be sorted for this to work */
int get_subset_intersection(vector<int> s1, vector<int> s2) {
    int count = 0;

    for (auto i = s1.begin(); i != s1.end(); ++i) {
        if (std::find(s2.begin(), s2.end(), *i) != s2.end()) {
            count++;
        }
    }

    return count;
}

int count_coverage(vector_2d_t& nj_subsets, vector<int>& ticket, vector<bool>& v, int j, int l) {
    int covered_count = 0;

    for (int i = 0; i < v.size(); i++) {
        if (v[i] == true) {
            continue;
        }

        vector<int> curr_subset = nj_subsets[i];

        int intersection = get_subset_intersection(ticket, curr_subset);

        if (intersection >= l) {
            v[i] = true;
            covered_count++;
        }
    }

    return covered_count;
}

vector_2d_t lotto_ticket_set(int n, int k, int j, int l, int RANDOM_SAMPLE_LEN) {
    vector_2d_t ticket_set;

    vector_2d_t nj_subsets = combine(n, j);
    vector<bool> v(nj_subsets.size(), false);

    cout << "NJ subsets size: " << v.size() << "\n";

    int covered_so_far = 0;
    int max_coverage = 0;
    vector<bool> temp_v = v;

    cout << "Picking tickets...\n" << "---\n";

    while (covered_so_far != v.size()) {
        max_coverage = 0;
        vector<int> max_coverage_ticket;

        for (int i = 0; i < RANDOM_SAMPLE_LEN; i++) {
            vector<int> k_ticket_sample = sample_k_subset(n, k);
            temp_v = v;

            int covered = count_coverage(nj_subsets, k_ticket_sample, temp_v, j, l);

            if (covered > max_coverage) {
                max_coverage = covered;
                max_coverage_ticket = k_ticket_sample;
            }
        }

        if (max_coverage != 0) {
            covered_so_far += max_coverage;
            count_coverage(nj_subsets, max_coverage_ticket, v, j, l);

            ticket_set.push_back(max_coverage_ticket);
        }

        cout << "Covered: " << covered_so_far << " out of " << v.size()
             << " (" << ticket_set.size() << ")\n";
    }

    return ticket_set;
}

bool vector_contains(vector<int> v, int item) {
    return std::find(v.begin(), v.end(), item) != v.end();
}

void test(vector_2d_t tickets, int n, int k, int j, int l, int TEST_EXPERIMENTS) {
    int s = n * 2;

    for (int i = 1; i < TEST_EXPERIMENTS + 1; i++) {
        cout << "Experiment #" << i << ": ";

        vector<int> j_numbers = sample_k_subset(n, j);
        vector<int> win_numbers = j_numbers;

        while (win_numbers.size() < k) {
            int sample_s = sample_k_number(s);

            if (!vector_contains(win_numbers, sample_s)) {
                win_numbers.push_back(sample_s);
            }
        }

        sort(win_numbers.begin(), win_numbers.end());

        vector<int> winning_ticket;

        for (auto ticket : tickets) {
            if (get_subset_intersection(ticket, win_numbers) >= l) {
                winning_ticket = ticket;
            }
        }

        if (winning_ticket.size() > 0) {
            cout << "Winning ticket: " << winning_ticket << '\n';
        } else {
            cout << "Experiment failed: Tickets did not win!" << '\n';
            cout << "Predicted numbers: " << j_numbers << '\n';
            cout << "Winning numbers: " << win_numbers << '\n';
            return;
        }
    }
}

int estimate_lower_bound(int n, int k, int j, int l) {
    int max_nj_covered_with_ticket_of_k = 0;

    for (int i = l; i <= j; i++) {
        max_nj_covered_with_ticket_of_k += n_choose_k(k, i) * n_choose_k(n - k, j - i);
    }

    int nj_subsets_size = n_choose_k(n, j);
    int lower_bound_ticket_size = ceil(nj_subsets_size / (double)max_nj_covered_with_ticket_of_k);

    cout << "NJ subsets to cover: " << nj_subsets_size << '\n';
    cout << "Max subsets covered with one ticket: " << max_nj_covered_with_ticket_of_k << '\n';
    cout << "Lower bound: " << lower_bound_ticket_size << '\n';

    return lower_bound_ticket_size;
}

void print_answer(vector_2d_t tickets) {
    cout << "---\n";
    cout << "Winning tickets: \n";
    cout << tickets;
    cout << "Tickets size: " << tickets.size() << '\n';
}

int main() {
    /*
        n: set of predicted numbers
        k: amount of numbers in the ticket
        j: number of guaranteed items from set of predicted numbers
        l: matched numbers to win
    */
    const int n = 18, k = 10, j = 7, l = 6;
    const int RANDOM_SAMPLE_LEN = 100;
    const int TEST_EXPERIMENTS = 3000;

    int ticket_set_lower_bound = estimate_lower_bound(n, k, j, l);

    vector_2d_t tickets = lotto_ticket_set(n, k, j, l, RANDOM_SAMPLE_LEN);

    test(tickets, n, k, j, l, TEST_EXPERIMENTS);

    print_answer(tickets);
}