Angel "Java" Lopez

NET, Java, PHP y Desarrollo de Software

This Blog

Syndication

Search

Tags

Community

Email Notifications

Archives

.NET

ASP.NET

Windows Form

VB.NET

C#

Sitios

Blogs

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

Published Sun, Jun 23 2013 18:07 by lopez

Comments

# TDD Kata (4): La cortadora de césped@ Sunday, July 07, 2013 12:51 PM

Anterior Post Siguiente Post Como comentaba en el anterior post, hace una semana participé de

Angel "Java" Lopez

# TDD Kata (6): Ojos de Buey@ Sunday, July 07, 2013 1:00 PM

Anterior Post Ya en la ronda 1A Google Code Jam de este año, me encontré con este problema: https://code

Angel "Java" Lopez

Leave a Comment

(required) 
(required) 
(optional)
(required) 
If you can't read this number refresh your screen
Enter the numbers above: