Finding Lottery odds – Topcoder #268

By Posted on

Problem

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:

  1. Code structure
  2. Test cases that could be added
  3. 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.

Solution

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.

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

  1. 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…

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.

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);
   }
}

Leave a Reply

Your email address will not be published. Required fields are marked *