#include "lib/exec.h"

#include <functional>
#include <iostream>
#include <numeric>
#include <ranges>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>

using namespace std;
using namespace std::ranges;

using MemoKey = tuple<size_t, size_t, size_t>;

class TupleHash : function<size_t(const MemoKey &)> {
    public:
        size_t operator()(const MemoKey &k) const {
            return get<0>(k) ^ get<1>(k) ^ get<2>(k);
        }
};

class PairHash : function<size_t(const MemoKey &)> {
    public:
        template <typename T, typename U>
            size_t operator()(const pair<T, U> &p) const {
                return hash<T>{}(p.first) ^ hash<U>{}(p.second);
            }
};

template <typename T>
size_t lcss_inner(
        const vector<T> &a, const vector<T> &b, size_t i, size_t j, size_t length,
        size_t &longest, vector<T> &longest_seq,
        unordered_map<tuple<size_t, size_t, size_t>, size_t, TupleHash> &cache) {
    if (i >= a.size() || j >= b.size()) {
        return length;
    }

    const auto key = make_tuple(i, j, length);
    if (cache.contains(key)) {
        return get<1>(*cache.find(key));
    }

    if (a.at(i) == b.at(j)) {
        // Current (i, j) is member of a common subsequence.
        longest = max(longest, length + 1);
        size_t remaining_longest =
            lcss_inner(a, b, i + 1, j + 1, length + 1, longest, longest_seq, cache);
        if (remaining_longest == longest) {
            // This element is part of the longest common subsequence.
            longest_seq.at(length) = a.at(i);
        }
        cache.insert(make_pair(key, remaining_longest));
        return remaining_longest;
    } else {
        // Skip element from a.
        size_t remaining_longest_skip_a =
            lcss_inner(a, b, i + 1, j, length, longest, longest_seq, cache);
        // Skip element from b.
        size_t remaining_longest_skip_b =
            lcss_inner(a, b, i, j + 1, length, longest, longest_seq, cache);
        size_t result = max(remaining_longest_skip_a, remaining_longest_skip_b);
        cache.insert(make_pair(key, result));
        return result;
    }
}

template <typename T> vector<T> lcss(const vector<T> &a, const vector<T> &b) {
    size_t longest = 0;
    vector<T> longest_seq(min(a.size(), b.size()));
    unordered_map<tuple<size_t, size_t, size_t>, size_t, TupleHash> cache(100);
    size_t longest_r = lcss_inner(a, b, 0, 0, 0, longest, longest_seq, cache);

    fmt::print("Length: {} / {}\n", longest, longest_r);

    return longest_seq;
}
// g++ only
    template <typename T, template <typename> typename C>
void evaluate_lcss(const C<T> &a, const C<T> &b)
    requires ranges::range<C<T>>
{
    vector<T> va(a.begin(), a.end());
    vector<T> vb(b.begin(), b.end());
    auto result = timeit_f(function([&va, &vb]() { return lcss(va, vb); }));

    fmt::print("{}\n", va);
    fmt::print("{}\n", vb);
    fmt::print("{}\n", result);
}

template <typename T>
size_t longest_increasing_subsequence(const vector<T> &a, size_t i, size_t prev,
        size_t length, size_t &longest,
        vector<size_t> &seqixs) {
    longest = max(length, longest);
    if (i >= a.size())
        return length;

    size_t length_with_current =
        a.at(i) < a.at(prev) ? length
        : longest_increasing_subsequence(
                a, i + 1, i, length + 1, longest, seqixs);
    size_t length_without_current =
        longest_increasing_subsequence(a, i + 1, prev, length, longest, seqixs);
    size_t result = max(length_with_current, length_without_current);

    if (result == length_with_current && result == longest) {
        seqixs.at(length) = i;
    }
    return result;
}

// Bug: if first element is 0 or negative, may repeat last index in seqixs
template <typename T>
T max_sum_incr_subseq(const vector<T> &a, size_t i, size_t prev, size_t length,
        T sum, T &highest_sum, vector<size_t> &seqixs) {
    highest_sum = max(sum, highest_sum);
    if (i >= a.size())
        return sum;

    T sum_with_this =
        a.at(i) < a.at(prev)
        ? sum
        : max_sum_incr_subseq(a, i + 1, i, length + 1, sum + a.at(i),
                highest_sum, seqixs);
    T sum_without_this =
        max_sum_incr_subseq(a, i + 1, prev, length, sum, highest_sum, seqixs);
    T result = max(sum_with_this, sum_without_this);

    if (result == sum_with_this && sum_with_this > sum_without_this &&
            sum_with_this == highest_sum) {
        seqixs.at(length) = i;
    }

    return result;
}

    template <typename T, template <typename> typename C>
