Making Good Software

A blog by Alberto G (Alberto Gutierrez)

Archive for March, 2011

The obsession with beautiful code, the refactor syndrome.

with 18 comments

There is lately an emerging obsession with beatiful code, up to the point where some programmers are overprioritizing it over more important goals such as:

  • Correctness
  • Robustness
  • Traceability
  • Supportability

When this is taken to the extreme, and all that the programmer cares about is the beauty of the code, can cause him/her to fall under the refactor syndrome.

The refactor syndrome has the following symptoms:

And usually causes:

  • An explosion of services, managers, helpers or other utility like classes.
  • Integration bugs.
  • Lack of robustness.
  • Loss of productivity.

The main issue with the refactoring syndrome is that is based in the beauty of the code, and this, upfront, has three big issues.

  1. Not achievable. All code is crap. This is one of my favorite quotes, and to me is proven by the following facts:
    • Exclusion principle. All programmers tend to think that only their code is the only good code in the universe.
    • Legacy code principle. As a programmer, as you learn new stuff, you even consider your not so new code to be crap.
    • Experience principle.I have never seen, or produced any real code which I thought it was beautiful.
  2. Not so important. Even if beatiful code was achievable, it doesn’t prove that the code is correct, and among other things, correctness is way more important than beauty.
  3. Wrong perspective. Focusing in the code itself, and not in the application makes the programmer forget about other more important areas.

This refactor syndrome seems to be associated with some programmers taking the last agile tendencies as religious dogmas. This happens when programmers confuse the tools and engineering practies like TDD, refactoring, pairing and unit testing… with what needs to be achieved. This would be comparable to a builder who believes that having shiny, new and clean tools, is more important than the house he is building.

It is important to understand that none of the tools or engineering process that the different agile family of processes propose are bad per se, they are usually great. Is just that when we decide to overuse them that we might be getting close to the refactoring syndrome.

In summary, is important to remember that:

  1. It is not important how beatiful is your code if it doesn’t work.
  2. Refactor only when is necessary, not only when you don’t like the code or you think you are going to make it more beatiful. Not liking something IS NOT a reason enough to change it.
  3. Unit tests have very limited value when it comes to integration and end to end issues. Do real end to end test!!
  4. Know all the different tools and engineering practices, but don’t take them as dogmas, learn what is good and bad from each and apply them when necessary.
  5. Good programmers are gonna keep doing good software, bad programmers are gonna keep doing bad software, no matter what processes they follow.

Update

Apparently this article is causing some controversy, so I want to make clear some points which I see after the comments I didn’t made clear enough.

  1. I do think that Unit Test is great, I just want to point out that it CAN’T and it SHOULDN’T pretend to substitute integration and end to end test from the developer.
  2. When I say that a bad programmer is going to write bad software, no matter what process he follows, I didn’t mean to say as in, a bad programmer also will always be a bad programmer, we all have been very bad programmers when we started, and we only hope that we improve as we aquire more experience.

Written by Alberto Gutierrez

March 27th, 2011 at 12:19 pm

Solving Sudokus with Java and tree data structures

with one comment

A few weeks ago I published Java and tree data structures a post where I mentioned that I would try to put together some code to handle tree data structures… Well, this is the first installment of what I hope it will become a series of articles/code that will look into creating this tree library.

This first article/code is going to be about building trees dynamically. It is going to be illustrated by an example on how to use dynamic tree building to find the solution for a Sudoku. All the source code is available for downloading in a SVN repository, the URLs are:

Tree source code: https://subversion.assembla.com/svn/making-good-software/trunk/mgsTrees
Sudoku source code: https://subversion.assembla.com/svn/making-good-software/trunk/mgsSudoku

Dynamic tree building to find a solution

One widely used technique in computer science is to use a tree data structure to find the solution for something that needs to be solved but which solution is not obvious and requires many steps. One example could be chess, or a puzzle, a crossword, or like in this case, a sudoku.

The premise is simple, given an initial state, start building a tree of developed states from this original step until we find the state we were looking for. In the specific case of a sudoku, start building a tree where the branches are the different valid developments for that sudoku and stop when we find the solution.

The key element for building a tree dynamically is recursivity, starting from the original state, we find what the next candidate are, and them we do the same with each of them. In the mgsTrees library this can be easily accomplished by implementing an interface:

public interface ExpandTreeStrategy<T> {
	public ExpandAction<T> expand (T toExpand);
}

The return type of the ExpandTreeStrategy is an ExpandAction. An ExpandAction has 3 flavors.

  • stopBranch: It signals that this node is not expandable. In the Sudoku solver this is used when an ilegal Sudoku is reached.
  • stopTree: It signals that is not necessary to keep building the tree. In the sudoku solver this is used when the solution is found.
  • continueWith: This is used to specify what are the next states to look at. In the sudoku solver this is used when a intermediate sudoku is reached to specify what the next candidates are.

This is how to create the ExpandTreeStrategy Implementation for the Sudoku solver.

public class ExpandSudokuLookingForSolutionStrategy implements ExpandTreeStrategy<Sudoku> {
	private final SudokuAnaliser sudokuAnaliser;

	public ExpandSudokuLookingForSolutionStrategy(SudokuAnaliser sudokuAnaliser) {
		this.sudokuAnaliser = sudokuAnaliser;
	}

