File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Beginning Java and the fly likes Recursion help Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Recursion help" Watch "Recursion help" New topic
Author

Recursion help

Tiffany Rich
Greenhorn

Joined: Apr 22, 2004
Posts: 4
Hey Guys

New here so bear with me... I have a program that reads a text file into a two dimensional array. The text files that are read in can change so this is just an example. The file that is read in looks something like this>>

x x - - x - - - - - - x x - -
x x - - x - - - x - - - x - -
x x - - x - - x - - - - - - -
x - x - x x - - - - - - x - -
- - x - x x - x x x - - x - x
x x x - x x - x - - - - x - x
x x - - - - - - - - - - - - x
x x - x x - - x x x x - - - -
x x - x - - - - - - - - - x x
x x - x x x x x x x x x x - x


I have to use recursion that takes connected edges (diagonals don't count) so the output will look like this>>

A A - - B - - - - - - C C - -
A A - - B - - - D - - - C - -
A A - - B - - E - - - - - - -
A - F - B B - - - - - - G - -
- - F - B B - H H H - - G - I
F F F - B B - H - - - - G - I
F F - - - - - - - - - - - - I
F F - J J - - K K K K - - - -
F F - J - - - - - - - - - L L
F F - J J J J J J J J J J - L


My question is I don't even know where to start to come up with code to detect the appropriate edges. Any help or hints would be great!
David Harkness
Ranch Hand

Joined: Aug 07, 2003
Posts: 1646
Your first task, as with any program, is to break it down into discrete steps. This is an iterative process, meaning that you start with a single step -- "solve the problem" -- and break that step into smaller steps. You then recursively break those steps into smaller steps, and so on until all of the steps are "sufficiently small." Defining this latter term comes with experience.

One first cut at breaking it apart might be
  • Read the input file into a data structure.
  • Find all of the contiguous blocks.
  • Write the complete solution to the screen of file (whatever assignment says).

  • Clearly, these are still pertty big steps. You'll need to think about how to break it down further. Instead of having us do it for you, which will teach you nothing, try it out yourself and post what you can get. I'm sure you have some ideas about this, so let's have 'em!

    Now, you don't necessarily have to break all the steps down into detail before you start. This is key! If you start by working on the first step, you can ignore the other two for now. I'd even recommend that you do #1 and #3 before attempting #2 for the simple reason that without #3 you won't know when you have #2 working.*

    [ * True, you could write up an algorithm to programmatically test your solution, but I think that's a bit beyond the beginner level. ]
    [ February 03, 2005: Message edited by: David Harkness ]
    Marcus Laubli
    Ranch Hand

    Joined: Dec 24, 2004
    Posts: 116
    Hey Tiffany,

    This one looks like lots of fun.

    I'll be watching to see how David helps you. Like he said, just take one small step at a time.

    I'm sure that there's lots of help here on this site, but as one of my mentors says, I'd rather you sweat for half an hour before I give you the answer!

    ... as he tiptoes away, hoping that Marilyn doesn't see this!

    She's actually right.
    [ February 03, 2005: Message edited by: Marcus Laubli ]

    Marcus L´┐Żubli, SCJP 1.4, CLP 5.0, SCWCD 1.4 (preparing)
    Stan James
    (instanceof Sidekick)
    Ranch Hand

    Joined: Jan 29, 2003
    Posts: 8791
    I'm absolutely with David on breaking this down. Get the file & data structure stuff out of the way before you try to solve the real problem. For that I'll give you some hints, but no Java ...

    It's fun to think about these problems as if you're walking among the squares on your board, or if you're old enough to remember adventure games "You are standing in a maze of twisty passages, all alike."

    Imagine you are standing in the top left square. It has a * so mark the square with an A, then look around. Look East and you see another *, so you go to that square, mark it with an A and look around. Look East, find an empty, look South, see another * and ... well, the same darned thing over and over. When you finally reach a dead-end, start backtracking until you reach a square where you have not yet looked all four directions.

    See if you can translate that to Java. Recursion hurts your brain the first time, but after that it's great fun.


    A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
    Marc Peabody
    pie sneak
    Sheriff

    Joined: Feb 05, 2003
    Posts: 4727

    I would make my first step to get the program working without the recursive part. In other words, make it so your output is:
    A B - - C - - - - - - D E - -
    F G - - H - - - I - - - J - -
    K L - - M - - N - - - - - - -
    etc.

    After that, you can slip the recursion in without having to change what you've already done.


    A good workman is known by his tools.
    marc weber
    Sheriff

    Joined: Aug 31, 2004
    Posts: 11343

    Hmmm... Reminds me of Minesweeper -- figuring out which adjacent tiles to automatically "open."


    "We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." ~Joe Strummer
    sscce.org
     
    With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
     
    subject: Recursion help
     
    Similar Threads
    extracting image binary data from file
    The Conditional Operator ?:
    Retrieving list from a map mapping to an arraylist
    conditional operater?
    extracting image binary data from file