Menu
Topics Index
...
`

Weekend Hack - 12 Jan 2013 - Results

Thanks to Aruna Gunda, Deepika Koduri and Srihari Adelli 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 12 Jan 2013 is Deepika Koduri. She will get a recharge or gift voucher worth Rs. 200. Since the problem was complex and since we got only two answers, we would also like to give a recharge of Rs. 40 for the other two participants who submitted it correctly.

Solution 1 - Submitted on Sat Jan 12 16:14:48 2013

public class FindWordPresentInCharacterMatrixBiDirectional {

    public static void main(String s[]) {
        char[][] input = {{'A', 'S', 'C', 'D'}, {'C', 'T', 'A', 'F'}, {'Q', 'M', 'A', 'S'}, {'V', 'X', 'Z', 'C'}};
        System.out.println("CAT is present : " + isWordIsPresentInMatrix(input, "CAT"));
    }

    public static boolean isWordIsPresentInMatrix(char[][] matrix, String searchWord) {
        String s;
        char[] arr = new char[matrix.length];
        boolean flag = false;
        /*checking horizontally including the reverse direction for the String*/
        for (char[] element : matrix) {
            if (flag)
                break;
            for (int j = 0; j < matrix.length; j++) {
                arr[j] = element[j];
            }
            s = new String(arr);
            if (s.equals(searchWord) || !(s.indexOf(searchWord) < 0) || reverse(s).equals(searchWord) || !(reverse(s).indexOf(searchWord) < 0))
                flag = true;
        }
        /*checking vertiically including the reverse direction for the string*/
        for (int i = 0; i < matrix.length; i++) {
            if (flag)
                break;
            for (int j = 0; j < matrix.length; j++) {
                arr[j] = matrix[j][i];
            }
            s = new String(arr);
            if (s.equals(searchWord) || !(s.indexOf(searchWord) < 0) || reverse(s).equals(searchWord) || !(reverse(s).indexOf(searchWord) < 0))
                flag = true;
        }
        /*checking main diagonal in both the directions */
        if (!flag) {
            for (int i = 0; i < matrix.length; i++) {
                arr[i] = matrix[i][i];
            }
            s = new String(arr);
            if (s.equals(searchWord) || !(s.indexOf(searchWord) < 0) || reverse(s).equals(searchWord) || !(reverse(s).indexOf(searchWord) < 0))
                flag = true;
        }
        /*checking main cross diagonal in both the directions*/
        if (!flag) {
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix.length; j++) {
                    if (i + j == matrix.length - 1)
                        arr[i] = matrix[i][j];
                }
                s = new String(arr);
                if (s.equals(searchWord) || !(s.indexOf(searchWord) < 0) || reverse(s).equals(searchWord) || !(reverse(s).indexOf(searchWord) < 0))
                    flag = true;
            }
        }
        /*checking remaining diagonals on leftside to the main diagonal in both the directions*/
        for (int k = 1; k < matrix.length - 1; k++) {
            int i = k, j = 0;
            if (flag)
                break;
            while (j < (matrix.length - k)) {
                arr[j] = matrix[i][j];
                i++;
                j++;
            }
            for (int n = j; n < matrix.length; n++)
                arr[n] = '@';
            s = new String(arr);
            if (s.equals(searchWord) || !(s.indexOf(searchWord) < 0) || reverse(s).equals(searchWord) || (reverse(s).indexOf(searchWord) >= 0))
                flag = true;
        }
        /*checking remaining diagonals on righttside of the diagonal iin both the directions*/
        for (int k = 0; k < matrix.length; k++) {
            int i = k, j = 1;
            if (flag)
                break;
            while (i < j && j < matrix.length) {
                arr[j] = matrix[i][j];
                i++;
                j++;
            }
            s = new String(arr);
            if (s.equals(searchWord) || !(s.indexOf(searchWord) < 0) || reverse(s).equals(searchWord) || !(reverse(s).indexOf(searchWord) < 0))
                flag = true;
        }
        /*checking diagonals left to cross diagonal in both the directions*/
        for (int k = matrix.length - 2; k > 0; k--) {
            int i = 0, j = k;
            while (i <= k) {
                arr[i] = matrix[i][j];
                j--;
                i++;
            }
            s = new String(arr);
            if (s.equals(searchWord) || !(s.indexOf(searchWord) < 0) || reverse(s).equals(searchWord) || !(reverse(s).indexOf(searchWord) < 0))
                flag = true;
        }
        /*checking remaining diagonals right to cross diagonal in both the directions*/
        for (int k = matrix.length - 1; k > 0; k--) {
            int i = k, j = 1;
            while (j <= k) {
                arr[i] = matrix[i][j];
                i--;
                j++;
            }
            s = new String(arr);
            if (s.equals(searchWord) || !(s.indexOf(searchWord) < 0) || reverse(s).equals(searchWord) || !(reverse(s).indexOf(searchWord) < 0))
                flag = true;
        }
        return flag;
    }

    public static String reverse(String input) {
        char[] arr = new char[input.length()];
        for (int i = 0; i < input.length(); i++) {
            arr[i] = input.charAt(input.length() - i - 1);
        }
        String result = new String(arr);
        return result;
    }
}

Review Comments

  1. The idea of converting the char array to String is good, but the only downside is it takes more memory.
  2. The comments describing what the code is doing are useful.
  3. Creating a method reverse for reversing the strings is good, but we could have used the StringBuilder's reverse method to reverse a string.
  4. There is duplicate code between various searches, we could have created few more methods to drastically reduce the code size.

Solution 2 - Submitted at Sat Jan 12 21:40:06 2013

public class FindWordPresentInCharacterMatrixBiDirectional {

    public static void main(String s[]) {
        char[][] input = {{'A', 'S', 'C', 'D'}, {'C', 'T', 'A', 'F'}, {'Q', 'M', 'A', 'S'}, {'V', 'X', 'Z', 'C'}};
        System.out.println("CAT is present : " + isWordIsPresentInMatrix(input, "CAT"));
    }

    public static boolean isWordIsPresentInMatrix(char[][] matrix, String searchWord) {
        int temp = 0, k = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == searchWord.charAt(k)) {
                    temp = check(i, j, matrix, searchWord);
                    if (temp == 1)
                        return true;
                }
            }
        }
        return false;
    }

    public static int check(int p, int q, char input[][], String search) {
        int count = 1, len, t, s, k = 0;
        int m, n;
        m = input.length;
        n = input[0].length;
        len = search.length();
        s = p;
        t = q;
        if (q >= len - 1) {
            while (k < len - 1 && t > 0) {
                t--;
                k++;
                if (input[p][t] == search.charAt(k))
                    count++;
                else
                    break;
            }
            if (count == len)
                return 1;
            t = q;
            k = 0;
            count = 1;
        }
        if (n - q >= len) {
            while (k < len - 1 && t < n - 1) {
                t++;
                k++;
                if (input[p][t] == search.charAt(k))
                    count++;
                else
                    break;
            }
            if (count == len)
                return 1;
            t = q;
            k = 0;
            count = 1;
        }
        if (p >= len - 1) {
            while (k < len - 1 && s > 0) {
                s--;
                k++;
                if (input[s][q] == search.charAt(k))
                    count++;
                else
                    break;
            }
            if (count == len)
                return 1;
            s = p;
            k = 0;
            count = 1;
        }
        if (m - p >= len) {
            while (k < len - 1 && s < m - 1) {
                s++;
                k++;
                if (input[s][q] == search.charAt(k))
                    count++;
                else
                    break;
            }
            if (count == len)
                return 1;
            s = p;
            k = 0;
            count = 1;
        }
        while (k < len - 1 && t < (n - 1) && s < (m - 1)) {
            t++;
            s++;
            k++;
            if (input[s][t] == search.charAt(k))
                count++;
            else
                break;
        }
        if (count == len)
            return 1;
        t = q;
        s = p;
        k = 0;
        count = 1;
        while (k < len - 1 && t > 0 && s > 0) {
            t--;
            s--;
            k++;
            if (input[s][t] == search.charAt(k))
                count++;
            else
                break;
        }
        if (count == len)
            return 1;
        t = q;
        s = p;
        k = 0;
        count = 1;
        while (k < len - 1 && s < m - 1 && t > 0) {
            t--;
            s++;
            k++;
            if (input[s][t] == search.charAt(k))
                count++;
            else
                break;
        }
        if (count == len)
            return 1;
        t = q;
        s = p;
        k = 0;
        count = 1;
        while (k < len - 1 && s > 0 && t < n - 1) {
            t++;
            s--;
            k++;
            if (input[s][t] == search.charAt(k))
                count++;
            else
                break;
        }
        if (count == len)
            return 1;
        t = q;
        s = p;
        k = 0;
        count = 1;
        return 0;
    }
}

Review Comments

  1. The idea of creating the method check is good, but we could have created more methods to remove the duplicate code further.
  2. The naming of variables could have been better, it will be very confusing to have variables like t, s, k, q etc.
  3. The duplicate code could be removed, by creating more methods.

Solution 3 - Submitted at Sun Jan 13 08:12:11 2013

public class FindWordPresentInCharacterMatrixBiDirectional {

    public static void main(String s[]) {
        char[][] input = {{'A', 'S', 'C', 'D'}, {'C', 'T', 'A', 'F'}, {'Q', 'M', 'A', 'S'}, {'V', 'X', 'Z', 'C'}};
        System.out.println("CAT is present : " + isWordIsPresentInMatrix(input, "CAT"));
    }

    public static boolean isWordIsPresentInMatrix(char[][] matrix, String searchWord) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (searchWord.charAt(0) == matrix[i][j]) {
                    if (search(searchWord, matrix, i, j, 1, 1) || search(searchWord, matrix, i, j, -1, -1) || search(searchWord, matrix, i, j, 0, 1) || search(searchWord, matrix, i, j, 0, -1) || search(searchWord, matrix, i, j, 1, 0) || search(searchWord, matrix, i, j, -1, 0) || search(searchWord, matrix, i, j, -1, 1) || search(searchWord, matrix, i, j, 1, -1))
                        return true;
                }
            }
        }
        return false;
    }

    public static boolean search(String searchWord, char[][] matrix, int starti, int startj, int incm, int incn) {
        starti += incm;
        startj += incn;
        int count = 1;
        for (int k = 1; k < searchWord.length() && starti < matrix.length && startj < matrix[0].length && starti >= 0 && startj >= 0; k++) {
            if (searchWord.charAt(k) == matrix[starti][startj]) {
                count++;
                starti += incm;
                startj += incn;
            } else
                break;
        }
        if (count == searchWord.length())
            return true;
        return false;
    }
}

Review Comments

  1. Creating a method to perform multiple searches is very good idea and it reduced the duplicate code drastically.
  2. The lengthy if condition could have been split into multiple for better readability.
  3. The names of the variables like starti, startj, incm, incn could have been made more clearer.
  4. The if condition to match the word length in the method search could have been avoided if used a return variable and initialized it to true.

© meritcampus 2019

All Rights Reserved.

Open In App