12
\$\begingroup\$

I would like to ask your comments on my contest code for the following problem:

We're going to have a slightly more logical puzzle today. We're going to write a program that will find a path through a simple maze.

Formal Inputs & Outputs

Input Description

Through standard console, you will be given two numbers X and Y. After that you will be given a textual ASCII grid, X wide and Y tall, of walls # and spaces. In the maze there will be exactly one letter S and exactly one letter E. There will be no spaces leading to the outside of the maze - ie. it will be fully walled in.

Output Description

You must print out the maze. Within the maze there should be a path drawn with askerisks * leading from the letter S to the letter E. Try to minimise the length of the path if possible - don't just fill all of the spaces with *!

Sample Inputs & Outputs

Sample Input 15 15
###############
#S        #   #
### ### ### # #
#   #   #   # #
# ##### ##### #
#     #   #   #
# ### # ### ###
# #   # #   # #
# # ### # ### #
# # # # # #   #
### # # # # # #
#   #   # # # #
# ####### # # #
#           #E#
###############


Sample Output
###############
#S**      #   #
###*### ### # #
#***#   #   # #
#*##### ##### #
#*****#   #   #
# ###*# ### ###
# #***# #   # #
# #*### # ### #
# #*# # # #***#
###*# # # #*#*#
#***#   # #*#*#
#*####### #*#*#
#***********#E#
###############

I coded my solution in Java. I would like to ask on possible improvements on my solution such as parts I can optimize. Any other comments regarding the code is also very much appreciated as my purpose of posting this is to improve my coding skills.

public class Solution {

        BufferedReader bufferedReader;

        public static void main(String[] args) {
                Solution sol = new Solution();
                sol.solve();

        }

        public Solution() {
                bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        }

        private void solve() {
                int[] inputs = convertStringArraytoIntArray(nextLine().split(" "));
                int x = inputs[0];
                int y = inputs[1];
                char[][] maze = new char[y][x];
                for (int ctr = 0; ctr < y; ctr++) {
                        maze[ctr] = nextLine().toCharArray();
                }
                Maze inputMaze = new Maze(maze);
                int maxMoves = inputMaze.numOfSpaces();
                HashSet<Maze> seenMazes = new HashSet<>();
                Stack<Maze> mazeStack = new Stack<>();
                mazeStack.add(inputMaze);
                Maze answer = null;
                while (mazeStack.size() > 0) {
                        Maze currMaze = mazeStack.pop();
                        if (seenMazes.size() > 300000)
                                break;
                        if (currMaze.isSolved()) {
                                if (answer == null || answer.getMoves() > currMaze.getMoves()) {
                                        answer = currMaze;
                                }

                        } else {
                                if (currMaze.getMoves() < maxMoves) {
                                        if (currMaze.canMoveUp()) {
                                                Maze temp = currMaze.moveUp();
                                                if (!seenMazes.contains(temp)) {
                                                        mazeStack.push(temp);
                                                        seenMazes.add(temp);
                                                }
                                        }
                                        if (currMaze.canMoveDown()) {
                                                Maze temp = currMaze.moveDown();
                                                if (!seenMazes.contains(temp)) {
                                                        mazeStack.push(temp);
                                                        seenMazes.add(temp);
                                                }
                                        }
                                        if (currMaze.canMoveLeft()) {
                                                Maze temp = currMaze.moveLeft();
                                                if (!seenMazes.contains(temp)) {
                                                        mazeStack.push(temp);
                                                        seenMazes.add(temp);
                                                }
                                        }
                                        if (currMaze.canMoveRight()) {
                                                Maze temp = currMaze.moveRight();
                                                if (!seenMazes.contains(temp)) {
                                                        mazeStack.push(temp);
                                                        seenMazes.add(temp);
                                                }
                                        }
                                }
                        }
                }
                answer.print();
        }

        private int[] convertStringArraytoIntArray(String[] strArray) {
                int[] intArr = new int[strArray.length];
                for (int ctr = 0, len = strArray.length; ctr < len; ctr++) {
                        intArr[ctr] = Integer.parseInt(strArray[ctr]);
                }
                return intArr;
        }

        private int nextInt() {
                try {
                        return Integer.parseInt(bufferedReader.readLine().trim());
                } catch (NumberFormatException | IOException e) {
                        e.printStackTrace();
                        return 0;
                }
        }

        private String nextLine() {
                try {
                        return bufferedReader.readLine();
                } catch (IOException e) {
                        e.printStackTrace();
                }
                return "";
        }
}

public class Maze {

        public int moves;
        private char[][] maze;
        private Point currLoc;
        private Point endPoint;
        private int width;
        private int height;

