Solving Combinatory Problems with LINQ

Originally published by MSDN in April, 2010.

The other day I ran into a very interesting blog post by Intel engineer James Cownie, Intel Parallel Studio: Great for Serial Code Too (Episode 1). The article uses as an example an application that solves the following problem (I quote):

Find a number consisting of 9 digits in which each of the digits from 1 to 9 appears only once. This number must also satisfy these divisibility requirements:

  1. The number should be divisible by 9.
  2. If the rightmost digit is removed, the remaining number should be divisible by 8.
  3. If the rightmost digit of the new number is removed, the remaining number should be divisible by 7.
  4. And so on, until there’s only one digit (which will necessarily be divisible by 1).

While the C++ solution proposed by the author in that article runs along more “conventional” lines, I (having the enormous luck of being a C# developer) was immediately drawn to applying LINQ to tackle this problem. I find LINQ an ideal tool for solving this type of exploratory problem, where one needs to traverse a full tree of possible combinations, backtracking from unsuccessful branches as soon as they are encountered.

With LINQ queries, cascaded from clauses serve as the generators of combinations, while where clauses determine the failure points that trigger backtracking. The first time I saw this technique used was in the blog post Using LINQ to solve puzzles, by Luke Hoban, a member of the Microsoft Languages Team. I was inspired to write about the approach in my book C# 3.0 and LINQ (C# 3.0 y LINQ, Krasis Press, 2007 (in Spanish)), and then occasionally in my blog, the last time to solve a puzzle involving the generation of a magic square similar to the Dührer square mentioned in the latest Dan Brown bestseller, The Lost Symbol. The post, Buscando el símbolo perdido con LINQ, is in Spanish.

The code that follows shows my implementation of the solution to the problem, which I find a good example of the enormous expressive power of LINQ.

using System;
using System.Linq;
 
namespace Geeks
{
  // C# and LINQ solution to the numeric problem presented in: 
  // http://software.intel.com/en-us/blogs/2009/12/07/intel-parallel-studio-great-for-serial-code-too-episode-1/
  class MainClass
  {
    static void Main()
    {
      int[] oneToNine = new int[] { 123456789 };

      // the query 
      var query =
        from i1 in oneToNine
        from i2 in oneToNine
        where i2 != i1
           && (i1 * 10 + i2) % 2 == 0
        from i3 in oneToNine
        where i3 != i2 && i3 != i1
           && (i1 * 100 + i2 * 10 + i3) % 3 == 0
        from i4 in oneToNine
        where i4 != i3 && i4 != i2 && i4 != i1
           && (i1 * 1000 + i2 * 100 + i3 * 10 + i4) % 4 == 0
        from i5 in oneToNine
        where i5 != i4 && i5 != i3 && i5 != i2 && i5 != i1
           && (i1 * 10000 + i2 * 1000 + i3 * 100 + i4 * 10 + i5) % 5 == 0
        from i6 in oneToNine
        where i6 != i5 && i6 != i4 && i6 != i3 && i6 != i2 && i6 != i1
          && (i1 * 100000 + i2 * 10000 + i3 * 1000 + i4 * 100 + i5 * 10 + i6) % 6 == 0
        from i7 in oneToNine
        where i7 != i6 && i7 != i5 && i7 != i4 && i7 != i3 && i7 != i2 && i7 != i1
          && (i1 * 1000000 + i2 * 100000 + i3 * 10000 + i4 * 1000 + i5 * 100 + i6 * 10 + i7) % 7 == 0
        from i8 in oneToNine
        where i8 != i7 && i8 != i6 && i8 != i5 && i8 != i4 && i8 != i3 && i8 != i2 && i8 != i1
          && (i1 * 10000000 + i2 * 1000000 + i3 * 100000 + i4 * 10000 +
              i5 * 1000 + i6 * 100 + i7 * 10 + i8) % 8 == 0
        from i9 in oneToNine
        where i9 != i8 && i9 != i7 && i9 != i6 && i9 != i5 && i9 != i4 && i9 != i3 && i9 != i2 && i9 != i1
        let number = i1 * 100000000 +
                     i2 * 10000000 +
                     i3 * 1000000 +
                     i4 * 100000 +
                     i5 * 10000 +
                     i6 * 1000 +
                     i7 * 100 +
                     i8 * 10 +
                     i9 * 1
        where number % 9 == 0
        select number;

      // run it! 
      foreach (int n in query)
        Console.WriteLine(n);
    }
  }
}

Note that no attempt at all has been made to optimize the code (for instance, applying individual divisibility criteria for the different positions). I firmly believe in Don Knuth‘s statement that “premature optimization is the root of all evil,” and the program as it stands perfectly satisfied my expectations. On my laptop, it finds the only solution to the problem (the number 381654729) in much less than a second.

Acerca de “Solving Combinatory Problems with LINQ”

“I saw you, I knew you, I touched you
When the world was young …”
Jimmy Page & Robert Plant, “When the World Was Young” (1998)

Hace unos días, en el contexto de una conversación con un colega de trabajo, me acordé del artículo “Solving Combinatory Problems with LINQ“, que en su día me publicó gentilmente MSDN y aún sigue por ahí (también lo he copiado aquí, con el código listo para copiar y pegar). Sin duda alguna, y por una diferencia abismal (gracias, por supuesto, a Microsoft), es el texto más leído que haya escrito yo jamás, y en su momento dio lugar a discusiones como ésta.

Revisando el artículo al cabo de todo este tiempo, se me antoja ciertamente un poco naïve; me consuela la idea de que, al fin y cabo, eran tiempos en que “el mundo era joven” y LINQ acababa de nacer.


Referencia musical: Durante la década de los 90, los líderes del inolvidable Led Zeppelin, Jimmy Page y Robert Plant, publicaron dos discos que hicieron las delicias de los numerosos fans de la banda: “No Quarter” (1994) y “Walking into Clarksdale” (1998). “When the World Was Young” pertenece al segundo de esos trabajos.

Applying LINQ to new data types

[This article was originally published in MSDN C# Developer Center, February 2008]

Given the enormous expressive power that LINQ (Language Integrated Query) puts in the hands of developers, it is not surprising that we have started to search for ways to “LINQ-enable” more and more data types and technologies. As Dinesh Kulkarni humorously put it in this post, soon we will have even “LINQ to Coffee Machine” :-). .NET Framework 3.5 and C# 3.0 offer us several ways to achieve that goal.

In many occasions, all that is needed in order to be able to apply integrated queries to objects of a certain type (of our own, or belonging to the .NET Framework class library) is to define for the type one or more entry points which could serve as the generators to which all the basic object query machinery incorporated into .NET Framework (LINQ to Objects) can be applied. This has been, for instance, the approach used in LINQ to XML, where a set of iterators (implemented as extension methods) have been defined that produce subsets of the nodes that compose an XML document as IEnumerable<T> sequences; once you call any one of these methods, you obtain an XML node generator to which the predefined implementations of the standard query operators Where(), OrderBy(), etc. can be applied. LINQ to XML also introduces several specialized query operators (“extensions”), but that’s another story.

As an example of simple “LINQ activation” of classes, here we present the implementation of an extension that will allow us to use integrated query syntax over data received through a named pipe. Pipes are a well-known inter-process communication mechanism that has been in use since very long in the DOS/Windows world; but only with .NET Framework 3.5 we will be able to use them in our managed code applications without having to recur to platform invocation. Pipes can be anonymous, conceived to be used to communicate a parent process and a child process residing on the same machine; or named, which offer much more power and can be used over a network. Specifically, named pipes offer message-oriented communications.

The following program implements a server which sends UTF8-encoded string messages to its listener through a pipe named CS3:

using System;
using System.Text;
using System.IO;
using System.IO.Pipes;

namespace Demos
{
class Server
{
static void Main(string[] args)
{
const string PipeName = “CS3”;

using (NamedPipeServerStream pipeStream =
new NamedPipeServerStream(PipeName, PipeDirection.InOut,
1, PipeTransmissionMode.Message, PipeOptions.None))
{
pipeStream.WaitForConnection();

// sending messages
UTF8Encoding encoding = new UTF8Encoding();
for (int i = 1; i <= 1000; i++)
{
string msg = i.ToString();
byte[] bytes = encoding.GetBytes(msg);
pipeStream.Write(bytes, 0, bytes.Length);
}
}
}
}
}

The client, on the other end, composes received messages:

namespace Demos
{
class Client
{
static void Main(string[] args)
{
const string Server = “.”;
const string PipeName = “CS3”;

using (NamedPipeClientStream pipeStream =
new NamedPipeClientStream(Server, PipeName, PipeDirection.InOut))
{
pipeStream.Connect();
pipeStream.ReadMode = PipeTransmissionMode.Message;

Decoder decoder = Encoding.UTF8.GetDecoder();

const int BufferSize = 256;
byte[] bytes = new byte[BufferSize];
char[] chars = new char[BufferSize];
int numBytes = 0;
StringBuilder msg = new StringBuilder();
do
{
msg.Length = 0;
do
{
numBytes = pipeStream.Read(bytes, 0, BufferSize);
if (numBytes > 0)
{
int numChars = decoder.GetCharCount(bytes, 0, numBytes);
decoder.GetChars(bytes, 0, numBytes, chars, 0, false);
msg.Append(chars, 0, numChars);
}
} while (numBytes > 0 && !pipeStream.IsMessageComplete);
decoder.Reset();
if (numBytes > 0)
{
// we’ve got a message – process it
Console.WriteLine(msg.ToString());
}
} while (numBytes != 0);
}
Console.ReadLine();
}
}
}

What if the client process needed to filter, sort, group, etc. the received strings? Traditional coding approaches to implement these tasks could be applied, of course, but a more far-sighted approach would be to define a “LINQ entry point” in the form of an extension method for the NamedPipeClientStream class, so that it can be used as source for language integrated queries:

namespace PlainConcepts.Linq
{
public static partial class Extensions
{
public static IEnumerable<string> GetMessages(
this NamedPipeClientStream pipeStream)
{
pipeStream.Connect();
pipeStream.ReadMode = PipeTransmissionMode.Message;

Decoder decoder = Encoding.UTF8.GetDecoder();

const int BufferSize = 256;
byte[] bytes = new byte[BufferSize];
char[] chars = new char[BufferSize];
int numBytes = 0;
StringBuilder msg = new StringBuilder();
do
{
msg.Length = 0;
do
{
numBytes = pipeStream.Read(bytes, 0, BufferSize);
if (numBytes > 0)
{
int numChars = decoder.GetCharCount(bytes, 0, numBytes);
decoder.GetChars(bytes, 0, numBytes, chars, 0, false);
msg.Append(chars, 0, numChars);
}
} while (numBytes > 0 && !pipeStream.IsMessageComplete);
decoder.Reset();
if (numBytes > 0)
{
// we’ve got a message – yield it!
yield return msg.ToString();
}
} while (numBytes != 0);
}
}
}

Note that thanks to the use of an iterator, queries built around this extension method will take advantage of lazy evaluation, so that messages will be retrieved on demand, as they are needed by the client application.

With such an extension method at hand, we will be able to process messages received from a named pipe stream this way:

namespace Demos
{
using PlainConcepts.Linq;

class Client
{
static void Main(string[] args)
{
const string Server = “.”;
const string PipeName = “CS3”;

using (NamedPipeClientStream pipeStream =
new NamedPipeClientStream(Server, PipeName, PipeDirection.InOut))
{
var input = from s in pipeStream.GetMessages()
where string.Compare(s, “3”) < 0
orderby s
select s;
foreach (var s in input)
Console.WriteLine(s);
}
Console.ReadLine();
}
}
}

Processing messages this way can save us a lot of coding, making at the same time our code much more elegant and readable.

Download source code (VS 2010)

More fun with LINQ

“Standing on a bridge, watch the water passing under me
It must’ve been much harder when there was no bridge just water…”
(“Funny the Way it is”, Dave Matthews Band, 2009)

Ayer se publicó en el área de Community Content de MSDN mi artículo corto “Solving Combinatory Problems with LINQ“, un divertimento basado en LINQ al estilo de otros que ya he publicado tanto en “C# 3.0 y LINQ” como aquí. Estos puzzles siempre me traen a la memoria los problemas que poníamos a nuestros alumnos hace veintitantos años en la Universidad de La Habana, y me hacen pensar en cómo el progreso hace fácil lo que un tiempo atrás era bastante más difícil, que es precisamente a lo que se hace alusión en la referencia musical de hoy.


Pop/Rock tip: De entre los grupos contemporáneos de música popular, uno de los que más me gustan por su calidad, originalidad y eclecticismo es Dave Matthews Band. Su música es una interesante combinación de rock, jazz, soul, bluegrass e incluso música clásica, y en sus conciertos acostumbran a improvisar alrededor de sus canciones al estilo de las jam sessions tan típicas del jazz. “Funny the Way it is” fue el primer single del disco “Big Whiskey and the GrooGrux King” (2009), que vi por primera vez (y no dejé escapar 🙂 en un Starbucks, a mediados del año pasado.

Buscando "El símbolo perdido" con LINQ

Últimamente he estado leyendo en los ratos libres “El símbolo perdido“, la última obra de Dan Brown, el autor de “El código Da Vinci” y otros best sellers. Como parte de los hechos a los que se enfrenta el protagonista durante sus peripecias para descifrar un oculto misterio, el autor nos presenta un cuadrado ultra-mágico que aparece en el cuadro “Melencolia I” (1514), del pintor alemán Alberto Durero:

16 3 2 13
5 10 11 8
9 6 7 12
4 15 14 1

La “magia” de este cuadrado (más información aquí) radica en el hecho de que no solo todas las filas, todas las columnas y las dos diagonales suman 34; adicionalmente, los cuatro “cuadrantes” del cuadrado también suman 34, así como las cuatro casillas centrales. Por último, las dos casillas centrales de la última fila son 15 y 14, que concatenadas producen ‘1514’, el año en el que Durero pintó el cuadro.

En cierto momento de la lectura, pensé: ¿y por qué no buscar un cuadrado similar, pero que tenga en esas casillas inferiores ’20’ y ’10’ (en homenaje, claro está, a Visual Studio 2010 :-)? La siguiente pregunta surgió casi inmediatamente: ¿y por qué no utilizar LINQ, que es parte del producto y de seguro nos permitirá especificar el problema de una manera natural, para resolverlo?

Al final de este post incluyo el código que escribí en pocos minutos para resolver una simplificación del problema que me pareció ya bastante difícil: simplemente buscar un cuadrado tal, que todas las filas, columnas y diagonales sumen lo mismo, con ’20’ y ’10’ en las casillas centrales inferiores. Pensé que encontrar una solución tal podía requerir un enorme tiempo de cálculo en el peor de los casos dada la complejidad algorítmica del programa. Pero como últimamente mi viejo amigo Rainmaker (llamado así, por supuesto, en honor a un tema de Kansas) se pasa los días ocioso y solito en casa, ¿por qué no intentarlo y de paso alegrarle un poco la vida?

Al final, la simplificación resultó ser mucho menos dura de lo que pensaba, y a los pocos minutos el programa estaba escupiendo respuestas con cierta frecuencia. A continuación, la primera de las soluciones encontradas:

1 2 15 29
14 21 5 7
23 4 17 3
9 20 10 8

Por supuesto, este cuadrado no cumple con todas las condiciones del cuadrado de Durero. Desde aquí invito a los lectores a completar mi programa con las condiciones que faltan o crear el suyo propio y buscar un cuadrado que cumpla todas las condiciones (si es que existe).

Sobre la utilización de LINQ para resolver problemas de este tipo ya escribí en su momento (http://geeks.ms/blogs/ohernandez/archive/2007/04/25/191-debemos-aprender-una-nueva-forma-de-escribir-bucles.aspx), aunque sigo teniendo algunas dudas existenciales al respecto :-). Un experimento que se me antoja interesante sería el de comparar el rendimiento de implementaciones como ésta al utilizar LINQ y PLINQ en máquinas con múltiples núcleos. Pero ese experimento, por mi parte, tendrá que esperar…

(Vea la continuación aquí)

Código utilizado:

using System;
using System.IO;
using System.Linq;

namespace LostSymbol
{
class Program
{
private const int MAX = 100;

static void Main(string[] args)
{
const int firstSeed = 20;
const int secondSeed = 10;

var res =
/* first row /
from a11 in Enumerable.Range(1, MAX)
where a11 != firstSeed && a11 != secondSeed
from a12 in Enumerable.Range(1, MAX)
where a12 != firstSeed && a12 != secondSeed &&
a12 != a11
from a13 in Enumerable.Range(1, MAX)
where a13 != firstSeed && a13 != secondSeed &&
a13 != a11 && a13 != a12
from a14 in Enumerable.Range(1, MAX)
where a14 != firstSeed && a14 != secondSeed &&
a14 != a11 && a14 != a12 && a14 != a13
let sum = a11 + a12 + a13 + a14
/
second row /
from a21 in Enumerable.Range(1, MAX)
where a21 != firstSeed && a21 != secondSeed &&
a21 != a11 && a21 != a12 && a21 != a13 && a21 != a14
from a22 in Enumerable.Range(1, MAX)
where a22 != firstSeed && a22 != secondSeed &&
a22 != a21 &&
a22 != a11 && a22 != a12 && a22 != a13 && a22 != a14
from a23 in Enumerable.Range(1, MAX)
where a23 != firstSeed && a23 != secondSeed &&
a23 != a21 && a23 != a22 &&
a23 != a11 && a23 != a12 && a23 != a13 && a23 != a14
let a24 = sum – (a21 + a22 + a23)
where a24 > 0 && a24 <= MAX &&
a24 != firstSeed && a24 != secondSeed &&
a24 != a21 && a24 != a22 && a24 != a23 &&
a24 != a11 && a24 != a12 && a24 != a13 && a24 != a14
/
third row /
from a31 in Enumerable.Range(1, MAX)
where a31 != firstSeed && a31 != secondSeed &&
a31 != a11 && a31 != a12 && a31 != a13 && a31 != a14 &&
a31 != a21 && a31 != a22 && a31 != a23 && a31 != a24
let a32 = sum – (a12 + a22 + firstSeed)
where a32 > 0 && a32 <= MAX &&
a32 != firstSeed && a32 != secondSeed &&
a32 != a31 &&
a32 != a11 && a32 != a12 && a32 != a13 && a32 != a14 &&
a32 != a21 && a32 != a22 && a32 != a23 && a32 != a24
let a33 = sum – (a13 + a23 + secondSeed)
where a33 > 0 && a33 <= MAX &&
a33 != firstSeed && a33 != secondSeed &&
a33 != a31 && a33 != a32 &&
a33 != a11 && a33 != a12 && a33 != a13 && a33 != a14 &&
a33 != a21 && a33 != a22 && a33 != a23 && a33 != a24
let a34 = sum – (a31 + a32 + a33)
where a34 > 0 && a34 <= MAX &&
a34 != firstSeed && a34 != secondSeed &&
a34 != a31 && a34 != a32 && a34 != a33 &&
a34 != a11 && a34 != a12 && a34 != a13 && a34 != a14 &&
a34 != a21 && a34 != a22 && a34 != a23 && a34 != a24
/
fourth row /
let a41 = sum – (a11 + a21 + a31)
where a41 > 0 && a41 < MAX &&
a41 != firstSeed && a41 != secondSeed &&
a41 != a11 && a41 != a12 && a41 != a13 && a41 != a14 &&
a41 != a21 && a41 != a22 && a41 != a23 && a41 != a24 &&
a41 != a31 && a41 != a32 && a41 != a33 && a41 != a34 &&
a41 + a32 + a23 + a14 == sum     /
right-to-left diagonal /
let a42 = firstSeed
let a43 = secondSeed
let a44 = sum – (a14 + a24 + a34)
where a44 > 0 && a44 < MAX &&
a44 != firstSeed && a44 != secondSeed &&
a44 != a41 &&
a44 != a11 && a44 != a12 && a44 != a13 && a44 != a14 &&
a44 != a21 && a44 != a22 && a44 != a23 && a44 != a24 &&
a44 != a31 && a44 != a32 && a44 != a33 && a44 != a34 &&
a41 + firstSeed + secondSeed + a44 == sum &&
a11 + a22 + a33 + a44 == sum     /
left-to-right diagonal */
select new
{
a11, a12, a13, a14,
a21, a22, a23, a24,
a31, a32, a33, a34,
a41, a42, a43, a44,
};

using (StreamWriter sw = new StreamWriter(“C:\TEMP\Solutions.txt“))
{
sw.WriteLine(“Start : ” + DateTime.Now.ToString(“yyyy/MM/dd hh:mm:ss”));
int n = 0;
foreach (var r in res)
{
sw.WriteLine(“Solution ” + n);
sw.WriteLine(“=============”);
sw.WriteLine(“{0} {1} {2} {3}”, r.a11, r.a12, r.a13, r.a14);
sw.WriteLine(“{0} {1} {2} {3}”, r.a21, r.a22, r.a23, r.a24);
sw.WriteLine(“{0} {1} {2} {3}”, r.a31, r.a32, r.a33, r.a34);
sw.WriteLine(“{0} {1} {2} {3}”, r.a41, r.a42, r.a43, r.a44);
sw.WriteLine();
sw.Flush(); n++;
}
sw.WriteLine(“Finish: ” + DateTime.Now.ToString(“yyyy/MM/dd hh:mm:ss”));
}
Console.ReadLine();
}
}
}