A-maze-ing maze entry point guessing

Question

You're a blind adventurer (bad luck eh). To go through the maze that'll lead you to freedom, you must first find the maze's wall, then follow this wall to find the maze's entry. Then, to get an idea about the size of the maze, you want to see how large is the said entry, so you walk until you touch another wall, which is the other border of the entrance. Still following? If not, here's a boolean[][] that'll show my example :

1,1,1,1,1,0,0,0,1,1,1,1,1

0,0,0,1,1,0,0,0,1,1,0,0,0

• Zeros implies there is no wall
• Ones implies there is a wall.

The entry of the maze can be found on the last index of the array, meaning :

maze[x,maze.length-1]

In my example, the entrance is found at [6,1]. As it is a first iteration, the maze is expected to have only one entry, which is valid, which will be situated on the last row of the array. @DoubleDouble already pointed out a flaw of my algorithm in his answer.

If the maze contained an even number of "columns", the entrance could be either the "left" or "right", it doesn't matter.

To find the entrance to my maze, I wrote the function guessEntry, in my Maze class :

package com.mazr.domain;

import java.awt.Point;

public class Maze {
    private boolean[][] content;

    public Maze(boolean[][] content) {
        this.content = content;
    }

    public Point guessEntry() throws InvalidMazeException {

        int openingBorder, closingBorder;
        int xIndex = 0;
        final int bottomYIndex = content[0].length-1;

        try {
            //Find the wall
            while (!content[xIndex][bottomYIndex])
                xIndex++;

            //Follow the wall to the entry
            while (content[xIndex][bottomYIndex])
                xIndex++;

            openingBorder = xIndex;

            //Follow the entry until the end of it
            while (!content[xIndex][bottomYIndex])
                xIndex++;

            closingBorder = xIndex;

            return new Point((closingBorder - openingBorder) / 2, bottomYIndex);
        }
        catch(IndexOutOfBoundsException e){
            throw new InvalidMazeException("The maze has no guessable entry", e);
        }
    }
}

