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;
}
}
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 < grid.length && 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;
}
}
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;
}
}
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 < grid.length && 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;
}
}
lang-java