14
\$\begingroup\$

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

<NAME>:_<CHOICES>_<BLANKS>_<SORTED>_<UNIQUE>

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<BigInteger, String> life_saver = new MinPriorityQueue<BigInteger, String>(rules.length);

    // scan rules - "<NAME>:_<CHOICES>_<BLANKS>_<SORTED>_<UNIQUE>"
    // <names: choices blanks sorted unique>
    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!/(n-k)! 
        // n k T F C(n-1+k, n-1) // n k F F
        // pow(n,k)
        if ("T".equals(sorted) && "T".equals(unique)) {
            // C(n, n-k)
            possibilities = binomial(n, n - k);
        } else if ("T".equals(sorted) && "F".equals(unique)) {
            // C(n-1+k, n-1)
            possibilities = binomial(n - 1 + k, n - 1);
        } else if ("F".equals(sorted) && "T".equals(unique)) {
            // perm
            possibilities = permutation(n, k);
        } else { //if(sorted == "F" && unique == "F") {
            // pow(n,k)
            possibilities = power(n, k);
        }

        //double probability = BigInteger.valueOf(1).divide(possibilities).doubleValue();
        life_saver.insert(possibilities, rule_name);
    }

    int i = 0;
    while (life_saver.size() != 0) {
        out[i++] = life_saver.delMin();
    }

    return out;
}

// "<NAME>:_<CHOICES>_<BLANKS>_<SORTED>_<UNIQUE>"
private String[] rule_parser(String rule) {
    String[] tokens = rule.split("\\:");
    String[] phase2 = tokens[1].split("\\ ");
    // algo for inplace merging of two arrays
    String[] out = new String[5];
    out[0] = tokens[0];
    // phase2[0] is empty string
    out[1] = phase2[1];
    out[2] = phase2[2];
    out[3] = phase2[3];
    out[4] = phase2[4];
    return out;
}

BigInteger one = BigInteger.valueOf(1);

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

private BigInteger power(int n, int k) {
    return power(BigInteger.valueOf(n), k);
}

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

// n choices:range::[10,100]
// k blanks:range::[1,8]
BigDecimal d1 = BigDecimal.valueOf(1);
BigDecimal d0 = BigDecimal.valueOf(0);

private BigInteger binomial(int n, int k) {
    if (k > n - k) {
        k = (n - k);
    }
    return binomial_iter(BigDecimal.valueOf(n), k, d0, d1).toBigInteger();
}

// tail-recursive iteration code
private BigDecimal binomial_iter(BigDecimal n, int k, BigDecimal i, BigDecimal prev) {
    if (i.intValue() >= k) {
        return prev;
    }
    prev = prev.multiply(n.subtract(i).divide(i.add(d1), 8, RoundingMode.HALF_UP));
    return binomial_iter(n, k, i.add(d1), prev);
}

// Value is the abstract data-type for the information one is wanting to be associated along with 
//   node in the priority queue
private class MinPriorityQueue<Key extends Comparable, Value extends Comparable> {

    private final int capacity;

    // size = elements in priority queue
    private int N = 0;

    // Our Heap - actually array based - complete binary min-heap
    private final Node<Key, Value>[] heap;

    private Node<Key, Value> node; // node in a priority queue

    private class Node<Key, Value> { //<Value> {

        Key probability;
        Value value; // We want value to be rule-name for now 
        //  but could be something else

        private Node() {
            super();
        }

        private Node(Key probability, Value value) {
            this.probability = probability;
            this.value = value;
        }

    }

    // Dynamic array resizing
    // in my case, I know the size of elements beforehand
    // multiway heaps
    // immutability of keys
    private MinPriorityQueue(int capacity) {
        this.capacity = capacity;
        // 1 -based index (0 would not be used)
        this.heap = new Node[capacity + 1]; //(Node<Value>[]) new Object[capacity]; //(Node<Value>[]) new ArrayList<Node>().toArray(new Object[capacity]); //(Node[]) new Object[capacity];
    }

    // operations I need:
    // insertion        
    // delMin
    void insert(Key probability, Value rule) {
        // create node
        Node<Key, Value> newNode = new Node<Key, Value>(probability, rule);

        // heap insertion logic
        // swim - get to its destiny
        this.heap[++N] = newNode;

        swim(N);

    }

