BoardTest

BoardTest.java

import org.junit.After;
import org.junit.Test;

import java.util.*;

import static org.hamcrest.CoreMatchers.*;
import static org.hamcrest.Matchers.containsInAnyOrder;
import static org.junit.Assert.assertThat;


public class BoardTest {

    private Board underTest;

    @After
    public void cleanup() {

        underTest = null;
    }

    @Test
    public void shouldCreateBoard() {

        // given
        final int[][] initState = createCompleteBoard(4);

        // when
        underTest = new Board(initState);

        // then
        assertThat(underTest, not(nullValue()));
    }

    // test for defensive copy which is implicitly tested further
    // down in equals but only due to way to tests are written so
    // nice to have explicit test even though relies on equals
    @Test
    public void shouldCopyConstructorArgs() {

        // given
        final int[][] initState = createCompleteBoard(4);

        // when
        underTest = new Board(initState);
        swapBlocks(initState, 0, 0, 0, 1);
        final Board that = new Board(initState);

        // then
        assertThat(underTest.equals(that), is(false));
    }

    @Test(expected = NullPointerException.class)
    public void shouldThrowExceptionIfBoardIsNull() {

        // when
        underTest = new Board(null);
    }

    @Test(expected = IllegalArgumentException.class)
    public void shouldThrowExceptionIfBoardMissingRows() {

        // given
        final int[][] initState = {{1, 2}};

        // when
        underTest = new Board(initState);
    }

    @Test(expected = IllegalArgumentException.class)
    public void shouldThrowExceptionIfBoardHasShortRow() {

        // given
        final int[][] initState = {{1, 2}, {3}};

        // when
        underTest = new Board(initState);
    }

    @Test(expected = IllegalArgumentException.class)
     public void shouldThrowExceptionIfBoardHasExtraRow() {

        // given
        final int[][] initState = {{1, 2}, {3, 0}, {0, 0}};

        // when
        underTest = new Board(initState);
    }

    @Test(expected = IllegalArgumentException.class)
    public void shouldThrowExceptionIfBoardNumbersAreIncorrect() {

        // given
        final int[][] initState = {{3, 3}, {3, 0}};

        // when
        underTest = new Board(initState);
    }

    @Test(expected = IllegalArgumentException.class)
    public void shouldThrowExceptionIfBoardSmallerThanTwo() {

        // given
        final int[][] initState = createCompleteBoard(1);

        // when
        underTest = new Board(initState);
    }

    @Test(expected = IllegalArgumentException.class)
    public void shouldThrowExceptionIfBoardLargerThan127() {

        // given
        final int[][] initState = createCompleteBoard(128);

        // when
        underTest = new Board(initState);
    }

    @Test
    public void shouldGiveCorrectDimensionForLargeBoard() {

        // given
        final int expectedDimension = 127;
        final int[][] initState = createCompleteBoard(expectedDimension);
        underTest = new Board(initState);

        // when
        final int dimension = underTest.dimension();

        // then
        assertThat(dimension, is(expectedDimension));
    }

    @Test
    public void shouldGiveCorrectDimensionForRandomBoard() {

        // given
        final int expectedDimension = StdRandom.uniform(2, 127);
        final int[][] initState = createCompleteBoard(expectedDimension);
        underTest = new Board(initState);

        // when
        final int dimension = underTest.dimension();

        // then
        assertThat(dimension, is(expectedDimension));
    }

    @Test
    public void shouldGiveHammingOfZeroWhenAllBlocksCorrect() {

        // given
        final int expectedDimension = StdRandom.uniform(2, 127);
        final int[][] initState = createCompleteBoard(expectedDimension);
        underTest = new Board(initState);

        // when
        final int hamming = underTest.hamming();

        // then
        assertThat(hamming, is(0));
    }

    @Test
    public void shouldGiveHammingOfTwoWhenSingleBlocksIncorrect() {

        // given
        createBoardWith2SwappedBlocks();

        // when
        final int hamming = underTest.hamming();

        // then
        assertThat(hamming, is(2));
    }

    @Test
    public void shouldGiveCorrectHammingForPuzzle04() {

        // given
        final int[][] initState = createPuzzle04();
        underTest = new Board(initState);

        // when
        final int hamming = underTest.hamming();

        // then
        assertThat(hamming, is(4));
    }

