At the first look it seems just a simple sort problem, but it isn’t! It involves sorting operations on all strings permutation.

Since the bound of 9 words is really low I just apply the sort operation on all of permutations (9!)

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

Sample 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

Sample output:

cupfacebookforhackerstudentsstudious
duzklvrawqrc
dyroiymybeaxeyubxzdr
bwjibwjibwjijp
dcyihopjijliuiuy

The code (C++):

//============================================================================
// Name        : studious-student.cpp
// Author      : Francesco Laurita
// Version     : 1.0
// Copyright   : Francesco Laurita
// Description : Studious Student solution (FB hacke cup qualification round)
//============================================================================

#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <algorithm>
using namespace std;

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

Bookmark and Share

Leave a Reply

(required)

(required)

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

© 2013 Francesco Laurita' s blog Suffusion theme by Sayontan Sinha