info@meritcampus.com    +91-85006-22255
...
`

# Weekend Hack - 25 May 2013 - Results

Thanks to Pramod Jain for spending so much time, coming up with original and innovative answers and for submitting them. Thanks to many others who have tried to get the solution.
We have reviewed the solutions as per the criteria mentioned at Weekend Hack and included the comments below. Given the experience of the participants, they were really innovative and clean. Few minor comments found are included below in the order of the submission. These comments are not intended to point out the mistakes in the solutions but to learn from them.

The winner of the Weekend Hack 25 May 2013 - 1 is Pramod Jain. He will get a recharge or gift voucher worth Rs. 175.

# To find the best way to collect maximum amount from the money grid

Write a program to find the best way to collect maximum amount from the money grid. The start position and the end position are given. For every step taken, an amount of 15 will be deducted. There are bombs placed in the money grid and they are marked as -99. The way should not step on the bombs.

Input (int[][], Position, Position) Output (String)
{{-10, -99, -30}, {10, 30, -10}, {50, 0, 80}}, [1, 0], [2, 2] BestWayDetails [positions=[(1,0), (2,0), (2,1), (2,2)], amount=95]
{{5, 0, 13}, {35, -99, 50}}, [1, 0], [1, 2] BestWayDetails [positions=[(1,0), (0,0), (0,1), (0,2), (1,2)], amount=43]
{{0, 23, 33, 19, 11}, {-1, -99, 99, -1, 45}, {4, -13, 23, 0, 13}, {6, 12, -99, 1, 7}, {19, 17, 18, 3, 0}, {3, -11, 50, 2, 1}}, [0, 2], [5, 2] BestWayDetails [positions=[(0,2), (0,3), (0,4), (1,4), (1,3), (1,2), (2,2), (2,1), (3,1), (4,1), (4,2), (5,2)], amount=148]
{{25, 1, 0, 15}, {-1, 3, -99, 0}, {12, -1, -11, 2}}, [0, 0], [0, 3] BestWayDetails [positions=[(0,0), (0,1), (0,2), (0,3)], amount=-4]
{{-99, 2, 3, 4, -99, 8}, {0, 1, -99, 5, 6, 7}}, [1, 0], [0, 5] BestWayDetails [positions=[(1,0), (1,1), (0,1), (0,2), (0,3), (1,3), (1,4), (1,5), (0,5)], amount=-84]
{{-20, 16}, {21, -15}, {-22, 20}, {23, 10}, {24, 26}, {-25, 30}}, [0, 0], [5, 1] BestWayDetails [positions=[(0,0), (1,0), (1,1), (2,1), (3,1), (3,0), (4,0), (4,1), (5,1)], amount=-1]

## Solution 1 - Submitted on Sun May 26 01:10:37 2013

``` import java.util.List;class CollectMaximumAmount {    public static void main(String s[]) {        int[][] input = {{0, 80, 0}, {25, 50, 63}, {-99, -20, 10}};        System.out.println(getBestWay(input, new Position(0, 0), new Position(2, 2)));    }    public static BestWayDetails getBestWay(int[][] input, Position source, Position destination) {        BestWayDetails result = new BestWayDetails();        BestWayDetails tempResult = new BestWayDetails();        BestWayDetails bestResult = new BestWayDetails();        int[][] nodesSelected = new int[input.length][input[0].length];        nodesSelected[source.rowPosition][source.columnPosition] = 1; // source node is selected        result.amount = Integer.MIN_VALUE; //worst result possible in the integer limits        tempResult.amount = input[source.rowPosition][source.columnPosition]; //amount updated as source node is added        tempResult.positions.add(source); //adding source node to positions list        bestResult = getBestWay2(input, source, destination, nodesSelected, result, tempResult);        return bestResult;    }    public static BestWayDetails getBestWay2(int[][] input, Position source, Position destination, int[][] nodesSelected, BestWayDetails bestResult, BestWayDetails temporaryResult) {        if (source.columnPosition == destination.columnPosition && source.rowPosition == destination.rowPosition) {            return temporaryResult;        }        if (source.rowPosition - 1 >= 0 && input[source.rowPosition - 1][source.columnPosition] != -99 && nodesSelected[source.rowPosition - 1][source.columnPosition] == 0) {            //moving up if upper node is not visited and is not bomb            int[][] newNodesSelected = new int[input.length][input[0].length];            copyArray(nodesSelected, newNodesSelected); //copying nodesSelected array to newNodesSelected            newNodesSelected[source.rowPosition - 1][source.columnPosition] = 1; //making the upper node as visited             Position tempSource = new Position(source.rowPosition - 1, source.columnPosition); // position object created for upper node            BestWayDetails newTemporaryResult = new BestWayDetails();            copyBestWayDetails(temporaryResult, newTemporaryResult); //copying from temporaryResult to newTemporaryResult            newTemporaryResult.positions.add(tempSource); //adding the upper node object to positions list            newTemporaryResult.amount += input[tempSource.rowPosition][tempSource.columnPosition] - 15; //updating amount as upper node is added            BestWayDetails tempWay = getBestWay2(input, tempSource, destination, newNodesSelected, bestResult, newTemporaryResult); //calling function recursively with new parameters            if (bestResult.amount < tempWay.amount) { //if answer is better than the previous best answer then change the best answer                clearAndCopyBestWayDetails(bestResult, tempWay);            }        }        if (source.rowPosition + 1 < input.length && input[source.rowPosition + 1][source.columnPosition] != -99 && nodesSelected[source.rowPosition + 1][source.columnPosition] == 0) {            //moving down if lower node is not visited and is not bomb            int[][] newNodesSelected = new int[input.length][input[0].length];            copyArray(nodesSelected, newNodesSelected); //copying nodesSelected array to newNodesSelected            newNodesSelected[source.rowPosition + 1][source.columnPosition] = 1; //making the lower node as visited            Position tempSource = new Position(source.rowPosition + 1, source.columnPosition); // position object created for lower node            BestWayDetails newTemporaryResult = new BestWayDetails();            copyBestWayDetails(temporaryResult, newTemporaryResult); //copying from temporaryResult to newTemporaryResult            newTemporaryResult.positions.add(tempSource); //adding the lower node object to positions list            newTemporaryResult.amount += input[tempSource.rowPosition][tempSource.columnPosition] - 15; //updating amount as lower node is added            BestWayDetails tempWay = getBestWay2(input, tempSource, destination, newNodesSelected, bestResult, newTemporaryResult);            if (bestResult.amount < tempWay.amount) { //if answer is better than the previous best answer then change the best answer                clearAndCopyBestWayDetails(bestResult, tempWay);            }        }        if (source.columnPosition - 1 >= 0 && input[source.rowPosition][source.columnPosition - 1] != -99 && nodesSelected[source.rowPosition][source.columnPosition - 1] == 0) {            //moving left if left node is not visited and is not bomb            int[][] newNodesSelected = new int[input.length][input[0].length];            copyArray(nodesSelected, newNodesSelected); //copying nodesSelected array to newNodesSelected            newNodesSelected[source.rowPosition][source.columnPosition - 1] = 1; //making the left node as visited            Position tempSource = new Position(source.rowPosition, source.columnPosition - 1); // position object created for left node            BestWayDetails newTemporaryResult = new BestWayDetails();            copyBestWayDetails(temporaryResult, newTemporaryResult); //copying from temporaryResult to newTemporaryResult            newTemporaryResult.positions.add(tempSource); //adding the left node object to positions list            newTemporaryResult.amount += input[tempSource.rowPosition][tempSource.columnPosition] - 15; //updating amount as left node is added            BestWayDetails tempWay = getBestWay2(input, tempSource, destination, newNodesSelected, bestResult, newTemporaryResult);            if (bestResult.amount < tempWay.amount) { //if answer is better than the previous best answer then change the best answer                clearAndCopyBestWayDetails(bestResult, tempWay);            }        }        if (source.columnPosition + 1 < input[0].length && input[source.rowPosition][source.columnPosition + 1] != -99 && nodesSelected[source.rowPosition][source.columnPosition + 1] == 0) {            //moving right if right node is not visited and is not bomb            int[][] newNodesSelected = new int[input.length][input[0].length];            copyArray(nodesSelected, newNodesSelected); //copying nodesSelected array to newNodesSelected            newNodesSelected[source.rowPosition][source.columnPosition + 1] = 1; //making the right node as visited            Position tempSource = new Position(source.rowPosition, source.columnPosition + 1); // position object created for right node            BestWayDetails newTemporaryResult = new BestWayDetails();            copyBestWayDetails(temporaryResult, newTemporaryResult); //copying from temporaryResult to newTemporaryResult            newTemporaryResult.positions.add(tempSource); //adding the right node object to positions list            newTemporaryResult.amount += input[tempSource.rowPosition][tempSource.columnPosition] - 15; //updating amount as right node is added            BestWayDetails tempWay = getBestWay2(input, tempSource, destination, newNodesSelected, bestResult, newTemporaryResult);            if (bestResult.amount < tempWay.amount) { //if answer is better than the previous best answer then change the best answer                clearAndCopyBestWayDetails(bestResult, tempWay);            }        }        return bestResult;    }    public static void copyArray(int[][] original, int[][] duplicate) {        for (int i = 0; i < original.length; i++) {            for (int j = 0; j < original[0].length; j++) {                duplicate[i][j] = original[i][j];            }        }    }    public static void copyBestWayDetails(BestWayDetails original, BestWayDetails duplicate) {        duplicate.amount = original.amount;        duplicate.positions.addAll(original.positions);    }    public static void clearAndCopyBestWayDetails(BestWayDetails destination, BestWayDetails sourceForCopy) {        destination.amount = sourceForCopy.amount;        destination.positions.clear();        destination.positions.addAll(sourceForCopy.positions);    }}class Position {    int rowPosition;    int columnPosition;    public Position(int rowPosition, int columnPosition) {        this.rowPosition = rowPosition;        this.columnPosition = columnPosition;    }    @Override    public boolean equals(Object obj) {        return rowPosition == ((Position) obj).rowPosition && columnPosition == ((Position) obj).columnPosition;    }    @Override    public String toString() {        return "(" + rowPosition + "," + columnPosition + ")";    }}class BestWayDetails {    List positions = new ArrayList();    int amount;    @Override    public String toString() {        return "BestWayDetails [positions=" + positions + ", amount=" + amount + "]";    }} ```