    // test with known amount of randomness which allows prediction of the
    // number of swaps without having to duplicate the logic in the implementation
    @Test
    public void shouldGiveCorrectHammingWhenOneBlocksInEachRowIncorrect() {

        // given
        final int dimension = StdRandom.uniform(2, 127);
        final int[][] initState = createCompleteBoard(dimension);
        int swaps = swapRandomBlocksFromPairsOfRows(dimension, initState);
        underTest = new Board(initState);

        // when
        final int hamming = underTest.hamming();

        // then
        assertThat(hamming, is(swaps));
    }

    @Test
    public void shouldGiveManhattanOfZeroWhenAllBlocksCorrect() {

        // given
        final int expectedDimension = StdRandom.uniform(2, 127);
        final int[][] initState = createCompleteBoard(expectedDimension);
        underTest = new Board(initState);

        // when
        final int manhattan = underTest.manhattan();

        // then
        assertThat(manhattan, is(0));
    }

    @Test
    public void shouldGiveCorrectManhattanWhenSingleBlockIsIncorrect() {

        // given
        final int[][] initState = {{2, 1}, {3, 0}};
        underTest = new Board(initState);

        // when
        final int manhattan = underTest.manhattan();

        // then
        assertThat(manhattan, is(2));
    }

    @Test
    public void shouldGiveCorrectManhattanForPuzzle04() {

        // given
        final int[][] initState = createPuzzle04();
        underTest = new Board(initState);

        // when
        final int manhattan = underTest.manhattan();

        // then
        assertThat(manhattan, is(4));
    }

    private static int[][] createPuzzle04() {

        return new int[][]{{0, 1, 3}, {4, 2, 5}, {7, 8, 6}};
    }

    @Test
    public void shouldGiveCorrectManhattanWhenCornersAreSwapped() {

        // given
        final int dimension = 10;
        final int[][] initState = createCompleteBoard(dimension);
        swapBlocks(initState, 0, 0, dimension-1, 0); // top left with bottom left
        swapBlocks(initState, 0, dimension-1,
                   dimension-1, dimension-1); // top right with bottom right
        underTest = new Board(initState);
        final int expectedManhattan = 9 * 3;

        // when
        final int manhattan = underTest.manhattan();

        // then
        assertThat(manhattan, is(expectedManhattan));
    }

    @Test
    public void shouldReturnTrueIfAllBlocksCorrect() {

        // given
        final int dimension = StdRandom.uniform(2, 127);
        final int[][] initState = createCompleteBoard(dimension);
        underTest = new Board(initState);

        // when
        final boolean goal = underTest.isGoal();

        // then
        assertThat(goal, is(true));
    }

    @Test
    public void shouldReturnFalseIfAnyBlockIncorrect() {

        // given
        final int dimension = StdRandom.uniform(2, 127);
        final int[][] initState = createCompleteBoard(dimension);
        int swaps = swapRandomBlocksFromPairsOfRows(dimension, initState);
        underTest = new Board(initState);

        // when
        final boolean goal = underTest.isGoal();

        // then
        assertThat(goal, is(false));
    }

    @Test
    public void shouldCreateTwin() {

        // given
        final int dimension = StdRandom.uniform(2, 127);
        final int[][] initState = createCompleteBoard(dimension);
        underTest = new Board(initState);
        assertThat(underTest.isGoal(), is(true));
        assertThat(underTest.hamming(), is(0));

        // when
        final Board twin = underTest.twin();

        // then
        assertThat(twin, not(nullValue()));
        assertThat(twin.isGoal(), is(false));
        assertThat(twin.hamming(), is(2));
    }

    @Test
    public void shouldCreateTwinForPuzzle04() {

        // given
        final int[][] initState = createPuzzle04();
        underTest = new Board(initState);
        final int[][] twinState = {{0, 1, 3}, {2, 4, 5}, {7, 8, 6}};
        final Board expectedTwin = new Board(twinState);

        // when
        final Board twin = underTest.twin();

        // then
        assertThat(twin, is(expectedTwin));
    }