To make the example even clearer, I will show how the algorithm behaves to find an entrance (Don't forget that it only works on the bottom row of the array, which is assumed to contain some walls.):

//Find the wall    
while (!content[xIndex][bottomYIndex])
    xIndex++;

0,0,0,1,1,0,0,0,1,1,0,0,0

------^ xIndex is now at this position, since it went through all the left zeroes.

//Follow the wall to the entry
while (content[xIndex][bottomYIndex])
    xIndex++;

0,0,0,1,1,0,0,0,1,1,0,0,0

----------^ xIndex is now there, since it went through the first wall. We set openingBorder to xIndex since this is the beginning of the entrance "hall".

//Follow the entry until the end of it
while (!content[xIndex][bottomYIndex])
    xIndex++;

0,0,0,1,1,0,0,0,1,1,0,0,0

----------------^ xIndex went to the next wall, which marks the end of the entrance "hall". We set the closingBorder to xIndex so we can know where is the hall situated.

Then, averaging (sorry if that's not a word) the closing and opening border, we can figure out where is the middle of the hall, so we can start solving it (in an upcoming question).

The jagged array is rectangular, meaning that wether we talk about index 0 or 1732, the jagged array will have the same length.

Now, it is easy to seek why I need a review. The function works, it is arguably easy to understand. But I can't stand these following while loops..

I'm using Java 1.8.

I know I'm providing only one method, but I feel like it is already hard to explain briefly and to be clear about the cases.

Answer 1

Make that private final boolean[][] content; - note the final

Also, I can recommend making a deep copy of the two dimensional array, as otherwise the array can be mutated from outside.

I hope InvalidMazeException is a RuntimeException, or at least that's what I would prefer. In that case, you could consider removing that completely and using IllegalStateException instead.

That try-catch is smelly. ArrayIndexOutOfBoundsException should be avoided, not caught.

The while-loops can be handled by extracting a method, such as:

int findFirst(boolean[][] content, int index, boolean wall) {
    while (content[index][bottomYIndex] != wall) {
        index++;
        if (index >= content.length) {
             throw new PickYourException("Invalid maze...");
        }
    }
    return index;
}

Then you could use it like this:

xIndex = findFirst(content, xIndex, true);
xIndex = findFirst(content, xIndex, false);
openingBorder = xIndex;
xIndex = findFirst(content, xIndex, true);
closingBorder = xIndex;

For the future, if you ever would want to support more things in your maze, you might need more than just true/false values. As such, I would add methods such as isWall(int x, int y) or isEmptySpace(int x, int y), and use them whereever possible instead of using the boolean[][] directly. Then you could also handle out-of-range values inside the isWall/isEmptySpace methods to always count such areas as wall for example, or throw an IllegalArgumentException.

Answer 2

I believe the while() loops are the best way to accomplish your task with how your code is now, so I'm not sure why you "can't stand" them.

You could use a for() loop, and break out of it using an if statement to check the same thing that your while loops are doing, but I would prefer the while loops myself.

---

One other thing I'd like to mention: if your input is always going to be similar to your example you have nothing to worry about, but your code might not work correctly on the following examples:

Extra line of blank space:
1,1,1,1,1,0,0,0,1,1,1,1,1
0,0,0,1,1,0,0,0,1,1,0,0,0
0,0,0,0,0,0,0,0,0,0,0,0,0

No wall separator before the entrance:
1,1,1,1,1,0,0,0,1,1,1,1,1
0,0,0,0,0,0,0,0,1,1,0,0,0

No wall separator before the entrance #2:
0,0,0,1,1,1,1,1,1,1,1,1,1
0,0,0,1,1,1,1,1,1,1,1,1,1

You'd catch the ArrayIndexOutOfBounds exception as an "unguessable entry", which I assume is the intentional response - but thought I'd put this here just in case.

Answer 3

I'd go with removing the try-catch block. In the while conditions you just have to check that xIndex is smaller than the array's length.

I'd also avoid throwing the InvalidMazeException and instead just return a Point that cannot exist in any maze, if such a point exists, or null, but that's just a preference of mine (I don't like throwing many exceptions and tend to keep them to a minimum, especially if we're talking about checked exceptions, see here why).

public Point guessEntry() throws InvalidMazeException {

    int openingBorder, closingBorder;
    int xIndex = 0;
    final int bottomYIndex = content[0].length-1;

    try {
        //Find the wall
        while (!content[xIndex][bottomYIndex])
            xIndex++;

        //Follow the wall to the entry
        while (content[xIndex][bottomYIndex])
            xIndex++;

        openingBorder = xIndex;

        //Follow the entry until the end of it
        while (!content[xIndex][bottomYIndex])
            xIndex++;

        closingBorder = xIndex;

        return new Point((closingBorder - openingBorder) / 2, bottomYIndex);
    }
    catch(IndexOutOfBoundsException e){
        throw new InvalidMazeException("The maze has no guessable entry", e);
    }
}

would become something like:

public Point guessEntry() {
    int openingBorder, closingBorder;
    int xIndex = 0;
    Point result = null;
    final int bottomYIndex = content[0].length-1;
    final int contentLength = content.length;

    //Find the wall
    while (xIndex < contentLength && !content[xIndex][bottomYIndex])
        xIndex++;

    //Follow the wall to the entry
    while (xIndex < contentLength && content[xIndex][bottomYIndex])
        xIndex++;

    openingBorder = xIndex;

    //Follow the entry until the end of it
    while (xIndex < contentLength && !content[xIndex][bottomYIndex])
        xIndex++;

    closingBorder = xIndex;

    if(openingBorder < contentLength && closingBorder < contentLength)
        result = new Point((closingBorder - openingBorder) / 2, bottomYIndex);

    return result;
}