Asp Forum - Newby Maze solution

Alex Combas

3/25/2006 10:58:00 AM

Hello folks,Tonight I tried out some of that good old extreme programming TDD stuffwith mixed results.I was initially surprised how much it helped get things started butI noticed after a while that it kind of petered out because I wasn'tsure just how to test the code that I was writing.Naturally, you will say, I should have kept to writing tests first.Well the damage is done. So now I would like to ask for suggestionson how to write a test for this code so I can learn for next time.Also, if I have done anything really stupid in the code and thereis a more rubyish way to do this please feel free to set me strait.Thank you very much!Here is my test:require 'test/unit'require 'Lab'class TestLab < Test::Unit::TestCase def setup@maze = <<MAZE_STRING##########################s--###----#####-#####-#####-#---##-##--#-##-----####-#-#-#--##-##-##-###-##---#-#-#-###-##-##-##--##-#---#-#---#-##----##-###-#-#-#-#-#-#-##-#########-#-#-#-#-#---##--------######-###---###########-######-#####-###########-######------------------e##########################MAZE_STRING @t = Tracker.new(@maze) end def test_grid assert_equal @maze[25].chr,"\n","uhoh" end def test_tracker assert_equal @t.track(@maze,27),28,"doesnt track" assert_equal @t.track(@maze,28),29,"doesnt track" endendAnd Now the Code:class Tracker def initialize(map) @forest = map end def track(path,mark) prey = '*-es' if prey.index(path[mark+1]) mark+1 elsif prey.index(path[mark+26]) mark+26 elsif prey.index(path[mark-1]) mark-1 elsif prey.index(path[mark-26]) mark-26 end end def get_it! for_teh_win = nil @s = @forest.index('s') until for_teh_win @s = track(@forest,@s) if @forest[@s].chr == 'e' for_teh_win = "WOOT!" else @forest[@s] = '*' end end puts @forest endendme = Tracker.new(maze)me.get_it!--Alex Combashttp://noodlej...

11 Answers

Jim Weirich

3/25/2006 1:32:00 PM

Alex Combas wrote:
> Hello folks,
> Tonight I tried out some of that good old extreme programming TDD stuff
> with mixed results.

Good for you! I've been using TDD for over 5 years and it has radically
changed the way I approach programming.

> I was initially surprised how much it helped get things started but
> I noticed after a while that it kind of petered out because I wasn't
> sure just how to test the code that I was writing.

As with all things, it helps to practice. The secret to TDD is learning
to let the tests drive the code. Never write code that isn't dictated
by a test somewhere.

So, with that in mind, I took your tests and threw away your tracker
program. I wrote a new tracker program entirely based on your test
code. The following program passes all the tests you supplied, with no
extra baggage:

class Tracker
def initialize(maze)
end
def track(maze, index)
index + 1
end
end

Hmmm ... doesn't look much like a maze solver, does it? Yet it does
pass the tests.

So, your next thought should be, what tests do I add to force me to
write code that will make this look more like a maze solver. The key is
to work with little bits of functionality at a time, so the problem is
never too hard all at once.

I would suggest that your current test is too complicated. I would
start off with the goal of writing a maze solver that can solve really
trivial mazes. For example, my first four tests would probably have it
solve the following four one step mazes:

#### ### #### ###
#se# #s# #es# #e#
#### #e# #### #s#
### ###

Then I would add tests to make sure it could solve multi-step mazes:

########
#s----e#
########

Then I would make sure it could solve mazes with corners.

######
#s---#
####-#
#-#
#e#
###

Then finally I would make sure it can solve mazes that involve possible
back tracking:

##### #####
#e--# #---#
###-# ###-#
#s--# #s--#
###-# ###-#
#---# #e--#
##### #####

At this point, I would suspect I have a fully general maze solver
(although by the time I actually reach this point, I may have discovered
other potential problems that may need further testing). I might be
ready to throw your test maze at the problem and see if it works.

The key is little steps that build upon the previous code base. Write a
test, write a little code. Write a new test, write more code. Repeat
until the problem is solved.

Sounds easy, and it is with practice. But it does take some experience
to get it down.

Good luck.

--
-- Jim Weirich

--
Posted via http://www.ruby-....

benjohn

3/25/2006 1:58:00 PM

On 25 Mar 2006, at 10:57, Alex Combas wrote:
> def test_tracker
> assert_equal @t.track(@maze,27),28,"doesnt track"
> assert_equal @t.track(@maze,28),29,"doesnt track"
> end

This is no use to you at all, but thank you for:

