Facebook Hacker Cup: "Studious Student" Solution in Java - CodeProject

Facebook Hacker Cup: "Studious Student" Solution in Java - CodeProject
You've been given a list of words to study and memorize. Being a diligent student of language and the arts, you've decided to not study them at all and instead make up pointless games based on them. One game you've come up with is to see how you can concatenate the words to generate the lexicographically lowest possible string.
Input
As input for playing this game you will receive a text file containing an integer N, the number of word sets you need to play your game against. This will be followed by N word sets, each starting with an integer M, the number of words in the set, followed by M words. All tokens in the input will be separated by some whitespace and, aside from N and M, will consist entirely of lowercase letters.
Output
Your submission should contain the lexicographically shortest strings for each corresponding word set, one per line and in order.

Constraints
1 <= N <= 100
1 <= M <= 9
1 <= all word lengths <= 10
Example input
5
6 facebook hacker cup for studious students
5 k duz q rc lvraw
5 mybea zdr yubx xe dyroiy
5 jibw ji jp bw jibw
5 uiuy hopji li j dcyi
Example output
cupfacebookforhackerstudentsstudious
duzklvrawqrc
dyroiymybeaxeyubxzdr
bwjibwjibwjijp
dcyihopjijliuiuy
http://www.nitinh.com/2011/01/facebook-hacker-cup-studious-student-problem-solution/

Some of the contestants solved this problem with brute force, as input range was not that big. With M<=9 one could have only 9!= 362880 possible permutations. And answer can be obtained by sorting these permutations.

However, I didn’t went this approach. I used python internal Sort function with custom compare.

	def func(stings): strings.sort(compare)
	return ''.join(strings)
	def compare(x,y):
	if(x.find(y) == 0 or y.find(x) == 0):
	return cmp(x+y,y+x)
	return cmp(x,y)
	def main(filename):
	f = open(filename, 'r')
	s = f.readlines()
	for i in s[1:]:
	strings = i.split(' ')
	strings = [k.strip() for k in strings[1:]]
	print func(strings)
	if __name__ == '__main__':
	main(sys.argv[1])

http://francesco-laurita.info/wordpress/2011/01/24/facebook-hacker-cup-2011-qualification-round-studious-student-solution/

bool compare(const string a, const string b) {

    string aa = a;

    string bb = b;

    if (aa + bb < bb + aa) {

        return true;

    }

    return false;

}

int main(int argc, char **argv) {

    ifstream fp(argv[1]);

    string *current = NULL;

    int nlines;

 

    if (!fp) {

        cerr << "Unble to open file!" << endl;

        return 1;

    }

 

    fp >> nlines;

    fp.ignore();

 

    for (int i = 0; i < nlines; i++) {

 

        string result;

        int nword;

        string line, token;

        getline(fp, line);

 

        stringstream ss(line);

        ss >> nword;

        current = new string[nword];

        for (int j = 0; j < nword; j++) {

            ss >> token;

            current[j] = token;

        }

        std::sort(current, current + nword, compare);

 

        for (int j = 0; j < nword; j++) {

            result.append(current[j]);

        }

        cout << result << endl;

 

    }

 

    fp.close();

    delete[] current;

    return 0;

}

Read full article from Facebook Hacker Cup: "Studious Student" Solution in Java - CodeProject