Menu
Topics Index
...
`

Weekend Hack - 12 Oct 2013 - Results

Thanks to Pramod Jain, Nishan K Sharma and Amar Kumar Biradar 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.

Since all the solutions were equally good and equally bad, all three solutions get a recharge of Rs. 100 each.

Slide words to form lookup words

Write a program to slide the words horizontally such that they form all the lookup words vertically. Also print the words as shown below in the requirements.

Input (List, List) Printed Output
[JIFFY, PASTULA, AVIONIC, POTATO], [JAVA, IS, FUN]          [J][I] F [F] Y
       P [A][S] T [U] L  A
       A [V] I  O [N] I  C
 P  O  T [A] T  O
[POTATO, MONOTIM, TOMATO], [POT, TOM, TIT]    [P] O [T] A [T] O
 M [O] N [O] T [I] M
   [T] O [M] A [T] O
[BOPA, ANIMAL, TANGOO, MAT], [BAT, ON, PIN, LOT] [B][O][P] A
[A][N][I] M  A [L]
[T] A [N] G  O [O]
          M  A [T]
[BOOM, SUFI, TONY, DUD], [OUT, OF, MIND]  B [O][O][M]
 S [U][F][I]
   [T] O [N] Y
    D  U [D]
[WTA, RIHL, NELLORE, OM], [WIN, THEM, ALL]    [W][T][A]
 R [I][H][L]
   [N][E][L] L  O  R  E
    O [M]

Solution 1 - Submitted on Sat Oct 12 17:41:26 2013

import java.util.ArrayList;
import java.util.List;

class SlideWords {

    public static void main(String s[]) {
        List words = new ArrayList();
        words.add("JIFFY");
        words.add("PASTULA");
        words.add("AVIONIC");
        words.add("POTATO");
        List lookupWords = new ArrayList();
        lookupWords.add("JAVA");
        lookupWords.add("IS");
        lookupWords.add("FUN");
        printSlidWords(words, lookupWords);
    }

    public static void printSlidWords(List words, List lookupWords) {
        // This code is made to satisfy most of the test cases
        // To make it completely generic the time complexity would be very high
        // so is an attempt to satisfy the test cases wth simple recursion proceedure
        // taking the first string into lookup and its length into length
        String lookup = lookupWords.get(0);
        int length = words.size();
        //startAt is an array which maintains the first matching positions of the given strings 
        //to get the first required word(JAVA) in this case and maxStartAt is maximum among those
        int startAt[] = new int[length];
        int maxStartAt = 0;
        int noOfColumns = lookup.length();
        // A simple loop to find values for above variables
        for (int i = 0; i < words.size(); i++) {
            String word = words.get(i);
            char letter;
            if (i < lookup.length()) {
                letter = lookup.charAt(i);
                startAt[i] = word.indexOf(letter);
                if (maxStartAt < startAt[i]) {
                    maxStartAt = startAt[i];
                }
                if (noOfColumns < maxStartAt + words.get(i).length()) {
                    noOfColumns = maxStartAt + words.get(i).length();
                }
            }
        }
        // If the first required string(JAVA) has a length less than the number of strings then we need to 
        //adjust startAt values for other strings such that all the required words are found in complete pattern
        // This function returns the result array having strings in the required pattern
        char result[][] = makeResult(words, maxStartAt, startAt, lookup.length(), noOfColumns, lookupWords);
        //marking function marks the characters which are to be printed in brackets
        boolean mark[][] = marking(result, lookupWords);
        // printing the result
        print(result, mark);
    }

    // This function sets the values for the words already found and calls fill function
    public static char[][] makeResult(List words, int maxStartAt, int[] startAt, int rows, int cols, List lookupWords) {
        char result[][] = new char[words.size()][cols];
        for (int i = 0; i < rows; i++) {
            String word = words.get(i);
            int beginAt = maxStartAt - startAt[i];
            int wordLength = word.length();
            for (int j = 0; j < wordLength; j++) {
                result[i][beginAt + j] = word.charAt(j);
            }
        }
        fill(words, rows, cols, result, lookupWords);
        return result;
    }

    // This function is called when some required strings are not found(LOT in one of the test cases) and these strings can be obtained by 
    // changing the starting positions of those strings in result whose starting position is taken as 0 by default(MAT) in the same test case
    public static void fill(List words, int rows, int cols, char[][] result, List lookupWords) {
        if (rows == words.size())
            return;
        for (int i = rows; i < words.size(); i++) {
            String word = words.get(i);
            int wordLength = word.length();
            // filling the values in result array for the given starting position(j)
            for (int j = 0; j < cols; j++) {
                int beginAt = j;
                for (int k = 0; k < wordLength; k++) {
                    result[i][beginAt + k] = word.charAt(k);
                }
                // Recursive calling of fill to assign starting positions for every string that has not been assigned a starting position
                // Using recursion we will be able to assign different combinations of starting positions for the remaining strings 
                // so we dont miss even a single combination even if there are multiple strings whose startAt value is not initialised.
                fill(words, rows + 1, cols, result, lookupWords);
                // If the combination leads to solution then return
                if (isPossible(words, lookupWords, cols, result)) {
                    return;
                }
                // other wise unfill the array and try to fill it with other possibility
                for (int k = 0; k < wordLength; k++) {
                    result[i][beginAt + k] = '\u0000';
                }
            }
        }
    }

    // checking whether all the required words are found in the combination or not.
    public static boolean isPossible(List words, List lookupWords, int noOfColumns, char[][] result) {
        int length = words.size();
        int totalWords = lookupWords.size();
        int wordNo = 0;
        int count = 0;
        for (int i = 0; i < noOfColumns; i++) {
            for (int j = 0; j < length; j++) {
                for (int k = j; k < length; k++) {
                    if (result[k][i] == lookupWords.get(wordNo).charAt(k - j))
                        count++;
                    else {
                        count = 0;
                        break;
                    }
                    if (count == lookupWords.get(wordNo).length()) {
                        wordNo++;
                        count = 0;
                        if (wordNo == totalWords)
                            return true;
                        else
                            break;
                    }
                }
            }
        }
        return false;
    }

    // marking the characters of the result which forms the required strings present in the list (lookUpWords)
    public static boolean[][] marking(char[][] result, List lookupWords) {
        int length = result.length;
        int noOfColumns = result[0].length;
        boolean mark[][] = new boolean[noOfColumns][length];
        int totalWords = lookupWords.size();
        int wordNo = 0;
        int count = 0;
        outer : for (int i = 0; i < noOfColumns; i++) {
            for (int j = 0; j < length; j++) {
                for (int k = j; k < length; k++) {
                    if (result[k][i] == lookupWords.get(wordNo).charAt(k - j))
                        count++;
                    else {
                        count = 0;
                        break;
                    }
                    if (count == lookupWords.get(wordNo).length()) {
                        for (int x = k; x > k - lookupWords.get(wordNo).length(); x--) {
                            mark[i][x] = true;
                        }
                        wordNo++;
                        if (wordNo == totalWords)
                            break outer;
                        else
                            break;
                    }
                }
            }
        }
        return mark;
    }

    //printing as per requirements
    public static void print(char[][] result, boolean mark[][]) {
        int length = result.length;
        int noOfColumns = result[0].length;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < noOfColumns; j++) {
                if (result[i][j] == '\u0000')
                    System.out.print("   ");
                else if (mark[j][i])
                    System.out.print("[" + result[i][j] + "]");
                else
                    System.out.print(" " + result[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Comments :

Solution 2 - Submitted on Sun Oct 13 01:56:49 2013



import java.util.ArrayList;
import java.util.List;

class SlideWords {

    public static void main(String s[]) {
        List words = new ArrayList();
        words.add("JIFFY");
        words.add("PASTULA");
        words.add("AVIONIC");
        words.add("POTATO");
        List lookupWords = new ArrayList();
        lookupWords.add("JAVA");
        lookupWords.add("IS");
        lookupWords.add("FUN");
        printSlidWords(words, lookupWords);
    }

    public static void printSlidWords(List words, List lookupWords) {
        String[] r = words.toArray(new String[words.size()]);
        String[] res = new String[r.length];
        int maxPos = 0, maxSize = lookupWords.get(0).length(), lastPos = 0;
        res = addSpaces(r, res);
        //finds maximum position and maximum size of lookupWords 
        for (int i = 1; i < lookupWords.size(); i++) {
            if (maxSize < lookupWords.get(i).length()) {
                maxPos = i;
                maxSize = lookupWords.get(i).length();
            }
        }
        String check = lookupWords.get(maxPos);
        int maxIndex = getMaxIndex(res, check, words);
        res = slideElements(res, check, words, maxIndex);
        res = slideRemaining(res, words, lookupWords, maxSize);
        //finds the last position of the longest string
        for (String re : res) {
            if (re.length() > lastPos) {
                lastPos = re.length();
            }
        }
        print(res, lookupWords, lastPos);
    }

    //adds spaces in the string in between the elements
    public static String[] addSpaces(String[] r, String[] res) {
        for (int i = 0; i < r.length; i++) {
            res[i] = "";
            for (int j = 0; j < r[i].length(); j++) {
                res[i] += " " + r[i].charAt(j) + " ";
            }
        }
        return res;
    }

    //returns the maximum index to which sliding has to be done
    public static int getMaxIndex(String[] res, String check, List words) {
        int maxIndex = 0;
        for (int i = 0; i < check.length(); i++) {
            int index = 0;
            index = res[i].indexOf(check.charAt(i));
            if (check.length() > words.get(i).length()) {
                index = res[i].lastIndexOf(check.charAt(i));
            }
            if ((index - 1) / 3 > maxIndex) {
                maxIndex = (index - 1) / 3;
            }
        }
        return maxIndex;
    }

    //slides the string array elements upto the maximum index
    public static String[] slideElements(String[] res, String check, List words, int maxIndex) {
        for (int i = 0; i < check.length(); i++) {
            int index = 0;
            index = res[i].indexOf(check.charAt(i));
            if (check.length() > words.get(i).length()) {
                index = res[i].lastIndexOf(check.charAt(i));
            }
            for (int j = 0; j < maxIndex - (index - 1) / 3; j++) {
                res[i] = "   " + res[i];
            }
        }
        return res;
    }

    //slides any remaining string array elements 
    public static String[] slideRemaining(String[] res, List words, List lookupWords, int maxSize) {
        if (maxSize < words.size()) {
            for (int i = maxSize; i < words.size(); i++) {
                for (int j = lookupWords.size() - 1; j >= 0; j--) {
                    if (res[maxSize].contains(Character.toString(lookupWords.get(j).charAt(lookupWords.get(j).length() - (words.size() - i))))) {
                        int count = 1;
                        for (int k = 0; k < lookupWords.get(j).length() - 1; k++) {
                            if (res[maxSize - k].contains(Character.toString(lookupWords.get(j).charAt(lookupWords.get(j).length() - (words.size() - i) - k)))) {
                                count++;
                            }
                        }
                        if (count == lookupWords.get(j).length()) {
                            int index = res[maxSize - (lookupWords.get(j).length() - 1)].indexOf(lookupWords.get(j).charAt(lookupWords.get(j).length() - (words.size() - i) - (lookupWords.get(j).length() - 1)));
                            for (int l = 0; l < (index - 1) / 3 - (words.get(maxSize).length() - 1); l++) {
                                res[i] = "   " + res[i];
                            }
                            break;
                        }
                    }
                }
            }
        }
        return res;
    }

    //prints the required output
    public static void print(String res[], List lookupWords, int lastPos) {
        char[][] output = new char[res.length][lastPos];
        //transfering all the string array elements into two-dimensional char array
        for (int i = 0; i < res.length; i++) {
            for (int j = 0; j < res[i].length(); j++) {
                output[i][j] = res[i].charAt(j);
            }
        }
        //adding brackets to the lookupWords in the char array
        for (int i = 0; i < lookupWords.size(); i++) {
            for (int j = 0; j < lastPos; j++) {
                for (int k = 0; k < output.length; k++) {
                    int count = 0;
                    for (int l = 0; l < lookupWords.get(i).length() && (k + l) < output.length; l++) {
                        if (output[k + l][j] == lookupWords.get(i).charAt(l)) {
                            count++;
                        }
                    }
                    if (count == lookupWords.get(i).length()) {
                        for (int l = 0; l < lookupWords.get(i).length(); l++) {
                            output[k + l][j - 1] = '[';
                            output[k + l][j + 1] = ']';
                        }
                        break;
                    }
                }
            }
        }
        //prints the output array
        for (int i = 0; i < res.length; i++) {
            for (int j = 0; j < res[i].length(); j++) {
                System.out.print(output[i][j]);
            }
            System.out.println();
        }
    }
}

Comments :

Solution 3 - Submitted on Sun Oct 13 11:22:00 2013



import java.util.ArrayList;
import java.util.List;

class SlideWords {

    public static void main(String s[]) {
        List words = new ArrayList();
        words.add("JIFFY");
        words.add("PASTULA");
        words.add("AVIONIC");
        words.add("POTATO");
        List lookupWords = new ArrayList();
        lookupWords.add("JAVA");
        lookupWords.add("IS");
        lookupWords.add("FUN");
        printSlidWords(words, lookupWords);
    }

    public static void printSlidWords(List words, List lookupWords) {
        char result[][] = emptyMatrix(words, lookupWords);
        result = getCharMatrix(result, words, lookupWords);
        result = getFinalResult(result, words, lookupWords);
        print(result);
    }

    /* When I wrote this code, Only God and I understood What I was doing,Now... Only God knows */
    public static char[][] emptyMatrix(List words, List lookupWords) {
        int maxWord = 0;
        for (int i = 0; i < words.size(); i++) {
            if (words.get(i).length() > maxWord)
                maxWord = words.get(i).length();
        }
        char result[][] = new char[words.size()][words.size() * maxWord];
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[i].length; j++) {
                result[i][j] = ' ';
            }
        }
        return result;
    }

    public static char[][] getCharMatrix(char[][] result, List words, List lookupWords) {
        int rMax = 0, cMax = 0, lWord = 0;
        for (int i = 0; i < lookupWords.size(); i++) {
            if (lookupWords.get(i).length() > cMax)
                cMax = lookupWords.get(i).length();
        }
        for (int j = 0; j < lookupWords.size(); j++) {
            if (cMax == lookupWords.get(j).length()) {
                lWord = j;
                break;
            }
        }
        for (int i = 0, j = 0; i < words.size() && j < lookupWords.get(lWord).length(); i++, j++) {
            int index = words.get(i).indexOf(lookupWords.get(lWord).charAt(i));
            if (rMax < index)
                rMax = index;
        }
        for (int i = 0, j = 0; i < words.size() && j < lookupWords.get(lWord).length(); i++, j++) {
            int index = words.get(i).indexOf(lookupWords.get(lWord).charAt(i));
            if (words.get(i).length() < lookupWords.get(lWord).length())
                index = words.get(i).lastIndexOf(lookupWords.get(lWord).charAt(i));
            if (index == rMax) {
                for (int k = 0, l = 0; l < words.get(i).length(); k++, l++) {
                    k++;
                    result[i][k] = words.get(i).charAt(l);
                    k++;
                }
            } else if (index < rMax) {
                for (int k = 3 * (rMax - index), l = 0; l < words.get(i).length(); k++, l++) {
                    k++;
                    result[i][k] = words.get(i).charAt(l);
                    k++;
                }
            }
        }
        for (int lupw = 0; lupw < words.size() - lookupWords.get(lWord).length(); lupw++) {
            for (int rRows = lookupWords.get(lWord).length(); rRows < result.length; rRows++) {
                for (int p = 0; p < lookupWords.get(rRows).length(); p++) {
                    int rIndex;
                    if (words.get(rRows).contains(Character.toString(lookupWords.get(rRows).charAt(p)))) {
                        rIndex = words.get(rRows - 1).lastIndexOf(lookupWords.get(rRows).charAt(p - 1));
                        for (int k = 3 * (rIndex - words.get(rRows).length() + 1), l = 0; l < words.get(rRows).length(); k++, l++) {
                            k++;
                            result[rRows][k] = words.get(rRows).charAt(l);
                            k++;
                        }
                    }
                }
            }
        }
        return result;
    }

    public static char[][] getFinalResult(char[][] result, List words, List lookupWords) {
        for (int i = 0; i < lookupWords.size(); i++) {
            for (int j = 0; j < result[0].length; j++) {
                for (int k = 0; k < result.length; k++) {
                    int count = 0;
                    for (int l = 0; (k + l) < result.length && l < lookupWords.get(i).length(); l++) {
                        if (result[k + l][j] == lookupWords.get(i).charAt(l)) {
                            count++;
                        }
                    }
                    if (count == lookupWords.get(i).length()) {
                        for (int m = 0; m < lookupWords.get(i).length(); m++) {
                            result[k + m][j - 1] = '[';
                            result[k + m][j + 1] = ']';
                        }
                        break;
                    }
                }
            }
        }
        return result;
    }

    public static void print(char[][] result) {
        for (char[] element : result) {
            for (char element2 : element) {
                System.out.print(element2);
            }
            System.out.println();
        }
    }
}

Comments :

© meritcampus 2019

All Rights Reserved.

Open In App