Avatar of nathanchere

nathanchere's solution

to Dominoes in the C# Track

Published at Sep 17 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
{
    public static bool CanChain(IEnumerable<(int, int)> input)
    {
        var dominoes = input.ToList();
        if (!dominoes.Any()) return true;

        // If any of the domino values appears an odd number of times, a full circular chain is not possible
        var values = dominoes.FlattenTuples();
        if (values.IsUnbalancedSet()) return false;

        // From this point we only care about unique values to speed up procesing
        dominoes = dominoes.Distinct().ToList();
        values = values.Distinct().ToList();

        // Starting at the first unique value, we'll track all other values which have a domino connecting it
        var connectedValues = new HashSet<int> { values.First() };
        values.RemoveAt(0);

        foreach (var value in values)
        {
            if (connectedValues.Contains(value)) continue;

            // If there are no dominoes joining the current value to any of the already connected values, a chain is not possible
            if (!dominoes.Any(d => d.ContainsAny(value, connectedValues))) return false;

            // Record any other values we can chain to from this value
            var matches = dominoes.Where(d => d.Contains(value)).ToList();
            foreach (var domino in matches)
            {
                connectedValues.Add(domino.Item1);
                connectedValues.Add(domino.Item2);
                dominoes.Remove(domino);
            }
        }

        // If we reach here, we've proven it is possible to create a circular chain from all of the dominoes provided
        return true;
    }

    // Indicates if a domino consists of one specific number AND one of various possible second numbers 
    private static bool ContainsAny(this (int, int) domino, int expected1, HashSet<int> expected2) =>
        domino.Item1 == expected1 && expected2.Contains(domino.Item2) ||
        expected2.Contains(domino.Item1) && domino.Item2 == expected1;

    // Indicates if a domino contains the expected face value on either side
    private static bool Contains(this (int, int) domino, int expected) =>
        domino.Item1 == expected || domino.Item2 == expected;

    private static List<int> FlattenTuples(this IEnumerable<(int, int)> dominoes) =>
        dominoes.SelectMany(d => new[] { d.Item1, d.Item2 }).ToList();

    // If any of the face values appear an uneven number of times, a full chain is not possible
    private static bool IsUnbalancedSet(this IEnumerable<int> dominoValues) =>
        dominoValues
            .GroupBy(i => i)
            .Select(grp => grp.Count())
            .Any(count => count % 2 != 0);
}

Community comments

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

nathanchere's Reflection

Rather than brute-force through all possible chains (which works for the provided tests since they're limited to at most 9 dominoes but really doesn't scale well at all), the approach I've come up with is to simplify the problem. As long as all of the values that appear on the dominoes appear an even number of times, and as long as it is possible to form a chain with at least one of each face value, then the entire domino set can be chained. I generated tests with 1,000,000 dominoes and it still runs in under 2 seconds on my laptop.