Request for a Blog Pair

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.

Original Comments:

No test??? :-p

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

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 (this comment mechanism doesn’t allow pre tags):

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.

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

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.

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.

Ah, it appears that the trackback is automatic.

+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?

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.

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.

I didn’t look at the other solutions, so this might be a duplicate, but I would probably do this:

1. Unroll the loops in each of the four methods.
2. Inline the four methods.
3. 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.

Scrumalicious

The Scrum Yahoo! group is again undergoing some minor turbulence about proper use of the list. Someone from the Scrum Alliance laid out the law with a number of rules about what could and could not be posted to the list. Many people reacted poorly–supposedly this is the poster’s first post, and he’s not even a Certified Scrum Master (CSM). (gasp!)

Oddly, a year or so ago when there was similar agonizing over the use of the list, it appeared as if L. Ken Schwaber “owned” the Yahoo! group and thus controlled(an important word in the Scrum community) appropriate content. Not that there’s anything wrong with that. For those who like command & control, with the additional potential of being part of a good multi-level marketing machine, the Scrum system provides a wonderful starting point.

The nice thing is that you can still do Scrum and talk about Scrum without succumbing to the controlled community that is S©rum. As far as I know, there’s no licensing scheme required to be able to say, “I’m doing Scrum.” And that’s exactly what I’d recommend. No annual maintenance fee required! No required trainer tiering! Yes, you need a Scrum Master in order to successfully execute Scrum. But I don’t believe they must be “certified.” (I could be wrong–perhaps I need a lawyer here!)

Where might you find a good Scrum Master? Well, you should probably read L. Ken Schwaber’s book, Agile Project Management With Scrum (that link is my piece of the Scrum machine’s gravy train, by the way). You’ll quickly discover, through a number of case studies that L. relates, that Scrum and S©rum are mostly a matter of executing to common sense, best done by someone with good experience in people-oriented problem solving and leadership. Find someone who can do that well, and hire them. It really doesn’t matter if they’re a CSM.

The Realities of Test-After Development (aka Why POUT Sucks)

“Plain Old Unit Testing,” or “POUT,” implies that developers are coding unit tests, but they are not doing test-driven development (TDD). In other words, they are following the classic pattern of writing the code, then coming back and coding unit tests to verify the correctness of the code. Instead of POUT, I prefer the acronym TAD, or Test-After Development, which is always a “TAD” too late.

Why does it matter whether tests are written first or last? Theoretically, someone doing TAD could easily produce as high-quality a system with as comprehensive test coverage as produced via TDD. In reality, however, it never happens.

Here are some of the reasons why TAD sucks:

Doesn’t promote a testable design Most of the time, testability is in concert with notions of “good,” or sustainable, design (coupling and cohesion and all that). Usually, developers discover too late that their design isn’t testable. Most often in this case, they quickly give up on trying to test the code, Over time, sure, developers figure out how to produce a more testable design out of the gate, but it’s still never a certainty. The real problem is that almost no developer will go back and fix an untestable design in order to be able to write tests.
Is undisciplined No rule says that a developer must write tests. Good developers might write enough (usually they do not), but there are plenty of not-so-good developers that will use the lack of a standard as a quick excuse to write as few tests as possible.
Falls victim to ego “My sh*t don’t stink, I don’t need to bother with writing unit tests, so I’ll do the fewest that I can get away with.” Enough said. This attitude doesn’t belong in a professional development team, but it’s sadly common.
Appears unnecessary “I already proved that the code works, I loaded it up in the app server and tried it myself. Why would I bother writing unit tests now?”
Clashes with deadlines When it comes down to deadlines, managers will quickly say, “Never mind with the unit tests, we just have to ship this software.”
Decreases average coverage For many of the reasons already stated, the practical coverage ceiling for TAD is about 70%. This is based on lots of anecdotal evidence, often stated by TAD proponents themselves. I met with Agitar reps about 18 months ago; they confirmed that their TAD-tool (which generates unit tests automatically) has a comparable ceiling. No matter how TAD tests get there, the result is that up to 30% of your app remains unverified at the unit level. Maybe that’s not such a big deal if you have higher-level (integration) tests, but…
Doesn’t afford adequate refactoring If up to 30% of your app is not well-covered, that means you cannot safely and effectively refactor almost a third of your application. A third of your system will progressively get worse almost by definition.
Results in difficult tests Many TAD tests are closer to integration tests in nature. “Who cares,” say some of the TAD proponents, “about the distinction between unit tests and integration tests?” I don’t care about the semantic distinction either, but integration tests are harder to maintain, harder to comprehend, harder to use to pinpoint a problem, and slower.
Isn’t very enjoyable Few people enjoy writing unit tests; many people will claim that they love TDD. Honestly, it’s not very satisfying to spend time on unit tests when you’re pretty sure the code already works.
Questionable return on value TAD is expensive. If you have to choose between TAD and more end-to-end functional tests, dump the TAD.
Does nothing to advance the craft TAD is a haphazard approach. TAD proponents insist that we’re all smart enough to figure out what should be verified at the unit level, and what can be safely ignored. Reality tells us otherwise, but still, that choice may be acceptable in some shops. However, the industry has been screaming for a more disciplined approach to software development that can consistently produce higher code quality. Perhaps TDD isn’t it, but TAD most certainly ain’t it.

