ðŸŽ‰ Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io ðŸŽ‰

# sparklicorn's solution

## to Rectangles in the Java Track

Published at Sep 17 2020 · 0 comments
Instructions
Test suite
Solution

Count the rectangles in an ASCII diagram like the one below.

``````   +--+
++  |
+-++--+
|  |  |
+--+--+
``````

The above diagram contains 6 rectangles:

``````

+-----+
|     |
+-----+
``````
``````   +--+
|  |
|  |
|  |
+--+
``````
``````   +--+
|  |
+--+

``````
``````

+--+
|  |
+--+
``````
``````

+--+
|  |
+--+
``````
``````
++
++

``````

You may assume that the input is always a proper rectangle (i.e. the length of every line equals the length of the first line).

## Setup

Go through the setup instructions for Java to install the necessary dependencies:

https://exercism.io/tracks/java/installation

# Running the tests

You can run all the tests for an exercise by entering the following in your terminal:

``````\$ gradle test
``````

In the test suites all tests but the first have been skipped.

Once you get a test passing, you can enable the next one by removing the `@Ignore("Remove to run test")` annotation.

## Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

### RectangleCounterTest.java

``````import org.junit.Before;
import org.junit.Ignore;
import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class RectangleCounterTest {

private RectangleCounter rectangleCounter;

@Before
public void setUp() {
rectangleCounter = new RectangleCounter();
}

@Test
public void testInputWithNoRowsContainsNoRectangles() {
String[] inputGrid = new String[]{};

assertEquals(0, rectangleCounter.countRectangles(inputGrid));
}

@Ignore("Remove to run test")
@Test
public void testInputWithNoColumnsContainsNoRectangles() {
String[] inputGrid = new String[]{""};

assertEquals(0, rectangleCounter.countRectangles(inputGrid));
}

@Ignore("Remove to run test")
@Test
public void testNonTrivialInputWithNoRectangles() {
String[] inputGrid = new String[]{" "};

assertEquals(0, rectangleCounter.countRectangles(inputGrid));
}

@Ignore("Remove to run test")
@Test
public void testInputWithOneRectangle() {
String[] inputGrid = new String[]{
"+-+",
"| |",
"+-+"
};

assertEquals(1, rectangleCounter.countRectangles(inputGrid));
}

@Ignore("Remove to run test")
@Test
public void testInputWithTwoRectanglesWithoutSharedEdges() {
String[] inputGrid = new String[]{
"  +-+",
"  | |",
"+-+-+",
"| |  ",
"+-+  "
};

assertEquals(2, rectangleCounter.countRectangles(inputGrid));
}

@Ignore("Remove to run test")
@Test
public void testInputWithFiveRectanglesWithSharedEdges() {
String[] inputGrid = new String[]{
"  +-+",
"  | |",
"+-+-+",
"| | |",
"+-+-+"
};

assertEquals(5, rectangleCounter.countRectangles(inputGrid));
}

@Ignore("Remove to run test")
@Test
public void testThatRectangleOfHeightOneIsCounted() {
String[] inputGrid = new String[]{
"+--+",
"+--+"
};

assertEquals(1, rectangleCounter.countRectangles(inputGrid));
}

@Ignore("Remove to run test")
@Test
public void testThatRectangleOfWidthOneIsCounted() {
String[] inputGrid = new String[]{
"++",
"||",
"++"
};

assertEquals(1, rectangleCounter.countRectangles(inputGrid));
}

@Ignore("Remove to run test")
@Test
public void testThatOneByOneSquareIsCounted() {
String[] inputGrid = new String[]{
"++",
"++"
};

assertEquals(1, rectangleCounter.countRectangles(inputGrid));
}

@Ignore("Remove to run test")
@Test
public void testThatIncompleteRectanglesAreNotCounted() {
String[] inputGrid = new String[]{
"  +-+",
"    |",
"+-+-+",
"| | -",
"+-+-+"
};

assertEquals(1, rectangleCounter.countRectangles(inputGrid));
}

@Ignore("Remove to run test")
@Test
public void testThatRectanglesOfDifferentSizesAreAllCounted() {
String[] inputGrid = new String[]{
"+------+----+",
"|      |    |",
"+---+--+    |",
"|   |       |",
"+---+-------+"
};

assertEquals(3, rectangleCounter.countRectangles(inputGrid));
}

@Ignore("Remove to run test")
@Test
public void testThatIntersectionsWithoutCornerCharacterDoNotCountAsRectangleCorners() {
String[] inputGrid = new String[]{
"+------+----+",
"|      |    |",
"+------+    |",
"|   |       |",
"+---+-------+"
};

assertEquals(2, rectangleCounter.countRectangles(inputGrid));
}

@Ignore("Remove to run test")
@Test
public void testLargeInputWithManyRectangles() {
String[] inputGrid = new String[]{
"+---+--+----+",
"|   +--+----+",
"+---+--+    |",
"|   +--+----+",
"+---+--+--+-+",
"+---+--+--+-+",
"+------+  | |",
"          +-+"
};

assertEquals(60, rectangleCounter.countRectangles(inputGrid));
}

}``````

### src/main/java/Graph.java

``````import java.util.HashMap;
import java.util.Map;

public class Graph<T> {
Map<T, Node<T>> nodes;

Graph() {
nodes = new HashMap<>();
}

void createAndConnectNodes(T aData, T bData) {
Node<T> a = nodes.get(aData);
Node<T> b = nodes.get(bData);

if (a == null) {
a = new Node<>(aData, null);
}
if (nodes.get(bData) == null) {
b = new Node<>(bData, null);
nodes.put(bData, b);
}

}
}``````

