CODEWITHSUNDEEP
javaarraysrecursionmatrix
SovietBeans
SovietBeans

Reputation: 1

Recursive grid counter

Before any of you ask, this is not a homework assignment. I got this lab form one of my siblings from his Computer Science class, and he gave it to me since I am learning Java as well. The following is a link to the word file for the lab- https://drive.google.com/open?id=0B0knwQqYII5BekhuTDFxcER3Qk0. I am primarily concerned about how I am to use a recursive method to navigate the grid. I am planning on marking the counted @ signs by changing them to $ signs, but I'm not sure what coordinates my recursive method should be returning.

Any help is very appreciated, thanks!

Upvotes: 0

Views: 1309

Answers (2)

Brian H.
Brian H.

Reputation: 2225

Like you, I'm new to coding in Java, so this was a good exercise for me. Thanks! Here is my solution. Let me know if you have any questions.

Below is a link to the two .java files for a full solution to the question. The solution isn't extensively tested so it might have obscure errors, but it solves the problem using simple recursion, is fairly intuitive, and includes the necessary plumbing code for a fully working example. This is a first-attempt solution and it could definitely be improved on for both efficiency and coding-style.

https://drive.google.com/folderview?id=0BxpVs-UD4OcwRjd2TjNtaEJndXc&usp=sharing

Here is the pseudo code for the algorithm. The key methods are getOccupiedNeighbors() and recursiveFind(). The neighbors method uses four hard-coded checks to find the north, east, south, and west squares. It first checks to make sure that any potential neighbor is in bounds, then looks to see if the neighbor is "occupied".

The recursive method asks if the current square has been checked ("visited") already.If not, then the count is increased, its neighbors are added to a list, and the square is marked as visited. Then the method calls itself recursively on each square in the list until all lists are empty of non-visited, occupied neighbors.

class Grid

HEIGHT = 10;
WIDTH = 20;
OCCUPIED_SYMBOL = "@";
EMPTY_SYMBOL = "-";
WEIGHT = 0.5f;

occupiedCount = 0;

grid = new String[HEIGHT][WIDTH];
visited = new boolean[HEIGHT][WIDTH];


toString()
    format for console output

randomize()
    for each SQUARE : GRID
        if random() < WEIGHT  then SQUARE.text = SYMBOL 

isOccupied(row, column)
    return (GRID[location] == SYMBOL)

getOccupiedNeighbors(row, column)
    //North
    if (ROW - 1 >= 0) & isOccupied()
        add Coordinate to list

    //South, West, East
    if (ROW + 1 > HEIGHT) {...}
    if (COLUMN - 1 >= 0) {...}
    if (COLUMN + 1 > WIDTH) {...}

    return LIST 

findSequence(row, column)
    reset OCCUPIED_COUNT and VISITED
    recursiveFind(currentSquare) // Start the process
    return OCCUPIED_COUNT

recursiveFind(row, column)
    if currentSquare has not been visited yet
        list = getOccupiedNeighbors()
        mark currentSquare as visited
        increase count

    for each SQUARE in LIST
        resursiveFind(SQUARE)

The algorithm is fairly efficient, but its performance could be improved in a few ways. First, the bounds-checking on the neighbors could be handled better. Hard-coded, repeatable sequences are usually a code-smell for me. Second, using an array of previously visited locations might not be the most efficient way for limiting the recursion. I'm not sure on this one, but I think it might be more performant to build the recursive method in a way that eliminates the possibility looking at any previously examined neighbor.

The object-orientedness of the example could also be improved quite a bit. There is a Coordinate class, but it is only used in one place. All of the (row, column) arguments should be replaced by (Coordinate c). This would eliminate a good source of errors. Things like access modifiers, instance fields, mutators and accessors, and other standard OO features are completely missing.

Hope this helps. Please let me know if you have any questions or problems running the code.

Upvotes: 0

Jean Logeart
Jean Logeart

Reputation: 53809

Try something like:

char[][] table = // ...

private static int countConnectedSigns(char[][] table, int r, int c) {
    char[][] tableCopy = // ...
    return countConnectedSignsAux(tableCopy[][], r, c, 0);
}

private static int countConnectedSignsAux(char[][] table, int r, int c, int currentCount) {
    if(r < 0 || r >= table.length || c < 0 || c >= table[0].length ||
       table[r][c] != '@') {
        return currentCount;
    }
    table[r][c] = '-';    // mark visited
    return countConnectedSignsAux(table, r + 1, c, currentCount + 1) +
        countConnectedSignsAux(table, r - 1, c, currentCount + 1) +
        countConnectedSignsAux(table, r, c + 1, currentCount + 1) +
        countConnectedSignsAux(table, r, c - 1, currentCount + 1) +;
}

Upvotes: 1

Related Questions