HuntingtonHill.java

Below is the syntax highlighted version of HuntingtonHill.java.

/*******************************************************************************
 *  Name:    Kevin Wayne
 *  Login:   wayne
 *  Precept: P00
 *
 *  Compilation:  javac HuntingtonHill.java
 *  Execution:    java HuntingtonHill H < input.txt
 *  Dependencies: StdIn.java StdOut.java
 *
 *  Reads an integer H from the command line, an integer N and N pairs of
 *  names and populations from standard input; writes the Huntington-Hill
 *  apportionment to standard output.
 *
 ******************************************************************************/


public class HuntingtonHill {

    public static double priority(int population, int seat) {
        return population / Math.sqrt(1.0*seat * (seat+1));
    }

    public static int next(int[] populations, int[] seats) {
        int max = 0;
        for (int i = 0; i < populations.length; i++) {
            if (priority(populations[i], seats[i]) > priority(populations[max], seats[max]))
                max = i;
        }
        return max;
    }

    public static void main(String[] args) {
        int H = Integer.parseInt(args[0]);

        // read in populations of each state
        int N = StdIn.readInt();
        String[] names = new String[N];
        int[] populations = new int[N];
        for (int i = 0; i < N; i++) {
            names[i] = StdIn.readString();
            populations[i] = StdIn.readInt();
        }

        // initialize 1 seat per state
        int[] seats = new int[N];
        for (int i = 0; i < N; i++)
            seats[i] = 1;

        // Huntington-Hill algorithm
        for (int i = 0; i < H - N; i++) {
            int max = next(populations, seats);
            seats[max]++;
        }        

        // print results
        for (int i = 0; i < N; i++) {
            StdOut.printf("%-16s %8d %5d\n", names[i], populations[i], seats[i]);
        }        
    }
}