Walking Boxes ( 2007 )

Problem :
During the era of DOS games, point-and-click adventure games were able to gain a great deal of popularity before fading away into obscurity, replaced by action games that made use of hardware-accelerated graphics.

In a point-and-click adventure game, the player is able to walk their character around a room by simply clicking where they want to go. One way this is accomplished is through the use of walking boxes. For each room the player explores, in addition to the background image that is visible to the player, there exist a series of connected boxes that the player is constrained to walking within. Keeping the player within these boxes is a straightforward enough task, but navigation from one box to another poses a problem. What if two boxes are not connected directly; which intermediate boxes must his character pass through to arrive at his destination? This problem can be solved through the use of a matrix. To get from one box to another, successive lookups into the matrix will be made until the destination box is reached.

For example, the layout shown above would produce the following matrix:

0 1 1 1 1
0 1 2 3 2
1 1 2 1 4
1 1 1 3 1
2 2 2 2 4

To get from box 0 to box 4, the game engine will look up the element at row 0 and column 4, which is 1, and therefore the character will first proceed to box 1. The lookup for getting from box 1 to box 4 will yield the value 2, so the character will continue to box 2. The next lookup will yield the value 4, which is the number of the destination box, so when the character moves there no further lookups will be required.

Write a program that generates one of these walking box matrices. You will be given a set of boxes and the connections between them. The boxes will never form loops or be isolated from each other, so there will always be exactly one path from one box to another, assuming that paths do not double back on themselves.

Input

Input will consist of a box count on the first line. Whatever this number is, it will be followed by exactly that many additional lines. Each of these lines will specify the other boxes one box is connected to (the first line will be for box 0, the next for box 1, etc.).
Output

Output will consist of the walking boxes matrix that may be used for the purposes of navigation as detailed above. Column and row labels should not be included; only the contents of the matrix are required.

Sample input

5
1
0 2 3
1 4
1
2

Sample output

0 1 1 1 1
0 1 2 3 2
1 1 2 1 4
1 1 1 3 1
2 2 2 2 4

Solution :
Using BFS to generate all paths, then for each position on the matrix, for example m[ i ][ j ] :
we first find generate all paths that we can go from i, then from j we back up the find the second last destination.

#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <sstream>
#include <stack>
#include <queue>
#include <climits>

using namespace std;

typedef vector< vector< int > > matrix;

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;
}
 
int util_string_to_int( const string& s ) {
    istringstream i( s );
    int value;
    i >> value;
    return value;
}
 
template< typename T >
void print_matrix( const vector< vector< T > >& m ) {
    cout << "\n\n";
    int N = m[ 0 ].size();
    for( int i = 0; i < N; ++i ) {
        for( int j = 0; j < N; ++j ) {
            cout <<  "   " << m[ i ][ j ];
        }
        cout << endl << endl;
    }
}
 
vector< vector< bool > > get_list_vertices( const char* file_name ) {
    ifstream inf( file_name );
    int N;
    int count = 0;
    string line;
 
    getline( inf, line );
    N = util_string_to_int( line );
    vector< vector< bool > > m( N, vector< bool >( N, 0 ) );
 
 
    while( getline( inf, line ) ) {
        vector< string > temp = util_tokenize_string( line );
        for( int i = 0; i < temp.size(); ++i ) {
            int to = util_string_to_int( temp[ i ] );
            m[ count ][ to ] = 1;
            m[ to ][ count ] = 1;
        }
        count++;
    }
 
    return m;
}
 
void breadth_first_search( queue< int >& Q,
                           vector< int >& trace,
                           const vector< vector< bool > >& m,
                           int start ) {
    int N = m[ 0 ].size();
    int u;
    Q.push( start );
    trace[ start ] = -INT_MAX;
 
    do {
        u = Q.front();
        Q.pop();
        for( int v = 0; v < N; ++v ) {
            if( ( m[ u ][ v ] == 1 ) && trace[ v ] == -1 ) {
                Q.push( v );
                trace[ v ] = u;
            }
        }
    } while( !Q.empty() );
}
 
int find_trace_path( vector< int > trace, int start, int end, int N ) {
    // direct path
    if( trace[ end ] == start ) {
        return end;
    } else {
        vector< int > v;
        while( end != start ) {
            end = trace[ end ];
            v.push_back( end );
        }
        return v[ v.size() - 2 ];
    }
}
 
int main() {
    int MAXI = 100;
    vector< vector< bool > > m = get_list_vertices( "t.txt" );
    int N = m[ 0 ].size();
    vector< vector< int > > result( N, vector< int >( N, 0 ) );
    for( int i = 0; i < N; ++i ) {
        result[ i ][ i ] = i;
    }
 
    for( int count = 0; count < N; ++count ) {
        queue< int > Q;
        vector< int > trace_path( MAXI, -1 );
        breadth_first_search( Q, trace_path, m, count );
        for( int i = 0; i < N; ++i ) {
            if( count != i )
                result[ count ][ i ] = find_trace_path( trace_path, count, i, N );
        }
    }
 
    print_matrix( result );
 
    return 0;
}

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;
}