	@Override
	public ExpandAction<Sudoku> expand(Sudoku toExpand) {
		SudokuAnalysis sudokuAnalysis = sudokuAnaliser.analise(toExpand) ;
		
		if (sudokuAnalysis.isSolved()) return ExpandAction.stopTree ();
		if (! sudokuAnalysis.isLegal()) return ExpandAction.stopBranch ();
		
		if (sudokuAnalysis.hasDirectSolutions()) {
			return continueWithSudokuWithAllDirectSolutionsFilled(sudokuAnalysis);
		} else if (sudokuAnalysis.hasNextCandidates()){
			return continueWithSudokuVariantsForSquareLocationWithLessPossibleValues(sudokuAnalysis);
		}else{
			throw new RuntimeException("Is not possible to have a sudoku not solved, legal and without direct soluctions or candidates");
		}		
	}

	private ExpandAction<Sudoku> continueWithSudokuVariantsForSquareLocationWithLessPossibleValues(SudokuAnalysis sudokuAnalysis) {
		List<SudokuMovement> movements = sudokuAnalysis.getPossibleMovementsForSquareWithLessPossibleValues();
		List <Sudoku> nextSudokus = new ArrayList<Sudoku>();
		for (SudokuMovement movement : movements) {
			nextSudokus.add(sudokuAnalysis.getSudoku().with(movement));
		}
		return ExpandAction.continueWith(nextSudokus);
	}

	private ExpandAction<Sudoku> continueWithSudokuWithAllDirectSolutionsFilled(SudokuAnalysis sudokuAnalysis) {
		List<SudokuMovement> movements = sudokuAnalysis.getAllDirectSolutionMovements();
		return ExpandAction.continueWith(sudokuAnalysis.getSudoku().with(movements));
	}
}

At the end the entire tree building logic is wired in the TreeFactory class, which has a method, buildTree, that takes the starting point for the tree, and which constructor takes the ExpandStrategy to be used to build the tree. The result of this call is a TreeResult, which contains three main methods;

  • getTree(): The resulting tree
  • isBuildInterrupted(): Will tell you if the build is interrupted, in the case of the SudokuSolver this would mean that the solution was found.
  • getLastBranch(): A sequential ordered list of all the last branch nodes startging from the root node, the original node. In the case of the sudoku solver this is used to retrieve in case that the solution is found (isBuildInterrupted == true) the sequence of Sudokus from the original one to the solution.
public class TreeFactory<T> {
	private final ExpandTreeStrategy<T> expandTreeStrategy;
	
	public TreeFactory(ExpandTreeStrategy<T> expandTreeStrategy) {
		this.expandTreeStrategy = expandTreeStrategy;
	}
	
	public TreeResult<T> buildTree (T seed){
		System.out.println(seed);
		ExpandAction<T> expandActionResult = expandTreeStrategy.expand (seed);
		if (expandActionResult.isStopBranch ())	return TreeResult.stopBranch (seed);
		if (expandActionResult.isStopTree ()) return TreeResult.stopTree (seed);
		
		Node<T> rootNode = new Node<T> (seed);
		List<Node<T>> currentBranch = new ArrayList<Node<T>>();
		currentBranch.add(rootNode);
		
		Iterator<T> childIterator = expandActionResult.getChildIterator();
		TreeResult<T> lastSubTreeResult = null;
		while (childIterator.hasNext()){
			Node<T> next = new Node<T> (childIterator.next());
			lastSubTreeResult = buildTree(next.getContent());
			rootNode.addChild(lastSubTreeResult.getTree().getRootNode());
			if (lastSubTreeResult.isBuildInterrupted()) {
				currentBranch.addAll(lastSubTreeResult.getLastNodeBranch());
				return TreeResult.interrupt (rootNode, currentBranch);
			}
		}
		
		currentBranch.addAll(lastSubTreeResult.getLastNodeBranch());
		return TreeResult.buildCompleted (rootNode, currentBranch);
	}
}

The final code to solve any given Sudoku will look like:

public static void main(String[] args) {
		Sudoku sudoku = new Sudoku(
			new SquareValue [][]{
				{__, __, __, 	__, __, __, 	_6, __, __},
				{__, __, _3, 	_7, __, __, 	__, __, _1},
				{__, _8, __, 	_1, __, _6, 	_9, _4, __},
				
				{_7, __, __, 	_5, __, __, 	__, __, __}, 
				{__, __, _5, 	__, _4, __, 	_8, __, __},
				{__, __, __, 	__, __, _2, 	__, __, _7},
				
				{__, _2, _9, 	_6, __, _4, 	__, _3, __},
				{_6, __, __, 	__, __, _8, 	_4, __, __},
				{__, __, _4, 	__, __, __, 	__, __, __}
			}
		);
		
		IteratorStrategy rowNavigator = OneLineIteratorStrategy.horizontal();
		IteratorStrategy columnNavigator = OneLineIteratorStrategy.vertical();
		IteratorStrategy matrixNavigator = MatrixIteratorStrategy.instance();
		SudokuProcessor sudokuProcessor = new SudokuProcessorImpl(rowNavigator, columnNavigator, matrixNavigator);
		SudokuAnaliser sudokuAnaliser = new SudokuAnaliserImpl(sudokuProcessor );
		ExpandTreeStrategy<Sudoku> expandTreeStrategy = new ExpandSudokuLookingForSolutionStrategy(sudokuAnaliser);
		TreeFactory<Sudoku> treeFactory = new TreeFactory<Sudoku>(expandTreeStrategy);
		
		TreeResult<Sudoku> buildTree = treeFactory.buildTree(sudoku);
		List<Sudoku> lastBranch = buildTree.getLastBranch();
		System.out.println("Solution: " + lastBranch.get(lastBranch.size()-1));
	}

Written by Alberto Gutierrez

March 19th, 2011 at 9:32 am