/**
 * Originally taken as a timed coding test on Codility.com. This was one of two
 * problems that had to be solved in the space of 80 minutes. I completed the test
 * successfully, with correct answers for both exercises and plenty of time to spare
 *
 * Problem Definition:
 * There is a chess board of arbitrary number of rows and columns. On each square of the
 * board, a number of grains of rice have been placed. The arrangement of the squares, 
 * including how many grains of rice are in each, is provided via the input array.
 *
 * A pawn, starts at the top left corner of the board. It can move one square at a time,
 * but only left or down. 
 *
 * Write a program which returns the optimal path that the pawn must follow in order to collect
 * the maximum amount of grains of rice.
 */
class ChessPawnRiceSolution {
    public int solution(int[][] board) {
        int[] pawnLoc = {0,0};
        int totalGrains = 0;
        int totalRow = 0;
        int totalCol = 0;
        int boardWidth = board[0].length;
        int boardHeight = board.length;
 
        while((pawnLoc[1] < boardWidth) && ((pawnLoc[0]) < boardHeight)){ 
            totalRow = 0;
            totalCol = 0;
 
            // add grains in current square
            totalGrains += board[pawnLoc[0]][pawnLoc[1]];
 
            // count the total grains in pawns untravelled column
            for(int i = pawnLoc[0]; i < board.length; i++){
                totalCol += board[i][pawnLoc[1]];
            }
 
            // count the total grains in pawns untravelled row
            for(int i = pawnLoc[1]; i < board[0].length; i++){
                totalRow += board[pawnLoc[0]][i];
            }
 
            if(totalRow > totalCol){ // move horizontally
                pawnLoc[1] = pawnLoc[1] + 1;
            } else {                // move vertically
                pawnLoc[0] = pawnLoc[0] + 1;
            }
        }
 
        return totalGrains;
    }
}

