TDD Kata (5): Tree Search

Previous Post
Next Post

Some months ago, I read this message in a TDD list:

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

I read:

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

The first tests to implement:

* 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

All right, but:

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

The problem is the use of mocks: it complicates the solution. So, I started to solve the problem, without mocks, simply using a tree implementation to use as a base for other tests:

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

The solution is simple:

You can see the history of development at:

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

All tests are green:

Lesson learnt: some times (many times 😉 is easier to implement something concrete than build a mock. The tree I implemented could be refined, could be the base for an interface extraction, or could be implemented in other ways. But it served as a base for our search algorithm, using TDD.

Keep tuned!

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

6 thoughts on “TDD Kata (5): Tree Search

  1. Pingback: TDD Kata (4): Lawnmover | Angel "Java" Lopez on Blog

  2. Pingback: TDD Kata (5): Tree Search | MVPs de LATAM

  3. Pingback: New Month’s Resolutions: July 2013 | Angel "Java" Lopez on Blog

  4. Pingback: Resoluciones del Nuevo Mes: Julio 2013 - Angel "Java" Lopez

  5. Pingback: TDD Kata (6): Bulleyes | Angel "Java" Lopez on Blog

  6. Pingback: TDD Kata (6): Bulleyes | MVPs de LATAM

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s