void evaluate_liss(const C<T> &v)
    requires ranges::range<C<T>>
{
    vector<T> a(v.begin(), v.end());
    size_t longest = 0;
    vector<size_t> seqixs(a.size());
    size_t result = timeit_f(
            [&a, &longest, &seqixs]() -> size_t {
            return longest_increasing_subsequence(a, 0, 0, 0, longest, seqixs);
            },
            "longest incr. subsequence");

    fmt::print("Longest incr. subsequence has length {}/{} and has indices: {}\n",
            longest, result, seqixs);

    vector<T> seq(longest);
    for (size_t i = 0; i < seq.size(); i++)
        seq.at(i) = a.at(seqixs.at(i));
    fmt::print("Longest incr. subsequence is: {}\n", seq);
}

    template <typename T, template <typename> typename C>
void evaluate_msis(const C<T> &v)
    requires ranges::range<C<T>>
{
    vector<T> a(v.begin(), v.end());
    T highest = 0;
    vector<size_t> seqixs(a.size());
    size_t result = timeit_f(
            [&a, &highest, &seqixs]() -> size_t {
            return max_sum_incr_subseq(a, 0, 0, 0, static_cast<T>(0), highest,
                    seqixs);
            },
            "max sum incr. subsequence");

    fmt::print(
            "Max incr sum subseq subsequence has sum {}/{} and has indices: {}\n",
            highest, result, seqixs);

    vector<T> seq(seqixs.size());
    for (size_t i = 0; i < seq.size(); i++) {
        if (i > 0 && seqixs.at(i) == 0)
            break;
        seq.at(i) = a.at(seqixs.at(i));
    }
    fmt::print("Max sum incr. subsequence is: {}\n", seq);
}

template <typename T> string digits2string(const vector<T> &v) {
    ostringstream s;
    for (const T &e : v) {
        s << e;
    }
    return s.str();
}

void keypad(const unordered_map<int, vector<int>> &adj, vector<int> seq,
        int n) {
    if (n <= 0) {
        cout << digits2string(seq) << " ";
    } else {
        if (seq.empty()) {
            for (int k : views::keys(adj)) {
                keypad(adj, vector<int>{k}, n - 1);
            }
        } else {
            int last = seq.back();
            const vector<int> &neighbors = adj.at(last);
            for (int neigh : neighbors) {
                seq.push_back(neigh);
                keypad(adj, seq, n - 1);
                seq.pop_back();
            }
        }
    }
}

size_t count_keypad(const unordered_map<int, vector<int>> &adj, int last, int n,
        unordered_map<pair<int, int>, size_t, PairHash> &memo) {
    if (n == 0)
        return 1;

    const auto memopos = memo.find(make_pair(last, n));
    if (memopos != memo.end())
        return memopos->second;

    if (last < 0) {
        const auto ks = views::keys(adj);
        auto tf = views::transform(ks, [&adj, &memo, n](int key) -> size_t {
                return count_keypad(adj, key, n - 1, memo);
                });
        size_t result = reduce(tf.begin(), tf.end());
        memo.insert(make_pair(make_pair(last, n), result));
        return result;
    } else {
        const auto &neighbors = adj.at(last);
        const auto counts =
            views::transform(neighbors, [&adj, &memo, n](int neigh) -> size_t {
                    return count_keypad(adj, neigh, n - 1, memo);
                    });
        size_t result = reduce(counts.begin(), counts.end());
        memo.insert(make_pair(make_pair(last, n), result));
        return result;
    }
}

// https://www.techiedelight.com/count-total-possible-combinations-n-digit-numbers-mobile-keypad/
void evaluate_keypad(size_t n = 2) {
    unordered_map<int, vector<int>> adjacency{
        {1, {1, 2, 4}},    {2, {1, 2, 3, 5}},    {3, {2, 3, 6}},
            {4, {1, 4, 5, 7}}, {5, {2, 5, 6, 8, 4}}, {6, {3, 6, 5, 9}},
            {7, {4, 7, 8}},    {8, {7, 5, 8, 9, 0}}, {9, {6, 8, 9}},
            {0, {0, 8}},
    };
    unordered_map<pair<int, int>, size_t, PairHash> memo;

    // keypad(adjacency, vector<int>{}, n);
    cout << endl;

    size_t ck = timeit_f(([&adjacency, &memo, n]() {
                return count_keypad(adjacency, -1, n, memo);
                }),
            "count_keypad");
    fmt::print("count = {}\n", ck);

    fmt::print("memoize count = {}\n", memo.size());
}

