Avatar of -1

-1's solution

to Dominoes in the C# Track

Published at Sep 27 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));
    }
}

Dominoes.cs

using System.Collections.Generic;
using System.Linq;

public static class Dominoes
{
    public static bool CanChain(IEnumerable<(int first, int second)> dominoes)
    {
        if (dominoes is null || !dominoes.Any())
        {
            return true;
        }
        var permutations = new Permutations(dominoes.Count()).Get(makeCopies: false);
        foreach (var permutation in permutations)
        {
            var copinoes = dominoes.ToList();
            var doAllMatch = true;
            for (var i = 0; i < copinoes.Count; i++)
            {
                var nextI = i + 1;
                if (nextI >= copinoes.Count)
                {
                    nextI = 0;
                }
                if (!IsMatch())
                {
                    SwitchAt(nextI);
                    if (!IsMatch())
                    {
                        doAllMatch = false;
                        break;
                    }
                }

                bool IsMatch()
                {
                    return ElemAt(i).second == ElemAt(nextI).first;
                }
            }
            if (doAllMatch)
            {
                return true;
            }

            void SwitchAt(int i)
            {
                var first = ElemAt(i).first;
                var second = ElemAt(i).second;
                copinoes.RemoveAt(permutation[i]);
                copinoes.Insert(permutation[i], (second, first));
            }

            (int first, int second) ElemAt(int i)
            {
                return copinoes.ElementAt(permutation[i]);
            }
        }
        return false;
    }
}

Permutations.cs

using System.Collections.Generic;
using System.Linq;

class Permutations
{
    readonly List<int> _indices;

    public Permutations(int length) =>
        _indices = Enumerable.Repeat(-1, length).ToList();

    public IEnumerable<List<int>> Get(bool makeCopies = true, int currentPosition = 0)
    {
        if (currentPosition >= _indices.Count)
        {
            if (makeCopies)
            {
                yield return _indices.ToList();
            }
            else
            {
                yield return _indices;
            }
            yield break;
        }
        for (var indexToCheck = 0; indexToCheck < _indices.Count; indexToCheck++)
        {
            if (IsIndexOnPreviousPositions(currentPosition, indexToCheck))
            {
                continue;
            }
            _indices[currentPosition] = indexToCheck;
            foreach (var index in Get(makeCopies, currentPosition + 1))
            {
                yield return index;
            }
        }
    }

    bool IsIndexOnPreviousPositions(int currentPosition, int index)
    {
        for (var previousIndex = 0; previousIndex < currentPosition; previousIndex++)
        {
            if (_indices[previousIndex] == index)
            {
                return true;
            }
        }
        return false;
    }
}

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?