10
\$\begingroup\$

The Program

I wrote this program as an answer to a question I thought of for Programming Puzzles and Code Golf. To avoid cross-posting, I will only summarize the requirements:

  • Solve a game in a 3x4 grid that is similar to the fifteen puzzle, except there are colors instead of numbers, and some colors are duplicated; 4 red, 4 yellow, 2 blue, 1 gray, 1 empty
  • The goal is to make the top row exactly match the bottom row.
  • Input is in the other thread; basically, input the 12 cells (a permutation of RRRRYYYYBBG_ in one line
  • Output the moves (a string of LRUD), and then the resulting board.

Why Code Review?

Once I had it working, I decided this would be a really good sort of program for me to get some review on. I cleaned it up and turned it into something that I would be willing to turn into production (there would be some extra error handling, but that part isn't that hard to add in and is boring). There is nothing in particular that I'm looking for; I've worked really hard to polish my programming skills from books like Go4, Refactoring, and Clean Code, and I want to make sure I understand most of those concepts and am applying them correctly. Note: This program is too short for me to bother with a DI framework, but normally I do all my programming beyond a certain complexity level with Guice. Also; this code depends on Guava, but not for all that much, just Preconditions and the java.util factory methods.

FluxSolver.java (main class)

package org.durron597.codereview;

import static com.google.common.base.Preconditions.checkArgument;

import java.util.*;

import com.google.common.collect.Maps;
import com.google.common.collect.Sets;

public class FluxSolver implements Runnable {
    public static final String DEFAULT_TEMPLATE = "RRRRYYYYBBG_";

    private final Map<String, Board> allBoards = Maps.newHashMap();
    private final String template;

    private Set<Board> scoredBoards = Sets.newHashSet();

    public FluxSolver() {
        this(DEFAULT_TEMPLATE);
    }

    public FluxSolver(String template) {
        this.template = template;
    }

    @Override
    public void run() {
        computeAllBoards(template);
        solveAllBoards();

        Scanner c = new Scanner(System.in);
        while (c.hasNext()) {
            String input = c.nextLine();
            printSolution(input);
        }

        c.close();
    }

    private void printSolution(String boardString) {
        Board currentBoard = allBoards.get(boardString);
        while (!currentBoard.isSolved()) {
            System.out.print(currentBoard.getDirection().getSymbol());
            currentBoard = currentBoard.getParent();
        }
        System.out.println();
        System.out.print(currentBoard);
    }

    private void computeAllBoards(String template) {
        checkArgument(template.length() == Board.X_SIZE * Board.Y_SIZE,
                "Board size is the wrong length: %s", template.length());
        permuteHelper("", template);
    }

    private void solveAllBoards() {
        for (int score = 0; score < 20; score++) {
            Set<Board> nextBoardIteration = Sets.newHashSet(scoredBoards);

            for (Board currentBoard : scoredBoards) {
                if (currentBoard.getScore() == score) {
                    for (Direction direction : Direction.values()) {
                        Board boardAfterMove =
                                direction.moveSquare(this, currentBoard);
                        if (discoveredNewBoard(nextBoardIteration,
                                boardAfterMove)) {
                            boardAfterMove.setParent(currentBoard, direction);
                            nextBoardIteration.add(boardAfterMove);
                        }
                    }
                }
            }
            scoredBoards = nextBoardIteration;
        }
    }

    private void permuteHelper(String prefix, String remaining) {
        int charsLeft = remaining.length();
        if (charsLeft == 0) {
            Board newBoard = new Board(prefix);
            allBoards.put(prefix, newBoard);
            if (newBoard.isSolved())
                scoredBoards.add(newBoard);
        } else {
            Set<Character> seenCharacters = new HashSet<>();
            for (int i = 0; i < charsLeft; i++) {
                char c = remaining.charAt(i);
                if (!seenCharacters.contains(c)) {
                    permuteHelper(prefix + c, remaining.substring(0, i)
                            + remaining.substring(i + 1, charsLeft));
                    seenCharacters.add(c);
                }
            }
        }
    }

    private boolean discoveredNewBoard(Set<Board> nextBoardIteration,
            Board boardAfterMove) {
        return boardAfterMove != null
                && !nextBoardIteration.contains(boardAfterMove);
    }

    public Board getBoardFromRawString(String key) {
        return allBoards.get(key);
    }

    public static void main(String[] a) {
        new FluxSolver().run();
    }
}

Board.java

package org.durron597.codereview;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Board {
    public static final int X_SIZE = 4;
    public static final int Y_SIZE = 3;

    private final Board.CellType[][] boardCells = new Board.CellType[Y_SIZE][X_SIZE];
    private final Position emptyPosition;

    private final String rawString;
    private String prettyString = null;

    private Board parent;
    private Direction direction;
    private int score;

    Board(String rawString) {
        int y, x, raw;
        int emptyX = -1, emptyY = -1, emptyRaw = -1;
        for (y = 0; y < Y_SIZE; y++) {
            for (x = 0; x < X_SIZE; x++) {
                raw = calculateRawPosition(y, x);
                boardCells[y][x] =
                        CellType.getTypeFromSymbol(rawString.charAt(raw));
                if (boardCells[y][x] == CellType.EMPTY) {
                    if (emptyX > -1) {
                        throw new IllegalArgumentException(
                                "Multiple empty cells detected at position "
                                        + raw + ": " + rawString);
                    }
                    emptyX = x;
                    emptyY = y;
                    emptyRaw = raw;
                }
            }
        }

        if (emptyX == -1) {
            throw new IllegalArgumentException("No empty cell detected!");
        } else {
            emptyPosition = new Position(emptyX, emptyY, emptyRaw);
        }

        this.rawString = rawString;
    }

    public static int calculateRawPosition(int y, int x) {
        return X_SIZE * y + x;
    }

    public Position getEmptyPosition() {
        return emptyPosition;
    }

    public boolean isSolved() {
        return Arrays.equals(boardCells[0], boardCells[2]);
    }

    public void setParent(Board parent, Direction direction) {
        this.parent = parent;
        this.direction = direction;
        this.score = parent.getScore() + 1;
    }

    @Override
    public String toString() {
        if (prettyString == null) {
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < Y_SIZE; i++) {
                for (int j = 0; j < X_SIZE; j++) {
                    builder.append(boardCells[i][j].getSymbol());
                }
                builder.append(System.lineSeparator());
            }
            prettyString = builder.toString();
        }
        return prettyString;
    }

    public String getRawString() {
        return rawString;
    }

    public int getScore() {
        return score;
    }

    public Board getParent() {
        return parent;
    }

    public Direction getDirection() {
        return direction;
    }

    public static class Position {
        public final int x;
        public final int y;
        public final int raw;

        private Position(int x, int y, int raw) {
            this.x = x;
            this.y = y;
            this.raw = raw;
        }
    }

    public static enum CellType {
        EMPTY('_'), GREEN('G'), BLUE('B'), RED('R'), YELLOW('Y');

        private static Map<Character, CellType> reverseMap = new HashMap<>();

        static {
            for (CellType type : values()) {
                reverseMap.put(type.symbol, type);
            }
        }

        private char symbol;

        private CellType(char symbol) {
            this.symbol = symbol;
        }

        public char getSymbol() {
            return symbol;
        }

        public static CellType getTypeFromSymbol(char symbol) {
            return reverseMap.get(symbol);
        }
    }
}

Direction.java

package org.durron597.codereview;

public enum Direction {
    RIGHT("R") {
        public Board moveSquare(FluxSolver solver, Board input) {
            return input.getEmptyPosition().x == Board.X_SIZE - 1 ? null
                    : moveToEmpty(solver, input, 1);
        }
    },
    LEFT("L") {
        public Board moveSquare(FluxSolver solver, Board input) {
            return input.getEmptyPosition().x == 0 ? null : moveToEmpty(solver, input,
                    -1);
        }
    },
    DOWN("D") {
        public Board moveSquare(FluxSolver solver, Board input) {
            return input.getEmptyPosition().y == Board.Y_SIZE - 1 ? null
                    : moveToEmpty(solver, input, Board.X_SIZE);
        }
    },
    UP("U") {
        public Board moveSquare(FluxSolver solver, Board input) {
            return input.getEmptyPosition().y == 0 ? null : moveToEmpty(solver, input,
                    -Board.X_SIZE);
        }
    };

    private String symbol;

    private Direction(String symbol) {
        this.symbol = symbol;
    }

    public abstract Board moveSquare(FluxSolver solver, Board input);

    Board moveToEmpty(FluxSolver solver, Board i, int emptyOffset) {
        int newPosition = emptyOffset + i.getEmptyPosition().raw;
        char[] s = i.getRawString().toCharArray();
        s[i.getEmptyPosition().raw] = s[newPosition];
        s[newPosition] = Board.CellType.EMPTY.getSymbol();

        return solver.getBoardFromRawString(new String(s));
    }

    public String getSymbol() {
        return symbol;
    }
}
\$\endgroup\$
  • 8
    \$\begingroup\$ I totally agree with your commenting philosophy! ;) \$\endgroup\$ – Mathieu Guindon May 16 '14 at 20:42
