Menu
Topics Index
...
`

Weekend Hack - 26 Jan 2013 - Results

Thanks to Sulekha Metta, Deepika Koduri, Srihari Adelli, Srinivas Rao Bolla and Tejaswini Rao Potlapally 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 (three of them are only in 2nd year CSE and they have not yet completed the Java course), 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 26 Jan 2013 - 1 is Sulekha Metta. She will get a recharge or gift voucher worth Rs. 100.
The winner of the Weekend Hack 26 Jan 2013 - 2 is Srinivasa Rao Bolla . He will get a recharge or gift voucher worth Rs. 250.

Find out the order of stroke out letters by counting 1, 2, 3 etc

Write a program to find out the order of stroke out letters by counting 1, 2, 3 etc. As shown for SACHIN below, A is first cancelled out since it is 2nd (1 + 1) letter from begining, followed by I which is the 3rd letter (2 + 1) from A, followed by H which is the fourth letter (3 + 1) from A and so on. Please note that the last letter remaining should not be included in the output.

Input (Character array) Output (Character array)
['S', 'A', 'C', 'H', 'I', 'N'] S*CHIN -> A
S*CH*N -> I
S*C**N -> H
**C**N -> S
**C*** -> N
Output = ['A', 'I', 'H', 'S', 'N']
['G', 'A', 'N', 'G', 'U', 'L', 'Y'] ['A', 'U', 'N', 'G', 'G', 'L']
['L', 'A', 'X', 'M', 'A', 'N'] ['A', 'A', 'M', 'L', 'N']
['D', 'R', 'A', 'V', 'I', 'D'] ['R', 'I', 'V', 'D', 'D']

Solution 1 - Submitted on Sat Jan 26 11:25:18 2013

public class FindStrokeOutLettersOrder {

    public static void main(String s[]) {
        char input[] = {'Y', 'U', 'V', 'R', 'A', 'J'};
        System.out.print("The strike out order is : ");
        for (char ch : getStrikeOutOrder(input)) {
            System.out.print(ch + " ");
        }
        System.out.println();
        for (char ch : input) {
            System.out.print(ch + " ");
        }
    }

    public static char[] getStrikeOutOrder(char[] input) {
        //nextstroke_count is to keep track of stroke count order
        /*next is a temporary variable which is used to check whether the stroke count order is met or nor */
        int len = input.length, i, j = 0, nextstroke_count = 1, next = 0;
        char result[] = new char[len - 1];
        int result_index = 0;
        if (len == 1)
            return (null);
        int check[] = new int[len];
        for (i = 0; i < len - 1; i++) {
            while (next < nextstroke_count) {
                if (check[j] == 0) {
                    next++;
                }
                j = (j + 1) % len;
            }
            while (check[j] == 1)
                j = (j + 1) % len;
            result[result_index++] = input[j];
            check[j] = 1;
            j = (j + 1) % len;
            nextstroke_count++;
            next = 0;
        }
        return (result);
    }
}

Review Comments

  1. The logic is simple and clear and comments are helpful.
  2. Could have used boolean array for check, instead of integer array and checking for 0 and 1.
  3. There is no need to put the brackets while returning from the method.
  4. Than declaring the next variable outside the loop and resetting to 0, we could have created the next inside the loop.

Solution 2 - Submitted on Sat Jan 26 11:53:26 2013

public class FindStrokeOutLettersOrder {

    public static void main(String s[]) {
        char input[] = {'Y', 'U', 'V', 'R', 'A', 'J'};
        System.out.print("The strike out order is : ");
        for (char ch : getStrikeOutOrder(input)) {
            System.out.print(ch + " ");
        }
    }

    public static char[] getStrikeOutOrder(char[] input) {
        char out[] = new char[input.length - 1];
        int k = 0, i = 0, count = 1;
        while (count < input.length) {
            int j = 1;
            while (j <= count) {
                if (input[i] != '*')
                    j++;
                if (i == input.length - 1)
                    i = 0;
                else
                    i++;
            }
            while (input[i] == '*') {
                if (i == input.length - 1)
                    i = 0;
                else
                    i++;
            }
            out[k++] = input[i];
            input[i] = '*';
            if (i == input.length - 1)
                i = 0;
            else
                i++;
            count++;
        }
        return out;
    }
}

Review Comments

  1. The logic is simple and understandable.
  2. We could have created a variable for input.length - 1 and for '*'.
  3. Since the method name indicates no modification to the input, it is not a good idea to change the input

Solution 3 - Submitted on Sun Jan 27 10:13:16 2013

public class FindStrokeOutLettersOrder {

    public static void main(String s[]) {
        char input[] = {'Y', 'U', 'V', 'R', 'A', 'J'};
        System.out.print("The strike out order is : ");
        for (char ch : getStrikeOutOrder(input)) {
            System.out.print(ch + " ");
        }
    }

    public static char[] getStrikeOutOrder(char[] input) {
        /*variable declarations*/
        int n = input.length;
        char output[] = new char[n - 1];
        int count = 0;
        int temp = 0;
        int index = 1;
        int increase = 2;
        int i = 2;
        /*number of times increment is to be done*/
        while (count < n - 1) {
            while (input[index % n] == 0)
                index++;
            output[count++] = input[index % n];
            input[index % n] = 0;
            while (temp < i) {
                if (input[index % n] == 0)
                    i++;
                temp++;
                index++;
            }
            i = ++increase;
            temp = 0;
        }
        return output;
    }
}

Review Comments

  1. The logic is simple and understandable.
  2. The comments are helpful.
  3. Than declaring the temp variable outside the loop and resetting to 0, we could have created the temp inside the loop.

Find the list of all the words possible with the characters provided

Write a program to return the list of all the words possible with the characters provided. The list should be sorted in ascending order. Do not use String or StringBuffer or Arrays or any other advanced classes. Only use character arrays for solving this.

Input (Char Array) Output (Two Dimensional Char Array)
{M, Y} {{M, Y},
{Y, M}}
{B, A, T} {{A, B, T},
{A, T, B},
{B, A, T},
{B, T, A},
{T, A, B},
{T, B, A}}
{M, O, N} {{M, N, O},
{M, O, N},
{N, M, O},
{N, O, M},
{O, M, N},
{O, N, M}}
{J, U, B, A} {{A, B, J, U},
{A, B, U, J},
{A, J, B, U},
{A, J, U, B},
{A, U, B, J},
{A, U, J, B},
{B, A, J, U},
{B, A, U, J},
{B, J, A, U},
{B, J, U, A},
{B, U, A, J},
{B, U, J, A},
{J, A, B, U},
{J, A, U, B},
{J, B, A, U},
{J, B, U, A},
{J, U, A, B},
{J, U, B, A},
{U, A, B, J},
{U, A, J, B},
{U, B, A, J},
{U, B, J, A},
{U, J, A, B},
{U, J, B, A}}

Solution 1 - Submitted on Sun Jan 27 16:03:43 2013

public class GetAllCharCombinations {

    public static void main(String s[]) {
        char input[] = {'B', 'A', 'T'};
        char[][] words = getAllCombinations(input);
        for (char[] word : words) {
            for (char letter : word) {
                System.out.print(letter);
            }
            System.out.println();
        }
    }

    public static char[][] getAllCombinations(char word[]) {
        int fact = getFactorial(word.length);
        char output[][] = new char[fact][word.length];
        word = sort(word, 0, word.length);
        boolean flag = false;
        int first, second;
        int f = word.length - 2;
        first = f;
        int s = word.length - 1;
        int j = 0;
        while (j < word.length) {
            output[0][j] = word[j];
            j++;
        }
        for (int i = 1; i < fact; i++) {
            while (!flag) {
                if (word[f] < word[s]) {
                    first = f;
                    second = find_second(word, word[f], f + 1);
                    word = swap(word, first, second);
                    flag = true;
                } else {
                    if (f > 0 && s > 0) {
                        f--;
                        s--;
                    }
                }
            }
            f = word.length - 2;
            s = word.length - 1;
            word = sort(word, first + 1, word.length);
            flag = false;
            j = 0;
            while (j < word.length) {
                output[i][j] = word[j];
                j++;
            }
        }
        return output;
    }

    /*To calculate factorial*/
    public static int getFactorial(int n) {
        int fact = 1;
        for (int i = 1; i <= n; i++) {
            fact = fact * i;
        }
        return fact;
    }

    /*method for sorting in ascending order*/
    public static char[] sort(char array[], int start, int index) {
        for (int i = start; i < index - 1; i++) {
            for (int j = i + 1; j < index; j++) {
                if (array[i] > array[j]) {
                    char t = array[i];
                    array[i] = array[j];
                    array[j] = t;
                }
            }
        }
        return array;
    }

    public static int find_second(char array[], int first, int l) {
        int Index = l;
        for (int i = l + 1; i < array.length; i++)
            if (array[i] > first && array[i] < array[Index])
                Index = i;
        return Index;
    }

    /*method for swapping postions*/
    public static char[] swap(char a[], int i, int j) {
        char t = a[i];
        a[i] = a[j];
        a[j] = t;
        return a;
    }
}

Review Comments

  1. The solution is simple and easy to understand.
  2. The way multiple methods are created to solve the problem is good.
  3. Could have created a variable for word.length.
  4. Could have given better names for the variables f and s

Solution 2 - Submitted on Sun Jan 27 23:08:47 2013

public class GetAllCharCombinations {

    public static void main(String s[]) {
        char input[] = {'B', 'A', 'T'};
        char[][] words = getAllCombinations(input);
        for (char[] word : words) {
            for (char letter : word) {
                System.out.print(letter);
            }
            System.out.println();
        }
    }

    public static char[][] getAllCombinations(char word[]) {
        final int size = word.length;
        final char[] word1 = new char[size];
        System.arraycopy(word, 0, word1, 0, size);
        class Print /*nested class to find all combinations of letters*/
        {

            char[] input_word = new char[size];
            int as = factorial(); /* as contains no.of possible combinations*/
            char[][] ch = new char[as][size];
            int r = -1;

            int sort_word() {
                int x;
                System.arraycopy(word1, 0, input_word, 0, size); /*for copying word into another input array */
                int c, d;
                for (c = 0; c < size - 1; c++) /*sorting input*/
                {
                    for (d = c; d < size; d++) {
                        if (input_word[c] > input_word[d]) {
                            char temp;
                            temp = input_word[c];
                            input_word[c] = input_word[d];
                            input_word[d] = temp;
                        }
                    }
                }
                return size;
            }

            void swap(int x, int y) {
                char temp = input_word[x];
                input_word[x] = input_word[y];
                input_word[y] = temp;
            }

            char[][] combinations(int k) /*method to trace all combinations*/
            {
                int i;
                if (k == size) {
                    r++;
                    System.arraycopy(input_word, 0, ch[r], 0, size);
                } else {
                    for (i = k; i < size; i++) {
                        swap(i, k);
                        if (i - k > 1) {
                            int s;
                            for (s = i; s > k + 1; s--)
                                swap(s, s - 1);
                        }
                        combinations(k + 1);
                        swap(i, k);
                        if (i - k > 1) {
                            int s;
                            for (s = k; s < i - 1; s++)
                                swap(s, s + 1);
                        }
                    }
                }
                return ch;
            }

            int factorial() {
                int fact = 1;
                for (int f = size; f > 0; f--)
                    fact = fact * f;
                return fact;
            }
        }
        Print p = new Print();
        int col_size = p.sort_word();
        int row_size = p.factorial();
        char[][] chq = new char[row_size][col_size];
        chq = p.combinations(0);
        return chq;
    }
}

Review Comments

  1. The logic of getting the combinations by swapping is good.
  2. The comments and methods are named properly.
  3. As per the requirements, the advanced classes like String, Arrays should not be used, but we have used System.arraycopy
  4. We could have created additional methods instead of creating the Print class.

Solution 3 - Submitted on Mon Jan 28 00:41:30 2013

public class GetAllCharCombinations {

    public static void main(String s[]) {
        char input[] = {'B', 'A', 'T'};
        char[][] words = getAllCombinations(input);
        for (char[] word : words) {
            for (char letter : word) {
                System.out.print(letter);
            }
            System.out.println();
        }
    }

    public static char[][] getAllCombinations(char word[]) {
        int len = word.length;
        int result_len = 1;
        /* number of permutation for a given string will be n! , so to find the
        length of result set,this for loop is used */
        for (int i = 2; i <= len; i++)
            result_len *= i;
        char[][] result = new char[result_len][];
        get_combi(result, word);
        return (result);
    }

    public static void get_combi(char[][] result, char word[]) {
        int size = word.length;
        java.util.Arrays.sort(word);
        int result_size = result.length;
        for (int i = 0; i < result_size; i++) {
            result[i] = new char[size];
            for (int p = 0; p < size; p++)
                result[i][p] = word[p];
            int k;
            /*  from previous permutation ,find the rightmost character 
            which is smaller than its next character */
            for (k = size - 2; k >= 0; --k) {
                if (word[k] < word[k + 1])
                    break;
            }
            if (k == -1)
                break;
            /* find the smallest character on right and greatest than previously found charector */
            int next_element = search(word, word[k], k + 1, size - 1);
            //swap both the charectors
            swap(word, k, next_element);
            //now sort the word from k+1 to size
            java.util.Arrays.sort(word, k + 1, size);
        }
    }

    public static void swap(char word[], int start, int end) {
        char temp = word[end];
        word[end] = word[start];
        word[start] = temp;
    }

    public static int search(char word[], char first, int l, int h) {
        int index = l;
        for (int i = l + 1; i <= h; i++)
            if (word[i] > first && word[i] < word[index])
                index = i;
        return index;
    }
}

Review Comments

  1. Elegant and simple solution for the problem.
  2. The comments and variable naming conventions are good.
  3. As per the requirements, the advanced classes like String, Arrays should not be used, but we have used Arrays.sort

Solution 4 - Submitted on Mon Jan 28 08:33:47 2013

public class GetAllCharCombinations {

    public static void main(String s[]) {
        char input[] = {'B', 'A', 'T'};
        char[][] words = getAllCombinations(input);
        for (char[] word : words) {
            for (char letter : word) {
                System.out.print(letter);
            }
            System.out.println();
        }
    }

    public static char[][] getAllCombinations(char word[]) {
        int index = 0, count = 1, rowSize = 0, temp = 0;
        int row = 0, column = 0;
        char output[][] = null;
        char temparray[] = word.clone();
        char result[][] = null;
        char sortoutput[][] = null;
        if (word.length == 1) {
            output = new char[1][0];
            output[0][0] = word[0];
            return output;
        } else {
            if (word.length > 1) {
                output = new char[factorial(word.length)][word.length];
                result = getTheDifferentWords(word, index, count, output, rowSize, temp, temparray);
                sortoutput = getThesorting(result, row, row + 1, column);
            } else
                return null;
        }
        return sortoutput;
    }

    public static char[][] getTheDifferentWords(char input[], int index, int count, char sampleOutput[][], int rowSize, int temp, char[] temparray) {
        char b[] = temparray.clone();
        char tempchar[] = getSwap(b, index, count);// get the values swaped.
        index++;
        sampleOutput = storing(tempchar, sampleOutput, rowSize);//Storing the values in output.
        rowSize++;
        char tempchar1[] = getSwap(tempchar, 0, 1);
        sampleOutput = storing(tempchar1, sampleOutput, rowSize);
        rowSize++;
        if (index == count) {
            index = 0;
            count++;
        }
        if (count >= 3 && rowSize < sampleOutput.length) {
            temparray = input.clone();
            char temparray2[] = getSwap(temparray, temp++, count);
            count = 1;
            index = 0;
            getTheDifferentWords(input, index, count, sampleOutput, rowSize, temp, temparray2);
        } else {
            if (rowSize < sampleOutput.length)
                getTheDifferentWords(input, index, count, sampleOutput, rowSize, temp, temparray);
        }
        return sampleOutput;
    }

    public static char[][] storing(char temp1[], char[][] sampleOutput, int rowSize) {
        if (rowSize < sampleOutput.length) {
            for (int m = 0; m < temp1.length; m++)
                sampleOutput[rowSize][m] = temp1[m];
        }
        return sampleOutput;
    }

    public static char[] getSwap(char input[], int index, int count) {
        char temp = input[index];
        input[index] = input[count];
        input[count] = temp;
        return input;
    }//end of the getSwap function.

    public static char[][] getThesorting(char sample[][], int row, int row1, int column) {
        if (sample[row][column] == sample[row1][column] && column < sample[0].length - 1) {
            getThesorting(sample, row, row1, column + 1);
        } else {
            if (sample[row][column] > sample[row1][column]) {
                for (int m = 0; m < sample[0].length; m++) {
                    char temp = sample[row][m];
                    sample[row][m] = sample[row1][m];
                    sample[row1][m] = temp;
                }
            }
            column = 0;
            if (row1 == sample.length - 1 && row1 <= sample.length)
                row1 = ++row + 1;
            else
                row1++;
            if (row < sample.length - 1)
                getThesorting(sample, row, row1, column);
        }
        return sample;
    }//end of the sorting the words(sorting) function.

    public static int factorial(int number) {
        int fact = 1;
        for (int i = 1; i <= number; i++)
            fact *= i;
        return fact;
    }//end of the factorial function.
}

Review Comments

  1. The way of splitting the code into multiple methods is good.
  2. The variable naming and the comments are helpful.
  3. The code does not work for words greater than 5 letters.
  4. Could have created a variable for the 'word.length'

© meritcampus 2019

All Rights Reserved.

Open In App