0

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;   
    }

2 Answers 2

2

A few corrections to your algorithm:

  1. Suggestion from user1509803
  2. 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.
  3. 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?
      }
    
  4. 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;
    
            }   
            ...     
        }    
    
  5. 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.

8
  • The break was put there when I was running some tests. It isn't a permanent fixture. I set coins back to zero like you suggested and it put me in an endless loop.
    – user2088748
    Sep 9, 2013 at 4:30
  • @user2088748 Do you have a test input? Using the example you gave, I am getting a correct result.
    – jwalk
    Sep 9, 2013 at 4:46
  • I'm using a junit test. Maybe I put it in the wrong spot?... Where exactly did you put it so I can rule out error? I can post the junit test if you would find that useful
    – user2088748
    Sep 9, 2013 at 4:49
  • @user2088748 Thanks for posting the JUnit tests. Looks like they all pass for me after that last bug is fixed. Let me know if anything is unclear. Otherwise good luck!
    – jwalk
    Sep 9, 2013 at 5:06
  • So your two edits were great. It was such a relief to see my junit test go from 14 failures to 1 failure and 5 outofboundsexception: 1 errors.
    – user2088748
    Sep 9, 2013 at 5:07
1

Well I think col must be less than (map.length-1) instead of (map.length-2) For {1},{1}, map.length == 2 so map.length-2 = 0, then col must be less than 0 to execute the if block. Btw, you have map.length comparison to both col and row, so you map will be a square in any case?

4
  • I originally had it -1, but I forgot to change it back before posting the code. At that point I was hopeless and just changing things to see what would happen. Map is a 2d array so it'll either look like a rectangle or a square board.
    – user2088748
    Sep 9, 2013 at 4:20
  • I think {1}, {1} is not a square board, the rowlength==1 and the colLength==2? Sep 9, 2013 at 4:40
  • No its a rectangle. The index of that particular board would be [0][0] over [1][0]. Also setting more coin to false did knock me out of the endless loop, but setting coin to zero has no effect on my results. Would it be useful if I posted the junit test I'm using?
    – user2088748
    Sep 9, 2013 at 4:46
  • I think where you may be confused is I don't make the 2d array. I just create the method to process it so I can't tell you whats inside the array or what size it is. Those were just examples I posted taken from some of the test cases in the junit test I was given.
    – user2088748
    Sep 9, 2013 at 4:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.