Branch data     Line data    Source code

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