Finding Lottery odds - Topcoder #268

Question

I have implemented the question #268 from Topcoder. The question is that there are 4 conditions for a lottery ticket:

CHOICES - numbers available (10 ≤ CHOICES ≤ 100)
BLANKS - number of numbers that can be chosen (1 ≤ BLANKS ≤ 8)
SORTED - are the numbers sorted
UNIQUE - are the numbers unique

The input is given as

(CHOICES, BLANKS, SORTED, UNIQUE)

For example, when the conditions are

CHOICES = 15, BLANKS = 4, SORTED = FALSE and UNIQUE = TRUE

one of the values possible is

{3, 7, 12, 14}

Suppose these are the inputs: (in the format NAME: CHOICES BLANKS SORTED UNIQUE)

{"PICK ANY TWO: 10 2 F F",
"PICK TWO IN ORDER: 10 2 T F",
"PICK TWO DIFFERENT: 10 2 F T",
"PICK TWO LIMITED: 10 2 T T"}

The number of ways in which these can happen is:

PICK ANY TWO - 100 i.e (10 * 10)
PICK TWO IN ORDER - 55 
PICK TWO DIFFERENT - 90 i.e. (10 * 9) i.e. 10!/(10-2)!
PICK TWO LIMITED - 45 i.e. 10!/2!(10-2)!

And the output is:

PICK TWO LIMITED
PICK TWO IN ORDER
PICK TWO DIFFERENT
PICK ANY TWO

I would like to have some suggestions for:

Code structure
Test cases that could be added
Errors that can be found

Main Class

Lottery

public class Lottery {

    public String[] sortByOdds(String[] rules) {
        Rule[] rule = new Rule[rules.length];

        for (int i = 0; i < rules.length; i++) {
            rule[i] = parseStringAndCreateRule(rules[i]);
        }

        MergeSort.sort(rule);
        // MergeSort is REQUIRED because we shouldn't change the order of Rules
        // if 2 (or more) Rules have the same Odds. This is not guaranteed with
        // Array.sort().
        // Arrays.sort(rule);

        String[] namesOfRules = new String[rule.length];
        for (int i = 0; i < rule.length; i++) {
            namesOfRules[i] = rule[i].name;
        }
        return namesOfRules;
    }

    private Rule parseStringAndCreateRule(String rule) {
        StringTokenizer strTokenizer = new StringTokenizer(rule, ":");

        String name = strTokenizer.nextToken().trim();
        String[] conditions = strTokenizer.nextToken().trim().split(" ");

        return new Rule(name, conditions);
    }

}

Other Helper Classes

Rule

public class Rule implements Comparable<Rule> {

    String name;
    String[] conditions;
    int noOfChoices;
    int noOfBlanks;
    boolean isSorted;
    boolean isUnique;
    BigInteger numberOfOdds;

    public Rule(String name, String[] conditions) {
        this.name = name;
        this.conditions = conditions;
        checkAndAssignConditions(conditions);
        calculateOdds();
    }

    private void checkAndAssignConditions(String[] conditions) {
        try {
            if (conditions.length != 4) {
                throw new IllegalArgumentException(
                        "Number of conditions should be 4");
            }

            noOfChoices = Integer.valueOf(conditions[0]);
            noOfBlanks = Integer.valueOf(conditions[1]);
            if (conditions[2].length() != 1 || conditions[3].length() != 1) {
                throw new InvalidAttributesException(
                        "Conditions Sorted and Unique should be of length 1");
            }

            if (String.valueOf(conditions[2]).equalsIgnoreCase("T")) {
                isSorted = true;
            } else if (String.valueOf(conditions[2]).equalsIgnoreCase("F")) {
                isSorted = false;
            } else {
                throw new InvalidAttributesException(
                        "Sorted should either be TRUE of FALSE");
            }

            if (String.valueOf(conditions[3]).equalsIgnoreCase("T")) {
                isUnique = true;
            } else if (String.valueOf(conditions[3]).equalsIgnoreCase("F")) {
                isUnique = false;
            } else {
                throw new InvalidAttributesException(
                        "Unique should either be TRUE of FALSE");
            }

        } catch (NumberFormatException e) {
            System.out.println(e.getMessage());
            e.printStackTrace();
        } catch (InvalidAttributesException e) {
            System.out.println(e.getMessage());
            e.printStackTrace();
        } catch (RuntimeException e) {
            System.out.println(e.getMessage());
            e.printStackTrace();
        }

    }

