% 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[0]; 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[0]; 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;
}