    private void swim(int k) {
        while (k > 1 && greater(k / 2, k)) {
            exchange(k / 2, k);
            k = k / 2;
        }
    }

    private void exchange(int a, int b) {
        Node<Key, Value> temp = this.heap[a];
        this.heap[a] = this.heap[b];
        this.heap[b] = temp;
    }

    private boolean alphabeticGreater(Value a, Value b) {
        return a.compareTo(b) > 0;
    }

    private boolean greater(int a, int b) {
        if(this.heap[a].probability.compareTo(this.heap[b].probability) > 0) {
            return true;
        } else if (this.heap[a].probability.compareTo(this.heap[b].probability) == 0) {
            if(alphabeticGreater(this.heap[a].value, this.heap[b].value)) {
                return true;
            } else {
                return false;
            }
        }
        return false;
    }

    Value delMin() {
        if (N == 0) {
            return null;
        }
        // exchange with last
        // declare the last as not part of heap any more
        // sink the root and lets destiny find its way
        Node<Key, Value> node = this.heap[1];
        exchange(N--, 1);
        sink(1);
        heap[N + 1] = null;
        return node.value;
    }

    private void sink(int k) {
        while (2 * k <= N) {
            int j = 2 * k;
            int smaller = (j < N && greater(j, j + 1)) ? j + 1 : j;
            if (!greater(k, smaller)) {
                break;
            }

            exchange(k, smaller);
            k = smaller;
        }
    }

    int size() {
        return N;
    }
}
}
\$\endgroup\$
11
\$\begingroup\$

Priority queue

There are warnings of unchecked calls, mostly since you declared MinPriorityQueue<Key extends Comparable, Value extends Comparable>. Comparable to what? That should be MinPriorityQueue<Key extends Comparable<? super Key>, Value extends Comparable<? super Value>>.

One more warning happens at the array creation in MinPriorityQueue(), due to type erasure, for which you should @SuppressWarnings("unchecked").

Calling your instance of the priority queue life_saver is weird.

The priority queue implementation takes up about half of the length of your solution. But I don't think that it is necessary at all. You aren't constantly adding and removing items, so a one-time call to Arrays.sort() should do the trick!

So, what kind of objects do you want to sort? How about defining a Lottery object?

Splitting the work between sortByOdds() and rule_parser() is awkward, as it results in so much array-packing and -unpacking that nullifies any advantage of such a split. Instead, I would use a regular expression, which keeps the code short enough that the parsing code can be written directly in sortByOdds().

import java.math.BigInteger;
import java.util.Arrays;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Lottery implements Comparable<Lottery> {
    private final String name;
    private final BigInteger possibilities;

    public Lottery(String name, int choices, int blanks, boolean sorted, boolean unique) {
        this.name = name;
        this.possibilities =
            ( sorted &&  unique) ? binomial(choices, choices - blanks) :
            ( sorted && !unique) ? binomial(choices - 1 + blanks, choices - 1) :
            (!sorted &&  unique) ? permutation(choices, blanks) :
          /* !sorted && !unique */ power(choices, blanks);
    }

    public String getName() {
        return this.name;
    }

    public BigInteger getPossibilities() {
        return this.possibilities;
    }

    @Override
    public int compareTo(Lottery other) {
        int cmp = this.getPossibilities().compareTo(other.getPossibilities());
        return (cmp != 0) ? cmp : this.getName().compareTo(other.getName());
    }

    /* This meaningless constructor only exists to allow non-static calls to sortByOdds() */
    public Lottery() {
        this(null, 0, 0, false, false);
    }

    private static final Pattern SPEC_PATTERN = Pattern.compile("(.*): (\\d+) (\\d+) ([TF]) ([TF])");

    /* I think this should be static. Don't know if TopCoder accepts that. */
    public String[] sortByOdds(String[] rules) {
        Lottery[] lotteries = new Lottery[rules.length];
        for (int i = 0; i < rules.length; i++) {
            // "<NAME>:_<CHOICES>_<BLANKS>_<SORTED>_<UNIQUE>"
            Matcher match = SPEC_PATTERN.matcher(rules[i]);
            if (!match.matches()) throw new IllegalArgumentException(rules[i]);
            lotteries[i] = new Lottery(match.group(1),
                                       Integer.parseInt(match.group(2)),
                                       Integer.parseInt(match.group(3)),
                                       "T".equals(match.group(4)),
                                       "T".equals(match.group(5)));
        }

        Arrays.sort(lotteries);
        String[] names = new String[lotteries.length];
        for (int i = 0; i < lotteries.length; i++) {
            names[i] = lotteries[i].getName();
        }
        return names;
    }

    /* Private static methods (discussed below) */
}

