aspose file tools*
The moose likes Beginning Java and the fly likes To find a largest sector in a given input string of 1's and 0's Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "To find a largest sector in a given input string of 1 Watch "To find a largest sector in a given input string of 1 New topic
Author

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

Shareef Uddin
Greenhorn

Joined: Feb 06, 2011
Posts: 8


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
Ranch Hand

Joined: Sep 07, 2010
Posts: 98
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
Greenhorn

Joined: Feb 06, 2011
Posts: 8

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

Joined: Apr 06, 2010
Posts: 4240
    
    7

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
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10912
    
  12

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


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Shareef Uddin
Greenhorn

Joined: Feb 06, 2011
Posts: 8

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
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10912
    
  12

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
Greenhorn

Joined: Feb 06, 2011
Posts: 8

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
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10912
    
  12

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
Greenhorn

Joined: Feb 06, 2011
Posts: 8

sorry, mistakenly I have written user input.

Need to read from a file.
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3370
    
    9
This question has been cross posted at least here and here.

Shareef, please BeForthrightWhenCrossPostingToOtherSites.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10912
    
  12

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

Good luck on this.
Shareef Uddin
Greenhorn

Joined: Feb 06, 2011
Posts: 8


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,
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: To find a largest sector in a given input string of 1's and 0's
 
Similar Threads
Regular expression
print till the next blank line
Integer.toString.......
how to convert string into string array
SCJP6 study - regex string.split - strange results, can anyone explain please?