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

# handle4's solution

## to Dominoes in the Java Track

Published at Apr 24 2020 · 0 comments
Instructions
Test suite
Solution

#### Note:

This exercise has changed since this solution was written.

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
``````

Use `gradlew.bat` if you're on Windows

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 org.junit.Ignore;
import org.junit.Test;

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

import static org.junit.Assert.assertEquals;

import org.junit.Rule;
import org.junit.rules.ExpectedException;

public class DominoesTest {

@Rule
public ExpectedException expectedException = ExpectedException.none();

@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() throws ChainNotFoundException {
Dominoes dominoes = new Dominoes();

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

expectedException.expect(ChainNotFoundException.class);
expectedException.expectMessage("No domino chain found.");

dominoes.formChain(dominoesList);
}

@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() throws ChainNotFoundException {
Dominoes dominoes = new Dominoes();

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

expectedException.expect(ChainNotFoundException.class);
expectedException.expectMessage("No domino chain found.");

dominoes.formChain(dominoesList);
}

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

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

expectedException.expect(ChainNotFoundException.class);
expectedException.expectMessage("No domino chain found.");

dominoes.formChain(dominoesList);
}

@Ignore("Remove to run test")
@Test
public void disconnectedDoubleLoopTest() throws ChainNotFoundException {
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);

expectedException.expect(ChainNotFoundException.class);
expectedException.expectMessage("No domino chain found.");

dominoes.formChain(dominoesList);
}

@Ignore("Remove to run test")
@Test
public void disconnectedSingleIsolatedTest() throws ChainNotFoundException {
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);

expectedException.expect(ChainNotFoundException.class);
expectedException.expectMessage("No domino chain found.");

dominoes.formChain(dominoesList);
}

@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());
}
}
}``````
``````import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Dominoes {

List<Domino> dominoesList;

public Dominoes() {
this.dominoesList = new ArrayList<>();
}
String dominoesAsList(List<Domino> doms) {
String str = "";
for (Domino d : doms) {
str += "(" + d.getLeft() + ", " + d.getRight() + ")";
}
return str;
}

List<Domino> formChain(List<Domino> dominoes) throws Exception {
if (dominoes.size() > 1) {
List<Domino> domsClone = new ArrayList<>(dominoes);
List<Domino> chain = formSubChain(domsClone);

if ((!chain.isEmpty()) && (chain.get(0).getLeft() == chain.get(chain.size() - 1).getRight()) && (chain.size() == dominoes.size())) {
return chain;
} else {
throw new ChainNotFoundException("No domino chain found.");
}
} else if (dominoes.size() == 1) {
throw new ChainNotFoundException("No domino chain found.");
}
return dominoes;
}

List<Domino> formSubChain(List<Domino> dominoes) throws Exception {
if (dominoes.size() == 2) {
if (dominoes.get(0).getRight() == dominoes.get(1).getLeft()) {
return dominoes;
} else if (dominoes.get(0).getRight() == dominoes.get(1).getRight()) {
dominoes.remove(1);
return dominoes;
} else {
return (new ArrayList<Domino>());
}
} else if (dominoes.size() > 2) {
Domino head = dominoes.get(0);
int tail = dominoes.get(0).getRight();
dominoes.remove(0);

List<Domino> subchain = new ArrayList<Domino>();
for (int i=0; i < dominoes.size(); i++) {
Domino d = dominoes.get(i);
List<Domino> dominoesClone = new ArrayList<Domino>(dominoes);

if (tail == d.getLeft()) {
dominoesClone.remove(i);
subchain = formSubChain(dominoesClone);
}
else if (tail == d.getRight()) {
dominoesClone.remove(i);
dominoesClone.add(0, new Domino(d.getRight(), d.getLeft()));
subchain = formSubChain(dominoesClone);
}
}

return subchain;
} else {
throw new ChainNotFoundException("No domino chain found.");
}
}
}``````

### 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?
• Are there new concepts here that you could read more about to improve your understanding?