# Finding Lottery odds – Topcoder #268

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);
noOfBlanks = Integer.valueOf(conditions);
if (conditions.length() != 1 || conditions.length() != 1) {
throw new InvalidAttributesException(
"Conditions Sorted and Unique should be of length 1");
}

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

if (String.valueOf(conditions).equalsIgnoreCase("T")) {
isUnique = true;
} else if (String.valueOf(conditions).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 `BigInteger`s 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);
}
}
``````