2d array game that moves to adjacent spaces picking up coins

Question

So I've been working on this problem for the better part of today. Can someone help me figure out where I went wrong?

It’s greedy because it moves to the location with the highest number of coins; and it’s lazy because it will stop moving if no adjacent location increases its coin treasure. If several adjacent locations had the same highest number of coins, the gatherer will choose to move to the highest in a clockwise fashion. The gatherer empties the coins from any location it visits.

 public static int receiveCoins(int[][]map,int r,int c){

        int[] coins = {0,0,0,0}; 

        boolean moreCoins = true;
      int numOfCoins = 0;

        if(map[r][c] > 0){

                  numOfCoins += map[r][c];
                  map[r][c] = 0;                
        }  

        while(moreCoins == true){        

            if(c < (map.length-1)){

                if(map[r][c+1] > 0){

                    coins[1] = map[r][c+1];                
                }               
            }

            if(r < map[0].length-1){

                if(map[r+1][c] > 0){

                    coins[2] = map[r+1][c];

                }               
            }

               if(row > 0){
                if(map[r-1][c] > 0){

                    coins[0] = map[r-1][c];

                }
            }


            if(c > 0){

                if(map[r][c-1] > 0){

                    coins[3] = map[r][c-1];

                }               
            }           

            int maxCoin = 0;
            int nRow = 0;
            int nCol = 0;

            for(int i = 0; i < coins.length; i++){

                if(coins[i] > maxCoin){

                    maxCoin = coins[i];

                    if(i == 0){
                        nCol = c;
                        nRow = r - 1;

                    }else if(i == 1){
                        nRow = r;
                        nCol = c + 1;

                    }else if(i == 2){
                        nCol = c;
                        nRow = r + 1;

                    }else{
                        nRow = r;
                        nCol = c - 1;

                    }

                }   
                coins[i] = 0; 
            }           
                }               
            }

            if (maxCoin == 0){

                moreCoins = false;

            }else{                          

                r = nRow;
                c = nCol; 

                numOfCoins += map[r][c];
                map[r][c] = 0;


            }   
        }

        return numOfCoins;   
    }

jwalk · Accepted Answer

A few corrections to your algorithm:

Suggestion from user1509803
You should reset coins[] back to zero after checking them for the highest, so that in the next iteration you are not reusing the values from the previous iteration. For example, if a value is non-zero in one iteration and then zero in the next.
Why the break near the end? This will cause your program to always break after the first iteration in the while loop.
```
  map[row][col] = 0;

  if(map[row][col] == 0){
      break; // why?
  }
```

When checking for the highest-valued next position, be sure to set both the row and column in case a previous position had been identified as the highest.

    if(coins[i] > highestCoin){

        highestCoin = coins[i];

        if(i == 0){
            newCol = col; // this is important! do this for all cases!
            newRow = row - 1;

        }   
        ...     
    }

Switch the two bounds comparisons. row should compare to map.length, whereas col should compare to map[0].length. This is because rows can be thought of as vertical stacks (and so represent the first index in a 2d-array), whereas columns can be thought of as the horizontal units that make up the stacks (and so appear in the second index). Think of selecting first the stack, and then the unit in the stack.

2d array game that moves to adjacent spaces picking up coins

Answers (2)

Related Questions