Last week, we had the author of TDD for a Shopping Website LiveProject. Friday at 11am Ranch time, Steven Solomon will be hosting a live TDD session just for us. See for the agenda and registration link
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Paul Clapham
• Ron McLeod
• Jeanne Boyarsky
• Tim Cooke
Sheriffs:
• Liutauras Vilda
• paul wheaton
• Henry Wong
Saloon Keepers:
• Tim Moores
• Tim Holloway
• Stephan van Hulst
• Carey Brown
• Frits Walraven
Bartenders:
• Piet Souris
• Himai Minh

# moving through 2D arrays

Ranch Hand
Posts: 60
• Number of slices to send:
Optional 'thank-you' note:
i have a 2d array (a maze) which is filled with true and false (true = free space, false = wall).

using a stack im trying to write a method to find the correct path through the maze by first going right (if i can), then down(if i can), then left...and then up.

each free point i goto gets set as visited and if i come to a dead end (cant go right down left or up) this point is set as "discard" and i move back a step (using the stack) and check to see if going right down left or up is a free space, not doing anything if it is a wall or it has been discarded. i can do this with recursion but without im having difficulties, i can visualise what to do its writing the code im having troubles with.

Ranch Hand
Posts: 56
• Number of slices to send:
Optional 'thank-you' note:
This is a problem which really solves best with a recursive solution. If you already have that, why change it? If you must change it, you can make a recursive solution into an iterative one. I googled for a couple minutes using the keywords "recursion" and "iteration" and found several sites showing how it is done.

author and iconoclast
Posts: 24204
44
• Number of slices to send:
Optional 'thank-you' note:

Originally posted by Deyna Cegielski:
i can visualise what to do its writing the code im having troubles with.

OK, describe what you want to do, and we'll give you some pointers.

Deyna Cegielski
Ranch Hand
Posts: 60
• Number of slices to send:
Optional 'thank-you' note:
sorry...

"im trying to write a method that moves through a 2d array point by point. at each point it trys to go right if it can it goes right if it cant it trys to go down, then left, then up. if it can move then it will at the process is repeated for the new point. this can be done with recursion but i have no idea how to implement this as an iterative proceess and im not allowed to use recursion. please help!"

Deyna Cegielski
Ranch Hand
Posts: 60
• Number of slices to send:
Optional 'thank-you' note:
maybe its easier if i translate that into a bit of pseudocode...

1.for each point
is point up "free space", if so go there, repeat 1.
is point to right "free space", if so go there, repeat 1.
is point down "free space", if so go there, repeat 1.
is point to left "free space, if so go there, repeat 1.

the implementation at each step i can do myself, its setting up the above as an interative process i cant do. any help would be be greatly appreciated.

Ranch Hand
Posts: 3061
• Number of slices to send:
Optional 'thank-you' note:
Also, you might need a stack to help back up when you reach a dead end.

Layne

(instanceof Sidekick)
Posts: 8791
• Number of slices to send:
Optional 'thank-you' note:
A little more detail on the idea above ... Recursion gives you a new set of local variables on the JVM's stack. To convert from recursion to iteration you can put your local variables on your own stack instead. If you're in JDK 5 you have a Stack class, otherwise you can use a LinkedList like a stack.

I'd make a little data-only object with all the local variables I need, maybe row, column, length of path, etc. Then any time you were thinking about calling yourself recursively, push the current object onto the stack and initialize a new one. Where the recursion returned, pop the prior object off the stack again.

I remember doing this in COBOL to evaluate an expression with nested parens. (Still have the code on this PC!) Ah, the good old days!

Layne Lund
Ranch Hand
Posts: 3061
• Number of slices to send:
Optional 'thank-you' note:

Originally posted by Stan James:
If you're in JDK 5 you have a Stack class, otherwise you can use a LinkedList like a stack.

The Java API has had a Stack class since JDK 1.0, according to the javadocs.
Layne
[ November 30, 2004: Message edited by: Layne Lund ]

 I need a new interior decorator. This tiny ad just painted every room in my house purple. Free, earth friendly heat - from the CodeRanch trailboss https://www.kickstarter.com/projects/paulwheaton/free-heat