TopCoder problem "Lottery" - SRM 144 (Division I Level Two)

The problem statement

Summary:

The rules of a lottery are defined by two integers (choices and blanks) and two boolean variables (sorted and unique). choices represents the highest valid number that you may use on your lottery ticket, blanks represents the number of spots on your ticket where numbers can be written. Each element of rules will be in the format

:____

Given a list of lotteries and their corresponding rules, return a list of lottery names sorted by how easy they are to win.

My accepted working code is as follows. How can I make this more simple and efficient?

```
//package topcoder.srm.srm1_div1;

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.ArrayList;

public class Lottery {
public String[] sortByOdds(String[] rules) {
String out[] = new String[rules.length];
// To focus: binomial, multiplication, not factorial (since costly even
// using tail recursion not required), power
// calculate probability for each rule and arrange in a priority queue
// To focus: building priority queue and associating the priority queue element with the rules
// from priority queue - arrange the output
// To focus: iterator for priority queue
MinPriorityQueue life_saver = new MinPriorityQueue(rules.length);

// scan rules - ":____"
//
for (String rule : rules) {
String[] tokens = rule_parser(rule);
// token[0] = name, token[1] = choices(n), token[2] = blanks(k)
// token[3] = sorted, token[4] = unique
String rule_name = tokens[0];
int n = Integer.parseInt(tokens[1], 10);
int k = Integer.parseInt(tokens[2], 10);
String sorted = tokens[3];
String unique = tokens[4];

BigInteger possibilities;
// choices blanks sorted unique result // n choices:range::[10,100] // k
// blanks:range::[1,8]
// n k T T C(n, n-k)
// n k F T
// n.(n-1).....(n-k+1) or n!/(

Style

• Dead code should be removed.

Naming

• single letter variables should be avoided if they are not temporary.

• variable names should be named using camelCase casing

• names should be meaningful to support the readability of the code.

Comments

• Comments should be used to describe why something is done not what is done. **What is done should be described by the code itself.

General

Use built in finals rather than creating own. Also this should be at least final.

BigInteger one = BigInteger.valueOf(1);  
BigDecimal d1 = BigDecimal.valueOf(1);  
BigDecimal d0 = BigDecimal.valueOf(0);

should be replaced by

BigInteger.ONE 
BigDecimal.ONE  
BigDecimal.ZERO

Refactoring

This

int n = Integer.parseInt(tokens[1], 10);  
int k = Integer.parseInt(tokens[2], 10);

should be renamed to

int choices = Integer.parseInt(tokens[1], 10);
int blanks = Integer.parseInt(tokens[2], 10);

This

String sorted = tokens[3];  
String unique = tokens[4];

should be changed to

Boolean sorted = "T".equals(tokens[3]);
Boolean unique = "T".equals(tokens[4]);

and the if..elseif to

if (sorted && unique) {
    possibilities = binomial(choices, choices - blanks);
} else if (sorted && !unique) {
    possibilities = binomial(choices - 1 + blanks, choices - 1);
} else if (!sorted && unique) {
    possibilities = permutation(choices, blanks);
} else { 
    possibilities = power(choices, blanks);
}

This

private BigInteger permutation(int n, int k) {
    if (k == 0) {
        return one;
    }
    if (k == 1) {
        return BigInteger.valueOf(n);
    }

    int i = 1;
    BigInteger result = BigInteger.valueOf(n);
    while (i < k) {
        result = result.multiply(BigInteger.valueOf(n).subtract(BigInteger.valueOf(i)));
        i++;
    }

    return result;
}

can be made better by assigning the BigInteger.valueOf(n) to a local variable and giving the input parameter meaningful names.

private BigInteger permutation(int choices, int blanks) {
    if (blanks == 0) {
        return BigInteger.ONE;
    }

    BigInteger choice = BigInteger.valueOf(choices)

    if (blanks == 1) {
        return choice;
    }

    int i = 1;
    BigInteger result = choice;
    while (i < blanks) {
        result = result.multiply(choice.subtract(BigInteger.valueOf(i)));
        i++;
    }

    return result;
}

Here

private BigInteger power(BigInteger n, int k) {
    if (k == 0) {
        return one;
    }
    if (k == 1) {
        return n;
    }
    // FIXME: fix the code below - add precision or else ready for exceptions
    if (k < 0) {
        return one.divide(power(n, k));
    }
    if (k % 2 == 1) {
        return n.multiply(power(n.multiply(n), (k - 1) / 2));
    } else {
        return power(n.multiply(n), k / 2);
    }
}

the same as for the permutation() method applies

private BigInteger power(BigInteger choice, int blanks) {
    if (blanks == 0) {
        return BigInteger.ONE;
    }
    if (blanks == 1) {
        return choice;
    }

    if (blanks < 0) {
        return BigInteger.ONE.divide(power(choice, blanks));
    }
    if (blanks % 2 == 1) {
        return choice.multiply(power(choice.multiply(choice), (blanks - 1) / 2));
    } else {
        return power(choice.multiply(choice), blanks / 2);
    }
}

StackExchange Code Review Q#70889, answer score: 12