Creamsteak.java

import java.util.LinkedList;

/**
 * Implements my algorithm for solving the Creamsteak problem, for generic nxn
 * matrices.
 *
 * @author lackofcheese
 */
public class Creamsteak {
    /**
     * Represents a single row or column that needs to be processed when moving
     * a mark.
     *
     * @author lackofcheese
     */
    private static class Task {
        private boolean isRow;
        private int i;
        private int j;

        private Task(boolean isRow, int i, int j) {
            this.isRow = isRow;
            this.i = i;
            this.j = j;
        }
    }

    /**
     * Does the initial markup of largest elements in the columns and rows of a
     * matrix.
     *
     * @param m
     *            the matrix being solved.
     * @param marks
     *            The array of marks - should consist entirely of zeros
     *            initially.
     * @return An array containing the positions (as int[2]) of the elements.
     */
    private static int[][] init_marks(int[][] m, int[][] marks) {
        int n = m.length;
        int[][] collis = new int[n][2];
        int nc = 0;

        // Mark the largest element in each row
        for (int i = 0; i < n; i++) {
            int maxVal = m[i][0];
            int maxPos = 0;
            for (int j = 1; j < n; j++) {
                if (m[i][j] > maxVal) {
                    maxVal = m[i][j];
                    maxPos = j;
                }
            }
            marks[i][maxPos]++;
        }

        // Mark the largest element in each column, taking note of
        // any double-marking.
        for (int j = 0; j < n; j++) {
            int maxVal = m[0][j];
            int maxPos = 0;
            for (int i = 1; i < n; i++) {
                if (m[i][j] > maxVal) {
                    maxVal = m[i][j];
                    maxPos = i;
                }
            }
            marks[maxPos][j]++;
            if (marks[maxPos][j] > 1) {
                collis[nc][0] = maxPos;
                collis[nc][1] = j;
                nc++;
            }
        }

        // Create a new collision array with size equal to the number
        // of collisions.
        int[][] collis2 = new int[nc][2];
        for (int i = 0; i < nc; i++) {
            collis2[i][0] = collis[i][0];
            collis2[i][1] = collis[i][1];
        }
        return collis2;
    }

    /**
     * Moves a mark from a double-marked position (i0, j0) to the next best
     * available place in the matrix m.
     *
     * @param m
     *            the matrix being solved.
     * @param marks
     *            the markup array for the matrix.
     * @param i0
     *            the row of the double-marked position.
     * @param j0
     *            the column of the double-marked position.
     */
    public static void move_mark(int[][] m, int[][] marks, int i0, int j0) {
        int n = m.length;
        // An array that tells us which elements have already been
        // processed.
        boolean[][] done = new boolean[n][n];
        done[i0][j0] = true;

        // A queue that tells us which rows/columns still need to be
        // processed.
        LinkedList<Task> todo = new LinkedList<Task>();
        todo.push(new Task(true, i0, j0));
        todo.push(new Task(false, i0, j0));

        boolean hasMax = false;

        // The maximum value found so far, and its position.
        int maxVal = 0;
        int maxI = 0;
        int maxJ = 0;

        // Process the queue until we are done.
        while (!todo.isEmpty()) {
            Task t = todo.pop();
            boolean isRow = t.isRow;
            int i = t.i;
            int j = t.j;
            // Loop through every element in the same row/column as (i,j)
            for (int k = 0; k < n; k++) {
                int i1 = i;
                int j1 = j;
                if (isRow) {
                    j1 = k;
                } else {
                    i1 = k;
                }
                // (i1,j1) is the new value we are looking at.
                if ((i1 == i && j1 == j) || done[i1][j1]) {
                    continue;
                }
                done[i1][j1] = true; // Ensure this value is not processed again
                // later.
                if (marks[i1][j1] > 0) {
                    // If it's marked, we also need to process everything in the
                    // same
                    // column, if we're currently looking at a row, or the same
                    // row
                    // if we're currently looking at a column.
                    todo.add(new Task(!isRow, i1, j1));
                } else {
                    // Update our maximum if necessary.
                    int newVal = m[i1][j1];
                    if (!hasMax || newVal > maxVal) {
                        hasMax = true;
                        maxVal = newVal;
                        maxI = i1;
                        maxJ = j1;
                    }
                }
            }
        }
        // Move the mark.
        marks[i0][j0]--;
        marks[maxI][maxJ]++;
    }

    /**
     * Runs my algorithm for the creamsteak problem on the given matrix.
     *
     * @param m
     *            A matrix; should be nxn with n > 1.
     * @return The highest possible total meeting the Creamsteak criteria.
     */
    public static int creamsteak(int[][] m) {
        int n = m.length;
        for (int i = 0; i < n; i++) {
            if (m[i].length != n) {
                throw new RuntimeException("Not square!");
            }
        }
        if (n == 1) {
            throw new RuntimeException("No solution for 1x1 case");
        }

        // Mark maximums in the rows and columns, noting collisions.
        int[][] marks = new int[n][n];
        int[][] collis = init_marks(m, marks);

        // For each collision, move the mark to the best available place.
        for (int i = 0; i < collis.length; i++) {
            move_mark(m, marks, collis[i][0], collis[i][1]);
        }

        // Calculate the total of the marked elements, and return it.
        int total = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (marks[i][j] == 0) {
                } else if (marks[i][j] == 1) {
                    total += m[i][j];
                } else {
                    throw new RuntimeException("I AM ERROR!");
                }
            }
        }
        return total;
    }
}