EmptyStackException - Java Depth First Search algorithm on 2D array

Question

I have looked at this question here I tried most of the code samples from there but when i use it in my code it just skips the algorithm.

I have this DFS algorithm that uses stack, I am getting a EmptyStackException, I have debugged the algorithm and after first recursive search the stack is empty, the first search works but then the size of stack is set to 0, What am I missing here? github

How can I make sure that the stack is not empty after the first search?

The line that I get the exception on is while(true){AddBridges state = gameTree.peek(); ...

I am using a 2d Array to generate the nodes at random from 0 to 4 0 = null 1-4 = island The array generates Random Integers every time the user starts the game, could that cause the Algorithm to brake,

After a weekend of debugging I found that the algorithm sometimes brakes after 4-6 searches, and sometimes breaks after the first search.

public int[][] debug_board_state_easy = new int[4][4];

//This Generates random 2d array
private void InitializeEasy() {
   Random rand = new Random();

   setCurrentState(new State(WIDTH_EASY));
   for (int row = 0; row < debug_board_state_easy.length; row++) {
      for (int column = 0; column < debug_board_state_easy[row].length; column++) {
          debug_board_state_easy[row][column] = Integer.valueOf(rand.nextInt(5));
      }
  }

  for (int row = 0; row < debug_board_state_easy.length; row++) {
     for (int column = 0; column < debug_board_state_easy[row].length; column++) {
        System.out.print(debug_board_state_easy[row][column] + " ");
     }
     System.out.println(debug_board_state_easy);
  }
//I am applying the search algorithm here...
  this.search();

  for (int row = 0; row < WIDTH_EASY; ++row) {
     for (int column = 0; column < WIDTH_EASY; ++column) {
         getCurrentState().board_elements[row][column] = new BoardElement();
         getCurrentState().board_elements[row][column].max_connecting_bridges = Integer.valueOf(debug_board_state_easy[row][column]);
              getCurrentState().board_elements[row][column].row = row;
              getCurrentState().board_elements[row][column].col = column;

         if (getCurrentState().board_elements[row][column].max_connecting_bridges > 0) {
            getCurrentState().board_elements[row][column].is_island = true;
         }
      }
   }
}

void search() {
   Map<Point, List<Direction>> remainingOptions = new HashMap<>();
   Stack<Land> gameTree = new Stack<>();
   gameTree.push(new AddBridges(debug_board_state_easy));

   while(true) {
      AddBridges state = gameTree.peek();
      int[] p = state.lowestTodo();
      if (p == null)
         System.out.println("solution found");
      // move to next game state
         int row = p[0];
         int column = p[1];
         System.out.println("expanding game state for node at (" + row + ", " + column + ")");

         List<Direction> ds = null;
         if(remainingOptions.containsKey(new Point(row,column)))
            ds = remainingOptions.get(new Point(row,column));
         else{
            ds = new ArrayList<>();
            for(Direction dir : Direction.values()) {
               int[] tmp = state.nextIsland(row, column, dir);
               if(tmp == null)
                  continue;
               if(state.canBuildBridge(row,column,tmp[0], tmp[1]))
                  ds.add(dir);
            }
            remainingOptions.put(new Point(row,column), ds);
         }
      // if the node can no longer be expanded, and backtracking is not possible we quit
         if(ds.isEmpty() && gameTree.isEmpty()){
            System.out.println("no valid configuration found");
            return;
         }
      // if the node can no longer be expanded, we need to backtrack
         if(ds.isEmpty()){
            gameTree.pop();
            remainingOptions.remove(new Point(row,column));
            System.out.println("going back to previous decision");
            continue;
         }

         Direction dir = ds.remove(0);
         System.out.println("connecting " + dir.name());
         remainingOptions.put(new Point(row,column), ds);

         AddBridgesnextState = new AddBridges(state);
         int[] tmp = state.nextIsland(row,column,dir);
         nextState.connect(row,column, tmp[0], tmp[1]);
         gameTree.push(nextState);
      }
   }
}

Add bridges class

public class AddBridges {

    private int[][] BRIDGES_TO_BUILD;

    private boolean[][] IS_ISLAND;
    private Direction[][] BRIDGES_ALREADY_BUILT;

    public Land(int[][] bridgesToDo){
        BRIDGES_TO_BUILD = copy(bridgesToDo);

        int numberRows = bridgesToDo.length;
        int numberColumns = bridgesToDo[0].length;
        BRIDGES_ALREADY_BUILT = new Direction[numberRows][numberColumns];
        IS_ISLAND = new boolean[numberRows][numberColumns];
        for(int i=0;i<numberRows;i++) {
            for (int j = 0; j < numberColumns; j++) {
                BRIDGES_ALREADY_BUILT[i][j] = null;
                IS_ISLAND[i][j] = bridgesToDo[i][j] > 0;
            }
        }
    }