A TDD Contest

I love competition, and I suspect the majority of programmers do, too. I’ve met only a few very good programmers who weren’t into games or other forms of competition. I’ve also known a few developers whose egos exuded in everything they did, whether or not they’d admit it. These are the kinds who want to argue virtually every point that is made, not that there’s anything wrong with that. (Well, maybe there is–no one wants to feel like every one of their comments is possibly wrong.)

In listening to someone else’s contrarian nature take over, I often sit there and think, “We should just argue our respective positions in code.” Of course, I’m also thinking that “I can code this better than you can.”

The site TopCoder provides a place where money can be put in someone’s big mouth, but it’s not what I’m looking for. TopCoder is more a highly competitive marketplace, a great idea that appeals to my capitalistic nature. But it doesn’t appeal to the ego in me, nor does it appeal to my interest in TDD.

Rather, I’d prefer a competition that offers bragging rights. Not that I need to brag, but I would love some validation to my claims. I think as geeks we all like numbers, and I’d like to know if I am the best, or if I am only the 17th best.

So, a contest. Who is the most effective coder? Here are my thoughts for such a contest:

  • Devise a problem whose test-driven solution might take about 90 minutes
  • Insist that the problem be solved using some sort of solution recorder (maybe an IDE plugin); either that, or provide a proctoring mechanism. Unfortunately I’m not sure what the implication and cost of this is.
  • Award bonus points for early completion; subtract bonus points
  • Deduct points for deficiencies in solution–e.g. lack of test/code expressiveness, unnecessary duplication, etc.
  • Score tests using a panel of three or more judges

Could such a contest be used to determine a champion between TDD proponents and the rest of the world?

If I can get enough interest, I’ll happily run such a contest and offer up some kind of prize, although I’d just as soon participate in one. Step one involves getting feedback–are there enough fearless programmers who would participate? How would the judges come to at least some consensus on judging criteria?

Are you the best? Do you have any ideas about how to judge such a competition? Let me know.

Fine-Grained Incrementalism

Seeing a first-time demo of TDD, students inevitably ask, “do you really code that way?” The answer is yes, even after almost ten years of doing TDD.

They are of course asking, do I always code the simplest possible solution first, instead of just introducing the obvious solution, the one that I know I’m absolutely going to need in another five minutes? And the answer is still yes.

For example, when testing a container, the first test inquires whether or not it’s empty:

assertEquals(0, container.size());

and the passing implementation is:

int size() {
   return 0;
}

The next test usually involves adding an element to the container and asserting its size (which is of course only part of the complete verification):

container.add(element);
assertEquals(1, container.size());

Yes, I know I need a [hash map|array list|linked list|etc] in about 5 minutes. I still code:

void add(T element) {
   count = 1;
}

int size() {
   return count;
}

Not even a ++. That comes from writing a subsequent, failing assertion.

I offer many reasons:

  • It helps deeply ingrain the notion of incrementalism, which is at the heart of agile
  • It allows sustaining the fail-first, red-green rhythm, and thus keeps you out of trouble more often
  • Similarly, it allows adhering to the rule that insists on green bars every ten (five) minutes
  • It forces the addition of more assertions
  • It keeps with the spirit of YAGNI–sometimes you don’t end up needing what you think you will

This fine-grained incrementalism involves continual movement from the specific to the generalized: from hardcoded solutions to progressively-more-generalized solutions.

Fine-grained incrementalism is, as many things in software development, a tradeoff. It results in continual waste product, and thus a slower initial pace. A hardcoded value is discarded, and replaced with a counter, which too is soon discarded. But on the other side of this trade is the significant benefit of continual and consistent forward progress–“slow and steady wins the race.”

For the new TDD practitioner, and for even experienced TDD practitioners, it is very tedious and annoying. Often, developers simply discard rigid adherence to the practice. For an experienced TDD developer, that’s their prerogative, and I’ll admit that I have done so at times too.

For everyone else, I think it’s essential to first learn the value of something before discarding it. So I’ll define my use of “experienced TDD developer” in the prior paragraph as “someone who has not done enough fine-grained incremental development to understand how it helps.” Perhaps I’m slow–I still prefer to work this way.

A final justification (aka “the new thought” that entered my head this morning):

Yes, it’s slower, tedious, and produces continual waste, particularly as you build the rudiments of a class. But these complaints are focused at the early minutes in the lifetime of a class–a fraction of the effort and struggle involved with maintaining it. There’s a benefit I didn’t explicitly mention above, and that’s the ability to more easily and safely maintain a system, because of the increased number of assertion increments. The small amount of initial tedium is worth it.

Comments:

Even though the production code evolves slowly, and is continually reworked, expelling tiny bits of waste… The tests are real from the beginning. The simple minded, easy to get to solutions, prove that the test are right. These tests work and do their job while the production code evolves and gets more complex. It might seem like they slow you down in the beginning, but its these tests that keep you moving rapidly with confidence.

Jeff, you’re not slow. You are the fastest I’ve seen.

Thanks James, I particularly like the part about “moving rapidly with confidence.”

Hmm, someday I’d like to participate in a head-to-head speed-TDD challenge. Time to deliver is primary, but points would be taken off for insufficient tests, or inadequate refactoring.

Who else is fast?

Atom