Skip to content

Commit c464543

Browse files
kkyb123jmrunkle
kkyb123
and
jmrunkle
authored
Implement Connect Exercise (exercism#2027)
* exercism#1743 | Setup connect practice exercise * exercism#1743 | Implement verification tests * exercism#1743 | Provide an initial model of the board based on the disjoint-set data structure. * exercism#1743 | Complete implementation of connect * exercism#1743 | Update starter implementation * exercism#1743 | Fix code style * Update exercises/practice/connect/.docs/instructions.md Use splitting on sentence break to reduce the splash radius as suggested. Co-authored-by: Jason Runkle <jmrunkle@gmail.com> * Update exercises/practice/connect/src/main/java/Connect.java Add trailing newline as suggested Co-authored-by: Jason Runkle <jmrunkle@gmail.com> * exercism#1743 | Refactor: make the solution more readable. We clear define the UnionFind data structure in a class. We define a board and its methods. We then use them in providing a solution to the exercise. * exercism#1743 | Add example files to config.json * exercism#1743 | Use AssertJ for assertions in test * Update exercises/practice/connect/.docs/instructions.md Update instructions Co-authored-by: Jason Runkle <jmrunkle@gmail.com> * exercism#1743 | Fix instructions.md * exercism#1743 | add Winner enum as editor read-only file * Update exercises/practice/connect/.meta/config.json Co-authored-by: Jason Runkle <jmrunkle@gmail.com>
1 parent 2d905a2 commit c464543

File tree

13 files changed

+616
-0
lines changed

13 files changed

+616
-0
lines changed

‎config.json

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1882,6 +1882,20 @@
18821882
"conditionals-if",
18831883
"floating_point_numbers"
18841884
]
1885+
},
1886+
{
1887+
"slug": "connect",
1888+
"name": "Connect",
1889+
"uuid": "1532b9a8-7e0d-479f-ad55-636e01e9d19f",
1890+
"practices": ["enums", "switch-statements"],
1891+
"prerequisites": [
1892+
"strings",
1893+
"chars",
1894+
"enums",
1895+
"arrays",
1896+
"if-statements"
1897+
],
1898+
"difficulty": 8
18851899
}
18861900
],
18871901
"foregone": []

