Mercurial > lbo > hg > ccplay
view dynprog.cc @ 24:b89680a8af68 default tip
graph: detect negative cycles
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Sun, 09 Apr 2023 17:27:20 +0200 |
parents | ecc574aa2021 |
children |
line wrap: on
line source
#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> ¤t, 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; } template<typename It> requires random_access_iterator<It> bool is_palindrome(It begin, It end) { const size_t s = end - begin; for (size_t i = 0; i < s/2; i++) { if (begin[i] != begin[(s-i-1)]) return false; } return true; } // https://www.techiedelight.com/find-minimum-cuts-needed-palindromic-partition-string/ template <typename T, typename R> requires range<R> && is_same_v<range_value_t<R>, T> && random_access_iterator<iterator_t<R>> int minimum_palindrome_cuts( const R &range, size_t from, size_t to, unordered_map<pair<size_t, size_t>, int, PairHash> &memo) { if (is_palindrome(range.begin()+from, range.begin()+to)) return 0; if (to - from == 1) return 0; auto key = make_pair(from, to); auto entry = memo.find(key); if (entry != memo.end()) return entry->second; int mincuts = to-from; for (size_t i = from+1; i < to; i++) { // Split at i. int cuts1 = minimum_palindrome_cuts<T>(range, from, i, memo); int cuts2 = minimum_palindrome_cuts<T>(range, i, to, memo); int cuts = 1 + cuts1 + cuts2; if (cuts < mincuts) { mincuts = cuts; } } memo.insert(make_pair(key, mincuts)); return mincuts; } int minimum_palindrome_cuts_main(char** argv) { string s{argv[1]}; unordered_map<pair<size_t, size_t>, int, PairHash> memo{}; fmt::print("{}\n", timeit_f([&]() { return minimum_palindrome_cuts<char>(s, 0, s.size(), memo); })); } 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(int argc, char** argv) { minimum_palindrome_cuts_main(argv); return 0; }