4
\$\begingroup\$

FluxSolver

I don't see why this class needs to be a Runnable. It could be just a simple class with a solve method, no?

You're not using the command line arguments. It would be nice to offer a mode in which you can give the board string on the command line. Without arguments, the game could work in interactive mode like it is now, otherwise it could be batch mode.

You're not validating the input lines. If I make a mistake and enter an incorrect board string the game crashes with an NPE.

It would make sense to call getBoardFromRawString when you initialize currentBoard in printSolution. And the method could perform input validation.

It could be interesting to let the command line control the game dimensions as well. So for example you could run it with parameters 3 4 RRRRYYYYBBG_ to behave like the current game.

I don't have too much time now to look closely, but what is the number 20 in solveAllBoards?

Board

In isSolved there is a remnant of hard-coded grid information:

public boolean isSolved() {
    return Arrays.equals(boardCells[0], boardCells[2]);
}

You obviously meant Y_SIZE - 1 instead of "2" there. How about this instead:

public boolean isSolved() {
    return Arrays.equals(boardCells[0], boardCells[boardCells.length - 1]);
}

In the constructor, I found the raw variable name a bit confusing. rawPosition would be more clear.

It might make sense to let the dimensions be constructor parameters instead of static constants.

I think the class is doing a bit too much. It describes a board, and it keeps history and score too. It might be good to create a BoardWithHistory class or something to separate these other responsibilities.