    public AddBridges (AddBridges other){
        BRIDGES_TO_BUILD = copy(other.BRIDGES_TO_BUILD);
        int numberRows = BRIDGES_TO_BUILD.length;
        int numberColumns =  BRIDGES_TO_BUILD[0].length;
        BRIDGES_ALREADY_BUILT = new Direction[numberRows][numberColumns];
        IS_ISLAND = new boolean[numberRows][numberColumns];
        for(int i=0;i<numberRows;i++) {
            for (int j = 0; j < numberColumns; j++) {
                BRIDGES_ALREADY_BUILT[i][j] = other.BRIDGES_ALREADY_BUILT[i][j];
                IS_ISLAND[i][j] = other.IS_ISLAND[i][j];
            }
        }
    }

    public int[] next(int r, int c, Direction dir){
        int numberRows = BRIDGES_TO_BUILD.length;
        int numberColumns = BRIDGES_TO_BUILD[0].length;

        // out of bounds
        if(r < 0 || r >=numberRows || c < 0 || c >= numberColumns)
            return null;


        // motion vectors
        int[][] motionVector = {{-1, 0},{0,1},{1,0},{0,-1}};
        int i = Arrays.asList(Direction.values()).indexOf(dir);

        // calculate next
        int[] out = new int[]{r + motionVector[i][0], c + motionVector[i][1]};

        r = out[0];
        c = out[1];

        // out of bounds
        if(r < 0 || r >=numberRows || c < 0 || c >= numberColumns)
            return null;

        // return
        return out;
    }

    public int[] nextIsland(int row, int column, Direction dir){
        int[] tmp = next(row,column,dir);
        if(tmp == null)
            return null;
        while(!IS_ISLAND[tmp[0]][tmp[1]]){
            tmp = next(tmp[0], tmp[1], dir);
            if(tmp == null)
                return null;
        }
        return tmp;
    }

    public boolean canBuildBridge(int row0, int column0, int row1, int column1){
        if(row0 == row1 && column0 > column1){
            return canBuildBridge(row0, column1, row1, column0);
        }
        if(column0 == column1 && row0 > row1){
            return canBuildBridge(row1, column0, row0, column1);
        }
        if(row0 == row1){
            int[] tmp = nextIsland(row0, column0, Direction.EAST);
            if(tmp == null)
                return false;
            if(tmp[0] != row1 || tmp[1] != column1)
                return false;
            if(BRIDGES_TO_BUILD[row0][column0] == 0)
                return false;
            if(BRIDGES_TO_BUILD[row1][column1] == 0)
                return false;
            for (int i = column0; i <= column1 ; i++) {
                if(IS_ISLAND[row0][i])
                    continue;
                if(BRIDGES_ALREADY_BUILT[row0][i] == Direction.NORTH)
                    return false;
            }
        }
        if(column0 == column1){
            int[] tmp = nextIsland(row0, column0, Direction.SOUTH);
            if(tmp == null)
                return false;
            if(tmp[0] != row1 || tmp[1] != column1)
                return false;
            if(BRIDGES_TO_BUILD[row0][column0] == 0 || BRIDGES_TO_BUILD[row1][column1] == 0)
                return false;
            for (int i = row0; i <= row1 ; i++) {
                if(IS_ISLAND[i][column0])
                    continue;
                if(BRIDGES_ALREADY_BUILT[i][column0] == Direction.EAST)
                    return false;
            }
        }
        // default
        return true;
    }

    public int[] lowestTodo(){
        int R = BRIDGES_TO_BUILD.length;
        int C = BRIDGES_TO_BUILD[0].length;

        int[] out = {0, 0};
        for (int i=0;i<R;i++) {
            for (int j = 0; j < C; j++) {
                if(BRIDGES_TO_BUILD[i][j] == 0)
                    continue;
                if (BRIDGES_TO_BUILD[out[0]][out[1]] == 0)
                    out = new int[]{i, j};
                if (BRIDGES_TO_BUILD[i][j] < BRIDGES_TO_BUILD[out[0]][out[1]])
                    out = new int[]{i, j};
            }
        }
        if (BRIDGES_TO_BUILD[out[0]][out[1]] == 0) {
            return null;
        }
        return out;
    }

    @TargetApi(Build.VERSION_CODES.GINGERBREAD)
    private int[][] copy(int[][] other){
        int[][] out = new int[other.length][other.length == 0 ? 0 : other[0].length];
        for(int r=0;r<other.length;r++)
            out[r] = Arrays.copyOf(other[r], other[r].length);
        return out;
    }

    public void connect(int r0, int c0, int r1, int c1){
        if(r0 == r1 && c0 > c1){
            connect(r0, c1, r1, c0);
            return;
        }
        if(c0 == c1 && r0 > r1){
            connect(r1, c0, r0, c1);
            return;
        }
        if(!canBuildBridge(r0, c0, r1, c1))
            return;

        BRIDGES_TO_BUILD[r0][c0]--;
        BRIDGES_TO_BUILD[r1][c1]--;

        if(r0 == r1){
            for (int i = c0; i <= c1 ; i++) {
                if(IS_ISLAND[r0][i])
                    continue;
                BRIDGES_ALREADY_BUILT[r0][i] = Direction.EAST;
            }
        }
        if(c0 == c1){
            for (int i = r0; i <= r1 ; i++) {
                if(IS_ISLAND[i][c0])
                    continue;
                BRIDGES_ALREADY_BUILT[i][c0] = Direction.NORTH;
            }
        }
    }
}

