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;
+}
+