Menu
Topics Index
...
`

Weekend Hack - 27 Jul 2013 - Results

Thanks to Ramana T and 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 27 Jul 2013 - 1 is Pramod Jain. He will get a recharge or gift voucher worth Rs. 150.

The number of ways in which the frog can reach

A frog can jump either one foot or two feet at once, given the distance between its resting place and the pond in feet, Write a program to get the number of ways in which the frog can reach the pond from its resting place.

Input (int) Output(List)
1 [1]
0 []
3 [111, 12, 21]
-6 []
6 [111111, 11112, 11121, 11211, 12111, 21111, 1122, 1212, 1221, 2112, 2121, 2211, 222]

Solution 1 - Submitted on Sat Jul 27 12:58:09 2013

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

class FindPossibleFrogJumps {

    public static void main(String s[]) {
        List result = getPossibleJumps(6);
        System.out.println("The possible jumps are: " + result);
    }

    public static List getPossibleJumps(int number) {
        List result = new ArrayList();
        /* variable p,q,r,s,t,u are just used for iterating purpose only..
        and if their sum is equal to given number then it adds to the list*/
        for (int p = 1; p <= number; p++) {
            for (int q = 1; q <= number; q++) {
                for (int r = 1; r <= number; r++) {
                    for (int s = 1; s <= number; s++) {
                        for (int t = 1; t <= number; t++) {
                            for (int u = 1; u <= number; u++) {
                                if (p + q + r + s + t + u == number && (p == 1 || p == 2) && (q == 1 || q == 2) && (r == 1 || r == 2) && (s == 1 || s == 2) && (t == 1 || t == 2) && (u == 1 || u == 2)) {
                                    result.add("" + p + "" + q + "" + r + "" + s + "" + t + "" + u);
                                }
                            }
                            if (p + q + r + s + t == number && (p == 1 || p == 2) && (q == 1 || q == 2) && (r == 1 || r == 2) && (s == 1 || s == 2) && (t == 1 || t == 2)) {
                                result.add("" + p + "" + q + "" + r + "" + s + "" + t);
                            }
                        }
                    }
                }
            }
        }
        for (int p = 1; p <= number; p++) {
            for (int q = 1; q <= number; q++) {
                for (int r = 1; r <= number; r++) {
                    for (int s = 1; s <= number; s++) {
                        if (p + q + r + s == number && (p == 1 || p == 2) && (q == 1 || q == 2) && (r == 1 || r == 2) && (s == 1 || s == 2)) {
                            result.add("" + p + "" + q + "" + r + "" + s);
                        }
                    }
                }
            }
        }
        for (int p = 1; p <= number; p++) {
            for (int q = 1; q <= number; q++) {
                for (int r = 1; r <= number; r++) {
                    if (p + q + r == number && (p == 1 || p == 2) && (q == 1 || q == 2) && (r == 1 || r == 2)) {
                        result.add("" + p + "" + q + "" + r);
                    }
                }
                if (p + q == number && (p == 1 || p == 2) && (q == 1 || q == 2)) {
                    result.add("" + p + "" + q);
                }
            }
            if (p == number && (p == 1 || p == 2)) {
                result.add("" + p);
            }
        }
        return result;
    }
}

Comments :

Solution 2 - Submitted on Sun Jul 28 00:32:33 2013

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

class FindPossibleFrogJumps {

    public static void main(String s[]) {
        List result = getPossibleJumps(6);
        System.out.println("The possible jumps are: " + result);
    }

    public static List getPossibleJumps(int number) {
        List result = new ArrayList();
        // If number is negative or zero then return empty list
        if (number <= 0) {
            return result;
        }
        // The number of twos may vary from 0 to (number/2)
        for (int no_of_twos = 0; no_of_twos <= number / 2; no_of_twos++) {
            // Getting all the combinations with given number of two's (does not include duplicates but are not sorted)
            List list = getAllCombinations(number, no_of_twos);
            // sorting the strings
            Collections.sort(list);
            // Adding the strings to main result
            result.addAll(list);
        }
        return result;
    }

    public static List getAllCombinations(int number, int no_of_twos) {
        int no_of_ones = number - 2 * no_of_twos;
        int totalNumber = no_of_ones + no_of_twos;
        int array[] = new int[totalNumber];
        int i = 0;
        // Initializing array with the given number of 1's and 2's
        while (i < no_of_ones) {
            array[i] = 1;
            i++;
        }
        while (i < totalNumber) {
            array[i] = 2;
            i++;
        }
        List list = new ArrayList();
        // returning all permutations with the given combinations
        return permute(list, array, 0, array.length - 1);
    }

    // Function to swap two numbers present at given indexes
    public static void swap(int[] array, int index_one, int index_two) {
        int temp;
        temp = array[index_one];
        array[index_one] = array[index_two];
        array[index_two] = temp;
    }

    // Function to get all permutations using backtracking
    // In this case, as there is no need of swapping equal numbers,swap function is called only if the values to be swapped are different
    public static List permute(List list, int[] array, int i, int n) {
        int j;
        if (i == n) {
            // Duplicates are not allowed
            String answer = convert_to_string(array);
            if (!list.contains(answer)) {
                list.add(answer);
            }
        } else {
            for (j = i; j <= n; j++) {
                if (array[i] != array[j]) {
                    swap(array, i, j);
                }
                permute(list, array, i + 1, n);
                if (array[i] != array[j]) {
                    swap(array, i, j);
                }
            }
        }
        return list;
    }

    // Function to convert elements of an array into a string 
    public static String convert_to_string(int array[]) {
        String result = "";
        for (int element : array) {
            result = result + element;
        }
        return result;
    }
}

Comments :

© meritcampus 2019

All Rights Reserved.

Open In App