    @Test
    public void shouldCreateTwinWhereDifferenceIsValidMove() {

        // given
        final int[][] initState = {{0, 1}, {2, 3}};
        underTest = new Board(initState);
        final int[][] twinState = {{1, 0}, {2, 3}};
        final Board expectedTwin = new Board(twinState);

        // when
        final Board twin = underTest.twin();

        // then
        assertThat(twin, not(expectedTwin));
    }

    @Test
    public void shouldNotModifyOriginalWhenCreatingTwin() {

        // given
        final int dimension = StdRandom.uniform(2, 127);
        final int[][] initState = createCompleteBoard(dimension);
        underTest = new Board(initState);
        final boolean goal = underTest.isGoal();
        final int hamming = underTest.hamming();

        // when
        final Board twin = underTest.twin();

        // then
        assertThat(underTest.isGoal(), is(goal));
        assertThat(underTest.hamming(), is(hamming));
    }

    @Test
    public void shouldNotBeEqualIfNull() {

        // given
        final int dimension = StdRandom.uniform(2, 127);
        final int[][] initState = createCompleteBoard(dimension);
        underTest = new Board(initState);

        // when
        final boolean equal = underTest.equals(null);

        // then
        assertThat(equal, is(false));
    }

    @Test
    public void shouldBeEqualIfSymmetric() {

        // given
        final int dimension = StdRandom.uniform(2, 127);
        final int[][] initState = createCompleteBoard(dimension);
        underTest = new Board(initState);

        // when
        final boolean equal = underTest.equals(underTest);

        // then
        assertThat(equal, is(true));
    }

    @Test
    public void shouldBeEqualIfReflective() {

        // given
        final int dimension = StdRandom.uniform(2, 127);
        final int[][] initState = createCompleteBoard(dimension);
        underTest = new Board(initState);
        final Board that = new Board(initState);

        // when
        final boolean equal = underTest.equals(that);

        // then
        assertThat(equal, is(true));
    }

    @Test
     public void shouldBeEqualIfTransitive() {

        // given
        final int dimension = StdRandom.uniform(2, 127);
        final int[][] initState = createCompleteBoard(dimension);
        underTest = new Board(initState);
        final Board that = new Board(initState);
        final Board other = new Board(initState);
        assertThat(that.equals(other), is(true));

        // when
        final boolean equalThat = underTest.equals(that);
        final boolean equalOther = underTest.equals(other);

        // then
        assertThat(equalThat, is(equalOther));
    }

    @Test
    public void shouldNotBeEqualIfSameDimensionsButDifferent() {

        // given
        final int dimension = StdRandom.uniform(2, 127);
        final int[][] initState = createCompleteBoard(dimension);
        underTest = new Board(initState);
        swapBlocks(initState, 0, 0, 0, 1);
        final Board that = new Board(initState);

        // when
        final boolean equalThat = underTest.equals(that);

        // then
        assertThat(equalThat, is(false));
    }

    @Test
    public void shouldNotBeEqualIfDifferent() {

        // given
        final int[][] initState = createCompleteBoard(StdRandom.uniform(2, 50));
        underTest = new Board(initState);
        final int[][] initState2 = createCompleteBoard(StdRandom.uniform(50, 127));
        final Board that = new Board(initState2);

        // when
        final boolean equalThat = underTest.equals(that);

        // then
        assertThat(equalThat, is(false));
    }

    @Test
    public void shouldCreateNeighboursForTrivialCase() {

        // given
        final int zeroRow = 1;
        final int zeroCol = 1;
        final int[][] initState = createCompleteBoardWithZeroAt(3, zeroRow, zeroCol);
        underTest = new Board(initState);
        final NeighbourCreator expectedNeighbours =
                new NeighbourCreator(initState, zeroRow, zeroCol);
        expectedNeighbours.addNorth();
        expectedNeighbours.addEast();
        expectedNeighbours.addSouth();
        expectedNeighbours.addWest();

        // when
        final Iterable<Board> neighbours = underTest.neighbors();

        // then
        assertThat(neighbours, containsInAnyOrder(expectedNeighbours.toArray()));
    }

