Branch data     Line data    Source code

       1                 :             : #include <iostream>
       2                 :             : #include <fstream>
       3                 :             : #include <vector>
       4                 :             : #include <unordered_map>
       5                 :             : #include <sstream>
       6                 :             : #include <string_view>
       7                 :             : #include <array>
       8                 :             : using namespace std;
       9                 :             : 
      10                 :             : unordered_map<string_view, uint64_t> memo;
      11                 :             : vector<string> patterns;
      12                 :             : array<vector<string>, 256> buckets;
      13                 :             : 
      14                 :       52494 : uint64_t countWays(string_view design) {
      15         [ +  + ]:       52494 :   if (design.empty()) {
      16                 :         174 :     return 1;
      17                 :             :   }
      18         [ +  + ]:       52320 :   if (auto it = memo.find(design); it != memo.end()) {
      19                 :       34158 :     return it->second;
      20                 :             :   }
      21                 :             : 
      22                 :       18162 :   const auto& cand = buckets[design[0]];
      23                 :             : 
      24                 :       18162 :   uint64_t ways = 0;
      25         [ +  + ]:     1638057 :   for (const auto &pattern : cand) {
      26         [ +  + ]:     1619895 :     if (design.starts_with(pattern)) {
      27                 :       52094 :       ways += countWays(design.substr(pattern.size()));
      28                 :             :     }
      29                 :             :   }
      30                 :       18162 :   return memo[design] = ways;
      31                 :             : }
      32                 :             : 
      33                 :           2 : int main() {
      34                 :           2 :   ifstream input("input.txt");
      35         [ +  + ]:           2 :   if (!input) {
      36                 :           1 :     cerr << "Error opening file." << endl;
      37                 :           1 :     return 1;
      38                 :             :   }
      39                 :             : 
      40                 :           1 :   vector<string> designs;
      41                 :           1 :   string line;
      42                 :           1 :   getline(input, line);
      43                 :           1 :   stringstream ss(line);
      44         [ +  + ]:         447 :   for (string token; getline(ss, token, ',') >> ws; ) {
      45                 :         446 :     buckets[token[0]].push_back(std::move(token));
      46                 :           1 :   }
      47                 :             : 
      48         [ +  + ]:         403 :   while (getline(input, line)) {
      49         [ +  + ]:         401 :     if (!line.empty()) {
      50                 :         400 :       designs.push_back(std::move(line));
      51                 :             :     }
      52                 :             :   }
      53                 :             : 
      54                 :           1 :   uint64_t totalWays = 0;
      55         [ +  + ]:         401 :   for (const auto &design : designs) {
      56                 :         400 :     totalWays += countWays(design);
      57                 :             :   }
      58                 :             : 
      59                 :           1 :   cout << totalWays << endl;
      60         [ +  + ]:           3 : }