Menu
Topics Index
...
`

Weekend Hack - 10 Aug 2013 - Results

Thanks to Pramod Jain and Gayathri Chandra 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.

Both the solutions are equally good and both of them are winners. They get a recharge of Rs. 150 each.

Get all possibilities for stretching a word to the given size

Write a program to get all possibilities for stretching a word to the given size. The possibilities returned should be sorted. If the list of required indices is passed, then only those combinations present at those indices should be returned. If the required indices are null, then all the combinations have to be returned.

Input (String, int, int[]) Output (List)
1234, 6, null [111234, 112234, 112334, 112344, 122234, 122334, 122344, 123334, 123344, 123444]
1234, 6, [1, 5, 9] [112234, 122334, 123444]
1234, 5, null [11234, 12234, 12334, 12344]
merit, 6, null [meerit, meriit, meritt, merrit, mmerit]
merit, 6, [0, 4] [meerit, mmerit]
ABCD, 6, null [AAABCD, AABBCD, AABCCD, AABCDD, ABBBCD, ABBCCD, ABBCDD, ABCCCD, ABCCDD, ABCDDD]
ABCD, 6, [1, 3, 7, 8] [AABBCD, AABCDD, ABCCCD, ABCCDD]
PROGRAM, 5, null []
JAVA, 4, null [JAVA]
FIVE, -1, null []

Solution 1 - Submitted on Sat Aug 10 13:46:43 2013

class RubberbandWord {

    public static void main(String s[]) {
        System.out.println(stretchWords("TOPCODER", 10, null));
    }

    public static List stretchWords(String word, int requiredLength, int[] requestedIndices) {
        // If required length is less than the word length return empty arraylist
        if (requiredLength < word.length())
            return (new ArrayList());
        int additionalnoOfOccurences[] = new int[word.length()];
        // result is an array which stores all combinations of additional letters required 
        List result = new ArrayList();
        // calling recursive function with given parameters 
        // starting index -0 , additional letters count , array to store additional occurrences , list to store final result
        result = stretchWordByLength(0, requiredLength - word.length(), additionalnoOfOccurences, result);
        // now result stores all the combinations of possible answers as integer arrays
        // calling convertToString function to convert all combinations of answers to strings 
        List finalResult = convertToString(result, word);
        // returning the answer according to requirements
        if (requestedIndices == null)
            return finalResult;
        else {
            List finalResultTwo = new ArrayList();
            for (int requestedIndice : requestedIndices) {
                finalResultTwo.add(finalResult.get(requestedIndice));
            }
            return finalResultTwo;
        }
    }

    public static List stretchWordByLength(int startAt, int additionalRequiredLength, int[] additionalNoOfOccurences, List result) {
        // if no more letters can be added to it add the given combination to result list.
        if (additionalRequiredLength == 0) {
            result.add(additionalNoOfOccurences);
            return null;
        }
        // we have two options available 
        // 1)to add at element at startup and then proceed with the same startup value(as same element may repeat number of times)
        // 2)directly moving to next combinations by calling recursive function with the next startup value
        else if (startAt < additionalNoOfOccurences.length) {
            int[] arrayOne = additionalNoOfOccurences.clone();
            // adding a letter at startAt
            arrayOne[startAt]++;
            // calling recursive function with the same startAt
            // additional required length is decremented as we have added one letter
            stretchWordByLength(startAt, additionalRequiredLength - 1, arrayOne, result);
            int[] arrayTwo = additionalNoOfOccurences.clone();
            // calling the recursive function with the next startAt
            stretchWordByLength(startAt + 1, additionalRequiredLength, arrayTwo, result);
        }
        // when startAt is not less than the length of word return the result 
        return result;
    }

    public static List convertToString(List result, String word) {
        List finalResult = new ArrayList();
        // converting these combinations into strings
        for (int i = 0; i < result.size(); i++) {
            int[] temporaryArray = result.get(i);
            String finalString = "";
            for (int j = 0; j < word.length(); j++) {
                for (int k = 0; k < temporaryArray[j] + 1; k++) {
                    finalString = finalString + word.charAt(j);
                }
            }
            finalResult.add(finalString);
        }
        //sorting strings present in the list
        Collections.sort(finalResult);
        return finalResult;
    }
}

Comments :

Solution 2 - Submitted on Sun Aug 11 03:34:43 2013

class RubberbandWord {

    public static void main(String s[]) {
        System.out.println(stretchWords("TOPCODER", 10, null));
    }

    public static List stretchWords(String word, int requiredLength, int[] requestedIndices) {
        //if the given word is null or required length is less than the length of the word then empty list is returned
        if (word == "" || requiredLength < word.length()) {
            return possibleCombinationsList;
        }
        //instead of passing the input string and the list of combinations as arguments to every function call,global variables are used.
        inputString = "" + word;
        //stretch function adds all possible combinations to possibleCombinationsList
        stretch("", 0, requiredLength - inputString.length());
        //list of combinations is sorted
        Collections.sort(possibleCombinationsList);
        //if specific positions are mentioned then add objects at those positions or else add the entire list to another list and return it.
        if (requestedIndices == null) {
            List requestedList = new ArrayList(possibleCombinationsList);
            possibleCombinationsList.clear();
            return requestedList;
        } else {
            List requestedList = new ArrayList();
            for (int requestedIndice : requestedIndices) {
                requestedList.add(possibleCombinationsList.get(requestedIndice));
            }
            possibleCombinationsList.clear();
            return requestedList;
        }
    }

    public static void stretch(String subString, int indexToBeStretched, int remainingLength) {
        //firstly we stretch the present character to the maximum extent possible.Then we go on decreasing its stretch by 1 character at a time.
        //we pass the remaining no of characters to be stretched,apart from the no of characters that make up the original string and the no to which the present character has been stretched to as an argument to the function.
        //remaining no of characters is obtained by subtracting the no to which the present character has been stretched from the remaining no of characters.
        char c = inputString.charAt(indexToBeStretched);
        // To avoid duplicates if same character is present at consecutive positions, we check whether the character at the present index is equal to the character at its previous index.If it is same,then it is not stretched,instead appended as it is.
        //check for the presence of same character at consecutive positions is started from the 2nd position i.e., from indextoBeStretched=1.
        int i = remainingLength;
        if (indexToBeStretched != 0) {
            if (c == inputString.charAt(indexToBeStretched - 1)) {
                i = 0;
            }
        }
        //present character is stretched in all possible numbers and added to the string one at a time.
        //The stretched string till the present character position is passed as an argument to the next function call.
        for (; i >= 0; i--) {
            String stringToBeAdded = "" + subString;
            for (int j = i; j >= 0; j--) {
                stringToBeAdded = stringToBeAdded + c;
            }
            //if the last character of the string is being stretched,then just stretch it to the remaining no of characters left,append it to the string and add the string to the list.
            //Else call the function recursively to stretch the next characters to reach the required length.
            if (indexToBeStretched == inputString.length() - 1) {
                possibleCombinationsList.add(stringToBeAdded);
                return;
            } else {
                stretch(stringToBeAdded, indexToBeStretched + 1, remainingLength - i);
            }
        }
    }

    static String inputString;
    static List possibleCombinationsList = new ArrayList();
}

Comments :

© meritcampus 2019

All Rights Reserved.

Open In App