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

[Shareef Uddin]

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

[Kurt Van Etten]

There are two distinct phases to any problem like this: 1) describe the algorithm you will use to solve the problem, and 2) write an implement in a programming language. It's important to really have a grasp on step 1 before you start on step 2. So how would you describe, in English or in pseudocode, how you would tackle the problem? (Imagine you are solving it yourself using pencil and paper, but further suppose that you are extremely nearsighted so that you can only see one entry of the matrix and its immediate neighbors, at any given time.)

[Shareef Uddin]

I will try to use stringTokenizer API.
Is that ok?

[Matthew Brown]

Splitting up the input isn't going to be the hard part. The hard part will be working out the logic to use, which is what Kurt is on about. So you might end up using a StringTokenizer, but you really shouldn't worry about that yet.

I'd suggest starting with the assumption that you've loaded your grid into a two-dimensional array. Don't worry about how you build the array until you know what you're going to do with it. Now, what logical steps are you going to apply to work out your answer?

Writing off the top of my head, my first approach would be something like this:
- Find a '1'
- Now find all the adjacent '1's
- Keep going until I've identified the entire group. I'm going to need some way if remembering which '1's I've already looked at, to make sure I don't count one twice. I'm also going to need a way of remembering the group I've identified, unless I'm only interested in the size (in which case I need to remember that)
- Now find another '1' that wasn't in the first group, and repeat the steps above.
- Was it a bigger group than my previous biggest group? if so, remember it.
- Keep going till there are no more '1's left

[fred rosenberger]

Shareef Uddin wrote:
I will try to use stringTokenizer API.
Is that ok?

well...yes...but that is far from complete. Your original question was akin to "how do I build a skyscraper?" and this is like saying "I will try to use a screwdriver". while a screwdriver may be necesary, there is a LOT more going on here.

What I might do is
create a second 2d int array the same size as your input.
create a counter to keep track of which 'group' of 1's you are looking for
initialize each element to '-1'.
find the first element in this array that has a value of -1, which means I haven't looked at it yet.
if the corresponding element in the input array is 0, set it to 0
else
set the value in the new 2d array to the value of your counter
find all 1's next to this one, and set the corresponding elements to the counter value
find all neighbors of those elements, etc

in this way, you build a second array that keeps track of which 'grouping' a 1-value belongs to. Then, you can go through, count how many elements are in the 1-group, the 2-group, etc.

given your initial input, my new array would look something like

11000
01100
00102
30002
03022

[Shareef Uddin]

I need to read the input from a txt file i.e input.txt

The input will be something like this:


Sample Input
2

11000
01100
00101
10001
01011

1011
1010

Sample Output
5
3

[fred rosenberger]

I think we understand what you are trying to do. The key to all programming is to break it down into little parts. So you may want to first work on just getting the input and storing it.

Then you may want to work on how to parse a given input into usable pieces.

Then work on an algorithm to count the sizes.

Then work on an algorithm to find the largest.

Then work on outputting the results.

so...Why don't you show us what you've got so far?

[Shareef Uddin]

I read the file by following the below code:

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

then how should I proceed further?

[fred rosenberger]

so maybe I am confused. Your original post said "user input" - are they inputting from a keyboard, or are you reading a file?

[Shareef Uddin]

sorry, mistakenly I have written user input.

Need to read from a file.

[Stephan van Hulst]

This question has been cross posted at least here and here.

Shareef, please BeForthrightWhenCrossPostingToOtherSites.

[fred rosenberger]

Well, I'm glad to see I've been wasting my time.

Good luck on this.

[Shareef Uddin]

Thank you very much to all for helping.

I have cross posted the issue, because I have to fix it by 1 day.

I am sorry for that.

Thank you,