Skip to content

Commit 5422e53

Browse files
jtiggerjtigger
authored
Merge pull request exercism#243 from exercism/rectangles
rectangles: add to track
2 parents 204e243 + c1e9163 commit 5422e53

6 files changed

Lines changed: 309 additions & 1 deletion

File tree

‎config.json‎

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -55,7 +55,8 @@
5555
"wordy",
5656
"palindrome-products",
5757
"twelve-days",
58-
"sublist"
58+
"sublist",
59+
"rectangles"
5960
],
6061
"exercises": [
6162
{
@@ -317,6 +318,11 @@
317318
"slug": "sublist",
318319
"difficulty": 1,
319320
"topics": []
321+
},
322+
{
323+
"slug": "rectangles",
324+
"difficulty": 1,
325+
"topics": []
320326
}
321327
],
322328
"deprecated": [

‎exercises/rectangles/build.gradle‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
apply plugin: "java"
2+
apply plugin: "eclipse"
3+
apply plugin: "idea"
4+
5+
repositories {
6+
mavenCentral()
7+
}
8+
9+
dependencies {
10+
testCompile "junit:junit:4.12"
11+
}
12+
test {
13+
testLogging {
14+
exceptionFormat = 'full'
15+
events = ["passed", "failed", "skipped"]
16+
}
17+
}

‎exercises/rectangles/src/example/java/RectangleCounter.java‎

Lines changed: 115 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,115 @@
1+
import static java.util.Arrays.copyOfRange;
2+
import static java.util.Arrays.stream;
3+
4+
final class RectangleCounter {
5+
6+
int countRectangles(final String[] rawGrid) {
7+
final int nRows = rawGrid.length;
8+
if (nRows == 0) return 0;
9+
10+
final int nCols = rawGrid[0].length();
11+
if (nCols == 0) return 0;
12+
13+
return new Grid(nRows, nCols, rawGrid).countRectangles();
14+
}
15+
16+
private static final class Grid {
17+
18+
private enum Entry {
19+
CORNER,
20+
HLINE,
21+
VLINE,
22+
SPACE;
23+
24+
private static Entry fromChar(final char rawGridEntry) {
25+
switch (rawGridEntry) {
26+
case '+': return CORNER;
27+
case '-': return HLINE;
28+
case '|': return VLINE;
29+
case ' ': return SPACE;
30+
default: throw new IllegalStateException("Grid entry " + rawGridEntry + " not recognized.");
31+
}
32+
}
33+
}
34+
35+
private int nRows, nCols;
36+
private final Entry[][] entries;
37+
38+
private Grid(final int nRows, final int nCols, final String[] rawGrid) {
39+
this.nRows = nRows;
40+
this.nCols = nCols;
41+
this.entries = new Entry[nRows][nCols];
42+
43+
for (int nRow = 0; nRow < nRows; nRow++) {
44+
for (int nCol = 0; nCol < nCols; nCol++) {
45+
entries[nRow][nCol] = Entry.fromChar(rawGrid[nRow].charAt(nCol));
46+
}
47+
}
48+
}
49+
50+
private int countRectangles() {
51+
int result = 0;
52+
53+
for (int topRow = 0; topRow < nRows - 1; topRow++) {
54+
55+
for (int leftCol = 0; leftCol < nCols - 1; leftCol++) {
56+
57+
// Only check rectangles that lie below/to the right of our current coordinate:
58+
for (int bottomRow = topRow + 1; bottomRow < nRows; bottomRow++) {
59+
60+
for (int rightCol = leftCol + 1; rightCol < nCols; rightCol++) {
61+
62+
if (formsRectangle(topRow, bottomRow, leftCol, rightCol)) {
63+
result++;
64+
}
65+
}
66+
}
67+
}
68+
}
69+
70+
return result;
71+
}
72+
73+
private boolean formsRectangle(
74+
final int topRow,
75+
final int bottomRow,
76+
final int leftCol,
77+
final int rightCol) {
78+
79+
return entries[topRow][leftCol].equals(Entry.CORNER)
80+
&& entries[topRow][rightCol].equals(Entry.CORNER)
81+
&& entries[bottomRow][leftCol].equals(Entry.CORNER)
82+
&& entries[bottomRow][rightCol].equals(Entry.CORNER)
83+
&& isHorizontalLineSegment(topRow, leftCol, rightCol)
84+
&& isHorizontalLineSegment(bottomRow, leftCol, rightCol)
85+
&& isVerticalLineSegment(leftCol, topRow, bottomRow)
86+
&& isVerticalLineSegment(rightCol, topRow, bottomRow);
87+
}
88+
89+
private boolean isHorizontalLineSegment(final int row, final int leftCol, final int rightCol) {
90+
return stream(copyOfRange(getRow(row), leftCol, rightCol))
91+
.allMatch(entry -> entry.equals(Entry.HLINE) || entry.equals(Entry.CORNER));
92+
}
93+
94+
private boolean isVerticalLineSegment(final int col, final int topRow, final int bottomRow) {
95+
return stream(copyOfRange(getCol(col), topRow, bottomRow))
96+
.allMatch(entry -> entry.equals(Entry.VLINE) || entry.equals(Entry.CORNER));
97+
}
98+
99+
private Entry[] getRow(final int number) {
100+
return entries[number];
101+
}
102+
103+
private Entry[] getCol(final int number) {
104+
final Entry[] result = new Entry[nRows];
105+
106+
for (int nRow = 0; nRow < nRows; nRow++) {
107+
result[nRow] = entries[nRow][number];
108+
}
109+
110+
return result;
111+
}
112+
113+
}
114+
115+
}

‎exercises/rectangles/src/main/java/RectangleCounter.java‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
final class RectangleCounter {
2+
3+
4+
5+
}

‎exercises/rectangles/src/test/java/RectangleCounterTest.java‎

Lines changed: 164 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,164 @@
1+
import org.junit.Before;
2+
import org.junit.Ignore;
3+
import org.junit.Test;
4+
5+
import static org.junit.Assert.assertEquals;
6+
7+
public final class RectangleCounterTest {
8+
9+
private RectangleCounter rectangleCounter;
10+
11+
@Before
12+
public void setUp() {
13+
rectangleCounter = new RectangleCounter();
14+
}
15+
16+
@Test
17+
public void testInputWithNoColumnsContainsNoRectangles() {
18+
String[] inputGrid = new String[]{};
19+
20+
assertEquals(0, rectangleCounter.countRectangles(inputGrid));
21+
}
22+
23+
@Ignore
24+
@Test
25+
public void testNonTrivialInputWithNoRectangles() {
26+
String[] inputGrid = new String[]{" "};
27+
28+
assertEquals(0, rectangleCounter.countRectangles(inputGrid));
29+
}
30+
31+
@Ignore
32+
@Test
33+
public void testInputWithOneRectangle() {
34+
String[] inputGrid = new String[]{
35+
"+-+",
36+
"| |",
37+
"+-+"
38+
};
39+
40+
assertEquals(1, rectangleCounter.countRectangles(inputGrid));
41+
}
42+
43+
@Ignore
44+
@Test
45+
public void testInputWithTwoRectanglesWithoutSharedEdges() {
46+
String[] inputGrid = new String[]{
47+
" +-+",
48+
" | |",
49+
"+-+-+",
50+
"| | ",
51+
"+-+ "
52+
};
53+
54+
assertEquals(2, rectangleCounter.countRectangles(inputGrid));
55+
}
56+
57+
@Ignore
58+
@Test
59+
public void testInputWithFiveRectanglesWithSharedEdges() {
60+
String[] inputGrid = new String[]{
61+
" +-+",
62+
" | |",
63+
"+-+-+",
64+
"| | |",
65+
"+-+-+"
66+
};
67+
68+
assertEquals(5, rectangleCounter.countRectangles(inputGrid));
69+
}
70+
71+
@Ignore
72+
@Test
73+
public void testThatRectangleOfHeightOneIsCounted() {
74+
String[] inputGrid = new String[]{
75+
"+--+",
76+
"+--+"
77+
};
78+
79+
assertEquals(1, rectangleCounter.countRectangles(inputGrid));
80+
}
81+
82+
@Ignore
83+
@Test
84+
public void testThatRectangleOfWidthOneIsCounted() {
85+
String[] inputGrid = new String[]{
86+
"++",
87+
"||",
88+
"++"
89+
};
90+
91+
assertEquals(1, rectangleCounter.countRectangles(inputGrid));
92+
}
93+
94+
@Ignore
95+
@Test
96+
public void testThatOneByOneSquareIsCounted() {
97+
String[] inputGrid = new String[]{
98+
"++",
99+
"++"
100+
};
101+
102+
assertEquals(1, rectangleCounter.countRectangles(inputGrid));
103+
}
104+
105+
@Ignore
106+
@Test
107+
public void testThatIncompleteRectanglesAreNotCounted() {
108+
String[] inputGrid = new String[]{
109+
" +-+",
110+
" |",
111+
"+-+-+",
112+
"| | -",
113+
"+-+-+"
114+
};
115+
116+
assertEquals(1, rectangleCounter.countRectangles(inputGrid));
117+
}
118+
119+
@Ignore
120+
@Test
121+
public void testThatRectanglesOfDifferentSizesAreAllCounted() {
122+
String[] inputGrid = new String[]{
123+
"+------+----+",
124+
"| | |",
125+
"+---+--+ |",
126+
"| | |",
127+
"+---+-------+"
128+
};
129+
130+
assertEquals(3, rectangleCounter.countRectangles(inputGrid));
131+
}
132+
133+
@Ignore
134+
@Test
135+
public void testThatIntersectionsWithoutCornerCharacterDoNotCountAsRectangleCorners() {
136+
String[] inputGrid = new String[]{
137+
"+------+----+",
138+
"| | |",
139+
"+------+ |",
140+
"| | |",
141+
"+---+-------+"
142+
};
143+
144+
assertEquals(2, rectangleCounter.countRectangles(inputGrid));
145+
}
146+
147+
@Ignore
148+
@Test
149+
public void testLargeInputWithManyRectangles() {
150+
String[] inputGrid = new String[]{
151+
"+---+--+----+",
152+
"| +--+----+",
153+
"+---+--+ |",
154+
"| +--+----+",
155+
"+---+--+--+-+",
156+
"+---+--+--+-+",
157+
"+------+ | |",
158+
" +-+"
159+
};
160+
161+
assertEquals(60, rectangleCounter.countRectangles(inputGrid));
162+
}
163+
164+
}

‎exercises/settings.gradle‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -34,6 +34,7 @@ include 'phone-number'
3434
include 'pig-latin'
3535
include 'queen-attack'
3636
include 'raindrops'
37+
include 'rectangles'
3738
include 'rna-transcription'
3839
include 'robot-name'
3940
include 'robot-simulator'

0 commit comments

Comments
 (0)