    private void calculateOdds() {
        if (!isSorted && !isUnique) {
            numberOfOdds = LotteryUtils.getNoOfDrawsForNotSortedNotUnique(
                    noOfChoices, noOfBlanks);
        } else if (isSorted && !isUnique) {
            numberOfOdds = LotteryUtils.getNoOfDrawsForSortedNotUnique(
                    noOfChoices, noOfBlanks);
        } else if (!isSorted && isUnique) {
            numberOfOdds = LotteryUtils.getNoOfDrawsForNotSortedUnique(
                    noOfChoices, noOfBlanks);
        } else if (isSorted && isUnique) {
            numberOfOdds = LotteryUtils.getNoOfDrawsForSortedUnique(
                    noOfChoices, noOfBlanks);
        }
    }

    @Override
    public int compareTo(Rule o) {
        return numberOfOdds.compareTo(o.numberOfOdds);
    }

}

LotteryUtils

public class LotteryUtils {
    private static BigInteger getPow(int n, int r) {
        BigInteger noOfDraws = new BigInteger("1");
        for (int i = 0; i < r; i++) {
            noOfDraws = noOfDraws.multiply(BigInteger.valueOf(n));
        }
        return noOfDraws;
    }

    private static BigInteger getFactorial(int n) {
        BigInteger factorial = new BigInteger("1");
        for (int i = 1; i <= n; i++) {
            factorial = factorial.multiply(BigInteger.valueOf(i));
        }
        return factorial;
    }

    public static BigInteger getCombination(int n, int r) {
        BigInteger rFactorial = new BigInteger("1");
        BigInteger numeratorPart = new BigInteger("1");

        if (n == r)
            return new BigInteger("1");

        for (int i = 0; i < r; i++) {
            numeratorPart = numeratorPart.multiply(BigInteger.valueOf(n - i));
        }

        rFactorial = getFactorial(r);

        return numeratorPart.divide(rFactorial);
    }

    public static BigInteger getPermutation(int n, int r) {
        if (n == r)
            return getFactorial(n);
        else
            return getFactorial(n).divide(getFactorial(n - r));
    }

    public static BigInteger getNoOfDrawsForNotSortedNotUnique(int n, int r) {
        return getPow(n, r);
    }

    public static BigInteger getNoOfDrawsForSortedNotUnique(int n, int r) {
        // SEE: Stars and Bars (Combinatorics)
        return getCombination(n + r - 1, r);
    }

    public static BigInteger getNoOfDrawsForNotSortedUnique(int n, int r) {
        return getPermutation(n, r);
    }

    public static BigInteger getNoOfDrawsForSortedUnique(int n, int r) {
        return getCombination(n, r);
    }

}

TestCase

LotteryTest

public class LotteryTest {

    @Test
    public void testGetCombination() {
        assertEquals(new BigInteger("45"), LotteryUtils.getCombination(10, 2));
        assertEquals(new BigInteger("1"), LotteryUtils.getCombination(10, 10));
        assertEquals(new BigInteger("1"), LotteryUtils.getCombination(10, 0));
        assertEquals(new BigInteger("210"), LotteryUtils.getCombination(10, 4));
        assertEquals(new BigInteger("210"), LotteryUtils.getCombination(10, 6));
        assertEquals(new BigInteger("252"), LotteryUtils.getCombination(10, 5));
        assertEquals(LotteryUtils.getCombination(11, 6),
                LotteryUtils.getCombination(11, 5));
    }

    @Test
    public void testGetPermutation() {
        assertEquals(new BigInteger("90"), LotteryUtils.getPermutation(10, 2));
    }

    @Test
    public void testSortByOdds() {
        Lottery lottery = new Lottery();
        String[] lotteryTest;
        String[] lotterySolution = { "PICK TWO LIMITED", "PICK TWO IN ORDER",
                "PICK TWO DIFFERENT", "PICK ANY TWO" };
        String[] lotterySolution2 = { "RED", "ORANGE", "YELLOW", "GREEN",
                "BLUE", "INDIGO", "VIOLET" };
        String[] lotterySolution3 = {};

        lotteryTest = lottery.sortByOdds(new String[] {
                "PICK ANY TWO: 10 2 F F", "PICK TWO IN ORDER: 10 2 T F",
                "PICK TWO DIFFERENT: 10 2 F T", "PICK TWO LIMITED: 10 2 T T" });
        assertEquals(lotteryTest.length, lotterySolution.length);
        for (int i = 0; i < lotteryTest.length; i++) {
            assertEquals(lotteryTest[i], lotterySolution[i]);
        }

        lotteryTest = lottery.sortByOdds(new String[] { "INDIGO: 93 8 T F",
                "ORANGE: 29 8 F T", "VIOLET: 76 6 F F", "BLUE: 100 8 T T",
                "RED: 99 8 T T", "GREEN: 78 6 F T", "YELLOW: 75 6 F F" });
        assertEquals(lotteryTest.length, lotterySolution2.length);
        for (int i = 0; i < lotteryTest.length; i++) {
            assertEquals(lotteryTest[i], lotterySolution2[i]);
        }

        lotteryTest = lottery.sortByOdds(new String[] {});
        assertEquals(lotteryTest.length, lotterySolution3.length);
        for (int i = 0; i < lotteryTest.length; i++) {
            assertEquals(lotteryTest[i], lotterySolution3[i]);
        }

    }
}

