TDD Kata (5): Búsqueda en Arbol

Anterior Post 
Siguiente Post 


Hace ya unos meses, me topé con este mensaje en la lista de TDD en inglés:


Implementation of game tree search using TDD
http://tech.groups.yahoo.com/group/testdrivendevelopment/message/35419


Leo:


I am trying to use TDD to implement game tree searching but I am running
into some issues.Using C#, MS Test and Rhino Mocks.
My requirement is to traverse a tree to a specified depth and find the
maximum value of the nodes at this depth. If a path ends before the
specified depth then the value of the last node in the path should be
considered.
Sample usage looks like this:
var depth = 5;
var tree = new GameTree();
var treeSearch = new TreeSearch();var maxValue =
treeSearch.FindMaxValue(tree, depth);


Los primeros tests que se plantea el autor del mensaje:


* A search to depth zero should return the value of the root node
* A search to depth one with no children should return the value of
the root node
* A search to depth one with one child should return the value of the
child
* A search to depth one with two children should return the highest
value of the two children
* A search to depth one of a tree with depth two should return the
maximum value at depth one


Hasta ahí, todo bien, pero:


Up to this point the tests are simple enough and mocking of the tree is
simple. The last test starts driving towards a depth first tree
traversal.Now I start on depth 2 tests which should drive the rest of
the tree traversal algorithm:
* A search to depth two should return the maximum value at depth two
I decided to mock a complete binary tree with depth 2


El problema es tratar de mockear todo eso. Ni lerdo ni perezoso, me puse a resolver el tema, sin usar mocks, simplemente implementando un árbol que sirva de base para todo lo demás:


https://github.com/ajlopez/TddOnTheRocks/tree/master/GameTreeSearch


Queda una solución simple:



Pueden ver la historia del desarrollo en:


https://github.com/ajlopez/TddOnTheRocks/commits/master/GameTreeSearch


Al final, todos los tests en verde:



Lección aprendida: a veces (muchas veces ;-) es más fácil implementar algo, que armar un mock. El árbol que implementé luego puede ser refinado, extraer alguna interfaz, implementarlo de otras formas, etc. Pero sirvió de pilar para armar el algoritmo usando TDD.


Nos leemos!


Angel “Java” Lopez
http://www.ajlopez.com
@ajlopez

This entry was posted in 10549, 11699, 1389, 5374. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>