Trying to solve an Exercism problem (Dominoes). In this problem I am attempting to create a valid chain of dominoes such that numbers are touching each other and the first and last number are the same.
Example: [1|2], [3,1], [3,2] -> [1|2][2|3][3|1]
I am using brute force to try all combinations. To do so I start a chain with all possible combinations using the following code:
using System;
using System.Collections.Generic;
using System.Linq;
public static class Dominoes
{
private class Domino
{
public readonly int First;
public readonly int Last;
public Domino(int first, int last)
{
First = first;
Last = last;
}
public Domino Flip() => new Domino(Last, First);
}
private class Chain
{
private readonly List<Domino> chained = new List<Domino>();
private readonly List<Domino> remaining = new List<Domino>();
private int First => chained[0].First;
private int Last => chained[chained.Count - 1].Last;
public bool Complete => remaining.Count == 0 && First == Last;
private Chain(Domino domino, IEnumerable<Domino> remaining, IEnumerable<Domino> chained = null)
{
if (chained != null)
{
this.chained.AddRange(chained);
}
this.chained.Add(domino);
this.remaining.AddRange(remaining);
}
public static IEnumerable<Chain> Start(IEnumerable<Domino> dominoes)
{
var chains = new List<Chain>();
foreach (var domino in dominoes)
{
var remaining = dominoes.Where(d => d != domino);
chains.Add(new Chain(domino, remaining));
chains.Add(new Chain(domino.Flip(), remaining));
}
return chains;
}
public IEnumerable<Chain> Extend()
{
var chains = new List<Chain>();
foreach (var domino in this.remaining)
{
var remaining = this.remaining.Where(d => d != domino);
if (domino.First == Last)
{
chains.Add(new Chain(domino, remaining, chained));
}
if (domino.Last == Last)
{
chains.Add(new Chain(domino.Flip(), remaining, chained));
}
}
return chains;
}
}
public static bool CanChain(IEnumerable<(int, int)> dominoes)
{
var chains = Chain.Start(dominoes.Select(d => new Domino(d.Item1, d.Item2)));
return chains.Any() ? Iterate(chains) : true;
}
private static bool Iterate(IEnumerable<Chain> chains)
{
var newChains = new List<Chain>();
foreach (var chain in chains)
{
if (chain.Complete) return true;
newChains.AddRange(chain.Extend());
}
if (newChains.Count == 0) return false;
return Iterate(newChains);
}
}
Test Code
using System;
using Xunit;
public class DominoesTests
{
[Fact]
public void Singleton_that_cant_be_chained()
{
var dominoes = new[] { (1, 2) };
Assert.False(Dominoes.CanChain(dominoes));
}
}
Run using dotnet test
The filtering for remaining in Chain.Start does not appear to work.
Example (using new [] { (1, 2) } as input for CanChain)
# Expected: `Chain: [1|2] Remaining:`
# Actual: `Chain: [1|2] Remaining: [1|2]`
If I call .ToList() on the dominoes.Select(d => new Domino(d)) in CanChain it starts working.
EDIT: added more information
The problem is that the enumeration of Select is not executed right away, but instead is delayed. This means that each time you are accessing/using the IEnumerable<> returned by the Select() method you will get a new fresh list. But this also means you are creating new Domino objects all the time. And as you are not overwriting the Equals() method each of these Domino object will be different, even if they have the same values.
To show the problem check the following code:
private class Foobar {
private readonly int value;
public Foobar(int v) {
Console.WriteLine("## CONSTRUCTOR ## Foobar object created with value: "+v);
this.value = v;
}
public override string ToString() {
return "Foobar("+this.value+")";
}
}
public static void Main(string[] args) {
int[] numbers = new [] { 1, 5};
IEnumerable<Foobar> range = numbers.Select(i => new Foobar(i));
Console.WriteLine(range.Count());
foreach (Foobar entry in range) {
Console.WriteLine("Build an enumerable without "+entry);
IEnumerable<Foobar> remaining = range.Where(it => it != entry);
Console.WriteLine("The length of the remaining: "+remaining.Count());
foreach (Foobar remainingEntry in remaining) {
Console.WriteLine("Entry of remaining: "+remainingEntry);
}
}
}
When you run this code you will get the following output:
## CONSTRUCTOR ## Foobar object created with value: 1
## CONSTRUCTOR ## Foobar object created with value: 5
2
## CONSTRUCTOR ## Foobar object created with value: 1
Build an enumerable without Foobar(1)
## CONSTRUCTOR ## Foobar object created with value: 1
## CONSTRUCTOR ## Foobar object created with value: 5
The length of the remaining: 2
## CONSTRUCTOR ## Foobar object created with value: 1
Entry of remaining: Foobar(1)
## CONSTRUCTOR ## Foobar object created with value: 5
Entry of remaining: Foobar(5)
## CONSTRUCTOR ## Foobar object created with value: 5
Build an enumerable without Foobar(5)
## CONSTRUCTOR ## Foobar object created with value: 1
## CONSTRUCTOR ## Foobar object created with value: 5
The length of the remaining: 2
## CONSTRUCTOR ## Foobar object created with value: 1
Entry of remaining: Foobar(1)
## CONSTRUCTOR ## Foobar object created with value: 5
Entry of remaining: Foobar(5)
As you see the constructor is called way too often. Each time someone use the IEnumerable from the Select() call it will generate the enumerable list again so it doesn't interfere with other parallel running iterations on the same data. However, since you create new objects inside your Select() statement you will get new objects for each creation of the IEnumerable of Select().
As you have already noticed, to solve the problem you use something like ToList() and to evaluate/create the Domino objects once. With one ToList() call the output changes as follow:
## CONSTRUCTOR ## Foobar object created with value: 1
## CONSTRUCTOR ## Foobar object created with value: 5
2
Build an enumerable without Foobar(1)
The length of the remaining: 1
Entry of remaining: Foobar(5)
Build an enumerable without Foobar(5)
The length of the remaining: 1
Entry of remaining: Foobar(1)
You see, only two objects are created and the != will work as expected, since there are only these two objects.