Direction

The values would be slightly more readable if you aligned the moveToEmpty(...) calls the same way for all of them, for example:

LEFT("L") {
    public Board moveSquare(FluxSolver solver, Board input) {
        return input.getEmptyPosition().x == 0 ? null
                : moveToEmpty(solver, input, -1);
    }
},

instead of:

LEFT("L") {
    public Board moveSquare(FluxSolver solver, Board input) {
        return input.getEmptyPosition().x == 0 ? null : moveToEmpty(solver, input,
                -1);
    }
},

The line break in between the method parameters was awkward anyway, with -1 hanging there all alone.

It's a bit strange that moveToEmpty needs a FluxSolver to operate, in a logical sense. To me it's already a bit fishy that a Direction class is aware of Board, but that maybe be forgivable. Depending on a FluxSolver doesn't seem cool. Perhaps you can move the getBoardFromRawString method from FluxSolver to Board instead.

Also in the moveToEmpty method, i is hardly a good name for a Board.

But the biggest problem with this method is that it moves the empty cell in a pretty awkward way. Converting the board's raw string representation to char array, swapping the symbol, then converting back to raw string is not very cool.

Maybe you can refactor this part to work with Board.CellType[][] of the Board in a more direct way, without converting strings and char arrays back and forth. That might bring another benefit too: getting rid of Board.rawstring and Position.raw which look like noise in the class design.

