1,105,546 Community Members

To find a largest sector in a given input string of 1's and 0's

Member Avatar
Java_tyro
Newbie Poster
4 posts since Apr 2008
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Hello,

Help me in writing a logic for the program:

User input:


11000
01100
00101
10001
01011

Two 1's are said to be connected if they are adjacent to each other horizontally, vertically & diagonally.

Need to find the largest sector of 1's in the above input string.

For example: In the above input string the largest sector is of size 5.

Please help me.

Thank you

Member Avatar
Taywin
Posting Maven
2,632 posts since Apr 2010
Reputation Points: 134 [?]
Q&As Helped to Solve: 378 [?]
Skill Endorsements: 17 [?]
 
0
 

What is your current logic to the problem? I can give you a hint, use a search and iterate through the area until no more connected 1's is found. Don't forget to keep track of where you have already visited. The method could be recursive (easy to implement) or iterative (a bit longer).

Member Avatar
jon.kiparsky
Posting Virtuoso
1,837 posts since Jun 2010
Reputation Points: 326 [?]
Q&As Helped to Solve: 192 [?]
Skill Endorsements: 6 [?]
 
0
 

Start by figuring out what the steps are at a high level, then figure out how to execute them. Executing them may, and probably will, involve decomposing them into steps which you'll then re-examine in the same way until you have methods which are trivial to execute. Write the trivial methods.
Test.
If results pass tests, done. Else, find and fix bugs.

Member Avatar
Java_tyro
Newbie Poster
4 posts since Apr 2008
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Start by figuring out what the steps are at a high level, then figure out how to execute them. Executing them may, and probably will, involve decomposing them into steps which you'll then re-examine in the same way until you have methods which are trivial to execute. Write the trivial methods.
Test.
If results pass tests, done. Else, find and fix bugs.

I need to read a file for input like:

Sample Input

2 

11000 
01100 
00101 
10001 
01011  

1011
1010

Sample Output

5
3

Sample Input 2 indicates there are two grids.

        FileReader fr = new FileReader("input.txt");
        BufferedReader br = new BufferedReader(fr);
        String s;
        while( (s = br.readLine()) != null)
        {
            System.out.println(s.length());
        }

How should I proceed further now?

Member Avatar
jon.kiparsky
Posting Virtuoso
1,837 posts since Jun 2010
Reputation Points: 326 [?]
Q&As Helped to Solve: 192 [?]
Skill Endorsements: 6 [?]
 
0
 

So far your breakdown is:
Get the data
Solve the problem somehow for however many grids are submitted.
Report the result.

That middle step needs a little work.
You know you're going to have to solve the problem for one gird, so maybe you should work on that. Solve that, and you should be able to extend it to multiple grids without much trouble.

I'll give you this much for free: it'll look a little like this
private int solve(Grid g) {}

where Grid might be a 2D array or a custom object or whatever structure makes it easiest for you to solve it. Return your solution as an int. When you do multiple grids, you'll stuff that in an array or an ArrayList or whatever makes most sense to you at that point. Don't worry about that now, though, just return the int so you can use it later.

But now you have your solve method to break down.

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article