Improved part 2 day 19 2024 with string_view

4 files changed, 70 insertions, 16 deletions

diff --git a/.gitignore b/.gitignore
index e436bca..84e360c 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,3 @@
 */*/*.out
 */*/*.txt
-*/*/.swp
+*/*/*.swp
diff --git a/2024/19/day19b-string.cpp b/2024/19/day19b-string.cpp
new file mode 100644
index 0000000..6f8b8f4
--- /dev/null
+++ b/2024/19/day19b-string.cpp
@@ -0,0 +1,54 @@
+#include <algorithm>
+#include <cstdint>
+#include <iostream>
+#include <map>
+#include <queue>
+#include <ranges>
+#include <set>
+#include <sstream>
+#include <string>
+#include <string_view>
+#include <vector>
+using namespace std;
+
+vector<string> gettowels(const string& line) {
+        vector<string> ret;
+        int j = 0;
+        for (int i = 0; j != -1; i = j+2) {
+                j = line.find(",", i);
+                ret.push_back(line.substr(i, (j == -1 ? line.size() : j)-i));
+        }
+        return ret;
+}
+
+int64_t countpossible(const string& p, const vector<string>& towels, vector<int64_t>& mem) {
+        if (p.size() == 0)
+                return 1;
+        if (mem[p.size()] != -1)
+                return mem[p.size()];
+        int64_t ret = 0;
+        for (auto t : towels) {
+                if (t == p.substr(0, t.size()))
+                        ret += countpossible(p.substr(
+                            t.size(), p.size() - t.size()), towels, mem);
+        }
+        return (mem[p.size()] = ret);
+}
+
+int main() {
+        string line;
+        getline(cin, line);
+        auto towels = gettowels(line);
+        getline(cin, line);
+        vector<string> patterns;
+        while (getline(cin, line))
+                patterns.push_back(line);
+        vector<int64_t> mem(1000);
+        int64_t count = 0;
+        for (auto p : patterns) {
+                for (auto& m : mem) m = -1;
+                count += countpossible(p, towels, mem);
+        }
+        cout << count << endl;
+        return 0;
+}
diff --git a/2024/19/day19b.cpp b/2024/19/day19b.cpp
index 6f8b8f4..dd6055d 100644
--- a/2024/19/day19b.cpp
+++ b/2024/19/day19b.cpp
@@ -11,28 +11,27 @@
 #include <vector>
 using namespace std;
 
-vector<string> gettowels(const string& line) {
-        vector<string> ret;
-        int j = 0;
-        for (int i = 0; j != -1; i = j+2) {
+vector<string_view> gettowels(const string_view& line) {
+        vector<string_view> ret;
+        unsigned sz = line.size();
+        for (int i = 0, j = 0; j != -1; i = j+2) {
                 j = line.find(",", i);
-                ret.push_back(line.substr(i, (j == -1 ? line.size() : j)-i));
+                ret.push_back(line.substr(i, (j == -1 ? sz : j) - i));
         }
         return ret;
 }
 
-int64_t countpossible(const string& p, const vector<string>& towels, vector<int64_t>& mem) {
-        if (p.size() == 0)
-                return 1;
-        if (mem[p.size()] != -1)
-                return mem[p.size()];
+int64_t f(const string_view& p, const vector<string_view>& towels, vector<int64_t>& mem) {
+        unsigned lp = p.size();
+        if (lp == 0) return 1;
+        if (mem[lp] != -1) return mem[lp];
         int64_t ret = 0;
         for (auto t : towels) {
-                if (t == p.substr(0, t.size()))
-                        ret += countpossible(p.substr(
-                            t.size(), p.size() - t.size()), towels, mem);
+                unsigned lt = t.size();
+                if (t == p.substr(0, lt))
+                        ret += f(p.substr(lt, lp - lt), towels, mem);
         }
-        return (mem[p.size()] = ret);
+        return (mem[lp] = ret);
 }
 
 int main() {
@@ -47,7 +46,7 @@ int main() {
         int64_t count = 0;
         for (auto p : patterns) {
                 for (auto& m : mem) m = -1;
-                count += countpossible(p, towels, mem);
+                count += f(p, towels, mem);
         }
         cout << count << endl;
         return 0;
diff --git a/2024/learned.txt b/2024/learned.txt
index 440571a..ba00c6c 100644
--- a/2024/learned.txt
+++ b/2024/learned.txt
@@ -9,3 +9,4 @@ List of things I learned (or refreshed) with this year's AoC.
 * Day 8: set::insert_range(), but it is from C++23 only
 * Day 9: std::views
 * Day 11: if(init; cond)
+* Day 19: more practice with std::string_view for constant string