Find number of plus in a 2d array

Question

Problem

CharGrid

The CharGrid class encapsulates a 2-d char array with a couple operations.

int countPlus()

Look for a '+' pattern in the grid made with repetitions of a character. A '+' is made of single character in the middle and four "arms" extending out up, down, left, and right. The arms start with the middle char and extend until the first different character or grid edge. To count as a '+', all the arms should have two or more chars and should all be the same length. For example, the grid below contains exactly 2 +'s: the p-plus in the top left and the x-plus in the top right. The y in the bottom right doesn't work because the top, right, and left arms would be length 2, but the bottom arm would be length 3.

  p      
  p    x 
ppppp xxx
  p  y x 
  p yyy  
zzzzzyzzz
  xx y

Plusses may be formed using any character such as digits or punctuation marks, they do not have to be letters. Just treat all chars the same and your code should work fine.

I know as a matter of fact that there are many areas upon which my code could be improved. However, rather than asking other people to correct my code, I would much prefer to be given hints or general principles as to how my code could be improved. I think this way, me, and everyone that read this post could get more out of this exercise this way.

So could someone please provide me with some comments or suggestions? Critics of any level and kind are welcomed! Feel free to pick apart my code!

CharGrid Class:

import java.util.ArrayList;
import java.util.List;

public class CharGrid {

    private char[][] grid;

    /**
     * Constructs a new CharGrid with the given grid. Does not make a copy.
     *
     * @param grid
     */
    public CharGrid(char[][] grid) {
        this.grid = grid;
    }



    int countPlus() {

        //do not accept grid that has length or width less than 3
        if (grid.length < 3 || grid[0].length < 3) {
            return 0;
        }

        int numberOfPlus = 0;

        //exclude points near the boundary because the they could NOT be the middle character of a plus 
        for (int yCoordinate = 1; yCoordinate < grid.length - 1; yCoordinate++) {
            for (int xCoordinate = 1; xCoordinate < grid[yCoordinate].length - 1; xCoordinate++) {

                numberOfPlus += isPlus(xCoordinate, yCoordinate, grid[yCoordinate][xCoordinate]) ? 1 : 0;
            }
        }

        return numberOfPlus;
    }

    /**
     * find out if there is a plus formed with the middleCharacter as its center
     * @param xCoordinate the x coordinate of the middle character
     * @param yCoordinate y coordinate of the middle character
     * @param middleCharacter 
     * @return return true if the middle character is the center of a plus, otherwise return false
     */
    private boolean isPlus(int xCoordinate, int yCoordinate, char middleCharacter) {
        //the length of each of the four arms surrouding the middle character (i.e. top, bottom, left, right)
        int armLength = radiusOfPlus(xCoordinate, yCoordinate, 1, middleCharacter);
        return armLength > 0;
    }