    @Test
    public void shouldCreateNeighboursWhenZeroInTopRow() {

        // given
        final int zeroRow = 0;
        final int zeroCol = 1;
        final int[][] initState = createCompleteBoardWithZeroAt(3, zeroRow, zeroCol);
        underTest = new Board(initState);
        final NeighbourCreator expectedNeighbours =
                new NeighbourCreator(initState, zeroRow, zeroCol);
        expectedNeighbours.addEast();
        expectedNeighbours.addSouth();
        expectedNeighbours.addWest();

        // when
        final Iterable<Board> neighbours = underTest.neighbors();

        // then
        assertThat(neighbours, containsInAnyOrder(expectedNeighbours.toArray()));
    }

    @Test
    public void shouldCreateNeighboursWhenZeroInLeftCol() {

        // given
        final int zeroRow = 1;
        final int zeroCol = 0;
        final int[][] initState = createCompleteBoardWithZeroAt(3, zeroRow, zeroCol);
        underTest = new Board(initState);
        final NeighbourCreator expectedNeighbours =
                new NeighbourCreator(initState, zeroRow, zeroCol);
        expectedNeighbours.addNorth();
        expectedNeighbours.addEast();
        expectedNeighbours.addSouth();

        // when
        final Iterable<Board> neighbours = underTest.neighbors();

        // then
        assertThat(neighbours, containsInAnyOrder(expectedNeighbours.toArray()));
    }

    @Test
    public void shouldCreateNeighboursWhenZeroInRightCol() {

        // given
        final int zeroRow = 1;
        final int zeroCol = 2;
        final int[][] initState = createCompleteBoardWithZeroAt(3, zeroRow, zeroCol);
        underTest = new Board(initState);
        final NeighbourCreator expectedNeighbours =
                new NeighbourCreator(initState, zeroRow, zeroCol);
        expectedNeighbours.addNorth();
        expectedNeighbours.addSouth();
        expectedNeighbours.addWest();

        // when
        final Iterable<Board> neighbours = underTest.neighbors();

        // then
        assertThat(neighbours, containsInAnyOrder(expectedNeighbours.toArray()));
    }

    @Test
    public void shouldCreateNeighboursWhenZeroInBottomRow() {

        // given
        final int zeroRow = 2;
        final int zeroCol = 1;
        final int[][] initState = createCompleteBoardWithZeroAt(3, zeroRow, zeroCol);
        underTest = new Board(initState);
        final NeighbourCreator expectedNeighbours =
                new NeighbourCreator(initState, zeroRow, zeroCol);
        expectedNeighbours.addNorth();
        expectedNeighbours.addEast();
        expectedNeighbours.addWest();

        // when
        final Iterable<Board> neighbours = underTest.neighbors();

        // then
        assertThat(neighbours, containsInAnyOrder(expectedNeighbours.toArray()));
    }

    @Test
    public void shouldCreateNeighboursWhenZeroInTopCorner() {

        // given
        final int zeroRow = 0;
        final int zeroCol = 0;
        final int[][] initState = createCompleteBoardWithZeroAt(3, zeroRow, zeroCol);
        underTest = new Board(initState);
        final NeighbourCreator expectedNeighbours =
                new NeighbourCreator(initState, zeroRow, zeroCol);
        expectedNeighbours.addEast();
        expectedNeighbours.addSouth();

        // when
        final Iterable<Board> neighbours = underTest.neighbors();

        // then
        assertThat(neighbours, containsInAnyOrder(expectedNeighbours.toArray()));
    }

    @Test
    public void shouldCreateNeighboursWhenZeroInBottomRight() {

        // given
        final int zeroRow = 2;
        final int zeroCol = 2;
        final int[][] initState = createCompleteBoardWithZeroAt(3, zeroRow, zeroCol);
        underTest = new Board(initState);
        final NeighbourCreator expectedNeighbours =
                new NeighbourCreator(initState, zeroRow, zeroCol);
        expectedNeighbours.addNorth();
        expectedNeighbours.addWest();

        // when
        final Iterable<Board> neighbours = underTest.neighbors();

        // then
        assertThat(neighbours, containsInAnyOrder(expectedNeighbours.toArray()));
    }

    @Test
    public void shouldCreateCorrectStringRepresentation() {

        // given
        final int[][] initState = createCompleteBoard(3);
        underTest = new Board(initState);
        final StringBuilder expectedString = new StringBuilder(50);
        expectedString.append("3\n");
        expectedString.append(" 1 2 3\n");
        expectedString.append(" 4 5 6\n");
        expectedString.append(" 7 8 0\n");

        // when
        final String str = underTest.toString();

        // then
        assertThat(str, is(expectedString.toString()));
    }

