Avatar of artemkorsakov

artemkorsakov's solution

to Dominoes in the C# Track

Published at Jun 03 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

To run the tests, run the command dotnet test from within the exercise directory.

Initially, only the first test will be enabled. This is to encourage you to solve the exercise one step at a time. Once you get the first test passing, remove the Skip property from the next test and work on getting that test passing. Once none of the tests are skipped and they are all passing, you can submit your solution using exercism submit Dominoes.cs

Further information

For more detailed information about the C# track, including how to get help if you're having trouble, please visit the exercism.io C# language page.

DominoesTest.cs

// This file was auto-generated based on version 2.1.0 of the canonical data.

using System;
using Xunit;

public class DominoesTest
{
    [Fact]
    public void Empty_input_empty_output()
    {
        var dominoes = Array.Empty<(int, int)>();
        Assert.True(Dominoes.CanChain(dominoes));
    }

    [Fact(Skip = "Remove to run test")]
    public void Singleton_input_singleton_output()
    {
        var dominoes = new[] { (1, 1) };
        Assert.True(Dominoes.CanChain(dominoes));
    }

    [Fact(Skip = "Remove to run test")]
    public void Singleton_that_cant_be_chained()
    {
        var dominoes = new[] { (1, 2) };
        Assert.False(Dominoes.CanChain(dominoes));
    }

    [Fact(Skip = "Remove to run test")]
    public void Three_elements()
    {
        var dominoes = new[] { (1, 2), (3, 1), (2, 3) };
        Assert.True(Dominoes.CanChain(dominoes));
    }

    [Fact(Skip = "Remove to run test")]
    public void Can_reverse_dominoes()
    {
        var dominoes = new[] { (1, 2), (1, 3), (2, 3) };
        Assert.True(Dominoes.CanChain(dominoes));
    }

    [Fact(Skip = "Remove to run test")]
    public void Cant_be_chained()
    {
        var dominoes = new[] { (1, 2), (4, 1), (2, 3) };
        Assert.False(Dominoes.CanChain(dominoes));
    }

    [Fact(Skip = "Remove to run test")]
    public void Disconnected_simple()
    {
        var dominoes = new[] { (1, 1), (2, 2) };
        Assert.False(Dominoes.CanChain(dominoes));
    }

    [Fact(Skip = "Remove to run test")]
    public void Disconnected_double_loop()
    {
        var dominoes = new[] { (1, 2), (2, 1), (3, 4), (4, 3) };
        Assert.False(Dominoes.CanChain(dominoes));
    }

    [Fact(Skip = "Remove to run test")]
    public void Disconnected_single_isolated()
    {
        var dominoes = new[] { (1, 2), (2, 3), (3, 1), (4, 4) };
        Assert.False(Dominoes.CanChain(dominoes));
    }

    [Fact(Skip = "Remove to run test")]
    public void Need_backtrack()
    {
        var dominoes = new[] { (1, 2), (2, 3), (3, 1), (2, 4), (2, 4) };
        Assert.True(Dominoes.CanChain(dominoes));
    }

    [Fact(Skip = "Remove to run test")]
    public void Separate_loops()
    {
        var dominoes = new[] { (1, 2), (2, 3), (3, 1), (1, 1), (2, 2), (3, 3) };
        Assert.True(Dominoes.CanChain(dominoes));
    }

    [Fact(Skip = "Remove to run test")]
    public void Nine_elements()
    {
        var dominoes = new[] { (1, 2), (5, 3), (3, 1), (1, 2), (2, 4), (1, 6), (2, 3), (3, 4), (5, 6) };
        Assert.True(Dominoes.CanChain(dominoes));
    }
}
using System.Collections.Generic;
using System.Linq;

public static class Dominoes
{
    private static List<(int, int)> dominoesList;

    public static bool CanChain(IEnumerable<(int, int)> dominoes)
    {
        dominoesList = dominoes.ToList();
        var indexes = GetIndexesOfDifferentChains();
        if (indexes.Count == 1)
        {
            return IsChain(dominoesList);
        }

        var result = new List<(int, int)>(dominoesList.Take(indexes[1]));
        for (var i = 1; i < indexes.Count; i++)
        {
            var lastIndexOfChain = (i == indexes.Count - 1) ? dominoesList.Count() : indexes[i + 1];
            var chain = dominoesList.Skip(indexes[i]).Take(lastIndexOfChain - indexes[i]).ToArray();
            if (!IsChain(chain))
            {
                return false;
            }
            var startStone = chain.First().Item1;
            var indexex = Enumerable.Range(0, result.Count).Where(j => result[j].Item2 == startStone);
            var index = indexex.Count() > 0 ? indexex.First() : -1;
            var resultTmp = new List<(int, int)>(result.Take(index + 1));
            resultTmp.AddRange(chain);
            resultTmp.AddRange(result.Skip(index + 1));
            result = resultTmp;
        }

        return IsChain(result);
    }

    private static bool IsChain(IEnumerable<(int, int)> dominoes) =>
        dominoes.Count() == 0 || dominoes.First().Item1 == dominoes.Last().Item2;

    /**
     * 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 static List<int> GetIndexesOfDifferentChains()
    {
        var indexesOfDifferentChains = new List<int>
        {
            0
        };

        for (var i = 1; i < dominoesList.Count; i++)
        {
            var lastRightStone = dominoesList[i - 1].Item2;
            var indexOfNextDomino = IndexOfNextDomino(i, lastRightStone);
            if (indexOfNextDomino != -1)
            {
                ChangeDominoes(i, indexOfNextDomino);
            }
            else
            {
                indexesOfDifferentChains.Add(i);
            }
        }

        return indexesOfDifferentChains;
    }

    /**
     * It returns the index of the first domino that may be next in the chain.
     */
    private static int IndexOfNextDomino(int startIndex, int lastRightStone)
    {
        var indexes = Enumerable.Range(startIndex, dominoesList.Count - startIndex)
            .Where(i => dominoesList[i].Item1 == lastRightStone || dominoesList[i].Item2 == lastRightStone);
        var index = indexes.Count() == 0 ? -1 : indexes.First();
        if (index != -1 && dominoesList[index].Item1 != lastRightStone)
        {
            dominoesList[index] = (dominoesList[index].Item2, dominoesList[index].Item1);
        }
        return index;
    }

    /**
     * It swaps two dominoes with given indexes in the list of dominoes.
     */
    private static void ChangeDominoes(int index1, int index2)
    {
        if (index1 == index2)
        {
            return;
        }

        var temp = dominoesList[index1];
        dominoesList[index1] = dominoesList[index2];
        dominoesList[index2] = temp;
    }
}

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?