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());
}
}