You need to do a better job of attempting to debug yourself. You didn't even give it 10 minutes from your last question (which you have now deleted) before posting this one... Find out why int[] tmp = state.nextIsland(row,column,dir); nextState.connect(row,column, tmp[0], tmp[1]); is returning nothing — IsThisJavascript
– IsThisJavascript, Commented Aug 22, 2018 at 10:18
@IsThisJavascript have spent a lot of time debugging the algorithm, i feel like im going in circles here, The algorithm works for the first search then tries to back tracking and the stack size = 0, if(ds.isEmpty()){ gameTree.pop(); remainingOptions.remove(new Point(row,column)); System.out.println("going back to previous decision"); continue; } This is the loop for backtracking. — AutoTester213
– AutoTester213, Commented Aug 23, 2018 at 10:01
For quick and efficient help, please post minimal reproducible example. I can't debug the (too) long code without running it. — c0der
– c0der, Commented Aug 24, 2018 at 6:03
It's difficult to follow what your search is trying to find, but whatever it is, are you certain that it will always be present? Because the meaning of a correct DFS backtracking past the initial state is that the search failed. — John Bollinger
– John Bollinger, Commented Aug 27, 2018 at 13:36
The standard way to implement a DFS iteratively via a stack starts with creating a stack initially containing only the starting node. Then, on each iteration, you pop the top element from the stack, and test whether it's the one you're looking for. If so, you exit the loop. If not, then you push all the successor nodes you want to traverse from the current node. If on any iteration there is no node to pop, then the search has exhausted all nodes without finding one satisfying your criteria; this is not ordinarily a hard error. — John Bollinger
– John Bollinger, Commented Aug 27, 2018 at 14:36

thenamethatwasnottaken · Accepted Answer · 2018-08-29 23:58:43Z

One part of your question stood out to me as the root of the problem: "What am I missing here"? Unit tests, unless I just didn't see them in your project.

Questions like "the array generates Random Integers every time the user starts the game, could that cause the Algorithm to brake?", are the reason unit tests exist, along with the following:

In the course of writing tests on sections of code that don't end up being the problem, you'll prove definitively that they aren't the problem.
If the code you're working with can't be tested as-is, or is "too complex" to test, re-writing it will make you a better designer and will often lead to "I can't believe I didn't see that" moments.
When you refactor this program (reduce complexity, rename variables to make them easier to understand, etc), you'll be notified immediately if something breaks and you won't have to spend another weekend trying to figure it out.

As an example, instead of randomizing the board within the method that searches it, randomize it elsewhere and then drop it into that method as an argument (or into the class' constructor). That way, you can initialize your own test board(s) with your own supplied values and see if some boards work better than others and why. Split up larger methods into smaller methods, each with their own parameters and tests. Aim to make a program out of smaller confirmed-working pieces, instead of making a huge thing and then wondering if the problem is the small part you think it is or something else.

You'll save so much time and frustration in the long run, and you'll end up leagues ahead of those who code for hours and then debug for hours.

Rosa Mohammadi · Accepted Answer · 2018-08-25 21:11:01Z

0

There's a lot going on in the code, but the first thing I notice might help:

// if the node can no longer be expanded, we need to backtrack
            if(ds.isEmpty()){
                gameTree.pop();
                remainingOptions.remove(new Point(row,column));
                System.out.println("going back to previous decision");
                continue;
            }

you pop from the stack, and continue onto the next while(true) iteration, at that point, there may be nothing on the stack since you have not added anything else.

answered Aug 25, 2018 at 21:11

Rosa Mohammadi

661 bronze badge

1 Comment

AutoTester213 Over a year ago

How can sure not to pop the stack while its value is 1?

Jatish · Accepted Answer · 2018-08-29 08:20:17Z

0

I agree with @Rosa -

The EmptyStackException should occur when removing or looking up empty Stack-

======Iteration/State in code ======

 **if(ds.isEmpty()){**  //HashMap isEmpty = true and gameTree.size() = 1
            gameTree.pop();    // After removing element gameTree.size() = 0 (no elements in stack to peek or pop)
            remainingOptions.remove(new Point(row,column));
            System.out.println("going back to previous decision");
            continue;  //Skip all the instruction below this, continue to next iteration
        }

========Next iteration========

  while(true){
            AddBridges state = gameTree.peek(); // gameTree.size() = 0 and a peek

operation shall fail and program will return EmptyStackException.

Required isEmpty check -

if(gameTree.isEmpty()){ 
            System.out.println("no valid configuration found");
            return;
        }
        AddBridges state = gameTree.peek();

As, no actions have been performed by function but while loop. In case other instcutions to be processed , a "break" is required.

answered Aug 29, 2018 at 8:20

Jatish

4021 gold badge3 silver badges11 bronze badges

1 Comment

AutoTester213 Over a year ago

I am stuck in a infinite loop, Its getting the same values and tries to build bridges all over again

Collectives™ on Stack Overflow

EmptyStackException - Java Depth First Search algorithm on 2D array

3 Answers 3

Comments

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related