    /**
     * to find out the radius length of the plus, including the center character
     * @param xCoordinate the x coordinate of the middle character
     * @param yCoordinate y coordinate of the middle character
     * @param radiusOfPlus the length of each of the four arms (i.e. top, bottom, left, right), including center 
     * @param middleCharacter
     * @return the length of radius in each of the four arms (if they are equal in length), otherwise return 0
     */
    private int radiusOfPlus(int xCoordinate, int yCoordinate, int radiusOfPlus, char middleCharacter) {


        //current radius of the plus, including the center 
        int currentRadius = radiusOfPlus;

        //calculate x and y coordinate of points that are directly on top, at bottom, to left and right of center
        Point top = new Point(xCoordinate, yCoordinate - radiusOfPlus);
        Point bottom = new Point(xCoordinate, yCoordinate + radiusOfPlus);
        Point left = new Point(xCoordinate - radiusOfPlus, yCoordinate);
        Point right = new Point(xCoordinate + radiusOfPlus, yCoordinate);


        //find out if any of the top, bottom, left or right points are on the grid,
        //if the points are on the grid, find out if they contain the same character as the center 
        boolean topInBound = isInBounds(top);
        boolean topSameCharacter = false;
        if (topInBound) {
            topSameCharacter = isSameCharacter(top, middleCharacter);
        }

        boolean bottomInBound = isInBounds(bottom);
        boolean bottomSameCharacter = false;
        if (bottomInBound) {
            bottomSameCharacter = isSameCharacter(bottom, middleCharacter);
        }

        boolean leftInBound = isInBounds(left);
        boolean leftSameCharacter = false;
        if (leftInBound) {
            leftSameCharacter = isSameCharacter(left, middleCharacter);
        }

        boolean rightInBound = isInBounds(right);
        boolean rightSameCharacter = false;
        if (rightInBound) {
            rightSameCharacter = isSameCharacter(right, middleCharacter);
        }

        if (Boolean.TRUE.equals(topSameCharacter) && Boolean.TRUE.equals(bottomSameCharacter)
                && Boolean.TRUE.equals(leftSameCharacter) && Boolean.TRUE.equals(rightSameCharacter)) {

            //check if any of the boundary points around the plus sign contain the same character,
            //if yes, then it is not a plus sign
            List<Point> boundaryPoints = new ArrayList<>();

            boundaryPoints.add(new Point(xCoordinate - currentRadius, yCoordinate - 1));//top arm's left
            boundaryPoints.add(new Point(xCoordinate + currentRadius, yCoordinate - 1));//top arm's right
            boundaryPoints.add(new Point(xCoordinate - currentRadius, yCoordinate + 1));//bottom arm's left
            boundaryPoints.add(new Point(xCoordinate + currentRadius, yCoordinate + 1));//bottom arm's right
            boundaryPoints.add(new Point(xCoordinate - 1, yCoordinate - currentRadius));//left arm's top
            boundaryPoints.add(new Point(xCoordinate - 1, yCoordinate + currentRadius));//left arm's bottom
            boundaryPoints.add(new Point(xCoordinate + 1, yCoordinate - currentRadius));//right arm's top
            boundaryPoints.add(new Point(xCoordinate + 1, yCoordinate + currentRadius));//right arm's bottom

            for (Point aBoundaryPoint : boundaryPoints) {
                if (isInBounds(aBoundaryPoint)) {
                    if (isSameCharacter(aBoundaryPoint, middleCharacter)) {
                        return 0;
                    }
                }
            }

            // if all four sides contain the same character as the middle character, then call radiusOfPlus method recursively
            currentRadius = radiusOfPlus(xCoordinate, yCoordinate, radiusOfPlus + 1, middleCharacter);

            //else if all four surroudning space contain different character
        } else if (Boolean.FALSE.equals(topSameCharacter) && Boolean.FALSE.equals(bottomSameCharacter)
                && Boolean.FALSE.equals(leftSameCharacter) && Boolean.FALSE.equals(rightSameCharacter)) {

            //if the current radius is equal to 1, it means there is only the middle character, therefore arm length is zero
            if (currentRadius == 1) {
                return 0;

                //if the current radius does not equal to 1, it means that all four character 
                //surroudning the middle characters are the same and of equal length, 
                //therefore current radius is of valid number
            } else {
                return currentRadius;
            }
        } else {
            return 0;
        }

        return currentRadius;
    }

    /**
     * check if the point is on the grid
     * @param point the point to be tested
     * @return true if point is on the grid, else return false
     */
    private boolean isInBounds(Point point) {
        return (point.xCoordinate >= 0 && point.xCoordinate < grid[0].length && point.yCoordinate >= 0 && point.yCoordinate < grid.length);
    }

    /**
     * check if the point contain the same character as the center
     * @param point the point to be tested
     * @param middleCharacter the character in the middle
     * @return true the current point contain the same character as center, else return false
     */
    private boolean isSameCharacter(Point point, char middleCharacter) {
        return grid[point.yCoordinate][point.xCoordinate] == middleCharacter;
    }

}

Point class:

class Point {

    int xCoordinate, yCoordinate;

    Point(int xCoordinate, int yCoordinate) {
        this.xCoordinate = xCoordinate;
        this.yCoordinate = yCoordinate;
    }
}

Test class:

import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Test;

public class CharGridTest {

    // 
    // CountPlus Tests
    // 
    @Test
    public void testCountPlus1() {
        char[][] grid1 = new char[][]{
            {'x'}
        };
        char[][] grid2 = new char[][]{
            {'a'},
            {'b'}
        };
        char[][] grid3 = new char[][]{
            {'a'},
            {'b'},
            {'c'}
        };
        char[][] grid4 = new char[][]{
            {'a'},
            {'b'},
            {'c'},
            {'d'}
        };
        char[][] grid5 = new char[][]{
            {'a', 'b', 'c'}
        };
        char[][] grid6 = new char[][]{
            {'a', 'b', 'c', 'd'}
        };

        CharGrid cg1 = new CharGrid(grid1);
        CharGrid cg2 = new CharGrid(grid2);
        CharGrid cg3 = new CharGrid(grid3);
        CharGrid cg4 = new CharGrid(grid4);
        CharGrid cg5 = new CharGrid(grid5);
        CharGrid cg6 = new CharGrid(grid6);

        assertEquals(0, cg1.countPlus());
        assertEquals(0, cg2.countPlus());
        assertEquals(0, cg3.countPlus());
        assertEquals(0, cg4.countPlus());
        assertEquals(0, cg5.countPlus());
        assertEquals(0, cg6.countPlus());
    }

