Mercurial > lbo > hg > ccplay
view dynprog.cc @ 15:fc43055d41d8
DP: coin change, more efficient
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Wed, 22 Mar 2023 21:56:20 +0100 |
parents | 3cf1e46d317e |
children | f3324364ceda |
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 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); } 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) { evaluate_coin_change(); return 0; }