        public Maze(char[][] maze) {
                this.maze = maze;
                moves = 0;
                height = maze.length;
                width = maze[0].length;
                currLoc = findStart();
                endPoint = findEnd();
        }

        public int numOfSpaces() {
                int numOfSpaces = 0;
                for (int y = 0; y < height; y++)
                        for (int x = 0; x < width; x++) {
                                if (maze[y][x] == ' ' || maze[y][x] == 'E') {
                                        numOfSpaces++;
                                }
                        }
                return numOfSpaces;
        }

        private Point findStart() {
                for (int y = 0; y < height; y++)
                        for (int x = 0; x < width; x++) {
                                if (maze[y][x] == 'S') {
                                        return new Point(x, y);
                                }
                        }
                return null;
        }

        private Point findEnd() {
                for (int y = 0; y < height; y++)
                        for (int x = 0; x < width; x++) {
                                if (maze[y][x] == 'E') {
                                        return new Point(x, y);
                                }
                        }
                return null;
        }

        @Override
        public boolean equals(Object obj) {
                Maze secondMaze = (Maze) obj;
                for (int y = 0; y < height; y++)
                        for (int x = 0; x < width; x++) {
                                if (maze[y][x] != secondMaze.elementAt(y, x)) {
                                        return false;
                                }
                        }
                return true;
        }

        private char elementAt(int y, int x) {
                return maze[y][x];
        }

        public boolean canMoveUp() {
                int x = currLoc.x;
                int y = currLoc.y;
                if (y > 0 && maze[y - 1][x] != '#' && maze[y - 1][x] != '*') {
                        return true;
                }
                return false;
        }

        public int getHeight() {
                return height;
        }

        public int getWidth() {
                return width;
        }

        public Maze moveUp() {
                int x = currLoc.x;
                int y = currLoc.y;
                Maze temp = createClone();
                temp.setElementAt(y - 1, x, '*');
                temp.setCurrentLocation(y - 1, x);
                temp.setMoves(moves + 1);
                return temp;
        }

        private void setMoves(int moves) {
                this.moves = moves;
        }

        private void setCurrentLocation(int y, int x) {
                this.currLoc = new Point(x, y);
        }

        private void setElementAt(int y, int x, char c) {
                maze[y][x] = c;
        }

        private Maze createClone() {
                char[][] newMaze = new char[height][width];
                for (int y = 0; y < height; y++)
                        for (int x = 0; x < width; x++) {
                                newMaze[y][x] = maze[y][x];
                        }
                return new Maze(newMaze);
        }

        public boolean isSolved() {
                if (currLoc.x == endPoint.x && currLoc.y == endPoint.y) {
                        maze[currLoc.y][currLoc.x] = 'E';
                        return true;
                }
                return false;
        }

        public int getMoves() {
                return moves;
        }

        public boolean canMoveDown() {
                int x = currLoc.x;
                int y = currLoc.y;
                if (y < height - 1 && maze[y + 1][x] != '#' && maze[y + 1][x] != '*') {
                        return true;
                }
                return false;
        }

        public Maze moveDown() {
                int x = currLoc.x;
                int y = currLoc.y;
                Maze temp = createClone();
                temp.setElementAt(y + 1, x, '*');
                temp.setCurrentLocation(y + 1, x);
                temp.setMoves(moves + 1);
                return temp;
        }

        public boolean canMoveLeft() {
                int x = currLoc.x;
                int y = currLoc.y;
                if (x > 0 && maze[y][x - 1] != '#' && maze[y][x - 1] != '*') {
                        return true;
                }
                return false;
        }

        public Maze moveLeft() {
                int x = currLoc.x;
                int y = currLoc.y;
                Maze temp = createClone();
                temp.setElementAt(y, x - 1, '*');
                temp.setCurrentLocation(y, x - 1);
                temp.setMoves(moves + 1);
                return temp;
        }

        public boolean canMoveRight() {
                int x = currLoc.x;
                int y = currLoc.y;
                if (x < width - 1 && maze[y][x + 1] != '#' && maze[y][x + 1] != '*') {
                        return true;
                }
                return false;
        }

        public Maze moveRight() {
                int x = currLoc.x;
                int y = currLoc.y;
                Maze temp = createClone();
                temp.setElementAt(y, x + 1, '*');
                temp.setCurrentLocation(y, x + 1);
                temp.setMoves(moves + 1);
                return temp;
        }

        public void print() {
                for (int y = 0; y < height; y++) {
                        for (int x = 0; x < width; x++) {
                                System.out.print(maze[y][x]);
                        }
                        System.out.println();
                }
        }
}