    @Test
    public void testCountPlus2() {
        char[][] grid1 = new char[][]{
            {'x', 'y'},};
        char[][] grid2 = new char[][]{
            {'x', 'y'},
            {'a', 'b'},};
        char[][] grid3 = new char[][]{
            {'a', 'b'},
            {'c', 'd'},
            {'e', 'f'},};
        char[][] grid4 = new char[][]{
            {'a', 'b'},
            {'c', 'd'},
            {'e', 'f'},
            {'g', 'h'},};
        char[][] grid5 = new char[][]{
            {'a', 'b', 'c'},
            {'d', 'e', 'f'}
        };
        char[][] grid6 = new char[][]{
            {'a', 'b', 'c', 'd'},
            {'a', 'b', 'c', 'd'},};

        CharGrid cg1 = new CharGrid(grid1);
        CharGrid cg2 = new CharGrid(grid2);
        CharGrid cg3 = new CharGrid(grid3);
        CharGrid cg4 = new CharGrid(grid4);
        CharGrid cg5 = new CharGrid(grid5);
        CharGrid cg6 = new CharGrid(grid6);

        assertEquals(0, cg1.countPlus());
        assertEquals(0, cg2.countPlus());
        assertEquals(0, cg3.countPlus());
        assertEquals(0, cg4.countPlus());
        assertEquals(0, cg5.countPlus());
        assertEquals(0, cg6.countPlus());
    }

    @Test
    public void testCountPlus3() {
        char[][] grid1 = new char[][]{
            {' ', 'x', ' '},
            {'x', 'x', 'x'},
            {' ', 'x', ' '}
        };

        CharGrid cg1 = new CharGrid(grid1);

        assertEquals(1, cg1.countPlus());

    }

    @Test
    public void testCountPlus32() {
        char[][] grid2 = new char[][]{
            {' ', ' ', 'x', ' ', ' '},
            {' ', ' ', 'x', ' ', ' '},
            {'x', 'x', 'x', 'x', 'x'},
            {' ', ' ', 'x', ' ', ' '},
            {' ', ' ', 'x', ' ', ' '}
        };
        CharGrid cg2 = new CharGrid(grid2);
        assertEquals(1, cg2.countPlus());
    }

    @Test
    public void testCountPlus33() {
        char[][] grid3 = new char[][]{
            {' ', ' ', 'x', ' ', ' '},
            {' ', ' ', 'x', ' ', ' '},
            {'x', 'x', 'x', 'x', 'x'},
            {'x', ' ', 'x', ' ', ' '},
            {' ', ' ', 'x', ' ', ' '}
        };
        CharGrid cg3 = new CharGrid(grid3);
        assertEquals(0, cg3.countPlus());
    }

    @Test
    public void testCountPlus34() {
        char[][] grid4 = new char[][]{
            {' ', ' ', ' ', 'x', ' ', ' ', ' '},
            {' ', ' ', ' ', 'x', ' ', ' ', ' '},
            {' ', ' ', ' ', 'x', ' ', ' ', ' '},
            {' ', 'x', 'x', 'x', 'x', 'x', ' '},
            {' ', ' ', ' ', 'x', ' ', ' ', ' '},
            {' ', ' ', ' ', 'x', ' ', 'x', ' '},
            {' ', ' ', ' ', 'x', ' ', ' ', ' '}
        };
        CharGrid cg4 = new CharGrid(grid4);
        assertEquals(0, cg4.countPlus());
    }

    @Test
    public void testCountPlus35() {
        char[][] grid5 = new char[][]{
            {' ', ' ', ' ', ' ', ' ', ' ', ' '},
            {' ', ' ', ' ', 'x', ' ', ' ', ' '},
            {' ', ' ', ' ', 'x', ' ', ' ', ' '},
            {' ', 'x', 'x', 'x', 'x', 'x', ' '},
            {' ', ' ', ' ', 'x', ' ', ' ', ' '},
            {' ', ' ', ' ', 'x', ' ', 'x', ' '},
            {' ', ' ', ' ', ' ', ' ', ' ', ' '}
        };
        CharGrid cg5 = new CharGrid(grid5);
        assertEquals(1, cg5.countPlus());
    }

