Chaining Game ( 2007 )

Problem :
One popular party game involves one person thinking of a word and then each person afterward thinking of a different word which relates in some way. In some versions of the game, the words are related by the letters in them; the first letter of the new word must be the same as the last letter of the old word. These kinds of constructions are called “word chains”, and the more words you use, the harder it gets to put them together.

Write a program that is able to take a list of words and determine if the entire set of these words could be used in a single word chain, with each word used exactly once. For instance, the words “Carpenter”, “Thread”, and “Ratchet” would be a valid list of words, because they can be combined into a single chain (“CarpenteRatcheThread”), but “Yard”, “Denmark”, and “Cheese” would not, because “Cheese” can’t connect to either “Yard” or “Denmark”.

Input

Input will consist of several words, separated by spaces. These words should be able to interchange uppercase and lowercase freely; “cabin” should be processed identically to “CaBiN”.

Output

The output can take one of two forms. If the program finds that it is impossible to create a chain, it should simply print out the word “Impossible”. If a chain is found, the program should print out this chain, in order. Let the case of the connecting letter be determined by the word on the right.

Sample input

Carpenter threaD RatcheT

Sample output

CarpenteRatchethreaD

Solution :
The simplest solution that I used is "permutation" and then check the last character of the word at index i with the first character of the word index i + 1.

#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <climits>
#include <algorithm>
#include <cctype>

using namespace std;


vector< string > util_tokenize_string( const string& str, const string& del = " " ) {
    vector< string > result;
    unsigned start = 0;
    unsigned end  = str.find_first_of( del, start );
    unsigned length = str.length();
    string word;
    while( string::npos != end && end < length ) {
        word = str.substr( start, end - start );
        result.push_back( word );
        start = end + 1;
        end = str.find_first_of( del, start );
    }
 
    end = str.find_last_of( del ) + 1;
    result.push_back( str.substr( end ) );
 
    return result;
}
 
vector< string > read_file( const char* file_name ) {
    ifstream inf( file_name );
    string line;
    getline( inf, line );
    return util_tokenize_string( line );
}
 
void check_chaining_words( vector< string >& w ) {
    int len = w.size();
    vector< string > input = w;
    string output;
 
    do {
        bool is_it = true;
        next_permutation( w.begin(), w.begin() + len );
        output += w[ 0 ].substr( 0, w[ 0 ].length() - 1 );
        for( int i = 0; i < len - 1; ++i ) {
            if( i + 1 != len - 1 )
                output += w[ i + 1 ].substr( 0, w[ i + 1 ].length() - 1 );
            else
                output += w[ i + 1 ];
 
            if( toupper( w[ i ][ w[ i ].size() - 1 ] ) != toupper( w[ i + 1 ][ 0 ] ) ) {
                is_it = false;
                break;
            }
        }
        if( is_it == true ) {
            cout << output << endl;
        } else {
            output = "";
        }
 
    } while( w != input );
}
 
int main() {
    vector< string > w = read_file( "love.txt" );
    check_chaining_words( w );
 
    return 0;
}