54 lines
980 B
C++
54 lines
980 B
C++
#include "../../include/aoc.hpp"
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
|
|
unordered_map<string_view, ull> m;
|
|
vector<string> towels;
|
|
vector<string> designs;
|
|
|
|
ull rec(string_view s) {
|
|
if (s.empty()) {
|
|
return 1;
|
|
}
|
|
if (m.contains(s)) {
|
|
return m[s];
|
|
}
|
|
ull c = 0;
|
|
for (auto &t : towels) {
|
|
if (s.starts_with(t)) {
|
|
c += rec(s.substr(t.size()));
|
|
}
|
|
}
|
|
m[s] = c;
|
|
return c;
|
|
}
|
|
|
|
int main() {
|
|
ios::sync_with_stdio(0);
|
|
cin.tie(0);
|
|
|
|
string line;
|
|
getline(cin, line);
|
|
istringstream ll(line);
|
|
string s;
|
|
while (getline(ll, s, ',')) {
|
|
towels.push_back(s);
|
|
ll.ignore();
|
|
}
|
|
|
|
cin.ignore();
|
|
while (getline(cin, line)) {
|
|
designs.push_back(line);
|
|
}
|
|
|
|
// NOTE: designs gets their own global vector to make sure that the design
|
|
// strings live for as long as the memo does (it happened to work on the
|
|
// full data the first try without it but don't rely on that)
|
|
ull count = 0;
|
|
for (string &design : designs) {
|
|
count += rec(design);
|
|
}
|
|
|
|
cout << count << '\n';
|
|
}
|