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

## to Dominoes in the Java Track

Published at May 08 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:

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/Domino.java

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;
}

public boolean isAppendableTo(final Domino domino) {
return this.right == domino.left || this.right == domino.right;
}

public Domino placeNextTo(final Domino domino) {
return (this.left == domino.right) ? this : new Domino(this.right, this.left);
}

@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);
}
}

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

import static java.util.stream.Collectors.*;

import java.util.List;
import java.util.function.Function;
import java.util.stream.IntStream;
import java.util.stream.Stream;

class Dominoes {

List<Domino> formChain(final List<Domino> dominoesList) throws ChainNotFoundException {

if (dominoesList.isEmpty()) {
return dominoesList;
}

return IntStream.range(0, dominoesList.size())
.mapToObj(i -> this.getConfigurations(dominoesList.get(i))
.map(configuration -> this.formChain(this.removeStone(dominoesList, i), configuration, configuration.getLeft())))
.flatMap(Function.identity())
.filter(list -> list.size() == dominoesList.size() && list.get(0).getLeft() == list.get(list.size() - 1).getRight())
.findFirst()
.orElseThrow(() -> new ChainNotFoundException("No domino chain found."));
}

List<Domino> formChain(final List<Domino> dominoList, final Domino domino, final int left) {

return IntStream.range(0, dominoList.size())
.filter(i -> domino.isAppendableTo(dominoList.get(i)))
dominoList.get(i).placeNextTo(domino),
left)))
.filter(list -> list.size() == dominoList.size() + 1 && list.get(list.size() - 1).getRight() == left)
.findFirst()
.orElse(List.of(domino));

}

private List<Domino> removeStone(final List<Domino> stones, final int stone) {
return IntStream.range(0, stones.size())
.filter(i -> i != stone)
.mapToObj(stones::get)
.collect(toList());
}

private List<Domino> addStone(final Domino stone, final List<Domino> stones) {
return Stream.concat(Stream.of(stone), stones.stream())
.collect(toList());
}

private Stream<Domino> getConfigurations(final Domino domino) {
return (domino.getLeft() == domino.getRight())
? Stream.of(domino) : Stream.of(domino, new Domino(domino.getRight(), domino.getLeft()));
}
}