Mercurial > lbo > hg > ccplay
changeset 9:8499a9b9ae47
Restore sane indentation
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Mon, 13 Mar 2023 23:14:42 +0100 |
parents | 60c7a574d536 |
children | 3ad8456efad1 |
files | dynprog.cc |
diffstat | 1 files changed, 137 insertions(+), 137 deletions(-) [+] |
line wrap: on
line diff
--- a/dynprog.cc Sun Mar 12 22:50:42 2023 +0100 +++ b/dynprog.cc Mon Mar 13 23:14:42 2023 +0100 @@ -15,192 +15,192 @@ 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); - } + public: + size_t operator()(const MemoKey &k) const { + return get<0>(k) ^ get<1>(k) ^ get<2>(k); + } }; 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 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)); - } + 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); + 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; } - 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); + 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); + fmt::print("Length: {} / {}\n", longest, longest_r); - return longest_seq; + return longest_seq; } // g++ only -template <typename T, template <typename> typename C> + template <typename T, template <typename> typename C> void evaluate_lcss(const C<T> &a, const C<T> &b) - requires ranges::range<C<T>> + 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); })); + 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); + 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, 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); + 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; + 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, 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); + 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; - } + if (result == sum_with_this && sum_with_this > sum_without_this && + sum_with_this == highest_sum) { + seqixs.at(length) = i; + } - return result; + return result; } -template <typename T, template <typename> typename C> + template <typename T, template <typename> typename C> void evaluate_liss(const C<T> &v) - requires ranges::range<C<T>> + 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(function([&a, &longest, &seqixs]() -> size_t { - return longest_increasing_subsequence( - a, 0, 0, 0, longest, seqixs); - }), - "longest incr. subsequence"); + vector<T> a(v.begin(), v.end()); + size_t longest = 0; + vector<size_t> seqixs(a.size()); + size_t result = timeit_f(function([&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); + fmt::print("Longest incr. subsequence has length {}/{} and has indices: {}\n", + longest, result, seqixs); - vector<T> seq(longest); - for (int i = 0; i < seq.size(); i++) - seq.at(i) = a.at(seqixs.at(i)); - fmt::print("Longest incr. subsequence is: {}\n", seq); + vector<T> seq(longest); + for (int 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> + template <typename T, template <typename> typename C> void evaluate_msis(const C<T> &v) - requires ranges::range<C<T>> + 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(function([&a, &highest, &seqixs]() -> size_t { - return max_sum_incr_subseq(a, 0, 0, 0, static_cast<T>(0), - highest, seqixs); - }), - "max sum incr. subsequence"); + vector<T> a(v.begin(), v.end()); + T highest = 0; + vector<size_t> seqixs(a.size()); + size_t result = + timeit_f(function([&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); + fmt::print( + "Max incr sum subseq subsequence has sum {}/{} and has indices: {}\n", + highest, result, seqixs); - vector<T> seq(seqixs.size()); - for (int 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); + vector<T> seq(seqixs.size()); + for (int 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); } 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}; + 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; + 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) { - 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; + vector<int> a{-1, 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_msis(a); + return 0; } - -int msis_main(void) { - vector<int> a{-1, 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_msis(a); - return 0; -}