Menu
Topics Index
...
`

Weekend Hack - 13 Jul 2013 - Results

Thanks to Pramod Jain for spending so much time, coming up with original and innovative answers and for submitting them. Thanks to many others who have tried to get the solution.
We have reviewed the solutions as per the criteria mentioned at Weekend Hack and included the comments below. Given the experience of the participants, they were really innovative and clean. Few minor comments found are included below in the order of the submission. These comments are not intended to point out the mistakes in the solutions but to learn from them.

The winner of the Weekend Hack 13 Jul 2013 - 1 is Pramod Jain. He will get a recharge or gift voucher worth Rs. 150.

To create the longest word garland using the given words

Write a program to create the longest word garland using the given words. Word garland is something where the next word starts with last letter of the current word. The order of words in the result may vary, as long as it is equal in length it is okay.

Input (List) Output (String)
{ant, tin, nail, egg, nose, god, goe, yax, xenon, donkey, yaz} antinoseggodonkeyaxenonail
{hat, ten, hen, exit, texture, english, tap, pig, gun, next} englishatenextexturexitapigun
{goal, apple, eagle, banana, cork, slow, test, egg, kit, kitchen} bananappleagleggoal
{malayalam, maximum, nose, mom, minimum} minimumalayalamaximumom

Solution 1 - Submitted on Sun Jul 14 17:03:03 2013

class LongestWordGarland {

    public static void main(String s[]) {
        List input = new ArrayList();
        input.add("ant");
        input.add("tin");
        input.add("nail");
        input.add("egg");
        input.add("nose");
        input.add("god");
        input.add("goe");
        input.add("yax");
        input.add("xenon");
        input.add("donkey");
        input.add("yaz");
        System.out.println("The longest word garland is: " + getLongestWordGarland(input));
    }

    public static String getLongestWordGarland(List input) {
        boolean selected[] = new boolean[input.size()];
        String[] finalAnswer = {""};
        //finalAnswer to store the answer
        backtrackForLongestWordGarland("", input, selected, finalAnswer);
        return finalAnswer[0];
    }

    public static String backtrackForLongestWordGarland(String completeString, List input, boolean[] selected, String[] finalAnswer) {
        for (int i = 0; i < input.size(); i++) {
            // If the given word is not selected before
            if (selected[i] == false) {
                // If completeString is not empty means few words are already selected 
                // and checking for the match of the last letter of completeString and first letter of an unselected word
                if (completeString != "" && completeString.charAt(completeString.length() - 1) == input.get(i).charAt(0)) {
                    // Concatenating word excluding common last letter.
                    completeString = completeString + input.get(i).substring(1, input.get(i).length());
                    // making the word selected  so that it is not used again for further concatenation
                    selected[i] = true;
                    //calling the function recursively the function returns the longest garland possible
                    String temporaryResult = backtrackForLongestWordGarland(completeString, input, selected, finalAnswer);
                    // If the String returned is longer than the string in finalAnswer then finalANswer takes the value of the returned String.
                    if (finalAnswer[0].length() < temporaryResult.length()) {
                        finalAnswer[0] = temporaryResult;
                    }
                    // De-selecting the given word.
                    selected[i] = false;
                    // removing the letters that were concatenated before
                    completeString = completeString.substring(0, completeString.length() - input.get(i).length() + 1);
                }
                // If no word is selected then take one word and add it.
                if (completeString == "") {
                    // selecting the given word and adding it to completeString
                    completeString = input.get(i);
                    selected[i] = true;
                    if (finalAnswer[0].length() < completeString.length())
                        finalAnswer[0] = completeString;
                    // De-selecting the given word and removing the given word
                    // As only one word was added so removing the complete word and making completeString empty.
                    backtrackForLongestWordGarland(completeString, input, selected, finalAnswer);
                    selected[i] = false;
                    completeString = "";
                }
            }
        }
        return completeString;
    }
}

© meritcampus 2019

All Rights Reserved.

Open In App