Skip to content

Instantly share code, notes, and snippets.

@ioseb
Created February 23, 2009 16:41
Show Gist options
  • Save ioseb/69041 to your computer and use it in GitHub Desktop.
Save ioseb/69041 to your computer and use it in GitHub Desktop.
package ge.code.topcoder;
import java.util.Arrays;
import java.util.Comparator;
public class Lottery {
private static final Comparator<Rule> RULE_COMPARATOR = new Comparator<Rule>() {
public int compare(Rule o1, Rule o2) {
int result = 1;
if (o1.tickets == o2.tickets) {
result = o1.name.compareTo(o2.name);
} else {
result = Double.valueOf(o1.tickets).compareTo(o2.tickets);
}
return result;
}
};
private class Rule {
String name;
int choices;
int blanks;
boolean sorted;
boolean unique;
double tickets;
Rule(String rule) {
String[] tokens = rule.split(": ");
name = tokens[0];
tokens = tokens[1].split(" ");
choices = Integer.parseInt(tokens[0]);
blanks = Integer.parseInt(tokens[1]);
sorted = tokens[2].equals("T");
unique = tokens[3].equals("T");
if (sorted) {
if (unique) {
tickets = combinations(choices, blanks);;
} else {
tickets = multiset(choices, blanks);
}
} else {
if (unique) {
tickets = permutations(choices, blanks);
} else {
tickets = Math.pow(choices, blanks);
}
}
}
private double combinations(int m, int n) {
double numerator = 1, denominator = 1;
for (int i = 1; i <= n; i++) {
numerator *= m - n + i;
denominator *= i;
}
return numerator / denominator;
}
private double permutations(int m, int n) {
double result = 1;
for (int i = 1; i<= n; i++) {
result *= m - n + i;
}
return result;
}
private double multiset(int m, int n) {
double numerator = 1, denominator = 1;
for (int i = 1; i <= n; i++) {
numerator *= m - 1 + i;
denominator *= i;
}
return numerator / denominator;
}
}
public String[] sortByOdds(String[] rules) {
Rule[] rulez = new Rule[rules.length];
for (int i = 0; i < rules.length; i++) {
rulez[i] = new Rule(rules[i]);
}
Arrays.sort(rulez, RULE_COMPARATOR);
String[] sorted = new String[rulez.length];
for (int i = 0; i < rulez.length; i++) {
sorted[i] = rulez[i].name;
}
return sorted;
}
public static void main(String[] args) {
Lottery l = new Lottery();
String[] result = l.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"
}
);
for (int i = 0; i < result.length; i++) {
System.out.println(result[i]);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment