• Post Reply Bookmark Topic Watch Topic
  • New Topic
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
  • Tim Cooke
  • Devaka Cooray
  • Ron McLeod
  • Jeanne Boyarsky
Sheriffs:
  • Liutauras Vilda
  • paul wheaton
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Carey Brown
  • Tim Holloway
Bartenders:
  • Martijn Verburg
  • Frits Walraven
  • Himai Minh

Recursion help

 
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!
 
Ranch Hand
Posts: 1646
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
     
    Ranch Hand
    Posts: 116
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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 ]
     
    (instanceof Sidekick)
    Posts: 8791
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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.
     
    pie sneak
    Posts: 4727
    Mac VI Editor Ruby
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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.
     
    Sheriff
    Posts: 11343
    Mac Safari Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Hmmm... Reminds me of Minesweeper -- figuring out which adjacent tiles to automatically "open."
     
    passwords must contain 14 characters, a number, punctuation, a small bird, a bit of cheese and a tiny ad.
    the value of filler advertising in 2021
    https://coderanch.com/t/730886/filler-advertising
    reply
      Bookmark Topic Watch Topic
    • New Topic