Calculations

All of the arithmetic helper functions should be declared static to indicate that they are pure functions of their parameters.


permutation() has too many special cases. If you write the loop properly, you should need none.

BigInteger.valueOf(n).subtract(BigInteger.valueOf(i)) is too verbose. Since n and i are just small integers, regular arithmetic will do.

private static BigInteger permutation(int n, int k) {
    BigInteger result = BigInteger.ONE;
    for (k = n - k; n > k; n--) {
        result = result.multiply(BigInteger.valueOf(n));
    }
    return result;
}

power() should not attempt to handle negative values of k, as such results will certainly not be representable as integers. Also, you can eliminate k == 1 as a special case.

private static BigInteger power(int n, int k) {
    return power(BigInteger.valueOf(n), k);
}

private static BigInteger power(BigInteger n, int k) {
    if (k < 0) {
        throw new IllegalArgumentException("Negative exponent: power(" + n + ", " + k + ")");
    }
    return (k == 0)     ? BigInteger.ONE :
           (k % 2 == 0) ? power(n.multiply(n), k / 2) :
                          n.multiply(power(n.multiply(n), (k - 1) / 2));
}

I don't see any reason why binomial() should be implemented using recursion. Tail-call optimization isn't done in Java, as your comment would suggest. I also don't understand the foray into BigDecimal, as all results should be integers. Particularly perplexing is why i needs to be a BigDecimal — it's just a counter with "small" integer values.

// n choices:range::[10,100]
// k blanks:range::[1,8]
private static BigInteger binomial(int n, int k) {
    if (k > n - k) {
        k = n - k;
    }
    BigInteger result = BigInteger.ONE;
    for (int i = 0; i < k; i++) {
        result = result.multiply(BigInteger.valueOf(n - i)).divide(BigInteger.valueOf(i + 1));
    }
    return result;
}

With all of these changes, the total code length should be cut in half or better.

\$\endgroup\$
  • 2
    \$\begingroup\$ I didn't know so many things here. Thanks for eye opening. Efforts much appreciated. \$\endgroup\$ – Prakhar Nov 26 '14 at 10:47
  • \$\begingroup\$ For priority-queue versus Arrays.sort, I assume priority queue could be lesser in complexity, not sure about size of lottery rules I would receive. Sorting hope should take O(NlgN) and for N elements O(lgN) as maintaining priority queue, so take O(NlgN), so approximately same. PS: swapping in priority queue could not be more cache friendly so sorting might make sense. \$\endgroup\$ – Prakhar Nov 26 '14 at 10:52
  • \$\begingroup\$ I'm not sure about binomial being not tail-recursive, since last call is final and no need to keep the older stack state(s). Notice I'm not relying on Java to optimize this for tail-recursion, I assume the stack-depth would be 1 only, at any time. Am I not true in my assumption? \$\endgroup\$ – Prakhar Nov 26 '14 at 11:00
  • 3
    \$\begingroup\$ Tail call optimization is theoretically possible, but the JVM won't do it. \$\endgroup\$ – 200_success Nov 26 '14 at 11:04
  • \$\begingroup\$ All right, small doubt - even the tail-recursive code would have stack-depth >1 in Java (because of the JVM, which not being supporting tail recursion)? \$\endgroup\$ – Prakhar Nov 26 '14 at 11:13
12
\$\begingroup\$

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);
    }
}
\$\endgroup\$
  • \$\begingroup\$ All comments are very much appreciated, not sure about 'dead code' yet, however love Boolean sorted = "T".equals(tokens[3]); and lateral changes suggested. Thanks. \$\endgroup\$ – Prakhar Nov 26 '14 at 6:54
  • \$\begingroup\$ Dead code: ` } else { //if(sorted == "F" && unique == "F") {` \$\endgroup\$ – Heslacher Nov 26 '14 at 6:55
  • \$\begingroup\$ Ok, got it. I wanted to make "+1" but my reputation is not allowing me. \$\endgroup\$ – Prakhar Nov 26 '14 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.