I encountered a bit of code recently that screams out for refactoring. Problem is, I’m not sure of the most effective way to do this.
The context: this is a tic-tac-toe game that Paul Nelson and I paired on, in order to explore mobile device programming (Paul has an iPhone, I have a BlackBerry). Paul’s not here right now to pair, unfortunately, hence the blog request (a really slow way of virtual pairing).
Here’s the relevant code:
private boolean isRowWinner(int row) {
for (int column = 0; column < SIZE; column++)
if (grid[row] != currentPlayer)
return false;
return true;
}
private boolean isColumnWinner(int column) {
for (int row = 0; row < SIZE; row++)
if (grid[row] != currentPlayer)
return false;
return true;
}
private boolean isDescendingDiagonalWinner() {
for (int i = 0; i < SIZE; i++)
if (grid[i][i] != currentPlayer)
return false;
return true;
}
private boolean isAscendingDiagonalWinner() {
for (int i = 0; i < SIZE; i++)
if (grid[i][SIZE - 1 - i] != currentPlayer)
return false;
return true;
}
The field grid is simply a 3×3 matrix of Player references; Player is an enum; currentPlayer is a Player reference.
What’s the most effective way to simplify these four methods, seemingly rampant with duplication? I’m not looking for a “clever” solution; I’m looking for one that still retains high levels of expressiveness.
Comments
Adam Sroka July 29, 2008 at 10:10am
No test??? :-p
Bartosz Bańkowski July 29, 2008 at 10:33am
Here’s my refactoring. It removes duplications, but I’m not sure if it is more expressive.
private boolean isMarkedByCurrentPlayer(int row, int column) {
return grid[row] == currentPlayer;
}
private boolean isWinner(int a, int b, int bb) {
for (int i = 0; i < SIZE; i++) {
if (!isMarkedByCurrentPlayer(i * a, i * b + bb))
return false;
}
return true;
}
private boolean isWinner(int a, int b) {
return isWinner(a, b);
}
private boolean isRowWinner(int row) {
return isWinner(0, 1);
}
private boolean isColumnWinner(int column) {
return isWinner(1, 0);
}
private boolean isDescendingDiagonalWinner() {
return isWinner(1, 1);
}
private boolean isAscendingDiagonalWinner() {
return isWinner(1, -1, SIZE – 1);
}
posted by Bartosz Bańkowski : 7/29/2008 10:33:00 AM
Bartosz Bańkowski July 29 2008 at 10:36am
One mistake. Should be:
private boolean isWinner(int a, int b) {
return isWinner(a, b, 0);
}
Ah yes, tests… Of course there are tests. :-) But now you’ll probably want all of the code. I’ll post a zip file tonight, but here are the tests in raw form:
package domain;
import org.junit.*;
import static org.junit.Assert.*;
import static domain.Player.*;
public class GameTest {
private Game game;
@Before
public void initialize() {
game = new Game();
}
@Test
public void create() {
assertGrid0(” “); // using this form,
assertGrid1(” “); // source can be formatted,
assertGrid2(” “); // but still retain visual usefulness
assertFalse(game.isOver());
}
@Test
public void firstMoveAlwaysX() {
game.makeAMove(1, 1);
assertGrid0(” “);
assertGrid1(” X “);
assertGrid2(” “);
}
@Test
public void secondMoveMadeByY() {
game.makeAMove(1, 1);
game.makeAMove(1, 0);
assertGrid0(” “);
assertGrid1(“OX “);
assertGrid2(” “);
}
@Test
public void movesAlternateXandY() {
game.makeAMove(1, 1);
game.makeAMove(1, 0);
game.makeAMove(2, 0);
assertGrid0(” “);
assertGrid1(“OX “);
assertGrid2(“X “);
}
@Test
public void movesToTakenSquaresDisallowed() {
try {
game.makeAMove(1, 1);
game.makeAMove(1, 1);
} catch (IllegalMoveException expected) {
assertTrue(expected.getMessage().contains(“[1, 1]”));
assertGrid0(” “);
assertGrid1(” X “);
assertGrid2(” “);
}
}
@Test
public void xWinsByFillingTopRow() {
assertNonWinningMove(X, 0, 0);
assertNonWinningMove(O, 1, 0);
assertNonWinningMove(X, 0, 1);
assertNonWinningMove(O, 1, 1);
assertWinningMove(X, 0, 2);
assertGrid0(“XXX”);
assertGrid1(“OO “);
assertGrid2(” “);
}
@Test
public void oWinsByFillingTopRow() {
assertNonWinningMove(X, 1, 0);
assertNonWinningMove(O, 0, 0);
assertNonWinningMove(X, 1, 1);
assertNonWinningMove(O, 0, 1);
assertNonWinningMove(X, 2, 2);
assertWinningMove(O, 0, 2);
assertGrid0(“OOO”);
assertGrid1(“XX “);
assertGrid2(” X”);
}
@Test
public void oWinsByFillingAnyRow() {
assertNonWinningMove(X, 1, 0);
assertNonWinningMove(O, 2, 0);
assertNonWinningMove(X, 1, 1);
assertNonWinningMove(O, 2, 1);
assertNonWinningMove(X, 0, 2);
assertWinningMove(O, 2, 2);
assertGrid0(” X”);
assertGrid1(“XX “);
assertGrid2(“OOO”);
}
@Test
public void completedMixedRowNotAWin() {
assertNonWinningMove(X, 0, 0);
assertNonWinningMove(O, 0, 1);
assertNonWinningMove(X, 0, 2);
}
@Test
public void xWinsByFillingFirstColumn() {
assertNonWinningMove(X, 0, 0);
assertNonWinningMove(O, 2, 1);
assertNonWinningMove(X, 1, 0);
assertNonWinningMove(O, 2, 2);
assertWinningMove(X, 2, 0);
assertGrid0(“X “);
assertGrid1(“X “);
assertGrid2(“XOO”);
}
@Test
public void oWinsByFillingAnyColumn() {
assertNonWinningMove(X, 0, 0);
assertNonWinningMove(O, 2, 1);
assertNonWinningMove(X, 1, 0);
assertNonWinningMove(O, 1, 1);
assertNonWinningMove(X, 1, 2);
assertWinningMove(O, 0, 1);
assertGrid0(“XO “);
assertGrid1(“XOX”);
assertGrid2(” O “);
}
@Test
public void xWinsByFillingDescendingDiagonal() {
assertNonWinningMove(X, 0, 0);
assertNonWinningMove(O, 0, 1);
assertNonWinningMove(X, 1, 1);
assertNonWinningMove(O, 0, 2);
assertGrid0(“XOO”);
assertGrid1(” X “);
assertGrid2(” “);
assertWinningMove(X, 2, 2);
}
@Test
public void yWinsByFillingAscendingDiagonal() {
assertNonWinningMove(X, 0, 0);
assertNonWinningMove(O, 0, 2);
assertNonWinningMove(X, 0, 1);
assertNonWinningMove(O, 1, 1);
assertNonWinningMove(X, 1, 0);
assertGrid0(“XXO”);
assertGrid1(“XO “);
assertGrid2(” “);
assertWinningMove(O, 2, 0);
}
@Test
public void draw() {
assertNonWinningMove(X, 0, 0);
assertNonWinningMove(O, 0, 2);
assertNonWinningMove(X, 1, 2);
assertNonWinningMove(O, 1, 1);
assertNonWinningMove(X, 0, 1);
assertNonWinningMove(O, 2, 1);
assertNonWinningMove(X, 2, 0);
assertNonWinningMove(O, 1, 0);
assertGrid0(“XXO”);
assertGrid1(“OOX”);
assertGrid2(“XO “);
game.makeAMove(2, 2);
assertTrue(game.isOver());
assertEquals(Player.NO_ONE, game.winner());
}
private void assertNonWinningMove(Player player, int row, int col) {
assertEquals(player, game.currentPlayer());
game.makeAMove(row, col);
assertFalse(moveString(row, col) + ” unexpectedly completed game”, game.isOver());
}
private void assertWinningMove(Player winner, int row, int col) {
assertEquals(winner, game.currentPlayer());
game.makeAMove(row, col);
assertTrue(moveString(row, col) + ” unexpectedly did not win game”, game.isOver());
assertEquals(winner, game.winner());
}
private void assertGrid0(String row) {
assertRow(row, 0);
}
private void assertGrid1(String row) {
assertRow(row, 1);
}
private void assertGrid2(String row) {
assertRow(row, 2);
}
private void assertRow(String row, int rowIndex) {
for (int colIndex = 0; colIndex < row.length(); colIndex++) {
Player player = Player.toEnum(row.charAt(colIndex));
assertEquals(moveString(rowIndex, colIndex), player, game.square(rowIndex, colIndex));
}
}
private String moveString(int rowIndex, int colIndex) {
return “move at [” + rowIndex + “,” + colIndex + “]”;
}
}
Bartosz–I have two failing tests after applying your code. Email me and I’ll send the code back. I like where it’s headed but it needs better names for the variables, and some of the magic numbers need explanation.
Bartosz Bańkowski July 29, 2008 at 11:11am
So, it’s the next proof of refactoring without tests being a bad idea (or refactoring with tests written after, because that is what I did).
private static final int[] COLUMN = new int[] { 1, 0, 0 };
private static final int[] ROW = new int[] { 0, 1, 0 };
private static final int[] ASC_DIAGONAL = new int[] { 1, -1, SIZE – 1 };
private static final int[] DESC_DIAGONAL = new int[] { 1, 1, 0 };
private boolean isMarkedByCurrentPlayer(int row, int column) {
return grid[row] == currentPlayer;
}
<code language="javascript">
</code>
private boolean isWinner(int row, int column, int[] corr) {
for (int i = 0; i < SIZE; i++) {
if (!isMarkedByCurrentPlayer(row + i * corr[0], column + i * corr[1] + corr[2]))
return false;
}
return true;
}
public boolean isRowWinner(int row) {
return isWinner(row, 0, ROW);
}
public boolean isColumnWinner(int column) {
return isWinner(0, column, COLUMN);
}
public boolean isDescendingDiagonalWinner() {
return isWinner(0, 0, DESC_DIAGONAL);
}
public boolean isAscendingDiagonalWinner() {
return isWinner(0, 0, ASC_DIAGONAL);
}
Still, some magic numbers could be removed.
George Dinwiddie July 29, 2008 at 11:56pm
Jeff, I couldn’t figure out how to leave a trackback, but I posted my solution at http://blog.gdinwiddie.com/2008/07/29/tictactoe/ rather than put into a comment here. I went for a table-driven design.
George Dinwiddie July 30, 2008 at 12:00am
Ah, it appears that the trackback is automatic.
Curious Attempt Bunny July 30, 2008 at 12:49am
+1 for Adam’s solution -1 for Adam’s variable naming -1 for Jeff’s obscure test
Bunny–I think that’s Bartosz’s nice solution, not Adams.
Talk about the obscurity of the tests. What would make for less obscure tests? My pair and I thought it was about the easiest way possible to follow the tests–a number of one-liners to represent each move, and a visual set of assertions to show the resulting board.
George–I think Paul and I had discussed a couple similar solutions. For tic-tac-toe, that one’s a nice idea. What if it’s a game like connect 4?
George Dinwiddie July 30, 2008 at 05:43pm
Jeff, for larger boards like Connect 4, I don’t think I would use the table lookup, as it would be rather large. Even with automated generation of the table, there would be significant penalty from overlapping winning patterns.
I’ve not tried it, but it occurs to me that it might be worthy to have a table of straight-line paths, and then traverse those paths counting the consecutive squares of the same player. These straight-line paths could be arrays of Positions.
I think a contributing factor to the need for refactoring in the isXyzWinner() methods is that the concept of Position is implicit, rather than explicit. It’s made of separate row and column values. This requires the code that deals with positions to know how they connect with each other. By pushing these details out, the code is required to handle the variations in the way rows and columns are traversed. By expressing the locations as Positions, the code just needs to deal with sequences of positions.
George Dinwiddie July 31, 2008 at 06:17am
The straight-line paths I describe above for Connect 4 are really the same thing as the winning paths used in my Tic Tac Toe solution.
It also occurs to me that Path could be a class, itself. It could be initialized with a starting Position and x and y increments for a step along the path. It could also provide an iterator to allow walking through the Positions of the path checking it against the win criteria.
This is another possible implementation of separating the navigation across the board from the evaluation of the winning condition.
J. B. August 1, 2008 at 08:27pm
I didn’t look at the other solutions, so this might be a duplicate, but I would probably do this:
-
Unroll the loops in each of the four methods.
-
Inline the four methods.
-
Tease apart the duplication in the resulting mess.
In my experience, a more incremental approach, like inlining two of the methods then removing duplication, leads me down ratholes, so I prefer the break-it-all-down-then-build-it-back-up approach.
Pingback: George Dinwiddie's blog » TicTacToe