    @Test
    public void shouldCreateCorrectStringRepresentation2() {

        // given
        final int[][] initState = {{0, 2, 3}, {7, 8, 6}, {5, 1, 4}};
        underTest = new Board(initState);
        final StringBuilder expectedString = new StringBuilder(50);
        expectedString.append("3\n");
        expectedString.append(" 0 2 3\n");
        expectedString.append(" 7 8 6\n");
        expectedString.append(" 5 1 4\n");

        // when
        final String str = underTest.toString();

        // then
        assertThat(str, is(expectedString.toString()));
    }

    private void createBoardWith2SwappedBlocks() {

        final int dimension = StdRandom.uniform(2, 127);
        final int[][] initState = createCompleteBoard(dimension);
        final int row = StdRandom.uniform(1, dimension-1);
        final int col = StdRandom.uniform(1, dimension-1);
        swapBlocks(initState, 0, 0, row, col);
        underTest = new Board(initState);
    }

    // swap a random val in row 0 with one in row N, repeat for 1 and N-1 etc
    private static int swapRandomBlocksFromPairsOfRows(int dimension, int[][] initState) {

        final int midPoint = dimension / 2;
        // doesn't matter if odd leads to missed row since swaps are counted
        int swaps = 0;
        for (int i = 0; i < midPoint; i++) {
            final int destColLimit;
            if (i == 0) {
                destColLimit = dimension - 1;
            }
            else {
                destColLimit = dimension;
            }
            final int srcCol = StdRandom.uniform(0, dimension);
            final int destCol = StdRandom.uniform(0, destColLimit);
            swapBlocks(initState, i, srcCol, (dimension-1)-i, destCol);
            swaps += 2;
        }
        return swaps;
    }

    private static int[][] swapBlocks(int[][] blocks,
                            int srcRow, int srcCol,
                            int destRow, int destCol) {

        final int srcVal = blocks[srcRow][srcCol];
        blocks[srcRow][srcCol] = blocks[destRow][destCol];
        blocks[destRow][destCol] = srcVal;
        return blocks;
    }

    private static int[][] createCompleteBoard(int dimension) {

        return createCompleteBoardWithZeroAt(dimension, dimension-1, dimension-1);
    }

    private static int[][] createCompleteBoardWithZeroAt(int dimension,
                                                  int zeroRow, int zeroCol) {

        final int[][] blocks = new int[dimension][dimension];
        for (int i = 0, count = 1; i < blocks.length; i++) {

            for (int j = 0; j < blocks.length; j++) {
                if (i == zeroRow && j == zeroCol) {
                    blocks[i][j] = 0;
                }
                else {
                    blocks[i][j] = count++;
                }
            }
        }
        return blocks;
    }

    private static int[][] createDeepCopy(final int[][] src) {

        final int[][] dest = new int[src.length][];
        for (int i = 0; i < src.length; i++) {

            dest[i] = Arrays.copyOf(src[i], src[i].length);
        }
        return dest;
    }

    private static class NeighbourCreator {

        private final Collection<Board> neighbours = new ArrayList<Board>(4);
        private final int[][] blocks;
        private final int zeroRow;
        private final int zeroCol;


        private NeighbourCreator(int[][] blocks, final int row, final int col) {
            this.blocks = blocks;
            this.zeroRow = row;
            this.zeroCol = col;
        }

        private void addWest() {
            neighbours.add(createBoardWithZeroMovedBy(0, -1));
        }

        private void addSouth() {
            neighbours.add(createBoardWithZeroMovedBy(1, 0));
        }

        private void addEast() {
            neighbours.add(createBoardWithZeroMovedBy(0, 1));
        }

        private void addNorth() {
            neighbours.add(createBoardWithZeroMovedBy(-1, 0));
        }

        private Board createBoardWithZeroMovedBy(final int zRowDelta,
                                                 final int zColDelta) {

            return new Board(
                    swapBlocks(createDeepCopy(blocks),
                            zeroRow, zeroCol, zeroRow+zRowDelta, zeroCol+zColDelta));
        }

        public Object[] toArray() {
            return neighbours.toArray();
        }
    }
}