 # -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
{

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;
}
}``````