Avatar of artemkorsakov

artemkorsakov's solution

to Dominoes in the Java Track

Published at Feb 20 2019 · 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.

Running the tests

You can run all the tests for an exercise by entering

$ gradle test

in your terminal.

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.LinkedList;
import java.util.List;
import java.util.stream.IntStream;

class Dominoes {
    private ChainNotFoundException ex = new ChainNotFoundException("No domino chain found.");

    List<Domino> formChain(List<Domino> dominoesList) throws ChainNotFoundException {
        List<Domino> result = getConnectedChain(dominoesList);
        checkChain(result);
        return result;
    }

    private List<Domino> getConnectedChain(List<Domino> dominoesList) throws ChainNotFoundException {
        List<Integer> indexes = getIndexesOfDifferentChains(dominoesList);
        if (indexes.size() == 1) {
            return dominoesList;
        }

        LinkedList<Domino> result = new LinkedList<>(dominoesList.subList(0, indexes.get(1)));
        for (int i = 1; i < indexes.size(); i++) {
            int lastIndexOfChain = (i == indexes.size() - 1) ? dominoesList.size() : indexes.get(i + 1);
            List<Domino> chain = dominoesList.subList(indexes.get(i), lastIndexOfChain);
            checkChain(chain);
            int startStone = chain.get(0).getLeft();
            int index = IntStream.range(0, result.size())
                    .filter(j -> result.get(j).getRight() == startStone)
                    .findFirst().orElseThrow(() -> ex);
            result.addAll(index + 1, chain);
        }

        return result;
    }

    /**
     * It sorts the list of dominoes to the list of several correct domino chains
     * and returns indexes these chains.
     * It is known about each chain that its last right domino is not in the following chains which means that
     * each next chain can only join the previous one. Otherwise it will not be possible to build a complete chain.
     */
    private List<Integer> getIndexesOfDifferentChains(List<Domino> dominoesList) {
        List<Integer> indexesOfDifferentChains = new ArrayList<>();
        indexesOfDifferentChains.add(0);

        for (int i = 1; i < dominoesList.size(); i++) {
            int lastRightStone = dominoesList.get(i - 1).getRight();
            int indexOfNextDomino = indexOfNextDomino(dominoesList, i, lastRightStone);
            if (indexOfNextDomino != -1) {
                changeDominoes(dominoesList, i, indexOfNextDomino);
            } else {
                indexesOfDifferentChains.add(i);
            }
        }

        return indexesOfDifferentChains;
    }

    /**
     * It returns the index of the first domino that may be next in the chain.
     */
    private int indexOfNextDomino(List<Domino> dominoesList, int startIndex, int lastRightStone) {
        int index = IntStream.range(startIndex, dominoesList.size())
                .filter(i -> dominoesList.get(i).getRight() == lastRightStone || dominoesList.get(i).getLeft() == lastRightStone)
                .findFirst().orElse(-1);
        if (index != -1 && dominoesList.get(index).getLeft() != lastRightStone) {
            dominoesList.set(index, new Domino(dominoesList.get(index).getRight(), dominoesList.get(index).getLeft()));
        }
        return index;
    }

    /**
     * It swaps two dominoes with given indexes in the list of dominoes.
     */
    private void changeDominoes(List<Domino> dominoesList, int index1, int index2) {
        if (index1 == index2) {
            return;
        }

        Domino temp = dominoesList.get(index1);
        dominoesList.set(index1, dominoesList.get(index2));
        dominoesList.set(index2, temp);
    }

    private void checkChain(List<Domino> dominoesList) throws ChainNotFoundException {
        if (!dominoesList.isEmpty() &&
                dominoesList.get(0).getLeft() != dominoesList.get(dominoesList.size() - 1).getRight()) {
            throw ex;
        }
    }
}

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?