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

# rdlf0's solution

## to Dominoes in the Java Track

Published at Jun 16 2020 · 0 comments
Instructions
Test suite
Solution

Make a chain of dominoes.

Compute a way to order a given set of dominoes in such a way that they form a correct domino chain (the dots on one half of a stone match the dots on the neighbouring half of an adjacent stone) and that dots on the halves of the stones which don't have a neighbour (the first and last stone) match each other.

For example given the stones `[2|1]`, `[2|3]` and `[1|3]` you should compute something like `[1|2] [2|3] [3|1]` or `[3|2] [2|1] [1|3]` or `[1|3] [3|2] [2|1]` etc, where the first and last numbers are the same.

For stones `[1|2]`, `[4|1]` and `[2|3]` the resulting chain is not valid: `[4|1] [1|2] [2|3]`'s first and last numbers are not the same. 4 != 3

Some test cases may use duplicate stones in a chain solution, assume that multiple Domino sets are being used.

## 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.

### DominoesTest.java

``````import static org.assertj.core.api.Assertions.assertThat;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertThrows;

import org.junit.Ignore;
import org.junit.Test;

import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class DominoesTest {

@Test
public void emtpyInputEmptyOutputTest() throws ChainNotFoundException {
Dominoes dominoes = new Dominoes();

List<Domino> dominoesList = new ArrayList<>();

List<Domino> chain = dominoes.formChain(dominoesList);

assertEquals("The output list should be empty.", 0, chain.size());
}

@Ignore("Remove to run test")
@Test
public void singletonInputSingletonOutput() throws ChainNotFoundException {
Dominoes dominoes = new Dominoes();

Domino[] dominoesArray = {new Domino(1, 1)};
List<Domino> dominoesList = Arrays.asList(dominoesArray);

List<Domino> chain = dominoes.formChain(dominoesList);

assertValidChain(dominoesList, chain);
}

@Ignore("Remove to run test")
@Test
public void singletonCantBeChainedTest() {
Dominoes dominoes = new Dominoes();

Domino[] dominoesArray = {new Domino(1, 2)};
List<Domino> dominoesList = Arrays.asList(dominoesArray);

ChainNotFoundException expected =
assertThrows(
ChainNotFoundException.class,
() -> dominoes.formChain(dominoesList));

assertThat(expected).hasMessage("No domino chain found.");
}

@Ignore("Remove to run test")
@Test
public void threeElementsTest() throws ChainNotFoundException {
Dominoes dominoes = new Dominoes();

Domino[] dominoesArray = {new Domino(1, 2), new Domino(3, 1), new Domino(2, 3)};
List<Domino> dominoesList = Arrays.asList(dominoesArray);

List<Domino> chain = dominoes.formChain(dominoesList);

assertValidChain(dominoesList, chain);
}

@Ignore("Remove to run test")
@Test
public void canReverseDominoesTest() throws ChainNotFoundException {
Dominoes dominoes = new Dominoes();

Domino[] dominoesArray = {new Domino(1, 2), new Domino(1, 3), new Domino(2, 3)};
List<Domino> dominoesList = Arrays.asList(dominoesArray);

List<Domino> chain = dominoes.formChain(dominoesList);

assertValidChain(dominoesList, chain);
}

@Ignore("Remove to run test")
@Test
public void cantBeChainedTest() {
Dominoes dominoes = new Dominoes();

Domino[] dominoesArray = {new Domino(1, 2), new Domino(4, 1), new Domino(2, 3)};
List<Domino> dominoesList = Arrays.asList(dominoesArray);

ChainNotFoundException expected =
assertThrows(
ChainNotFoundException.class,
() -> dominoes.formChain(dominoesList));

assertThat(expected).hasMessage("No domino chain found.");
}

@Ignore("Remove to run test")
@Test
public void disconnectedSimpleTest() {
Dominoes dominoes = new Dominoes();

Domino[] dominoesArray = {new Domino(1, 1), new Domino(2, 2)};
List<Domino> dominoesList = Arrays.asList(dominoesArray);

ChainNotFoundException expected =
assertThrows(
ChainNotFoundException.class,
() -> dominoes.formChain(dominoesList));

assertThat(expected).hasMessage("No domino chain found.");
}

@Ignore("Remove to run test")
@Test
public void disconnectedDoubleLoopTest() {
Dominoes dominoes = new Dominoes();

Domino[] dominoesArray = {new Domino(1, 2), new Domino(2, 1), new Domino(3, 4), new Domino(4, 3)};
List<Domino> dominoesList = Arrays.asList(dominoesArray);

ChainNotFoundException expected =
assertThrows(
ChainNotFoundException.class,
() -> dominoes.formChain(dominoesList));

assertThat(expected).hasMessage("No domino chain found.");
}

@Ignore("Remove to run test")
@Test
public void disconnectedSingleIsolatedTest() {
Dominoes dominoes = new Dominoes();

Domino[] dominoesArray = {new Domino(1, 2), new Domino(2, 3), new Domino(3, 1), new Domino(4, 4)};
List<Domino> dominoesList = Arrays.asList(dominoesArray);

ChainNotFoundException expected =
assertThrows(
ChainNotFoundException.class,
() -> dominoes.formChain(dominoesList));

assertThat(expected).hasMessage("No domino chain found.");
}

@Ignore("Remove to run test")
@Test
public void needBacktrackTest() throws ChainNotFoundException {
Dominoes dominoes = new Dominoes();

Domino[] dominoesArray = {new Domino(1, 2), new Domino(2, 3), new Domino(3, 1), new Domino(2, 4),
new Domino(4, 2)};
List<Domino> dominoesList = Arrays.asList(dominoesArray);

List<Domino> chain = dominoes.formChain(dominoesList);

assertValidChain(dominoesList, chain);
}

@Ignore("Remove to run test")
@Test
public void separateLoopsTest() throws ChainNotFoundException {
Dominoes dominoes = new Dominoes();

Domino[] dominoesArray = {new Domino(1, 2), new Domino(2, 3), new Domino(3, 1),
new Domino(1, 1), new Domino(2, 2), new Domino(3, 3)};
List<Domino> dominoesList = Arrays.asList(dominoesArray);

List<Domino> chain = dominoes.formChain(dominoesList);

assertValidChain(dominoesList, chain);
}

@Ignore("Remove to run test")
@Test
public void nineElementsTest() throws ChainNotFoundException {
Dominoes dominoes = new Dominoes();
Domino[] dominoesArray = {new Domino(1, 2), new Domino(5, 3), new Domino(3, 1),
new Domino(1, 2), new Domino(2, 4), new Domino(1, 6),
new Domino(2, 3), new Domino(3, 4), new Domino(5, 6)};
List<Domino> dominoesList = Arrays.asList(dominoesArray);

List<Domino> chain = dominoes.formChain(dominoesList);

assertValidChain(dominoesList, chain);
}

private void assertValidChain(List<Domino> inputDominoes, List<Domino> outputDominoes) {
assertSameDominoes(inputDominoes, outputDominoes);
assertEndDominoesMatch(outputDominoes);
assertConsecutiveDominoes(outputDominoes);
}

private void assertEndDominoesMatch(List<Domino> outputDominoes) {
int leftValueOfFirstDomino = outputDominoes.get(0).getLeft();
int rightValueOfLastDomino = outputDominoes.get(outputDominoes.size() - 1).getRight();
String errorMessage = "The left value of the first domino ("
+ leftValueOfFirstDomino
+ ") needs to match the right value of the last domino ("
+ rightValueOfLastDomino
+ ").";

assertEquals(errorMessage, leftValueOfFirstDomino, rightValueOfLastDomino);
}

private void assertSameDominoes(List<Domino> inputDominoes, List<Domino> outputDominoes) {
String errorMessage = "The number of dominoes in the input list (" + inputDominoes.size()
+ ") needs to match the number of dominoes in the output chain (" + outputDominoes.size() + ")";

assertEquals(errorMessage, inputDominoes.size(), outputDominoes.size());

for (Domino domino : inputDominoes) {
int inputFrequency = Collections.frequency(inputDominoes, domino);
int outputFrequency = Collections.frequency(outputDominoes, domino);

String frequencyErrorMessage = "The frequency of domino (" + domino.getLeft() + ", " +
domino.getRight() + ")" +
" in the input is (" + inputFrequency + "), but (" + outputFrequency + ") in the output.";

assertEquals(frequencyErrorMessage, inputFrequency, outputFrequency);
}
}

private void assertConsecutiveDominoes(List<Domino> dominoes) {
for (int i = 0; i < dominoes.size() - 1; i++) {

int rightValueOfIthDomino = dominoes.get(i).getRight();
int leftValueOfNextDomino = dominoes.get(i + 1).getLeft();
String errorMessage = "The right value of domino number " + i + " ("
+ rightValueOfIthDomino
+ ") needs to match the left value of domino number " + (i + 1) + " ("
+ leftValueOfNextDomino
+ ").";

assertEquals(errorMessage, dominoes.get(i).getRight(), dominoes.get(i + 1).getLeft());
}
}
}``````

