Solve the game "Flux"

Question

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;
    }
}

Answer 1

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.

Answer 2

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

Answer 3

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.