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

to Rectangles in the Java Track

Published at Jun 18 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));
}

}``````
``````import static java.util.function.Function.identity;

import java.util.stream.IntStream;

class RectangleCounter {

private static final char CORNER = '+';
private static final char HORIZONTAL_LINE = '-';
private static final char VERTICAL_LINE = '|';

int countRectangles(final String[] inputGrid) {

final int width = inputGrid.length > 0 ? inputGrid[0].length() : 0;
final int height = inputGrid.length;

return IntStream.range(0, width - 1)
.mapToObj(left -> IntStream.range(0, height - 1)
.filter(top -> this.isCorner(inputGrid, left, top))
.mapToObj(top -> IntStream.range(left + 1, width)
.filter(right -> this.isCorner(inputGrid, right, top))
.mapToObj(right -> IntStream.range(top + 1, height)
.filter(bottom -> this.isRectangle(inputGrid, left, top, right, bottom))
.count())))
.flatMap(identity())
.flatMapToInt(list -> list.mapToInt(Long::intValue))
.sum();
}

private boolean isRectangle(final String[] inputGrid, final int left, final int top, final int right, final int bottom) {
return this.isCorner(inputGrid, left, bottom)
&& this.isCorner(inputGrid, right, bottom)
&& this.isHorizontalLine(inputGrid, top, left, right)
&& this.isHorizontalLine(inputGrid, bottom, left, right)
&& this.isVerticalLine(inputGrid, left, top, bottom)
&& this.isVerticalLine(inputGrid, right, top, bottom);
}

private boolean isCorner(final String[] inputGrid, final int x, final int y) {
return inputGrid[y].charAt(x) == CORNER;
}

private boolean isHorizontalLine(final String[] inputGrid, final int y, final int left, final int right) {
return IntStream.range(left + 1, right)
.allMatch(x -> (inputGrid[y].charAt(x) == HORIZONTAL_LINE || inputGrid[y].charAt(x) == CORNER));
}

private boolean isVerticalLine(final String[] inputGrid, final int x, final int top, final int bottom) {
return IntStream.range(top + 1, bottom)
.allMatch(y -> (inputGrid[y].charAt(x) == VERTICAL_LINE || inputGrid[y].charAt(x) == CORNER));
}

}``````