LyoqCiAqIE9yaWdpbmFsbHkgdGFrZW4gYXMgYSB0aW1lZCBjb2RpbmcgdGVzdCBvbiBDb2RpbGl0eS5jb20uIFRoaXMgd2FzIG9uZSBvZiB0d28KICogcHJvYmxlbXMgdGhhdCBoYWQgdG8gYmUgc29sdmVkIGluIHRoZSBzcGFjZSBvZiA4MCBtaW51dGVzLiBJIGNvbXBsZXRlZCB0aGUgdGVzdAogKiBzdWNjZXNzZnVsbHksIHdpdGggY29ycmVjdCBhbnN3ZXJzIGZvciBib3RoIGV4ZXJjaXNlcyBhbmQgcGxlbnR5IG9mIHRpbWUgdG8gc3BhcmUKICoKICogUHJvYmxlbSBEZWZpbml0aW9uOgogKiBUaGVyZSBpcyBhIGNoZXNzIGJvYXJkIG9mIGFyYml0cmFyeSBudW1iZXIgb2Ygcm93cyBhbmQgY29sdW1ucy4gT24gZWFjaCBzcXVhcmUgb2YgdGhlCiAqIGJvYXJkLCBhIG51bWJlciBvZiBncmFpbnMgb2YgcmljZSBoYXZlIGJlZW4gcGxhY2VkLiBUaGUgYXJyYW5nZW1lbnQgb2YgdGhlIHNxdWFyZXMsIAogKiBpbmNsdWRpbmcgaG93IG1hbnkgZ3JhaW5zIG9mIHJpY2UgYXJlIGluIGVhY2gsIGlzIHByb3ZpZGVkIHZpYSB0aGUgaW5wdXQgYXJyYXkuCiAqCiAqIEEgcGF3biwgc3RhcnRzIGF0IHRoZSB0b3AgbGVmdCBjb3JuZXIgb2YgdGhlIGJvYXJkLiBJdCBjYW4gbW92ZSBvbmUgc3F1YXJlIGF0IGEgdGltZSwKICogYnV0IG9ubHkgbGVmdCBvciBkb3duLiAKICoKICogV3JpdGUgYSBwcm9ncmFtIHdoaWNoIHJldHVybnMgdGhlIG9wdGltYWwgcGF0aCB0aGF0IHRoZSBwYXduIG11c3QgZm9sbG93IGluIG9yZGVyIHRvIGNvbGxlY3QKICogdGhlIG1heGltdW0gYW1vdW50IG9mIGdyYWlucyBvZiByaWNlLgogKi8KY2xhc3MgQ2hlc3NQYXduUmljZVNvbHV0aW9uIHsKICAgIHB1YmxpYyBpbnQgc29sdXRpb24oaW50W11bXSBib2FyZCkgewogICAgICAgIGludFtdIHBhd25Mb2MgPSB7MCwwfTsKICAgICAgICBpbnQgdG90YWxHcmFpbnMgPSAwOwogICAgICAgIGludCB0b3RhbFJvdyA9IDA7CiAgICAgICAgaW50IHRvdGFsQ29sID0gMDsKICAgICAgICBpbnQgYm9hcmRXaWR0aCA9IGJvYXJkWzBdLmxlbmd0aDsKICAgICAgICBpbnQgYm9hcmRIZWlnaHQgPSBib2FyZC5sZW5ndGg7CiAgICAgICAgCiAgICAgICAgd2hpbGUoKHBhd25Mb2NbMV0gPCBib2FyZFdpZHRoKSAmJiAoKHBhd25Mb2NbMF0pIDwgYm9hcmRIZWlnaHQpKXsgCiAgICAgICAgICAgIHRvdGFsUm93ID0gMDsKICAgICAgICAgICAgdG90YWxDb2wgPSAwOwogICAgICAgICAgICAKICAgICAgICAgICAgLy8gYWRkIGdyYWlucyBpbiBjdXJyZW50IHNxdWFyZQogICAgICAgICAgICB0b3RhbEdyYWlucyArPSBib2FyZFtwYXduTG9jWzBdXVtwYXduTG9jWzFdXTsKICAgICAgICAgICAgCiAgICAgICAgICAgIC8vIGNvdW50IHRoZSB0b3RhbCBncmFpbnMgaW4gcGF3bnMgdW50cmF2ZWxsZWQgY29sdW1uCiAgICAgICAgICAgIGZvcihpbnQgaSA9IHBhd25Mb2NbMF07IGkgPCBib2FyZC5sZW5ndGg7IGkrKyl7CiAgICAgICAgICAgICAgICB0b3RhbENvbCArPSBib2FyZFtpXVtwYXduTG9jWzFdXTsKICAgICAgICAgICAgfQogICAgICAgICAgICAKICAgICAgICAgICAgLy8gY291bnQgdGhlIHRvdGFsIGdyYWlucyBpbiBwYXducyB1bnRyYXZlbGxlZCByb3cKICAgICAgICAgICAgZm9yKGludCBpID0gcGF3bkxvY1sxXTsgaSA8IGJvYXJkWzBdLmxlbmd0aDsgaSsrKXsKICAgICAgICAgICAgICAgIHRvdGFsUm93ICs9IGJvYXJkW3Bhd25Mb2NbMF1dW2ldOwogICAgICAgICAgICB9CiAgICAgICAgICAgIAogICAgICAgICAgICBpZih0b3RhbFJvdyA+IHRvdGFsQ29sKXsgLy8gbW92ZSBob3Jpem9udGFsbHkKICAgICAgICAgICAgICAgIHBhd25Mb2NbMV0gPSBwYXduTG9jWzFdICsgMTsKICAgICAgICAgICAgfSBlbHNlIHsgICAgICAgICAgICAgICAgLy8gbW92ZSB2ZXJ0aWNhbGx5CiAgICAgICAgICAgICAgICBwYXduTG9jWzBdID0gcGF3bkxvY1swXSArIDE7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgCiAgICAgICAgcmV0dXJuIHRvdGFsR3JhaW5zOwogICAgfQp9