Angel \”Java\” Lopez on Blog

June 30, 2013

TDD Kata (5): Tree Search

Filed under: .NET, Agile Software Devevelopment, C Sharp, Test-Driven Development — ajlopez @ 3:28 pm

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 Comments »

  1. […] Previous Post Next Post […]

    Pingback by TDD Kata (4): Lawnmover | Angel "Java" Lopez on Blog — June 30, 2013 @ 3:30 pm

  2. […] TDD Kata (5): Tree Search […]

    Pingback by TDD Kata (5): Tree Search | MVPs de LATAM — July 2, 2013 @ 3:04 pm

  3. […] [complete] repo – New posts about RubySharp [pending] – New posts about TDD [complete] post post – New posts about Mass […]

    Pingback by New Month’s Resolutions: July 2013 | Angel "Java" Lopez on Blog — July 5, 2013 @ 4:03 pm

  4. […] repo – Nuevo post sobre RubySharp [pendiente] – Nuevo post sobre TDD [completo] post post – Nuevo post sobre lenguaje Mass […]

    Pingback by Resoluciones del Nuevo Mes: Julio 2013 - Angel "Java" Lopez — July 6, 2013 @ 5:44 pm

  5. […] Previous Post […]

    Pingback by TDD Kata (6): Bulleyes | Angel "Java" Lopez on Blog — July 14, 2013 @ 6:53 pm

  6. […] Previous Post […]

    Pingback by TDD Kata (6): Bulleyes | MVPs de LATAM — July 15, 2013 @ 5:52 pm


RSS feed for comments on this post. TrackBack URI

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

The Shocking Blue Green Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 65 other followers

%d bloggers like this: