Avatar of clechasseur

clechasseur's solution

to Dominoes in the Java Track

Published at Mar 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.Collections;
import java.util.List;
import java.util.stream.Collectors;

class Dominoes {
    List<Domino> formChain(List<Domino> dominoes) throws ChainNotFoundException {
        if (dominoes.isEmpty()) {
            return Collections.emptyList();
        }
        List<Domino> chainStart = new ArrayList<>(Collections.singletonList(dominoes.get(0)));
        List<Domino> chain = continueChain(chainStart, dominoes.subList(1, dominoes.size()));
        if (chain == null) {
            throw new ChainNotFoundException("No domino chain found.");
        }
        return chain;
    }

    private List<Domino> continueChain(List<Domino> chain, List<Domino> dominoes) {
        if (dominoes.isEmpty()) {
            if (chain.get(0).getLeft() == chain.get(chain.size() - 1).getRight()) {
                return chain;
            } else {
                return null;
            }
        }

        Domino last = chain.get(chain.size() - 1);
        List<Domino> possibilities = dominoes.stream()
                .filter(d -> d.getLeft() == last.getRight() || d.getRight() == last.getRight())
                .collect(Collectors.toList());
        for (Domino possibility : possibilities) {
            Domino realPossibility = possibility.getLeft() == last.getRight()
                    ? possibility
                    : new Domino(possibility.getRight(), possibility.getLeft());
            List<Domino> newChain = new ArrayList<>(chain);
            newChain.add(realPossibility);
            List<Domino> remainingDominoes = new ArrayList<>(dominoes);
            remainingDominoes.remove(possibility);
            List<Domino> endChain = continueChain(newChain, remainingDominoes);
            if (endChain != null) {
                return endChain;
            }
        }
        return null;
    }
}

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;
    }
    
    @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/ChainNotFoundException.java

class ChainNotFoundException extends Exception {
	public ChainNotFoundException(String message) {
		super(message);
	}
}

Community comments

Find this solution interesting? Ask the author a question to learn more.

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?