### src/main/java/Node.java

``````import java.util.HashSet;
import java.util.Set;

public class Node<T> {
T data;
Set<Node<T>> nexts;

Node(T data, Set<Node<T>> nextsSet) {
this.data = data;
this.nexts = new HashSet<>();
if (nextsSet != null) {
}
}

void addNext(Node<T> next) {
}

@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}

if (obj instanceof Node) {
return data.equals(((Node<?>) obj).data);
}

return false;
}

@Override
public int hashCode() {
return data.hashCode();
}
}``````

### src/main/java/RectangleCounter.java

``````import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class RectangleCounter {

public static final char NODE_CHAR = '+';
public static final char HORIZONTAL_EDGE_CHAR = '-';
public static final char VERTICAL_EDGE_CHAR = '|';

public int countRectangles(String[] inputGrid) {
// I prefer this to be a character matrix
char[][] inputChars = new char[inputGrid.length][];
for (int i = 0; i < inputGrid.length; i++) {
inputChars[i] = inputGrid[i].toCharArray();
}

// Node.data in this graph is an int representing coordinates in
// inputChars (coordinate = row * numCols + col).
Graph<Integer> graph = new Graph<>();
populateGraph(graph, inputChars);

Set<List<Node<Integer>>> paths = new HashSet<>();
for (Node<Integer> start : graph.nodes.values()) {
for (Node<Integer> next : start.nexts) {
List<Node<Integer>> path = new ArrayList<>();
findAllPaths(path, start.data, 4, paths);
}
}

// Not all paths are rectangular. There may be 4 nodes in a row, or similarly in a column.
int numCols = (inputChars.length > 0) ? inputChars[0].length : 0;
paths.removeIf((list) -> !isValidRectanglePath(list, numCols));

return paths.size();
}

void populateGraph(Graph<Integer> graph, char[][] input) {
for (int r = 0; r < input.length; r++) {
for (int c = 0; c < input[r].length; c++) {
if (input[r][c] == NODE_CHAR) {
findConnectedNodes(graph, r, c, input);
}
}
}
}

// Find nodes connected to the given coordinate
private void findConnectedNodes(Graph<Integer> graph, int row, int col, char[][] input) {
findConnectedNodesInDirection(graph, row, col, 0, -1, input, HORIZONTAL_EDGE_CHAR);
findConnectedNodesInDirection(graph, row, col, 0, 1, input, HORIZONTAL_EDGE_CHAR);
findConnectedNodesInDirection(graph, row, col, -1, 0, input, VERTICAL_EDGE_CHAR);
findConnectedNodesInDirection(graph, row, col, 1, 0, input, VERTICAL_EDGE_CHAR);
}

// Find nodes connected to the given coordinate by traversing the input
// in a given direction (specified by offsets).
// Only NODE_CHAR and edgeChars are allowed to be traversed over.
// Connected nodes are automatically added to the graph.
private static void findConnectedNodesInDirection(
Graph<Integer> graph,
int row, int col, int rowOffset, int colOffset,
char[][] input, char edgeChar
) {
for (
int rowIndex = row + rowOffset, colIndex = col + colOffset;
rowIndex >= 0 && rowIndex < input.length &&
colIndex >= 0 && colIndex < input[rowIndex].length;
rowIndex += rowOffset, colIndex += colOffset
) {
char c = input[rowIndex][colIndex];
if (c == edgeChar) {
continue;
}

if (c == NODE_CHAR) {
graph.createAndConnectNodes(
row * input[row].length + col,
rowIndex * input[row].length + colIndex
);

} else {
break;
}
}
}

/**
* Find all paths from a starting node path.get(0) to the target data, where no node is
* visited more than once.
* @param <T> Type of data Nodes contain.
* @param path - Starting path to search from. Pass a single node as a starting point.
* @param dest - Target data to locate.
* @param exactLength - an optional number of nodes that must be in the path to be added
* to the result set. Pass any int <= 0 for no length constraint.
* @param resultPaths - Set of paths that will be populated by this search.
*/
private static <T> void findAllPaths(List<Node<T>> path, T dest, int exactLength, Set<List<Node<T>>> resultPaths) {
// Base case: path is too long
if (exactLength > 0 && path.size() > exactLength) {
return;
}

Node<T> last = path.get(path.size() - 1);
//Base case: path.last holds our target data
if (last.data.equals(dest) && path.size() == exactLength) {
// Check if a permutation of this path already exists
for (List<Node<T>> resultPath : resultPaths) {
if (resultPath.containsAll(path)) {
return;
}
}
return;
}

for (Node<T> n : last.nexts) {
if (!path.contains(n)) {
List<Node<T>> nextPath = new ArrayList<>(path);
findAllPaths(nextPath, dest, exactLength, resultPaths);
}
}
}

private static boolean isValidRectanglePath(List<Node<Integer>> path, int numCols) {
if (path.size() != 4) {
return false;
}

int bits = 0;
int leftBit = 1<<3;
int rightBit = 1<<2;
int upBit = 1<<1;
int downBit = 1;

int destIndex = path.get(3).data;
int destRow = destIndex / numCols;
int destCol = destIndex % numCols;
for (int i = 0; i < 4; i++) {
int row = path.get(i).data / numCols;
int col = path.get(i).data % numCols;
if (row == destRow) {
if (col < destCol) {
bits |= leftBit;
} else {
bits |= rightBit;
}
} else {
if (row < destRow) {
bits |= upBit;
} else {
bits |= downBit;
}
}
destRow = row;
destCol = col;
}

return bits == 0xF;
}
}``````