# Jubamba's solution

## to Dominoes in the Java Track

Published at Apr 06 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.LinkedList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Dominoes {

List<Domino> formChain(List<Domino> dominoList) throws ChainNotFoundException {
if(dominoList == null || dominoList.isEmpty()){
return Collections.emptyList();
}

if(dominoList.size() == 1) {
throw new ChainNotFoundException("No domino chain found.");
}
return dominoList;
}

for (int i = 0; i < dominoList.size(); i++) {
List<Domino> dominoListResult = this.formChainFromLastDomino(i, false, dominoLinkedList);

if (dominoListResult.size() > 0) {
return dominoListResult;
}

if (dominoListResult.size() > 0) {
return dominoListResult;
}
}

throw new ChainNotFoundException("No domino chain found.");
}

private List<Domino> formChainFromLastDomino(int dominoLastIndex, boolean flipLastDomino, LinkedList<Domino> dominoList){
Domino dominoLast = dominoList.get(dominoLastIndex);

if(flipLastDomino){
dominoLast = new Domino(dominoLast.getRight(), dominoLast.getLeft());
}

if(dominoList.size() == 1){
}

dominoListToCheck.remove(dominoLastIndex);

for (int i = 0; i < dominoListToCheck.size(); i++) {
Domino dominoCheck = dominoListToCheck.get(i);

if(dominoLast.getRight() == dominoCheck.getLeft()){
dominoListChain = this.formChainFromLastDomino(i, false, dominoListToCheck);
} else if(dominoLast.getRight() == dominoCheck.getRight()) {
dominoListChain = this.formChainFromLastDomino(i, true, dominoListToCheck);
}

if(!dominoListChain.isEmpty()){
break;
}
}

return dominoListChain;
}

}``````

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

return 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);
}
}``````