Forum: Ruby Newby Maze solution

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Alex C. (Guest)
on 2006-03-25 12:58
(Received via mailing list)
Hello folks,
Tonight I tried out some of that good old extreme programming TDD stuff
with mixed results.

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.

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 suggestions
on 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 there
is 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"
  end
end

And 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
  end
end
me = Tracker.new(maze)
me.get_it!
Jim W. (Guest)
on 2006-03-25 15:31
Alex C. 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 W.
Benjohn B. (Guest)
on 2006-03-25 16:00
(Received via mailing list)
On 25 Mar 2006, at 10:57, Alex C. 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 D. (Guest)
on 2006-03-25 16:06
(Received via mailing list)
On 3/25/06, Benjohn B. <removed_email_address@domain.invalid> wrote:
> * 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 G. (Guest)
on 2006-03-25 16:11
(Received via mailing list)
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
Jim W. (Guest)
on 2006-03-25 16:49
Michael G. 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...

Ron J. Book "Extreme Adventures in C#"
(http://www.xprogramming.com/xpmag/Books20040324.ht...).
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=11...)

--
-- Jim W.
Christian N. (Guest)
on 2006-03-25 16:58
(Received via mailing list)
Jim W. <removed_email_address@domain.invalid> writes:

> Then I would add tests to make sure it could solve multi-step mazes:
>       #-#
>    ###-#   ###-#
>    #---#   #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#
  ########
Andrew J. (Guest)
on 2006-03-25 17:33
(Received via mailing list)
On Sat, 25 Mar 2006 22:32:16 +0900, Jim W. 
<removed_email_address@domain.invalid>
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
Jim W. (Guest)
on 2006-03-25 17:53
Christian N. wrote:
> Jim W. <removed_email_address@domain.invalid> 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 W.
Christian N. (Guest)
on 2006-03-25 19:13
(Received via mailing list)
Andrew J. <removed_email_address@domain.invalid> 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
Matthew M. (Guest)
on 2006-03-25 19:18
(Received via mailing list)
> And so at last we have uncovered the real secret to TDD ... getting Jim to
> look at your Problem Space.

LOL.  +1
Alex C. (Guest)
on 2006-03-26 01:57
(Received via mailing list)
Thanks everyone, and especially thank you Jim,
this boiled down approach to TDD has given me
fresh eyes (hopefully).

I'm going to take another swing at the problem tonight
if I have time, and I'll try to keep notes, if it turns out all right
perhaps I'll post it.

Oh, and I really like the idea
of solving a maze like this:

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

Good one!

best regards,
This topic is locked and can not be replied to.