Lastly, the line seenMazes.size() > 300000 is a dirty way to ensure that the program terminates after spending time searching possible solutions and might also cause answer to be null if ever no answer has been obtained yet. I found it difficult to calculate the maximum number of possible outcomes based on the input alone and also due to time constraint.

\$\endgroup\$
  • 1
    \$\begingroup\$ @Manny Meng Thank you for your comment, I did not check for possible exceptions during input because the rules of the contest stated that the inputs will always be correct. Also I needed to code fast since contests are about speed. \$\endgroup\$ – MykelXIII Jul 27 '14 at 2:17
5
\$\begingroup\$

Code Style

Your code is actually not bad. However, I would modify the general OO structure.

  • I would separate the Maze from its representation. There would be a MazeTextRepresentation which would read in text to create a Maze and a method to print out a Maze as text. This is standard "separation of concerns"; here we separate the model from its representation. You can later create a JavaFX MazeGUIRepresentation without having to modify your existing code at all. Related to this point: you really should not read in the Maze in your Solution class, but just give it a Maze.

  • I would rename Solution to PathFindingAlgorithm and actually make it an interface instead of a class. The interface would have only one method that takes a Maze and returns a path. You should also define a class Path. For example, your current solution would be public class BruteForceAlgorithm implements PathFindingAlgorithm.

Algorithm

As I just alluded above, the algorithm you are using is a brute force (exhaustive search) algorithm. It is not efficient. You could not scale this algorithm for large mazes. Take a look at path finding algorithms on Wikipedia. The A* algorithm is the one usually used in video games.

You could also improve your current algorithm a little bit. You have very many Mazes which you use to store different paths, but it would be more efficient to define a Path class and use a Stack<Path> instead of Stack<Maze>. You could change class Maze so that it only contains a boolean[][] (wall or empty). It could not contain a Path, but that is no big deal since you just need to combine a Maze and a Path at the very end to display the solution as text, or maybe on a GUI.

\$\endgroup\$
  • \$\begingroup\$ Accepted because of suggestions on how to improve the solution to the problem. \$\endgroup\$ – MykelXIII Jul 27 '14 at 3:38
4
\$\begingroup\$

Don't Repeat Yourself

You have this duplicated code for evaluating each direction:

if (currMaze.canMoveUp()) {
    Maze temp = currMaze.moveUp();
    if (!seenMazes.contains(temp)) {
        mazeStack.push(temp);
        seenMazes.add(temp);
    }
}

It would be good to create an enum Move to represent all the possible moves. And instead of functions like canMoveUp, create a more general function that takes a Move as its argument, like canMove(Move move), and use a loop to evaluate all the moves.


Likewise, the code of findStart and findEnd are almost identical. You could easily generalize and implement the logic in one place.

Practical issues

The equals method should check the class of its parameter, typically in this form:

@Override
public boolean equals(Object obj) {
    if (obj instanceof Maze) {
        // the real comparison to the other Maze goes here
    }
    return false;
}

This has the added benefit of preventing class cast exception and null pointer exception.


Declare variables with their interface types instead of the implementation. For example instead of:

HashSet<Maze> seenMazes = new HashSet<>();

Do like this:

Set<Maze> seenMazes = new HashSet<>();

This if statement can be simplified:

if (y > 0 && maze[y - 1][x] != '#' && maze[y - 1][x] != '*') {
    return true;
}
return false;

Like this:

return y > 0 && maze[y - 1][x] != '#' && maze[y - 1][x] != '*';

You have this in every canMoveX method.


The way you copy the char[][] array can be improved:

for (int y = 0; y < height; y++)
    for (int x = 0; x < width; x++) {
        newMaze[y][x] = maze[y][x];
    }

Like this:

for (int y = 0; y < height; y++) {
    System.arraycopy(maze[y], 0, newMaze[y], 0, width);
}

You have some unused methods:

  • getHeight
  • getWidth
  • nextInt

There's no need to speculate about potential future uses. Implement methods when you actually use them. Every line of code may potentially introduce bugsis potentially buggy.

Coding style

When checking the size of a Stack, instead of this:

while (mazeStack.size() > 0) {

Do like this:

while (!mazeStack.empty()) {

It's recommended to use braces with if statements, so instead of:

if (seenMazes.size() > 300000)
    break;

Do like this:

if (seenMazes.size() > 300000) {
    break;
}

The same goes for the outer for loop in the equals method.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the coding tips. They are very much appreciated. I'll try to apply them. \$\endgroup\$ – MykelXIII Jul 27 '14 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.