Mercurial > lbo > hg > ccplay
changeset 20:ecc574aa2021
wordcount with <algorithms>
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Fri, 07 Apr 2023 15:13:48 +0200 |
parents | 3a4bc31d0ffe |
children | ae1327f0f99f |
files | CMakeLists.txt arrays.cc dynprog.cc wordcount.cc |
diffstat | 4 files changed, 74 insertions(+), 16 deletions(-) [+] |
line wrap: on
line diff
--- a/CMakeLists.txt Tue Apr 04 22:11:01 2023 +0200 +++ b/CMakeLists.txt Fri Apr 07 15:13:48 2023 +0200 @@ -7,17 +7,16 @@ ADD_SUBDIRECTORY(lib) LINK_LIBRARIES(fmt) -ADD_EXECUTABLE(time time.cc) -TARGET_LINK_LIBRARIES(time exec) - ADD_EXECUTABLE(arrays arrays.cc) -TARGET_LINK_LIBRARIES(arrays exec) - ADD_EXECUTABLE(cclib cclib.cc) -TARGET_LINK_LIBRARIES(cclib exec) +ADD_EXECUTABLE(dynprog dynprog.cc) +ADD_EXECUTABLE(sorting sorting.cc) +ADD_EXECUTABLE(time time.cc) +ADD_EXECUTABLE(wordcount wordcount.cc) -ADD_EXECUTABLE(sorting sorting.cc) +TARGET_LINK_LIBRARIES(arrays exec) +TARGET_LINK_LIBRARIES(cclib exec) +TARGET_LINK_LIBRARIES(dynprog exec) TARGET_LINK_LIBRARIES(sorting exec) - -ADD_EXECUTABLE(dynprog dynprog.cc) -TARGET_LINK_LIBRARIES(dynprog exec) +TARGET_LINK_LIBRARIES(time exec) +TARGET_LINK_LIBRARIES(wordcount exec)
--- a/arrays.cc Tue Apr 04 22:11:01 2023 +0200 +++ b/arrays.cc Fri Apr 07 15:13:48 2023 +0200 @@ -48,8 +48,10 @@ return 0; } + + int main(int argc, char** argv) { - if (argc < 1) { + if (argc < 2) { cerr << "need task supplied on command line!\n"; return 1; }
--- a/dynprog.cc Tue Apr 04 22:11:01 2023 +0200 +++ b/dynprog.cc Fri Apr 07 15:13:48 2023 +0200 @@ -406,15 +406,20 @@ 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))) + 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) { +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) @@ -426,7 +431,6 @@ return entry->second; int mincuts = to-from; - size_t minix = to; for (size_t i = from+1; i < to; i++) { // Split at i. int cuts1 = minimum_palindrome_cuts<T>(range, from, i, memo); @@ -434,7 +438,6 @@ int cuts = 1 + cuts1 + cuts2; if (cuts < mincuts) { mincuts = cuts; - minix = i; } } memo.insert(make_pair(key, mincuts));
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/wordcount.cc Fri Apr 07 15:13:48 2023 +0200 @@ -0,0 +1,54 @@ + +#include "lib/exec.h" + +#include <algorithm> +#include <numeric> +#include <iterator> +#include <iostream> +#include <memory> +#include <string> +#include <unordered_map> + +using namespace std; + +unordered_map<string, unsigned int> word_count(istream& is) { + istream_iterator<string> iter(is); + unordered_map<string, unsigned int> counts; + + auto reducer = [](decltype(counts)* c, string word) -> decltype(counts)* { + auto entry = c->find(word); + if (entry != c->end()) { + entry->second++; + } else { + c->insert(make_pair(move(word), 1)); + } + + return c; + }; + auto mapper = [](const string& w) -> const string& { return w; }; + + transform_reduce(iter, decltype(iter)(), &counts, reducer, mapper); + + return counts; +} + +template<typename K, typename V> +void format_word_count(const unordered_map<K, V>& counts) { + vector<pair<K,V>> pairs(counts.cbegin(), counts.cend()); + sort(pairs.begin(), pairs.end(), [](const pair<K,V>& p1, const pair<K,V>& p2) -> bool { return p1.second < p2.second; }); + + for_each(pairs.begin(), pairs.end(), [](const pair<K,V>& p) { + fmt::print("{} -> {}\n", p.first, p.second); + }); +} + +int main(int argc, char** argv) { + if (argc < 2) { + timeit_f([]() { + format_word_count(word_count(cin)); + }, "wordcount"); + } + + return 0; +} +