% time ./challenge < words.txt > digest.txt Reading in single words. 61406 single words. Finding all useful single words. 3477 useful single words. Listing all pairs of words. 6043026 total pairs. Finding all useful pairs. 14574 useful pairs. Listing all triples of words. 50644650 total triples. Finding all useful triples. 289 useful triples. Finding a single universal quadruple. Universal quadruple found. 952.27u 3.88s 15:57.57 99.8% ##```## #include #include #include #include using namespace std; // Combination consists of chosen words and present letters bitfield struct combination { unsigned short a, b, c, d; unsigned long present; combination* next; // Next non-useless combination (see find_useless) }; bool operator < ( const combination& u, const combination& v ) { return u.present > v.present; } const short NONE = -1; // I'm aware of the signed -> unsigned conversion const unsigned long ALL = (1 << 26) - 1; int optimize( int ); void find_useless( vector&, vector& ); int main( ) { int i, j; vector words; vector one, onep, two, twop, three, threep, four; // Read input, compute "present" bitfields cerr << "Reading in single words." << endl; string word; for( i = 0; cin >> word; i++ ) { combination c = {i, NONE, NONE, NONE, 0, NULL}; for( j = 0; j < word.length(); j++ ) { if( word[j] >= 'A' && word[j] <= 'Z' ) word[j] += 'a' - 'A'; if( word[j] < 'a' || word[j] > 'z' ) continue; c.present |= 1 << (word[j] - 'a'); } words.push_back( word ); one .push_back( c ); } cerr << one.size() << " single words." << endl; // Find useless words cerr << "Finding all useful single words." << endl; find_useless( one, onep ); cerr << onep.size() << " useful single words." << endl; one = vector(); for( i = 0; i < onep.size(); i++ ) cout << words[onep[i].a] << "\n"; // Compute all doubles now cerr << "Listing all pairs of words.\n"; for( i = 0; i < onep.size(); i++ ) { for( j = i+1; j < onep.size(); j++ ) { combination c = {onep[i].a, onep[j].a, NONE, NONE, onep[i].present | onep[j].present, NULL}; two.push_back( c ); } } cerr << two.size() << " total pairs." << endl; // Find useless two-word combinations cerr << "Finding all useful pairs." << endl; find_useless( two, twop ); cerr << twop.size() << " useful pairs." << endl; two = vector(); for( i = 0; i < twop.size(); i++ ) cout << words[twop[i].a] << " " << words[twop[i].b] << "\n"; // Compute all triples now cerr << "Listing all triples of words." << endl; for( i = 0; i < onep.size(); i++ ) { for( j = 0; j < twop.size(); j++ ) { if( onep[i].a == twop[j].a || onep[i].a == twop[j].b ) continue; combination c = {onep[i].a, twop[j].a, twop[j].b, NONE, onep[i].present | twop[j].present, NULL}; three.push_back( c ); } } cerr << three.size() << " total triples." << endl; // Find useless three-word combinations cerr << "Finding all useful triples.\n"; find_useless( three, threep ); cerr << threep.size() << " useful triples.\n"; three = vector(); for( i = 0; i < threep.size(); i++ ) cout << words[threep[i].a] << " " << words[threep[i].b] << " " << words[threep[i].c] << "\n"; // Find four-letter combination spanning everything cerr << "Finding a single universal quadruple.\n"; for( i = 0; i < twop.size(); i++ ) { for( j = 0; j < twop.size(); j++ ) { if( (twop[i].present | twop[j].present) == ALL ) break; } if( j < twop.size() ) break; } if( i < twop.size() ) { cout << words[twop[i].a] << " " << words[twop[i].b] << " " << words[twop[j].a] << " " << words[twop[j].b] << "\n"; cerr << "Universal quadruple found." << endl; } else { cerr << "Universal quadruple not found." << endl; } return 0; } void find_useless( vector& in, vector& out ) { int i; // Sort (decreasing) by present sort( in.begin(), in.end() ); // String together nexts for( i = 0; i+1 < in.size(); i++ ) in[i].next = &in[i+1]; // Find useless words combination *c, *d; for( c = &in; c->next != NULL; c = c->next ) { for( d = c; d->next != NULL; ) { if( (d->next->present & ~c->present) == 0 ) { d->next = d->next->next; } else { d = d->next; } } if( c->next == NULL ) break; } // Output for( c = &in; c != NULL; c = c->next ) out.push_back( *c ); } ##``````## #include #include #include #include using namespace std; struct datum { string combination; unsigned long present; }; unsigned long present( string s ) { int j; unsigned long present = 0; for( j = 0; j < s.length(); j++ ) { if( s[j] >= 'A' && s[j] <= 'Z' ) s[j] += 'a' - 'A'; if( s[j] < 'a' || s[j] > 'z' ) continue; present |= 1 << (s[j] - 'a'); } return present; } int main( ) { int i; ifstream in( "digest.txt" ); vector data; // Read combinations from digest string line; for( i = 0; getline( in, line ); i++ ) { datum d = { line, present( line ) }; data.push_back( d ); } // Answer queries while( getline( cin, line ) ) { unsigned long query = present( line ); for( i = 0; i < data.size(); i++ ) { if( (query & ~data[i].present) == 0 ) break; } cout << data[i].combination << endl; } return 0; } ```