# Finding Lottery odds - Topcoder #268

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.

• I got a unit test failure: 1) testSortByOdds(LotteryTest) org.junit.ComparisonFailure: expected:<[INDIGO]> but was:<[BLUE]> Commented Jan 24, 2015 at 11:45
• Please include your import statements as well. Commented Jan 24, 2015 at 12:21
• @200_success I have added my MergeSort implementation as well, it will not cause any errors any more. Commented Jan 25, 2015 at 13:07

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.

• Should I make the class immutable? Would naming getPermutations() as just permutations() be fine? Commented Jan 27, 2015 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. Commented Jan 27, 2015 at 10:50
• The class is already stateless; just suppress the constructor and you'll be fine. Yes, I suggest renaming getPermutations() to permutations(). Commented Jan 27, 2015 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. Commented Jan 27, 2015 at 18:35

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.

• 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? Commented Jan 27, 2015 at 10:44
• I also wanted to know what all Exceptions are proper to use when we encounter an input error. Commented Jan 27, 2015 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. Commented Jan 27, 2015 at 18:43
• javax.naming.directory.InvalidAttributesException is weird, thanks for pointing out. Commented Jan 28, 2015 at 5:18

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. Commented Jan 27, 2015 at 10:43
• About the Comparable part of MergeSort how can I improve it? Commented Jan 27, 2015 at 10:52
• My MergeSort implementation is NOT stable. Thanks for pointing that out. Commented Jan 27, 2015 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];. Commented Jan 28, 2015 at 5:17
• Have you tried Comparable<T>[] aux = new Comparable[a.length];? Commented Jan 28, 2015 at 5:49