Sort Implementation

Merge Sort

public class MergeSort {

    @SuppressWarnings("rawtypes")
    private static void merge(Comparable[] a, Comparable[] aux, int lo,
            int mid, int hi) {
        for (int i = lo; i <= hi; i++) {
            aux[i] = a[i];
        }

        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (j > hi)
                a[k] = aux[i++];
            else if (i > mid)
                a[k] = aux[j++];
            else if (less(aux[i], aux[j]))
                a[k] = aux[i++];
            else
                a[k] = aux[j++];
        }
    }

    @SuppressWarnings({ "rawtypes", "unchecked" })
    private static boolean less(Comparable v, Comparable w) {
        return (v.compareTo(w) < 0);
    }

    @SuppressWarnings("rawtypes")
    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo)
            return;

        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        // Merge the two sorted subarrays
        merge(a, aux, lo, mid, hi);
    }

    @SuppressWarnings("rawtypes")
    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length - 1);
    }
}

The entire repository is hosted at GitHub.

I got a unit test failure: 1) testSortByOdds(LotteryTest) org.junit.ComparisonFailure: expected:<[INDIGO]> but was:<[BLUE]> — 200_success♦, Jan 24 at 11:45
@200_success I have added my MergeSort implementation as well, it will not cause any errors any more. — yadav_vi, Jan 25 at 13:07

200_success · Accepted Answer · 2015-01-25 18:22:52Z

up vote 1 down vote accepted

In LotteryUtils, drop "get" from the function names. "Get" implies fetching something that already exists. Here, you are just doing computations. You wouldn't say Math.getSin(x), for example.

Every function in the class is static, so you should suppress the default constructor by writing

private LotteryUtils() {}

BigInteger.pow() already exists. Don't write your own.

A productOfRange(low, high) function would be more generally useful than a factorial function.

You shouldn't need a special case in getPermutations().

In my opinion, your getNoOfDrawsFor…() functions belong in the Rule class.

answered Jan 25 at 18:22

200_success♦
59.3k471226

Should I make the class immutable? Would naming getPermutations() as just permutations() be fine? – yadav_vi Jan 27 at 10:47

Also, why 3 answers, why not just one? So that I can accept it and it would contain all the relevant information in the same place. – yadav_vi Jan 27 at 10:50

The class is already stateless; just suppress the constructor and you'll be fine. Yes, I suggest renaming getPermutations() to permutations(). – 200_success♦ Jan 27 at 18:29

My rationale for multiple answers: The three answers are independent; they focus on different issues, and there isn't any theme or progression. Writing them as separate answers allows users to agree/disagree with each answer separately, and keeps follow-up comment threads to a reasonable length as well. – 200_success♦ Jan 27 at 18:35

add a comment |

200_success · Answer 2 · 2015-01-27 18:26:58Z

Your comment says that you implemented a mergesort because you needed a stable sort. However, the Arrays.sort() documentation already guarantees that property:

This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.

On the other hand, your mergesort is not stable. Stability means that in the event of a tie, you should place the originally earlier element first. Therefore, your less() comparison should be lessOrEqual().

In addition, you shouldn't need to suppress the rawtypes warnings. What the warning is saying is that, for example, while integers are comparable and dates are comparable, it doesn't make sense to compare integers with dates, but your code allows it.

You can make use of System.arraycopy() to fill aux.

The default constructor should be suppressed.

I've modified the bounds so that the functions operate on lo ≤ i < hi. This inclusive-exclusive range convention is more idiomatic in Java: you can see it in the methods of Arrays, String.substring(beginIndex, endIndex), and Random.nextInt(n). The main advantage of this convention is that hi - lo gives you the size of the range, so that there is less ± 1 awkwardness.

import java.lang.reflect.Array;

public class MergeSort {

    private MergeSort() {}