    @Test
    public void testCountPlus36() {
        char[][] grid6 = new char[][]{
            {' ', 't', ' ', 'x', ' ', ' ', ' '},
            {'t', 't', 't', 'x', ' ', ' ', ' '},
            {' ', 't', ' ', 'x', ' ', ' ', ' '},
            {'x', 'x', 'x', 'x', 'x', 'x', 'x'},
            {' ', ' ', ' ', 'x', ' ', ' ', ' '},
            {' ', ' ', ' ', 'x', ' ', 'x', ' '},
            {' ', ' ', ' ', 'x', ' ', ' ', ' '}
        };
        CharGrid cg6 = new CharGrid(grid6);
        assertEquals(2, cg6.countPlus());
    }

    @Test
    public void testCountPlus37() {
        char[][] grid7 = new char[][]{
            {' ', ' ', 'p', ' ', ' ', 'y', ' ', ' ', ' '},
            {' ', ' ', 'p', ' ', 'y', 'y', 'y', 'x', ' '},
            {'p', 'p', 'p', 'p', 'p', 'y', 'x', 'x', 'x'},
            {' ', ' ', 'p', ' ', ' ', 'y', ' ', 'x', ' '},
            {' ', ' ', 'p', ' ', 'y', 'y', 'y', ' ', ' '},
            {'z', 'z', 'z', 'z', 'z', 'y', 'z', 'z', 'z'},
            {' ', ' ', 'x', 'x', ' ', ' ', ' ', ' ', ' '},};
        CharGrid cg7 = new CharGrid(grid7);
        assertEquals(2, cg7.countPlus());
    }

    @Test
    public void testCountPlus38() {
        char[][] grid8 = new char[][]{
            {' ', ' ', 'p', ' ', ' ', 'q', ' ', ' ', ' '},
            {' ', ' ', 'p', ' ', 'q', 'q', 'q', 'x', ' '},
            {'p', 'p', 'p', 'p', 'p', 'q', 'x', 'x', 'x'},
            {' ', ' ', 'p', ' ', ' ', 'y', ' ', 'x', ' '},
            {' ', ' ', 'p', ' ', 'y', 'y', 'y', ' ', ' '},
            {'z', 'z', 'z', 'z', 'z', 'y', 'z', 'z', 'z'},
            {' ', ' ', 'x', 'x', ' ', 'y', ' ', ' ', ' '},};
        CharGrid cg8 = new CharGrid(grid8);
        assertEquals(3, cg8.countPlus());
    }


}

Answer 1

I would much prefer to be given hints or general principles as to how my code could be improved. I think this way, me, and everyone that read this post could get more out of this exercise this way.

I don't know that I agree with this, but that's more of a meta discussion. This is me trying to follow that. I may miss in both directions though (not providing enough discussion to make my points or providing too much for what you want).

        //do not accept grid that has length or width less than 3

Why not?

        if (grid.length < 3 || grid[0].length < 3) {
            return 0;
        }

You might consider that zero is a perfectly good answer to the problem. If a dimension is less than three, how many pluses could you possibly find?

                numberOfPlus += isPlus(xCoordinate, yCoordinate, grid[yCoordinate][xCoordinate]) ? 1 : 0;

Why do numberOfPlus += 0? It's effectively a no-op. So why is this better than

                if (isPlus(xCoordinate, yCoordinate, grid[yCoordinate][xCoordinate])) {
                    numberOfPlus++;
                }

The latter version does the same number of comparisons and fewer additions. I would also find it easier to read.

        int currentRadius = radiusOfPlus;

You don't actually need to make a new variable for this. The radiusOfPlus variable can be modified and you never need both values at once.

        boolean topInBound = isInBounds(top);
        boolean topSameCharacter = false;
        if (topInBound) {
            topSameCharacter = isSameCharacter(top, middleCharacter);
        }

You don't use topInBound outside this block. And only use it once after setting it. There is an obvious way to drop a line from it. And you could actually drop the whole thing down to one if you define the helper method properly. Note that you always use isInBounds and isSameCharacter together such that topSameCharacter or whatever is only true if both are.