### src/main/java/Dominoes.java

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

public class Dominoes {

private static final String CHAIN_NOT_FOUND_EXCEPTION = "No domino chain found.";

List<Domino> formChain(final List<Domino> dominoes) throws ChainNotFoundException {
}

private List<Domino> formChain(
final List<Domino> dominoes,
final LinkedList<Domino> chain) throws ChainNotFoundException {

if (dominoes.isEmpty()) {
if (chain.isEmpty() ||
chain.getFirst().getLeft() == chain.getLast().getRight()) {
return chain;
}

throw new ChainNotFoundException(CHAIN_NOT_FOUND_EXCEPTION);
}

final ArrayList<Domino> dominoesCopy = new ArrayList<>(dominoes);

if (chain.isEmpty()) {
return formChain(dominoesCopy, chainCopy);
}

final Domino chainLast = chainCopy.getLast();

for (int i = 0; i < dominoesCopy.size(); i++) {
final Domino domino = dominoesCopy.get(i);
if (domino.getLeft() == chainLast.getRight() ||
domino.getRight() == chainLast.getRight()) {
if (domino.getRight() == chainLast.getRight()) {
domino.flip();
}

try {
return formChain(dominoesCopy, chainCopy);
} catch (ChainNotFoundException e) {
}
}
}

throw new ChainNotFoundException(CHAIN_NOT_FOUND_EXCEPTION);
}

}``````

### src/main/java/Domino.java

``````import java.util.LinkedList;
import java.util.Objects;

class Domino {
private int left;
private int right;

Domino(int left, int right) {
this.left = left;
this.right = right;
}

int getLeft() {
return this.left;
}

int getRight() {
return this.right;
}

void flip() {
this.left += this.right;
this.right = this.left - this.right;
this.left -= this.right;
}

@Override
public boolean equals(Object o) {
Domino otherDomino = (Domino) o;
return (this.getLeft() == otherDomino.getLeft() &&
this.getRight() == otherDomino.getRight()) ||
(this.getLeft() == otherDomino.getRight() && this.getRight() == otherDomino.getLeft());
}

@Override
public int hashCode() {
return Objects.hash(left, right);
}
}``````

### What can you learn from this solution?

A huge amount can be learned from reading other peopleâ€™s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

• What compromises have been made?