    private static <T extends Comparable<T>> void merge(T[] a, T[] aux, int lo,
            int mid, int hi) {
        System.arraycopy(a, lo, aux, lo, hi - lo);

        int i = lo, j = mid;
        for (int k = lo; k < hi; k++) {
            if (j >= hi)
                a[k] = aux[i++];
            else if (i >= mid)
                a[k] = aux[j++];
            else if (lessOrEqual(aux[i], aux[j]))
                a[k] = aux[i++];
            else
                a[k] = aux[j++];
        }
    }

    private static <T extends Comparable<T>> boolean lessOrEqual(T v, T w) {
        return (v.compareTo(w) <= 0);
    }

    private static <T extends Comparable<T>> void sort(T[] a, T[] aux, int lo, int hi) {
        if (hi - lo <= 1)
            return;

        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid, hi);
        // Merge the two sorted subarrays
        merge(a, aux, lo, mid, hi);
    }

    public static <T extends Comparable<T>> void sort(T[] a) {
        @SuppressWarnings("unchecked")
        T[] aux = (T[])Array.newInstance(a.getClass().getComponentType(), a.length);
        sort(a, aux, 0, a.length);
   }
}

Arrays.sort() is indeed stable. Apparently I didn't read the question well, there needs to be another compareTo() if the odds are equal. We need to compare the names of RULES in alphabetical order if the odds are equal. — yadav_vi, Jan 27 at 10:43
About the Comparable part of MergeSort how can I improve it? — yadav_vi, Jan 27 at 10:52
My MergeSort implementation is NOT stable. Thanks for pointing that out. — yadav_vi, Jan 27 at 12:32
(T[])Array.newInstance(a.getClass().getComponentType(), a.length); Instead of this, what if I use a method like this - public static <T> void sort(Comparable<T>[] a) { } with Comparable<T>[] aux = new Comparable[a.length];. — yadav_vi, Jan 28 at 5:17
Have you tried Comparable<T>[] aux = new Comparable[a.length];? — 200_success♦, Jan 28 at 5:49

Manny Meng · Answer 3 · 2015-01-26 02:35:31Z

up vote 2 down vote

Your code is generally sound. I would make a few changes:

new BigInteger("1")

BigInteger has a static final field , BigInteger.ONE, which represents the value one. I suggest you replace all your new BigInteger("1") with BigInteger.ONE as BigIntegers are immutable anyways and it saves you from creating another BigInteger.

Oh, I guess only one change...

answered Jan 26 at 2:35

Manny Meng
2,4181744

Thanks for the tip. – yadav_vi Jan 27 at 10:51

add a comment |

200_success · Answer 4 · 2015-01-25 18:34:16Z

up vote 0 down vote

The judges in programming challenges like this are generally not hostile: the input to your program is within the stated specifications. Unless the task description specifically asks you to validate the input, you shouldn't need to waste effort on it.

If you do validate, then printing an error message and stack trace is an ineffective error-handling strategy. Let the exception propagate, so that the program halts instead of blindly proceeding based on input that is known to be bad.

answered Jan 25 at 18:34

200_success♦
59.3k471226

I just added the checks so that they could be reviewed. Meaning, if I have to sanitize an input, would this be the way how we do it? – yadav_vi Jan 27 at 10:44

I also wanted to know what all Exceptions are proper to use when we encounter an input error. – yadav_vi Jan 27 at 10:55

Throwing IllegalArgumentException or NumberFormatException is good. (What is InvalidAttributesException, by the way? If it's javax.naming.directory.InvalidAttributesException, that's weird.) Catching them in a way that lets your program continue is bad. Catching them and halting with a polished error message would be good. Not catching them at all and letting the program crash would also be acceptable for this kind of program, where nobody really cares what the error message looks like. – 200_success♦ Jan 27 at 18:43

javax.naming.directory.InvalidAttributesException is weird, thanks for pointing out. – yadav_vi Jan 28 at 5:18

add a comment |

asked	2 months ago
viewed	145 times
active	1 month ago

current community

your communities

more stack exchange communities

Finding Lottery odds - Topcoder #268

Main Class

Lottery

Other Helper Classes

Rule

LotteryUtils

TestCase

LotteryTest

Sort Implementation

Merge Sort

4 Answers 4

Your Answer

Not the answer you're looking for? Browse other questions tagged java programming-challenge combinatorics or ask your own question.

Visit Chat

Hot Network Questions

current community

your communities

more stack exchange communities

Finding Lottery odds - Topcoder #268

Main Class

Lottery

Other Helper Classes

Rule

LotteryUtils

TestCase

LotteryTest

Sort Implementation

Merge Sort

4 Answers 4

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged java programming-challenge combinatorics or ask your own question.

Visit Chat

Related

Hot Network Questions