bool wildcard_matches(string::const_iterator pbegin,
        string::const_iterator pend,
        string::const_iterator sbegin,
        string::const_iterator send) {
    // Pattern finished but string not finished.
    if (pbegin == pend && sbegin < send) {
        return false;
    }
    // String ended and pattern not definitely ended.
    if (sbegin == send) {
        return pbegin == pend;
    }
    if (*pbegin == *sbegin || *pbegin == '?') {
        return wildcard_matches(pbegin + 1, pend, sbegin + 1, send);
    }
    if (*pbegin == '*') {
        // Keep or consume wildcard.
        return wildcard_matches(pbegin, pend, sbegin + 1, send) ||
            wildcard_matches(pbegin + 1, pend, sbegin + 1, send);
    }
    return false;
}

bool wildcard_matches(const string &pattern, const string &str) {
    return wildcard_matches(pattern.begin(), pattern.end(), str.begin(),
            str.end());
}

void evaluate_wildcard_matches() {
    vector<pair<string, string>> tests{
        {"xyxzzxy", "x***y"},
            {"xyxzzxy", "x***x"},
            {"xyxzzxy", "x***x?"},
            {"xyxzzxy", "*"},
    };

    for (const auto &p : tests) {
        benchmarkit_f([&]() { wildcard_matches(p.second, p.first); },
                "wildcard_matches");
        fmt::print("{} matches {} ? => {}\n", p.first, p.second,
                wildcard_matches(p.second, p.first));
    }
}

// TODO: store cutting way
int rodcutting_prod_max(int length) {
    if (length <= 1)
        return 1;
    int max_len = 0;
    for (int this_part = length; this_part > 0; this_part--) {
        max_len = max(max_len, this_part * rodcutting_prod_max(length - this_part));
    }
    return max_len;
}

// https://www.techiedelight.com/coin-change-problem-find-total-number-ways-get-denomination-coins/
int coin_change_problem(const vector<int> &coins, int amount_left,
        vector<int> &current,
        vector<vector<int>> &possibilities) {
    if (amount_left == 0 && !current.empty()) {
        possibilities.push_back(current);
        return 1;
    } else if (amount_left > 0) {
        int possible_count = 0;
        for (int coin : coins) {
            if (coin > amount_left)
                continue;
            if (!current.empty() && coin < *(current.end() - 1))
                continue;
            current.push_back(coin);
            possible_count += coin_change_problem(coins, amount_left - coin, current,
                    possibilities);
            current.pop_back();
        }
        return possible_count;
    }
    return 0;
}

void evaluate_coin_change() {
    vector<int> coins{1, 3, 5, 7};
    int amount = 8;
    vector<int> current{};
    vector<vector<int>> possibilities{};

    int N = timeit_f([&]() -> int {
            return coin_change_problem(coins, amount, current, possibilities);
            });

    fmt::print("{}: {}\n", N, possibilities);
}

template <typename R, typename RT>
requires range<R> && is_same_v<range_value_t<R>, RT> bool
three_partition_inner(const R &r, size_t ix, RT a, RT b, RT c, unordered_map<tuple<int,int,int>, bool, TupleHash>& memo) {
    if (r.begin() + ix == r.end()) {
        return (a == b) && (b == c);
    }

    //auto key = make_tuple(a, b, c);
    //auto entry = memo.find(key);
    //if (entry != memo.end()) {
    //    return entry->second;
    //}

    using It = decltype(std::ranges::begin(r));

    //fmt::print("{} : {} {} {}\n", ix, a, b, c);
    It beg = r.begin() + ix;
    RT val = *beg;

    // Check three cases.
    bool result = three_partition_inner(r, ix + 1, a + val, b, c, memo) ||
        three_partition_inner(r, ix + 1, a, b + val, c, memo) ||
        three_partition_inner(r, ix + 1, a, b, c + val, memo);
    //memo.insert({key, result});
    return result;
}

template <typename R>
requires range<R> bool
three_partition(const R &r) {
    using T = range_value_t<R>;
    unordered_map<tuple<int,int,int>, bool, TupleHash> memo;
    return three_partition_inner<R, T>(r, 0, T(0), T(0), T(0), memo);
}

int three_partition_main(void) {
    vector<int> a{50, 49, 1, 98, 1, 1, 90, 3, 3, 4};
    fmt::print("{}: {}\n", a, timeit_f([&a]() { return three_partition(a); }));
    return 0;
}

int lcss_main(void) {

    vector<int> a{1, 6, 2, -1, 3, 55, 2, 4, 23, 5, 6, 7, 8, 9, 10};
    vector<int> b{-3, 1, 5, 7, 2, 4, -1, 3, 6, 7, 9, 11, 10};

    evaluate_lcss(a, b);
    evaluate_lcss(views::single(11), views::single(11));
    return 0;
}

int liss_main(void) {
    vector<int> a{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11};
    // Expect: 0,2,6,9,13 or ,11
    // or 0,4,6,9,13
    evaluate_liss(a);
    return 0;
}

int main(void) {
    three_partition_main();
    return 0;
}