title: Stuck on recursion algorithm
body: <p>I got a question about recursion for an entry exam of a job, but I failed to do it within 2 hours. I am very curious about how to do this after the pre-exam but I cannot work out a solution.</p>
  
  <p>You can imagine there is a coin pusher with size n*m (2D array).
  Each operation (moving up or down or left or right) will throw away one row or one column of coins</p>
  
  <p>The question requires me to find the shortest possible moves that remains k coins at last. If it is impossible to remain k coins at last, then return -1</p>
  
  <p>I stuck on how to determine the next move when there is more than one operation that having the same maximum number of coins (same value to be thrown away)</p>
  
  <p>I believe that I need to calculate recursively that simulates all future possible moves to determine the current move operation.</p>
  
  <p>But I do not know how to implement this algorithm, can anyone help?</p>
  
  <p>Thank you!</p>
  
  <pre><code>Question : 
  There is a rectangular chessboard containing N‘M cells. each of
  which either has one coin or nothing.
  You can move all the coins together in one direction (such as up,
  down, left, and right), but each time you can move these coins by
  only one cell.
  
  If any coins fall out of the chessboard, they must be thrown away.
  If it is required to keep K coins on the board, what is the minimum
  moves you have to take?
  
  Output -1 if you can not meet this requirement.
  
  The first line of the input are two positive 
  integers n, representing the size of the board.
  
  For the next n line(s), each line has m numbers of 
  characters, with 'o' indicating a coin, '.' indicates an empty grid.
  
  The last line is a positive integer k, 
  indicating the number of coins to be retained.
  
  30% small input: 1 &lt;= n,m &lt;= 5, 0 &lt; k &lt; 25
  40% medium input: 1 &lt;= n,m &lt;= 10, 0 &lt; k &lt; 100
  30% large input: 1 &lt;= n,m &lt;= 100, 0 &lt; k &lt; 10000
  
  sample input:
  3 4
  .o..
  oooo
  ..o.
  3
  
  sample output:
  2
  </code></pre>
  
  <p>My temporary answer</p>
  
  <pre><code>import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collections;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.Map;
  import java.util.Map.Entry;
  import java.util.Scanner;
  
  public class main {
      String[][] inputArray;
  
      int n;
      int m;
      int k;
  
      int totalCoin = 0;
      int step = 0;
      public static void main(String[] args) {
          main temp = new main();
          temp.readData();
      }
  
      public void readData() {
          Scanner sc = new Scanner(System.in);
          n = sc.nextInt();
          m = sc.nextInt();
          inputArray = new String [n][m];
  
          sc.nextLine(); // skipping
  
          for (int i = 0; i &lt; n; i++) {
              String temp = sc.nextLine();
              for (int j = 0; j &lt; m; j++) {
                  if ((temp.charAt(j) + "").equals("o")) totalCoin++;
                  inputArray[i][j] = temp.charAt(j) + "";
              }
          }
  
          k = sc.nextInt();   
          int result = 0;
  
          if (totalCoin &gt;= k) {
              result = findMaxAndMove();
              System.out.println(result);
  
          }
  
      }
  
      public String findNextMove() {
          Map&lt;String,Integer&gt; tempList = new HashMap&lt;String,Integer&gt;();
          tempList.put("up", up());
          tempList.put("down", down());
          tempList.put("left", left());
          tempList.put("right", right());
  
          Map.Entry&lt;String, Integer&gt; maxEntry = null;
  
  
          for (Entry&lt;String,Integer&gt; temp : tempList.entrySet()) {
              if (maxEntry == null || temp.getValue() &gt; maxEntry.getValue()) {
                  maxEntry = temp;
              }
          }
  
          Map&lt;String,Integer&gt; maxList = new HashMap&lt;String,Integer&gt;();
          for (Entry&lt;String,Integer&gt; temp : tempList.entrySet()) {
              if (temp.getValue() == maxEntry.getValue()) {
                  maxList.put(temp.getKey(), temp.getValue());
              }
          }
  
  //      return maxList.entrySet().iterator().next().getKey();
  
          if (maxList.size() &gt; 1) {
              // how to handle this case when more than 1 operations has the same max value???????????
              return ??????????????
          }
          else {
              return maxList.entrySet().iterator().next().getKey();
          }
  
  
  
  //      
  
  
      }
  
      public int findMaxAndMove() {
  
          int up = up();
          int down = down();
          int left = left();
          int right = right();
  
          if ((totalCoin - up) == k) {
              step++;
              return step;
          }
  
          if ((totalCoin - down) == k) {
              step++;
              return step;
          }
  
          if ((totalCoin - left) == k) {
              step++;
              return step;
          }
  
          if ((totalCoin - right) == k) {
              step++;
              return step;
          }
  
          if (totalCoin - up &lt; k &amp;&amp; totalCoin - down &lt; k &amp;&amp; totalCoin - left &lt; k &amp;&amp; totalCoin - right &lt; k) return -1;
          else {
              switch (findNextMove()) {
                  case "up" :
                      totalCoin -= up;
                      this.moveUp();
                      break;
                  case "down" :
                      totalCoin -= down;
                      this.moveDown();
                      break;
                  case "left" :
                      totalCoin -= left;
                      this.moveLeft();
                      break;
                  case "right" :
                      totalCoin -= right();
                      this.moveRight();
                      break;
              }
              step++;
              return findMaxAndMove(); // going to next move
          }
  
      }
  
      public String[] createBlankRow() {
          String[] temp = new String[m];
          for (int i = 0; i &lt; m; i++) {
              temp[i] = ".";
          }
          return temp;
      }
  
  
      public int up() {
          int coinCounter = 0;
          for (int i = 0; i &lt; m; i++) {
              if (inputArray[0][i].equals("o")) {
                  coinCounter++;
              }
          }
  
  
          return coinCounter;
      }
  
      public void moveUp() {
          // going up
          for (int i = 0; i &lt; n - 1; i++) {
              inputArray[i] = inputArray[i + 1];
          }
  
          inputArray[n-1] = createBlankRow();
  
      }
  
      public int down() {
          int coinCounter = 0;
          for (int i = 0; i &lt; m; i++) {
              if (inputArray[n-1][i].equals("o")) {
                  coinCounter++;
              }
          }
  
  
          return coinCounter;
      }
  
      public void moveDown() {
          // going down
          for (int i = n-1; i &gt; 1; i--) {
              inputArray[i] = inputArray[i - 1];
          }
  
          inputArray[0] = createBlankRow();
  
  
      }
  
      public int left() {
          int coinCounter = 0;
          for (int i = 0; i &lt; n; i++) {
              if (inputArray[i][0].equals("o")) {
                  coinCounter++;
              }
          }
  
          return coinCounter;
      }
  
      public void moveLeft() {
          // going left
          for (int i = 0; i &lt; n; i++) {
              for (int j = 0; j &lt; m-1; j++) {
                  inputArray[i][j] = inputArray[i][j+1];
              }
              inputArray[i][m-1] = ".";
  
          }
  
  
      }
  
  
      public int right() {
          int coinCounter = 0;
          for (int i = 0; i &lt; n; i++) {
              if (inputArray[i][m-1].equals("o")) {
                  coinCounter++;
              }
          }
  
          return coinCounter;
      }
  
      public void moveRight() {
          // going right
          for (int i = 0; i &lt; n; i++) {
              for (int j = m-1; j &gt; 0; j--) {
                  inputArray[i][j] = inputArray[i][j-1];
              }
              inputArray[i][0] = ".";
          }
  
  
      }
  
  
  
      public void printboard() {
           for (int i = 0; i &lt; n; i++) {
              for (int j = 0; j &lt; m; j++) {
                  System.out.print(inputArray[i][j]);
              }
              System.out.println();
          }
  
      }
  
  
  }
  </code></pre>