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

heptalophos's solution

to Dominoes in the Java Track

Published at Jan 30 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());
}
}
}``````

src/main/java/Dominoes.java

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

public class Dominoes {

private final String NOT_FOUND =
"No domino chain found.";

public List<Domino> formChain(List<Domino> dominoes)
throws ChainNotFoundException {
if (dominoes.isEmpty())
return new ArrayList<>();
List<Domino> chain = new ArrayList<>();
findChain(chain,
new ArrayList<>(dominoes
.subList(1,
dominoes.size())));
return chain;
}

private void findChain(List<Domino> chain,
List<Domino> dominoes)
throws ChainNotFoundException {
List<Domino> candidates =
candidates(chain.get(chain.size() - 1)
.getRight(),
dominoes);
for (Domino candidate : candidates) {
dominoes.remove(candidate);
try {
findChain(chain, dominoes);
break;
} catch (Exception e) {
chain.remove(chain.size() - 1);
}
}
if (chain.get(0).getLeft() !=
chain.get(chain.size() - 1).getRight()
|| !dominoes.isEmpty())
throw new ChainNotFoundException(NOT_FOUND);
}

private List<Domino> candidates(int target,
List<Domino> dominoes) {
List<Domino> candidates = new ArrayList<>();
for (Domino candidate : dominoes) {
if (candidate.getLeft() == target)
else if (candidate.getRight() == target)
else
continue;
}
return candidates;
}
}``````

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

Domino reversed() {
return new Domino(right, 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);
}

@Override
public String toString() {
return "[" + this.getLeft() + "|" +
this.getRight() + "]";
}
}``````

src/main/java/ChainNotFoundException.java

``````class ChainNotFoundException extends Exception {
/**
*
*/
private static final long serialVersionUID =
12345678L;

public ChainNotFoundException(String message) {
super(message);
}
}``````