Solving the Zebra Puzzle with LINQ and C# 7

C# Implementation

Since we’ll be using some new C# 7 features in this post, if you’re following along at home, you’ll want to do the following:

1. Download the most recent Visual Studio 2017 release (currently in RC). This will also install the latest pre-release version of C# 7.
2. Create a new solution, and install the System.ValueTuple pre-release Nuget package. This will enable some additional C# 7 features.

First up, let’s knock out the easy part: writing the helper functions. Nothing too interesting here, it’s just a straightforward translation of the python helper functions:

/// <summary>
/// Is house h1 immediately right of h2?
/// </summary>
static bool ImmediatelyRight(int h1, int h2) => h1 - h2 == 1;

/// <summary>
/// Are house h1 and h2 next to each other?
/// </summary>
static bool NextTo(int h1, int h2) => Math.Abs(h1 - h2) == 1;

New C# 7 feature: Deconstruction

Next, we need to set up the initial house variables. The python version uses destructuring here, so we do the same, using C# 7’s new deconstruction feature on the second line:

// set up the houses
int[] houses = { 1, 2, 3, 4, 5 };
(int first, _, int middle, _, _) = houses;

The above deconstruction statement splits the houses array into 5 separate variables. We only care about the first and middle houses, so we discard the other variables by using the underscore discard variable in their places.

However, if we write that exact code, it won’t compile! C# doesn’t know how to deconstruct an array. We can teach C# how to do this by writing a Deconstruct extension method for arrays:

public static void Deconstruct<T>(this T[] array, out T first, out T second, out T third, out T fourth, out T[] rest)
{
    first = array[0];
    second = array[1];
    third = array[2];
    fourth = array[3];
    rest = array.Skip(4).ToArray();
}

Any type can implement Deconstruct as a method or extension method, and it will then be able to take part in the new C# 7 deconstruction syntax. This method we just wrote only works for deconstructing into 5 variables, but that’s all we need right now. Additional extension methods for array deconstruction can be found in this gist.

New C# 7 feature: Tuples

Our last step is to translate the Python list comprehension into a C# LINQ statement. What we’d like to write is something like this:

// this code does NOT work
var answers =
    from (Red, Green, Ivory, Yellow, Blue) in orderings
    //... etc.

It would be nice if C# 7 recognized our Deconstruct method and it all Just Worked. However, C# 7 doesn’t support deconstruction in LINQ statements (see the issue tracking it), so we can’t quite do this yet.

There’s a workaround: rather than deconstructing inside the LINQ statement, we can represent our permutations as a list of System.ValueTuples.

System.ValueTuple isn’t related to the existing System.Tuple type. A System.ValueTuple is different in that you can optionally name its tuple members (no more Item1, Item2, etc!). It can also be returned from a method and retain those member names, unlike an anonymous type.

In our initial permutation list, we won’t name the tuple members:

var orderings =
    // generates List<List<int>> using the Combinatorics nuget package
    new Permutations<int>(houses)
    // creates List<System.ValueTuple<int, int, int, int, int>>
    .Select(p => (p[0], p[1], p[2], p[3], p[4])).ToList();

We can then provide helper functions to translate unnamed tuples into named tuples for each house attribute:

(int Red, int Green, int Ivory, int Yellow, int Blue)
    AsColors((int, int, int, int, int) permutation) => permutation;

(int Englishman, int Spaniard, int Ukranian, int Japanese, int Norwegian)
    AsNationalities((int, int, int, int, int) permutation) => permutation;

(int Coffee, int Tea, int Milk, int OJ, int Water)
    AsDrinks((int, int, int, int, int) permutation) => permutation;

(int OldGold, int Kools, int Chesterfields, int LuckyStrike, int Parliaments)
    AsCigarettes((int, int, int, int, int) permutation) => permutation;

(int Dog, int Snail, int Fox, int Horse, int Zebra)
    AsPets((int, int, int, int, int) permutation) => permutation;

With the above workaround in place, it’s now a straightforward translation of the original problem description, complete with static typing goodness:

// solve the problem
var answers =
    from color in orderings.Select(AsColors)
    where ImmediatelyRight(color.Green, color.Ivory) //6
    from nationality in orderings.Select(AsNationalities)
    where nationality.Englishman == color.Red &&     //2
          nationality.Norwegian == first &&          //10
          NextTo(nationality.Norwegian, color.Blue)  //15
    from drink in orderings.Select(AsDrinks)
    where drink.Coffee == color.Green &&             //4
          drink.Tea == nationality.Ukranian &&       //5
          drink.Milk == middle                       //9
    from smoke in orderings.Select(AsCigarettes)
    where smoke.Kools == color.Yellow &&             //8
          smoke.LuckyStrike == drink.OJ &&           //13
          nationality.Japanese == smoke.Parliaments  //14
    from pet in orderings.Select(AsPets)
    where nationality.Spaniard == pet.Dog &&         //3
          smoke.OldGold == pet.Snail &&              //7
          NextTo(smoke.Chesterfields, pet.Fox) &&    //12
          NextTo(smoke.Kools, pet.Horse)             //11
    select new { drink.Water, pet.Zebra };

var answer = answers.Single();
Console.WriteLine($"Water drinker lives in {answer.Water} and zebra owner lives in {answer.Zebra}");

Running this, we get the output:

Water drinker lives in 1 and zebra owner lives in 5

And we’re done! We found that sneaky zebra owner.

Conclusion

Overall, I feel like this LINQ implementation is fairly faithful to the original Python implementation, and in about 70 lines of code. If LINQ supported deconstruction, I would be 100% happy with it. However, due to the lack of LINQ support, we needed a couple of helper functions, and that definitely spoiled the fun a bit.

System.ValueTuple looks like a very useful feature – but I’ll need to be careful to balance this with code readability concerns. Sometimes it might be better to break a System.ValueTuple into a named class with documentation. For cases like this blog post though, where the types are only ever used inside a single method or class, I think it’s a valuable feature.