Avatar of vgrigoriu

vgrigoriu's solution

to Dominoes in the C# Track

Published at Sep 29 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;
using System.Collections.Generic;
using System.Linq;

public static class Dominoes
{
    public static bool CanChain(IEnumerable<(int, int)> dominoes)
    {
        if (dominoes.Count() == 0)
        {
            Console.WriteLine("No dominoes");
            return true;
        }

        var firstDomino = dominoes.First();
        var (found, chain) = FindChainStartingWith(firstDomino, dominoes.Skip(1));

        return found && IsValidChain(chain);
    }

    private static (bool, IEnumerable<(int, int)>) FindChainStartingWith((int, int) start, IEnumerable<(int,int)> candidates)
    {
        if (candidates.Count() == 0)
        {
            return (true, new List<(int,int)> {start});
        }

        var candidatesArray = candidates.ToArray();
        for (var i = 0; i < candidatesArray.Length; i++)
        {
            var domino = candidatesArray[i];
            var remainingCandidates = GetRemainingCandidates(candidatesArray, domino);
            bool found = false;
            IEnumerable<(int, int)> chain = Enumerable.Empty<(int, int)>();
            if (domino.Item1 == start.Item2)
            {
                (found, chain) = FindChainStartingWith(domino, remainingCandidates);
            }
            else if (domino.Item2 == start.Item2)
            {
                (found, chain) = FindChainStartingWith((domino.Item2, domino.Item1), remainingCandidates);
            }

            if (found)
            {
                return (true, new List<(int,int)> {start}.Concat(chain));
            }
        }

        return (false, null);
    }

    private static IEnumerable<(int,int)> GetRemainingCandidates((int, int)[] dominoes, (int, int) except)
    {
        var eliminated = false;
        foreach (var domino in dominoes)
        {
            if (domino.Item1 == except.Item1 && domino.Item2 == except.Item2 && !eliminated)
            {
                eliminated = true;
                continue;
            }

            yield return domino;
        }
    }

    private static bool IsValidChain(IEnumerable<(int, int)> dominoes)
    {
        var dominoesArray = dominoes.ToArray();
        for (int i = 0; i < dominoesArray.Length; i++)
        {
            var currDomino = dominoesArray[i];
            var nextDomino = dominoesArray[(i+1) % dominoesArray.Length];
            if (currDomino.Item2 != nextDomino.Item1)
            {
                return false;
            }
        }

        return true;
    }
}

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?