Menu
Topics Index
...
`

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 + "]";
    }
}

Review Comments

© meritcampus 2019

All Rights Reserved.

Open In App