‎exercises/practice/connect/.docs/instructions.md

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
# Instructions
2+
3+
Compute the result for a game of Hex / Polygon.
4+
5+
The abstract boardgame known as [Hex](https://en.wikipedia.org/wiki/Hex_%28board_game%29) / Polygon / CON-TAC-TIX is quite simple in rules, though complex in practice.
6+
Two players place stones on a parallelogram with hexagonal fields.
7+
The player to connect his/her stones to the opposite side first wins.
8+
The four sides of the parallelogram are divided between the two players (i.e. one player gets assigned a side and the side directly opposite it and the other player gets assigned the two other sides).
9+
10+
Your goal is to build a program that given a simple representation of a board computes the winner (or lack thereof).
11+
Note that all games need not be "fair". (For example, players may have mismatched piece counts or the game's board might have a different width and height.)
12+
13+
The boards look like this:
14+
15+
```text
16+
. O . X .
17+
. X X O .
18+
O O O X .
19+
. X O X O
20+
X O O O X
21+
```
22+
23+
"Player `O`" plays from top to bottom, "Player `X`" plays from left to right. In the above example `O` has made a connection from left to right but nobody has won since `O` didn't connect top and bottom.

‎exercises/practice/connect/.meta/config.json

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
{
2+
"blurb": "Compute the result for a game of Hex / Polygon.",
3+
"authors": [
4+
"kkyb123"
5+
],
6+
"contributors": [],
7+
"files": {
8+
"solution": [
9+
"src/main/java/Connect.java"
10+
],
11+
"test": [
12+
"src/test/java/ConnectTest.java"
13+
],
14+
"example": [
15+
".meta/src/reference/java/Connect.java",
16+
".meta/src/reference/java/Board.java",
17+
".meta/src/reference/java/UnionFind.java",
18+
".meta/src/reference/java/Winner.java"
19+
],
20+
"editor": [
21+
"src/main/java/Winner.java"
22+
]
23+
}
24+
}

‎exercises/practice/connect/.meta/src/reference/java/Board.java

Lines changed: 106 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,106 @@
1+
class Board {
2+
3+
private final boolean[][] boardFields;
4+
private final UnionFind unionFind;
5+
private final int boardHorizontalSize;
6+
private final int boardVerticalSize;
7+
private final boolean winHorizontally;
8+
9+
Board(int boardHorizontalSize, int boardVerticalSize, boolean winHorizontally) {
10+
11+
this.boardHorizontalSize = boardHorizontalSize;
12+
this.boardVerticalSize = boardVerticalSize;
13+
this.winHorizontally = winHorizontally;
14+
15+
//The fields of the board. A field has a stone if it is set to true, otherwise it is set to false.
16+
boardFields = new boolean[boardVerticalSize][boardHorizontalSize];
17+
18+
//The number of fields on the board is equal to the board's length multiply by its height.
19+
//Here the fields also represent the elements of our UnionFind (Disjoint-set) data structure.
20+
unionFind = new UnionFind(boardHorizontalSize * boardVerticalSize);
21+
22+
int indexOfTopLeftField = 0;
23+
if (winHorizontally) {
24+
//If the player wins horizontally, then we;
25+
//Make the top left field the representative of all the fields of the left. And makes the top right field
26+
//the representation of all the fields of the right. In the future, by just checking if the top left field
27+
//and the top right field have the same representatives (are connected), we will be able to determine if
28+
//the left and right side are connected, therefore determine if player X won.
29+
int indexOfTopRightField = boardHorizontalSize - 1;
30+
for (int i = 1; i < boardVerticalSize; i++) {
31+
unionFind.union(indexOfTopLeftField, i * boardHorizontalSize);
32+
unionFind.union(indexOfTopRightField, indexOfTopRightField + (i * boardHorizontalSize));
33+
}
34+
} else {
35+
//If the player wins vertically, then we;
36+
//Make the top left field the representative of all the fields of the top. And makes the bottom left field
37+
//the representation of all the fields of the bottom. In the future, by just checking if the top left field
38+
//and the bottom left field have the same representatives (are connected), we will be able to determine if
39+
//the top and bottom side are connected, therefore determine if player O won.
40+
int indexOfBottomLeftField = boardHorizontalSize * (boardVerticalSize - 1);
41+
for (int i = 1; i < boardHorizontalSize; i++) {
42+
unionFind.union(indexOfTopLeftField, i);
43+
unionFind.union(indexOfBottomLeftField, indexOfBottomLeftField + i);
44+
}
45+
}
46+
47+
48+
}
49+
50+
void placeStone(int row, int col) {
51+
if (hasStone(row, col)) {
52+
return;
53+
}
54+
boardFields[row][col] = true;
55+
56+
//Check if the player has a stone on the field at the top, then connect it to this field
57+
if (row > 0 && hasStone(row - 1, col)) {
58+
connect(row, col, row - 1, col);
59+
}
60+
//Check if the player has a stone on the field at the top-right, then connect it to this field
61+
if (row > 0 && col < boardHorizontalSize - 1 && hasStone(row - 1, col + 1)) {
62+
connect(row, col, row - 1, col + 1);
63+
}
64+
65+
//Check if the player has a stone on the field at the bottom, then connect it to this field
66+
if (row < boardVerticalSize - 1 && hasStone(row + 1, col)) {
67+
connect(row, col, row + 1, col);
68+
}
69+
//Check if the player has a stone on the field at the bottom-left, then connect it to this field
70+
if (row < boardVerticalSize - 1 && col > 0 && hasStone(row + 1, col - 1)) {
71+
connect(row, col, row + 1, col - 1);
72+
}
73+
74+
//Check if the player has a stone on the field on the left, then connect it to this field
75+
if (col > 0 && hasStone(row, col - 1)) {
76+
connect(row, col, row, col - 1);
77+
}
78+
//Check if the player has a stone on the field on the right, then connect it to this field
79+
if (col < boardHorizontalSize - 1 && hasStone(row, col + 1)) {
80+
connect(row, col, row, col + 1);
81+
}
82+
}
83+
84+
boolean hasStone(int row, int col) {
85+
return boardFields[row][col];
86+
}
87+
88+
void connect(int rowa, int cola, int rowb, int colb) {
89+
int indexOfFieldA = rowa * boardHorizontalSize + cola;
90+
int indexOfFieldB = rowb * boardHorizontalSize + colb;
91+
unionFind.union(indexOfFieldA, indexOfFieldB);
92+
}
93+
94+
boolean playerWins() {
95+
int topLeftRepresentative = unionFind.find(0);
96+
if (winHorizontally) {
97+
//If top-left field is connected to top-right field, then left side is connected to right side and player X
98+
// wins
99+
return topLeftRepresentative == unionFind.find(boardHorizontalSize - 1);
100+
} else {
101+
//If top-left field is connected to bottom-left field, then top side is connected to bottom side and
102+
// player O wins
103+
return topLeftRepresentative == unionFind.find(boardHorizontalSize * (boardVerticalSize - 1));
104+
}
105+
}
106+
}

‎exercises/practice/connect/.meta/src/reference/java/Connect.java

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
/**
2+
* To solve our exercise, we are going to model our board based on disjoint-set data structure, also called a
3+
* union-find data structure or merge-find set. We are going to use two sets. One for player O and the other for
4+
* player X.
5+
* For additional documentation, check
6+
* <a href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure">Wikipedia Disjoint-set Data Structure</a>
7+
* or <a href="https://algs4.cs.princeton.edu/15uf">Section 1.5</a> of
8+
* <i>Algorithms, 4th Edition, A nice book on DSA</i> by Robert Sedgewick and Kevin Wayne.
9+
*/
10+
class Connect {
11+
12+
private Board boardO;
13+
private Board boardX;
14+
private int boardHorizontalSize;
15+
private int boardVerticalSize;
16+
17+
public Connect(String[] board) {
18+
if (board.length == 0) {
19+
return;
20+
}
21+
22+
boardHorizontalSize = board[0]
23+
.replace(" ", "") // remove spaces
24+
.length();
25+
boardVerticalSize = board.length;
26+
27+
//Player O and Player X don't win in the same directions. Therefore, we use two different boards which track
28+
//their wins in different directions
29+
boardO = new Board(boardHorizontalSize, boardVerticalSize, false);
30+
boardX = new Board(boardHorizontalSize, boardVerticalSize, true);
31+
32+
//Place stones on the board
33+
for (int i = 0; i < board.length; i++) {
34+
String row = board[i].replace(" ", "");
35+
for (int j = 0; j < row.length(); j++) {
36+
if (row.charAt(j) == 'O') {
37+
boardO.placeStone(i, j);
38+
}
39+
if (row.charAt(j) == 'X') {
40+
boardX.placeStone(i, j);
41+
}
42+
}
43+
}
44+
}
45+
46+
public Winner computeWinner() {
47+
if (boardO == null || boardX == null) {
48+
return Winner.NONE;
49+
}
50+
51+
boolean playerOCanWin = boardHorizontalSize != 1 || boardO.hasStone(0, 0);
52+
boolean playerXCanWin = boardVerticalSize != 1 || boardX.hasStone(0, 0);
53+
54+
if (playerOCanWin && boardO.playerWins()) {
55+
return Winner.PLAYER_O;
56+
}
57+
58+
if (playerXCanWin && boardX.playerWins()) {
59+
return Winner.PLAYER_X;
60+
}
61+
return Winner.NONE;
62+
}
63+
}

‎exercises/practice/connect/.meta/src/reference/java/UnionFind.java

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
2+
/**
3+
* To solve our exercise, we are going to use the Union-find data structure, also called the Disjoint-set data
4+
* structure or Merge-find set. The Union-find data structure permit us to solve Dynamic Connectivity problems,
5+
* by helping us model the connections between elements of a system. Within such systems, the "connection" relation
6+
* is an equivalence relation. ie; An element is connected to itself, x connected to y implies y is connected to x,
7+
* and x connected to y, y connected to z, implies x is connected to z.
8+
* For additional documentation, check
9+
* <a href="https://en.wikipedia.org/wiki/Disjoint-set_data_structure">Wikipedia Disjoint-set Data Structure</a>
10+
* <a href="https://en.wikipedia.org/wiki/Dynamic_connectivity">Dynamic Connectivity</a>
11+
* <a href="https://algs4.cs.princeton.edu/15uf">Section 1.5</a> of
12+
* <i>Algorithms, 4th Edition, A nice book on DSA</i> by Robert Sedgewick and Kevin Wayne.
13+
*/
14+
class UnionFind {
15+
16+
/**
17+
* The disjoint-set of elements. An element is a parent (representative) of a subset of the disjoint set if it
18+
* is its own parent; ie parent[i] == i. At initialization all elements are their own parent.
19+
*/
20+
private final int[] parent;
21+
22+
/**
23+
* The sizes of each subset. This will help us better implemented the data structure.
24+
*/
25+
private final int[] size;
26+
27+
/**
28+
* We initialize the data structure with a number of elements.
29+
*
30+
* @param numberOfElements the number of elements
31+
*/
32+
UnionFind(int numberOfElements) {
33+
parent = new int[numberOfElements];
34+
size = new int[numberOfElements];
35+
36+
for (int i = 0; i < parent.length; i++) {
37+
parent[i] = i;
38+
size[i] = 1;
39+
}
40+
}
41+
42+
/**
43+
* We find the parent or representation of an element in the set. We browse up the ancestors of an element until
44+
* we reach the parent that is its own parent. This parent is the element's representative
45+
*
46+
* @param element the element
47+
* @return the parent representative of this element
48+
*/
49+
int find(int element) {
50+
while (element != parent[element]) {
51+
//We use a technique called path compression, so that subsequent find operations will be faster
52+
parent[element] = parent[parent[element]];
53+
element = parent[element];
54+
}
55+
return element;
56+
}
57+
58+
/**
59+
* Unify or connect two elements. The connection is done by making both elements have the same parent
60+
* representative
61+
*
62+
* @param elementA first element
63+
* @param elementB second element
64+
*/
65+
void union(int elementA, int elementB) {
66+
int parentA = find(elementA);
67+
int parentB = find(elementB);
68+
if (parentA == parentB) {
69+
return;
70+
}
71+
72+
// We place subsets of smaller sizes under bigger subsets making the find operation more performant
73+
if (size[parentA] < size[parentB]) {
74+
parent[parentA] = parentB;
75+
size[parentB] += size[parentA];
76+
} else {
77+
parent[parentB] = parentA;
78+
size[parentA] += size[parentB];
79+
}
80+
}
81+
}

‎exercises/practice/connect/.meta/src/reference/java/Winner.java

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
enum Winner {
2+
PLAYER_O,
3+
PLAYER_X,
4+
NONE
5+
}

‎exercises/practice/connect/.meta/tests.toml

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
# This is an auto-generated file.
2+
#
3+
# Regenerating this file via `configlet sync` will:
4+
# - Recreate every `description` key/value pair
5+
# - Recreate every `reimplements` key/value pair, where they exist in problem-specifications
6+
# - Remove any `include = true` key/value pair (an omitted `include` key implies inclusion)
7+
# - Preserve any other key/value pair
8+
#
9+
# As user-added comments (using the # character) will be removed when this file
10+
# is regenerated, comments can be added via a `comment` key.
11+
12+
[6eff0df4-3e92-478d-9b54-d3e8b354db56]
13+
description = "an empty board has no winner"
14+
15+
[298b94c0-b46d-45d8-b34b-0fa2ea71f0a4]
16+
description = "X can win on a 1x1 board"
17+
18+
[763bbae0-cb8f-4f28-bc21-5be16a5722dc]
19+
description = "O can win on a 1x1 board"
20+
21+
[819fde60-9ae2-485e-a024-cbb8ea68751b]
22+
description = "only edges does not make a winner"
23+
24+
[2c56a0d5-9528-41e5-b92b-499dfe08506c]
25+
description = "illegal diagonal does not make a winner"
26+
27+
[41cce3ef-43ca-4963-970a-c05d39aa1cc1]
28+
description = "nobody wins crossing adjacent angles"
29+
30+
[cd61c143-92f6-4a8d-84d9-cb2b359e226b]
31+
description = "X wins crossing from left to right"
32+
33+
[73d1eda6-16ab-4460-9904-b5f5dd401d0b]
34+
description = "O wins crossing from top to bottom"
35+
36+
[c3a2a550-944a-4637-8b3f-1e1bf1340a3d]
37+
description = "X wins using a convoluted path"
38+
39+
[17e76fa8-f731-4db7-92ad-ed2a285d31f3]
40+
description = "X wins using a spiral path"

‎exercises/practice/connect/build.gradle

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
apply plugin: "java"
2+
apply plugin: "eclipse"
3+
apply plugin: "idea"
4+
5+
// set default encoding to UTF-8
6+
compileJava.options.encoding = "UTF-8"
7+
compileTestJava.options.encoding = "UTF-8"
8+
9+
repositories {
10+
mavenCentral()
11+
}
12+
13+
dependencies {
14+
testImplementation "junit:junit:4.13"
15+
testImplementation "org.assertj:assertj-core:3.15.0"
16+
}
17+
18+
test {
19+
testLogging {
20+
exceptionFormat = 'short'
21+
showStandardStreams = true
22+
events = ["passed", "failed", "skipped"]
23+
}
24+
}

0 commit comments

Comments
 (0)