algorithm to find the largest area

Question

................................
.XXXXXXXXXXXXXXX.....XXXXXXXXXX.
.X.....X.......X.....X........X.
.X.....X.......XXXXXXX........X.
.XXXXXXXXXXXX.................X.
.X....X.....X.................X.
.X....X.....XXXX..............X.
.XXXXXX........X..............X.
......X........X..............X.
......X........X..............X.
......X........X..............X.
......XXXXXXXXXXXXXXXXXXXXXXXXX.
................................

Looking for an algorithm to find the largest area. Here, "area" is defined as a number of dots (.) bounded by Xs.

   private static void readFile(File inputFile) throws IOException {

    Scanner fileScanner = new Scanner(inputFile);

    Point previousPoint = null;

    int rowCount = 0;
    while(fileScanner.hasNext()){
        String line = fileScanner.next();

        String[] points = line.split(" ");

        for(int columnCount=0;columnCount<points.length;columnCount++){

            if(points[columnCount].equalsIgnoreCase("x")){
                Point currentPoint = new Point();
                currentPoint.setxValue(columnCount);
                currentPoint.setyValue(rowCount);
            }
        }

        rowCount++;
    }
  }

This is my first and struggling to move further.

Answer 1

This algorithm should work. You just need to implement it in Java.

1. Load the file into a char[][]. (1 char[] per line)
2. Loop through the char[][] (2 dimensionally)
   3. upon finding a '.', perform flood fill, changing all '.' to ',', also incrementing a counter on every change.
   4. At the end of flood fill, compare this counter with a globally set maximum. If it's higher, then set it as the new highest. (If the edges are not a proper boundary, then do not set this counter if you reached an edge during flood fill by setting a flag during 3)
3. Return the highest you set.

If you have any specific problems with the Java implementation, then let me know

Geobits:

Note: If you want to exclude the area "outside" any boxes, flood as usual, but discard any area that hits the edge during the fill(skip step 2.2 for that flood).

When doing the flood fill, you have 2 types of boundaries. A wall ('X'), and the edge of the array(which you need to explicitly check for to avoid OutOfBounds exceptions). If you hit an out of bounds, keep doing the fill, but set a flag so you know later to not consider the number you counted for the biggest box.

Answer 2

I was given this as assignment in an interview process and this is the compile and running code

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;

public class FindArea {
public static void main(String[] args) 
{
    String fileName="C:\\map.txt";
    FindArea area = new FindArea();
    try{
        FileReader inputFile = new FileReader(fileName);
        BufferedReader bufferReader = new BufferedReader(inputFile);

        char[][] twoArray= new char[100][100];
        String line;
        int i=0;

        while ((line = bufferReader.readLine()) != null) {
            twoArray[i] = line.toCharArray();
            System.out.println(line);
            i++;
        }
        bufferReader.close();

        System.out.println("file read");
        System.out.println("Max area: " + area.getMaxArea(twoArray));

    } catch(Exception e) {
        System.out.println("error : " + e.getMessage());
    }
}

/**
 * Get the maximum area from the given map
 * 
 * @param charArray
 * @return
 */
private int getMaxArea(char[][] charArray) {
    HashMap<Integer, ArrayList<String>> numberOfBoxes = convertToBoxes(charArray);

    numberOfBoxes = mergeOverlapAreas(numberOfBoxes);

    int largeSize = 0; 
    for (Integer key : numberOfBoxes.keySet()) {
        ArrayList<String> list = numberOfBoxes.get(key);
        System.out.println("Key : " + key + " Size : " + list.size());
        if (largeSize < list.size()) {
            largeSize = list.size();
        }
    }
    return largeSize;
}

/**
 * Convert the 2d Array to HashMap
 * Key being the count of boxes and 
 * Value being the list of indexes associations
 * 
 * @param charArray
 * @return
 */
private HashMap<Integer, ArrayList<String>> convertToBoxes(char[][] charArray) {
    HashMap<Integer, ArrayList<String>> numberOfBoxes = new HashMap<Integer, ArrayList<String>>();
    int boxes = 0;

    for(int i=1; i<charArray.length; i++) {

        for (int j=0; j<charArray[i].length; j++) {

            if (charArray[i][j] == '.') {

                boolean isExists = false;

                for(Integer key : numberOfBoxes.keySet()) {

                    ArrayList<String> arrList = numberOfBoxes.get(key);

                    if(arrList != null) {

                        if(arrList.contains((i-1) + "-" + j) ||
                           arrList.contains(i + "-" + (j-1))) {

                            isExists = true;
                            arrList.add(i + "-" + j);
                            numberOfBoxes.put(key, arrList);
                        }
                    } 
                }

                if (!isExists) {
                    ArrayList<String> list = new ArrayList<String>();
                    list.add(i + "-" + j);
                    numberOfBoxes.put(boxes, list);
                    boxes++;
                }
            }
        }
    }
    return numberOfBoxes;
}

/**
 * Check for the points exists in more than one area
 * @param numberOfBoxes
 * @return
 */
private  HashMap<Integer, ArrayList<String>> mergeOverlapAreas( HashMap<Integer, ArrayList<String>> numberOfBoxes) {

    for(Integer key : numberOfBoxes.keySet()) {
        ArrayList<String> list1 = numberOfBoxes.get(key);

        for (Integer key2 : numberOfBoxes.keySet()) {

            if (key < key2) {

                ArrayList<String> list2 = numberOfBoxes.get(key2);
                Iterator<String> listIter = list2.iterator();

                while(listIter.hasNext()) {

                    if (list1.contains(listIter.next())) {
                        list1.addAll(list2);
                        Set<String> noDuplicates = new HashSet<String>(list1);
                        numberOfBoxes.put(key, new ArrayList<String>(noDuplicates));
                        break;
                    }
                }
            }
        }

    }
    return numberOfBoxes;
}

}

Answer 3

Here's an algorithm that's an alternative to flood fill. This method sweeps through the 2d array and whenever you encounter a node(pixel) that's outside to the left (right, top, bottom), it flags the current node as outside, ie if your neighbour is 'outside', you're marked 'outside' too.

The algorithm continues like this until there're no more updates. That means that all the nodes that are reachable from the 'outside' have been flagged. BTW, this is a very similar problem to level sets functions and updating them (where flood fill is also used). The nice this about this method is that it is ideal for parallelization.

1. Load 2D Symbol Array from File 
2. hasupdates = false
3. Create 'isinside' bool array -> {
       if(symbolarray[row][col] == '.' and row or col is at boundary)
           isinside[row][col] = false
       else
           isinside[row][col] = true
   }

4. do{
    Do a sweep from left to right (for all rows) -> //This loop can be run parallely on all rows. 
        If (!isinside[row][col-1] and symbolarray[row][col] == '.'){
            isinside[row][col] = false //mark current value as 'outside'
            hasupdates = true
        }
    Do similar sweeps from right to left, top to bottom(all columns) and bottom to top.

}while(hasupdates)

5. Go through 'isinside' array and count the number of falses.

If you have huge files where you have to do this area calculation, you can have the sweeps along the rows and columns run parallely, because each row update (column update) is independent of the other updates.