Text3x3.java

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Comparator;

import org.junit.Assert;
import org.junit.Test;

public class Test3x3 {
    /**
     * The required functionality for a solver - must take a test case as a 3x3
     * matrix, and return the total as an integer.
     *
     * @author lackofcheese
     */
    public interface Solver {
        public int solve(int[][] m);
    }

    /**
     * Uses the special fast 3x3 algorithm to solve a test case.
     */
    public static Solver special = new Solver() {
        @Override
        public int solve(int[][] m) {
            // Get sorted indices.
            int[] vals = new int[9];
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    vals[3 * i + j] = m[i][j];
                }
            }
            Integer[] inds = indirectSort(vals);
            int score = 0;

            // Calculate overall total
            for (int i = 0; i < 9; i++) {
                score += vals[i];
            }
            score -= vals[inds[0]] + vals[inds[1]];

            // If the three picked values are in a single row or column...
            if ((inds[0] % 3 == inds[1] % 3 && inds[1] % 3 == inds[2] % 3)
                    || (inds[0] / 3 == inds[1] / 3 && inds[1] / 3 == inds[2] / 3)) {
                score -= vals[inds[3]];
            } else {
                score -= vals[inds[2]];
            }
            return score;
        }
    };

    /**
     * Uses the general algorithm to solve the test case.
     */
    public static Solver general = new Solver() {
        @Override
        public int solve(int[][] m) {
            return Creamsteak.creamsteak(m);
        }
    };

    /**
     * An indirect sorting algorithm. Returns the indices of the elements from
     * the one with the lowest value to the one with the highest.
     *
     * @param data the array of integer values.
     * @return an array of Integer indices into the data array.
     */
    public static Integer[] indirectSort(final int[] data) {
        Integer[] inds = new Integer[data.length];
        for (int i = 0; i < inds.length; i++) {
            inds[i] = i;
        }
        Arrays.sort(inds, new Comparator<Integer>() {
            @Override
            public int compare(final Integer o1, final Integer o2) {
                return data[o1] - data[o2];
            }
        });
        return inds;
    }

    /**
     * Checks all 9^9 possible configurations.
     */
    @Test
    public void testAll() {
        checkSameResults(0);
    }

    /**
     * Checks one million of the 9^9 possible configurations.
     */
    @Test
    public void test1M() {
        checkSameResults(1000000);
    }

    /**
     * Checks the general algorithm against the 3x3 special-case algorithm to
     * ensure they get the same results.
     *
     * @param numTests
     *            The number of cases to take out of the 9^9 possibilities.
     */
    public static void checkSameResults(int numTests) {
        long startTime = System.currentTimeMillis();
        checkSolvers(numTests, general, special);
        System.out.println(String.format("Time taken: %.2fs",
                (System.currentTimeMillis() - startTime) / 1000.0));
    }

    @Test
    /**
     * Checks the total value for a single solver.
     */
    public void checkTotal() {
        long startTime = System.currentTimeMillis();
        BigInteger total = checkSolvers(1000000, general, null);
        // Assert.assertEquals("Wrong total!", total, new BigInteger("2558136"));
        System.out.println(String.format("Time taken: %.2fs",
                (System.currentTimeMillis() - startTime) / 1000.0));
    }

    /**
     * Checks to make sure that two solvers get the same result for the given
     * number of test cases.
     *
     * @param numTests
     *            the number of test cases to run.
     * @param solver1
     *            the first solver.
     * @param solver2
     *            the second solver.
     * @return the overall total of the results for all of the test cases.
     */
    public static BigInteger checkSolvers(int numTests, Solver solver1,
            Solver solver2) {
        // Array to hold the values in.
        int[][] m = new int[3][3];

        // Initialise our total and problem number.
        BigInteger prob = BigInteger.ZERO;
        BigInteger total = BigInteger.ZERO;

        // Loop through each of the 9^9 possible combinations.
        outerloop:
        for (m[0][0] = 1; m[0][0] <= 9; m[0][0]++)
        for (m[0][1] = 1; m[0][1] <= 9; m[0][1]++)
        for (m[0][2] = 1; m[0][2] <= 9; m[0][2]++)
        for (m[1][0] = 1; m[1][0] <= 9; m[1][0]++)
        for (m[1][1] = 1; m[1][1] <= 9; m[1][1]++)
        for (m[1][2] = 1; m[1][2] <= 9; m[1][2]++)
        for (m[2][0] = 1; m[2][0] <= 9; m[2][0]++)
        for (m[2][1] = 1; m[2][1] <= 9; m[2][1]++)
        for (m[2][2] = 1; m[2][2] <= 9; m[2][2]++) {
            int score1 = solver1.solve(m);
            if (solver2 != null) {
                int score2 = solver2.solve(m);
                Assert.assertEquals(
                        "Different totals for matrix "
                                + Arrays.deepToString(m),
                                score1, score2);
            }
            total = total.add(new BigInteger(
                    Integer.toString(score1)));
            prob = prob.add(BigInteger.ONE);

            if (prob.equals(new BigInteger(
                    Integer.toString(numTests)))) {
                break outerloop;
            }
        }
        System.out.println("BigBoss = " + total.toString());
        System.out.println("BigCount = " + prob.toString());
        return total;
    }
}