You do this same pattern four times. Plus another eight times with a similar pattern later.

        if (Boolean.TRUE.equals(topSameCharacter) && Boolean.TRUE.equals(bottomSameCharacter)
                && Boolean.TRUE.equals(leftSameCharacter) && Boolean.TRUE.equals(rightSameCharacter)) {

The equal method returns a Boolean. So really, Boolean.TRUE.equals(topSameCharacter) is just a complicated way of writing topSameCharacter.

            //else if all four surroudning space contain different character

I find this location for the comment confusing. I'd put it after the next couple lines instead so that it is inside the block to which it applies. Also, note the spelling of "surrounding".

        } else if (Boolean.FALSE.equals(topSameCharacter) && Boolean.FALSE.equals(bottomSameCharacter)
                && Boolean.FALSE.equals(leftSameCharacter) && Boolean.FALSE.equals(rightSameCharacter)) {

Similarly, Boolean.FALSE.equals(topSameCharacter) is the same as !topSameCharacter.

What happens if you add && radiusOfPlus > 1 to that expression and remove all the code inside the {}? What will it return if that makes it false? What if it stays true?

Answer 2

Specification interpretation

I assume that the countPlus() method should have public access. Default access rarely makes sense.

By my interpretation, there is no rule prohibiting "whiskers" on a plus; even a swastika should count as a valid plus. That is, I would consider the following test to contain one plus:

@Test
public void testCountPlus33() {
    char[][] grid3 = new char[][]{
        {' ', ' ', 'x', ' ', ' '},
        {' ', ' ', 'x', ' ', ' '},
        {'x', 'x', 'x', 'x', 'x'},
        {'x', ' ', 'x', ' ', ' '},
        {' ', ' ', 'x', ' ', ' '}
    };
    CharGrid cg3 = new CharGrid(grid3);
    assertEquals(0, cg3.countPlus());
}

Unit tests

Since jUnit 4, you no longer need to name tests using the testName() convention. With the @Test annotation, you can name the test any method name you want.

Algorithm

I do not recommend writing unnecessary special-case tests like this:

//do not accept grid that has length or width less than 3
if (grid.length < 3 || grid[0].length < 3) {
    return 0;
}

Since the algorithm works in the general case, the loops will complete very quickly anyway for undersized grids, you would be better off simplifying the code.

Looking for crosses by starting at an assumed center point is not an efficient strategy. It ends up causing a lot of unnecessary guesswork. In contrast, it is very easy to look for horizontal bars, check that the width is odd, and verify the expected vertical bar.

I am also not fond of how the radiusOfPlus(…) method works recursively, and how it returns 0 to indicate a malformed cross.

Suggested solution

I know that you only asked for hints, but this solution is so short that it's easier to post it than to hint at how to write it. Note that I've used a regular expression as a convenient way to look for the horizontal bars.

import java.util.regex.*;

public class CharGrid {

    private char[][] grid;

    /**
     * Constructs a new CharGrid with the given grid. Does not make a copy.
     *
     * @param grid
     */
    public CharGrid(char[][] grid) {
        this.grid = grid;
    }

    /**
     * Regex for three or more of the same non-space character.
     */
    private static final Pattern SAME_CHAR = Pattern.compile("([^ ])\\1{2,}");

    public int countPlus() {
        int plusCount = 0;
        // Don't bother looking at the top or bottom row
        for (int r = 1; r < this.grid.length - 1; r++) {
            Matcher m = SAME_CHAR.matcher(new String(this.grid[r]));
            while (m.find()) {
                if (isPlusWithHorizontalBar(r, m.start(), m.end())) {
                    plusCount++;
                }
            }
        }
        return plusCount;
    }

    /**
     * Tests whether there is a plus sign with the specified streak of
     * identical characters as its horizontal bar.
     *
     * @param row      The row within the grid that contains the streak
     * @param startCol The index of the start of the streak
     * @param endCol   The index just beyond the end of the streak
     */
    private boolean isPlusWithHorizontalBar(int row, int startCol, int endCol) {
        int width = endCol - startCol,
            radius = width / 2,
            startRow = row - radius,
            endRow = row + radius + 1,
            col = startCol + radius;
        char c = this.grid[row][col];

        if (width % 2 == 0) {
            return false;       // Even width, cannot be symmetrical
        } else if (startRow < 0 || endRow > this.grid.length) {
            return false;       // Too close to top or bottom
        } else if (startRow > 0 && this.grid[startRow - 1][col] == c) {
            return false;       // Junk at top
        } else if (endRow < this.grid.length && this.grid[endRow][col] == c) {
            return false;       // Junk at bottom
        }

        for (int r = startRow; r < endRow; r++) {
            if (this.grid[r][col] != c) {
                return false;   // Broken vertical bar
            }
        }
        return true;
    }
}