Data Structures and Algorithm Analysis in C++ (Mark Allen Weiss)

#include <iostream> #include <fstream> #include <string> #include <vector> #include <map> #include <queue> #include <ctime> using namespace std; /* DISTRIBUTION OF DICTIONARY: Read the words...88984 1 1 2 48 3 601 4 2409 5 4882 6 8205 7 11989 8 13672 9 13014 10 11297 11 8617 12 6003 13 3814 14 2173 15 1169 16 600 17 302 18 107 19 53 20 28 Elapsed time FAST: 5.218 Elapsed time MEDIUM: 77.735 Elapsed time SLOW: 450.891 **/ vector<string> readWords( istream & in ) { string oneLine; vector<string> v; while( in >> oneLine ) v.push_back( oneLine ); return v; } // Returns true if word1 and word2 are the same length // and differ in only one character. bool oneCharOff( const string & word1, const string & word2 ) { if( word1.length( ) != word2.length( ) ) return false; int diffs = 0; for( int i = 0; i < word1.length( ); i++ ) if( word1[ i ] != word2[ i ] ) if( ++diffs > 1 ) return false; return diffs == 1; } // Computes a map in which the keys are words and values are vectors of words // that differ in only one character from the corresponding key. // Uses a quadratic algorithm. map<string,vector<string> > computeAdjacentWordsSlow( const vector<string> & words ) { map<string,vector<string> > adjWords; for( int i = 0; i < words.size( ); i++ ) for( int j = i + 1; j < words.size( ); j++ ) if( oneCharOff( words[ i ], words[ j ] ) ) { adjWords[ words[ i ] ].push_back( words[ j ] ); adjWords[ words[ j ] ].push_back( words[ i ] ); } return adjWords; } // Computes a map in which the keys are words and values are vectors of words // that differ in only one character from the corresponding key. // Uses a quadratic algorithm, but speeds things up a little by // maintaining an additional map that groups words by their length. map<string,vector<string> > computeAdjacentWordsMedium( const vector<string> & words ) { map<string,vector<string> > adjWords; map<int,vector<string> > wordsByLength; // Group the words by their length for( int i = 0; i < words.size( ); i++ ) wordsByLength[ words[ i ].length( ) ].push_back( words[ i ] ); // Work on each group separately map<int,vector<string> >::const_iterator itr; for( itr = wordsByLength.begin( ); itr != wordsByLength.end( ); ++itr ) { const vector<string> & groupsWords = itr->second; for( int i = 0; i < groupsWords.size( ); i++ ) for( int j = i + 1; j < groupsWords.size( ); j++ ) if( oneCharOff( groupsWords[ i ], groupsWords[ j ] ) ) { adjWords[ groupsWords[ i ] ].push_back( groupsWords[ j ] ); adjWords[ groupsWords[ j ] ].push_back( groupsWords[ i ] ); } } return adjWords; } // Computes a map in which the keys are words and values are vectors of words // that differ in only one character from the corresponding key. // Uses an efficient algorithm that is O(N log N) with a map, or // O(N) is a hash_map is used. map<string,vector<string> > computeAdjacentWords( const vector<string> & words ) { map<string,vector<string> > adjWords; map<int,vector<string> > wordsByLength; // Group the words by their length for( int i = 0; i < words.size( ); i++ ) wordsByLength[ words[ i ].length( ) ].push_back( words[ i ] ); // Work on each group separately map<int,vector<string> >::const_iterator itr; for( itr = wordsByLength.begin( ); itr != wordsByLength.end( ); ++itr ) { const vector<string> & groupsWords = itr->second; int groupNum = itr->first; // Work on each position in each group for( int i = 0; i < groupNum; i++ ) { // Remove one character in specified position, computing representative. // Words with same representatives are adjacent; so first populate // a map... map<string,vector<string> > repToWord; for( int j = 0; j < groupsWords.size( ); j++ ) { string rep = groupsWords[ j ]; rep.erase( i, 1 ); repToWord[ rep ].push_back( groupsWords[ j ] ); } // and then look for map values with more than one string map<string,vector<string> >::const_iterator itr2; for( itr2 = repToWord.begin( ); itr2 != repToWord.end( ); ++itr2 ) { const vector<string> & clique = itr2->second; if( clique.size( ) >= 2 ) { for( int p = 0; p < clique.size( ); p++ ) for( int q = p + 1; q < clique.size( ); q++ ) { adjWords[ clique[ p ] ].push_back( clique[ q ] ); adjWords[ clique[ q ] ].push_back( clique[ p ] ); } } } } } return adjWords; } // Find most changeable word: the word that differs in only one // character with the most words. Return a list of these words, in case of a tie. vector<string> findMostChangeable( const map<string,vector<string> > & adjacentWords ) { vector<string> mostChangeableWords; int maxNumberOfAdjacentWords = 0; map<string,vector<string> >::const_iterator itr = adjacentWords.begin( ); while( itr != adjacentWords.end( ) ) { const pair<string,vector<string> > & entry = *itr++; if( entry.second.size( ) > maxNumberOfAdjacentWords ) { maxNumberOfAdjacentWords = entry.second.size( ); mostChangeableWords.clear( ); } if( entry.second.size( ) == maxNumberOfAdjacentWords ) mostChangeableWords.push_back( entry.first ); } return mostChangeableWords; } void printMostChangeables( const vector<string> & mostChangeable, const map<string,vector<string> > & adjWords ) { map<string,vector<string> > & adjacentWords = const_cast<map<string,vector<string> > &>( adjWords ); for( int i = 0; i < mostChangeable.size( ); i++ ) { cout << mostChangeable[ i ] << ":"; vector<string> adjacents = adjacentWords[ mostChangeable[ i ] ]; for( int j = 0; j < adjacents.size( ); j++ ) cout << " " << adjacents[ j ]; cout << " (" << adjacents.size( ) << " words)" << endl; } } void printHighChangeables( const map<string,vector<string> > & adjacentWords, int minWords ) { map<string,vector<string> >::const_iterator itr = adjacentWords.begin( ); while( itr != adjacentWords.end( ) ) { const pair<string,vector<string> > & entry = *itr++; const vector<string> & words = entry.second; if( words.size( ) >= minWords ) { cout << entry.first << " (" << words.size( ) << "):"; for( int i = 0; i < words.size( ); i++ ) cout << " " << words[ i ]; cout << endl; } } } // After the shortest path calculation has run, computes the vector that // contains the sequence of words changes to get from first to second. vector<string> getChainFromPreviousMap( const map<string,string> & previous, const string & first, const string & second ) { map<string,string> & prev = const_cast<map<string,string> &>( previous ); vector<string> result; if( prev[ second ] != "" ) { string current = second; wh