\$\endgroup\$
  • \$\begingroup\$ This is by far the most valuable commentary so far. Some of your complaints are the case because of the actual statement of the problem, but many of them are valid. Thank you! \$\endgroup\$ – durron597 May 22 '14 at 22:04
  • \$\begingroup\$ Oh, the reason that loop stops at 20 is that it's not possible to have a path longer than 20. \$\endgroup\$ – durron597 May 22 '14 at 22:05
  • \$\begingroup\$ About 20, I thought so, and then you should derive it from the game's parameters instead of hardcoding the exact number. \$\endgroup\$ – janos May 22 '14 at 22:25
  • 1
    \$\begingroup\$ @durron597 "This is the most valuable commentary so far" suggests that you should choose this as your accepted answer. \$\endgroup\$ – 200_success Jun 7 '14 at 5:36
  • 1
    \$\begingroup\$ @durron597 - Given that the question needed to be asked, 20 should probably be a constant with a descriptive name. \$\endgroup\$ – psr Feb 13 '15 at 18:32
3
\$\begingroup\$

Why do you need to create a Variable here?

@Override
public void run() {
    computeAllBoards(template);
    solveAllBoards();

    Scanner c = new Scanner(System.in);
    while (c.hasNext()) {
        String input = c.nextLine();  // <----
        printSolution(input);
    }

    c.close();
}

this seems super simple and I think you should just skip creating a variable for this, it doesn't make it any clearer what you are doing here (in my opinion) it's just cluttering up the code

@Override
public void run() {
    computeAllBoards(template);
    solveAllBoards();

    Scanner c = new Scanner(System.in);
    while (c.hasNext()) {
        printSolution(c.nextLine());
    }

    c.close();
}

This is the only place in all the code that you posted where you have a block of code without brackets.

private void permuteHelper(String prefix, String remaining) {
    int charsLeft = remaining.length();
    if (charsLeft == 0) {
        Board newBoard = new Board(prefix);
        allBoards.put(prefix, newBoard);
        if (newBoard.isSolved())               // <--
            scoredBoards.add(newBoard);        // <--
    } else {

This is inconsistent with the rest of your code, there are other locations where you could do this but you don't, personally I don't think it is ever a good idea to code a block without braces (unless you are coding in a pretend (jk) language like VB or Python).

Doing this makes it really easy for you to forget a Brace or even a semi-colon, which can break your code. Doing this also makes it difficult to read larger portions of code.


Other than that, this looks pretty good

\$\endgroup\$
  • 1
    \$\begingroup\$ For your first point, do know that for debugging purpose it's a lot easier to have an intermediate variable to inspect the value. This could be one legitimate reason to do so. \$\endgroup\$ – Marc-Andre May 20 '14 at 14:17
  • \$\begingroup\$ Scanner c is a good variable, isn't it @Marc-Andre. I debug in Visual Studios on C# code so it doesn't matter to me because the c variable will have all the information that I need to see that a separate variable will give me. \$\endgroup\$ – Malachi May 20 '14 at 14:24
  • \$\begingroup\$ Except if you want to investigate what nextLine() is doing which in Eclipse at least will actually call the method and move the cursor of the scanner. I'm in no way saying it's a good or bad thing, but that there could be a good reason to actually have an intermediate variable (it's mention in Clean code if remember correctly) \$\endgroup\$ – Marc-Andre May 20 '14 at 14:43
  • 1
    \$\begingroup\$ @Marc-Andre okay, sounds like a good reason, but I don't think that is what the OP's purpose for the variable is. the OP code is printing that next line anyway, so debugging probably isn't an issue here. \$\endgroup\$ – Malachi May 20 '14 at 14:48
  • 1
    \$\begingroup\$ @Malachi Actually my code doesn't print the next line, it prints the solution. I don't remember why I made it like that but I know that part of the code definitely got refactored more than once and it's probably just how it ended up. Anyway, I think this is a lot of energy to talk about something really minor, IMO. \$\endgroup\$ – durron597 May 22 '14 at 19:12
3
\$\begingroup\$

There is a possible bug in your application.

@Override
public void run() {
    computeAllBoards(template);
    solveAllBoards();
    Scanner c = new Scanner(System.in);
    while (c.hasNext()) {
        String input = c.nextLine();
        printSolution(input);
    }
    c.close();
}

By closing the Scanner you're also closing System.in. So, if in a future version you're running your code more than once, getting input from System.in will not work. A possible way to fix this is to wrap System.in in a uncloseable stream class. There is some answer already on Stack Overflow if you need more information.

\$\endgroup\$

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.