Facebook Hacker Cup 2013, Round 1, Problem 1. Exercise from http://programmingpraxis.com/2013/02/15/facebook-hacker-cup-2013-round-1-problem-1

CardGame.java

package cardgame;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

/**
 * This class solves the card game problem from Facebook Hacker Cup 2013 round
 * 1. http://programmingpraxis.com/2013/02/15/facebook-hacker-cup-2013-round-1-
 * problem-1/
 * 
 */
public class CardGame {

    private static final int MOD_FACTOR = 1000000007;
    private int[][] decks;
    private int[] handSizes;

    /**
     * Main method. Expects one command-line argument: the name of the input
     * file.
     * @param args
     */
    public static void main(String[] args) {
        if (args.length > 0) {
            try {
                CardGame cg = new CardGame();
                cg.parseFile(args[0]);
                int[] strengths = cg.totalHandStrengths();
                for (int i = 0; i < strengths.length; i++) {
                    System.out
                            .println("Case #" + (i + 1) + ": " + strengths[i]);
                }
            } catch (FileNotFoundException e) {
                System.out.println("File not found");
            }
        } else {
            System.out.println("Supply file name as argument");
        }

    }

    /**
     * This method parses the input file. The input's format is described in the
     * problem statement.
     * 
     * @param fileName
     *            name of input file
     * @throws FileNotFoundException
     */
    public void parseFile(String fileName) throws FileNotFoundException {
        Scanner sc;
        sc = new Scanner(new File(fileName));
        int t = sc.nextInt();
        decks = new int[t][];
        handSizes = new int[t];
        for (int i = 0; i < t; i++) {
            int n = sc.nextInt();
            handSizes[i] = sc.nextInt();
            decks[i] = new int[n];
            for (int j = 0; j < n; j++) {
                decks[i][j] = sc.nextInt();
            }
        }
    }

    /**
     * This method computes the total strength of all hands for each (hand, hand
     * size) pair in the input file.
     */
    public int[] totalHandStrengths() {
        int[] strengths = new int[decks.length];
        for (int i = 0; i < decks.length; i++) {
            Arrays.sort(decks[i]);
            strengths[i] = handStrengths(decks[i], handSizes[i],
                    decks[i].length);
        }
        return strengths;
    }

    /**
     * This method computes the total hand strength for the first n cards in
     * deck, where hands have size k.
     * 
     * @param deck
     *            The deck of cards. This is assumed to be sorted.
     * @param k
     *            The size of a hand of cards.
     * @param n
     *            The number of cards in the deck.
     * @return Integer representing sum of scores of hands in deck.
     */
    private int handStrengths(int[] deck, int k, int n) {
        if (k == n) {
            return deck[n - 1];
        }
        // Make as many k-tuples you can that include the maximum card
        // Then, remove maximum and recurse.
        return (deck[n - 1] * choose(n - 1, k - 1) + handStrengths(deck, k,
                n - 1)) % MOD_FACTOR;
    }

    /**
     * This method computes n choose k. (How many subsets of size k there are in
     * a set of size n)
     */
    private int choose(int n, int k) {
        int answer = 1;
        for (int i = n - k + 1; i <= n; i++) {
            answer = answer * i;
        }
        for (int i = 1; i <= k; i++) {
            answer /= i;
        }
        return answer;
    }
}