* Reminding me that Ruby doesn't need parenthesise; I like the
'assert_euqal's without them a lot.
* Showing me that 'assert_equal' (and the others, I'm sure) will
accept a third descriptive argument - I didn't know that, and I can
see it's useful!

I've just started trying to use TDD, and so far I am very impressed.
What I like about it is how much it makes me think about what I'm
doing, rather than how I'm going to do it. I can see that it is a
discipline that is going to need a lot of practice though; it's
already given me benefits, but I do find it hard at the moment.

Interestingly, there are a few things I've been trying to build
without TDD for a while. I've sat down and tried to do them with TDD,
and it has been very helpful, in that I've got no where :) Basically,
I've realised that I don't _really_ know what I'm trying to do; and I
need to know that before I can work out how to do it.

I think I also need to learn to be a bit less strict, and just get on
with it. Write a test for something that seems about right, and be
prepared to chuck it all out if I find I'm barking up the wrong tree,
or I've not quite got the right slant on what I'm trying to do.

Cheers,
Benjohn

Robert Dober

3/25/2006 2:07:00 PM

On 3/25/06, Benjohn Barnes <benjohn@fysh.org> wrote:
>
>
> On 25 Mar 2006, at 10:57, Alex Combas wrote:
> > def test_tracker
> > assert_equal @t.track(@maze,27),28,"doesnt track"
> > assert_equal @t.track(@maze,28),29,"doesnt track"
> > end
>
>
>
> * Showing me that 'assert_equal' (and the others, I'm sure) will
> accept a third descriptive argument - I didn't know that, and I can
> see it's useful!

It seems worth to notice that assert_equal will expect the test value to go
*after* the expected value.
It seemed counter intuitive to me too at first, so be warned.

assert_equal 1+1, 3, "arithmethic polarity"
will tell
<2> expected but was
<3>
obviously the contrary of what you want.

Cheers
Robert

--
Deux choses sont infinies : l'univers et la bêtise humaine ; en ce qui
concerne l'univers, je n'en ai pas acquis la certitude absolue.

- Albert Einstein

Michael Gorsuch

3/25/2006 2:12:00 PM

Not to hijack this thread, but can any of you recommend a specific
resource to learn more about TDD? I'm using by own breed, but I KNOW
that there are better ways to approach it.

Thanks,

Michael

On 3/25/06, Robert Dober <robert.dober@gmail.com> wrote:
> On 3/25/06, Benjohn Barnes <benjohn@fysh.org> wrote:
> >
> >
> > On 25 Mar 2006, at 10:57, Alex Combas wrote:
> > > def test_tracker
> > > assert_equal @t.track(@maze,27),28,"doesnt track"
> > > assert_equal @t.track(@maze,28),29,"doesnt track"
> > > end
> >
> >
> >
> > * Showing me that 'assert_equal' (and the others, I'm sure) will
> > accept a third descriptive argument - I didn't know that, and I can
> > see it's useful!
>
>
> It seems worth to notice that assert_equal will expect the test value to go
> *after* the expected value.
> It seemed counter intuitive to me too at first, so be warned.
>
> assert_equal 1+1, 3, "arithmethic polarity"
> will tell
> <2> expected but was
> <3>
> obviously the contrary of what you want.
>
> Cheers
> Robert
>
>
>
>
> --
> Deux choses sont infinies : l'univers et la bêtise humaine ; en ce qui
> concerne l'univers, je n'en ai pas acquis la certitude absolue.
>
> - Albert Einstein
>
>

Jim Weirich

3/25/2006 2:50:00 PM

Michael Gorsuch wrote:
> Not to hijack this thread, but can any of you recommend a specific
> resource to learn more about TDD? I'm using by own breed, but I KNOW
> that there are better ways to approach it.

Here are a few:

The Craftsman series from ObjectMentor:
http://www.objectmentor.com/resources/listArticles?key=topic&topic...

Ron Jeffries Book "Extreme Adventures in C#"
(http://www.xprogramming.com/xpmag/Books20040324.htm#book...).
Browse Ron's site for other goodies. Also, Ron's book "Extreme
Programming Installed" has a chapter or two on test driven programming.

Kent Beck's "Test Driven Development by Example"
(http://www.amazon.com/gp/product/0321146530/qid=1143298096/sr=2-2/ref=pd_bbs_b_2_2/102-1005843-6529767?s=books&v=glance&am...)

--
-- Jim Weirich

--
Posted via http://www.ruby-....

Christian Neukirchen

3/25/2006 2:58:00 PM

Jim Weirich <jim@weirichhouse.org> writes:

> I would suggest that your current test is too complicated. I would
> start off with the goal of writing a maze solver that can solve really
> trivial mazes. For example, my first four tests would probably have it
> solve the following four one step mazes:
>
> #### ### #### ###
> #se# #s# #es# #e#
> #### #e# #### #s#
> ### ###
>
> Then I would add tests to make sure it could solve multi-step mazes:
>
> ########
> #s----e#
> ########
>
> Then I would make sure it could solve mazes with corners.
>
> ######
> #s---#
> ####-#
> #-#
> #e#
> ###
>
> Then finally I would make sure it can solve mazes that involve possible
> back tracking:
>
> ##### #####
> #e--# #---#
> ###-# ###-#
> #s--# #s--#
> ###-# ###-#
> #---# #e--#
> ##### #####
>
> At this point, I would suspect I have a fully general maze solver
> (although by the time I actually reach this point, I may have discovered
> other potential problems that may need further testing). I might be
> ready to throw your test maze at the problem and see if it works.

I would at least add an maze with a loop, like:

########
####---#
#s---#-#
####---#
####-###
####--e#
########

> The key is little steps that build upon the previous code base. Write a
> test, write a little code. Write a new test, write more code. Repeat
> until the problem is solved.
>
> Sounds easy, and it is with practice. But it does take some experience
> to get it down.
>
> Good luck.
>
> --
> -- Jim Weirich
--
Christian Neukirchen <chneukirchen@gmail.com> http://chneuk...

Andrew Johnson

3/25/2006 3:30:00 PM

On Sat, 25 Mar 2006 22:32:16 +0900, Jim Weirich <jim@weirichhouse.org> wrote:

Jim writes:
> The secret to TDD is learning to let the tests drive the code.

And that's true of course, but it isn't the real secret...

Jim later tells us:
> The key is to work with little bits of functionality at a time, so the
> problem is never too hard all at once.

And that's true of course, but it isn't the real secret...

Jim then writes:
> I would start off with the goal of writing a maze solver that can solve
> really trivial mazes.

[ substitute "problem X" for "maze" for generality ]

And now we begin to close in on the real secret ...

Jim follows with:
> For example, my first four tests would probably have it solve the following
> four one step mazes:
>
> #### ### #### ###
> #se# #s# #es# #e#
> #### #e# #### #s#
> ### ###

And suddenly we have a trivial reduction of the problem that makes
all that follows simply seem a natural process. Once you see it, it even
feels trivial and obvious --- but don't kid yourself! What Jim makes
look so easy is no trivial task (and, of course, isn't limited to TDD).

It is all too easy to slip into to thinking about the Solution Space
too early in the game: "What's the simplest, most naive maze solving
approach I can think of ... ", -- and of course, trying to write tests
for a naive maze solver is as hard as trying to write tests for a very
clever maze solver (and doesn't help us do TDD because we are thinking
in the wrong Space).

Jim focuses on the Problem Space: "What's the simplest, most naive maze I
can think of ...", and in one fell swoop he reduces the Problem Space to
just a step (or two) above the Null Problem Space, something that can serve
as a minimal test, and with a clear path of growing complexity.

And so at last we have uncovered the real secret to TDD ... getting Jim to
look at your Problem Space.

cheers,
andrew

--
Andrew L. Johnson http://www.s...
What have you done to the cat? It looks half-dead.
-- Schroedinger's wife

Jim Weirich

3/25/2006 3:54:00 PM

Christian Neukirchen wrote:
> Jim Weirich <jim@weirichhouse.org> writes:
>
>> Then I would add tests to make sure it could solve multi-step mazes:
>
> I would at least add an maze with a loop, like:

Great idea.

Here's another one that just occured to me. A maze where the endpoint
is not connected to an outside wall.

#######
#s----#
#-###-#
#-#e#-#
#-#-#-#
#-----#
#######

This is typical, that more tests will occur to you as you work through
the problem.

--
-- Jim Weirich

--
Posted via http://www.ruby-....

Christian Neukirchen

3/25/2006 5:13:00 PM

Andrew Johnson <ajohnson@cpan.org> writes:

> And so at last we have uncovered the real secret to TDD ... getting Jim to
> look at your Problem Space.

Haha, reminds me of how to use Feynman for problem solving. :-)

"There were, it was said, only two ways of solving difficult problems
in physics. One was to use mathematics; the other was to ask Feynman."
---John Naughton

> cheers,
> andrew
--
Christian Neukirchen <chneukirchen@gmail.com> http://chneuk...

matthew.moss.coder

3/25/2006 5:18:00 PM

> And so at last we have uncovered the real secret to TDD ... getting Jim to
> look at your Problem Space.

LOL. +1

comp.lang.ruby

Newby Maze solution

Alex Combas

Jim Weirich

benjohn

Robert Dober

Michael Gorsuch

Jim Weirich

Christian Neukirchen

Andrew Johnson

Jim Weirich

Christian Neukirchen

matthew.moss.coder

x Login to ForumsZone