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();
        }
    }
}

Published 12/10/2009 3:44 por Octavio Hernández
Archivado en: ,,
Comparte este post:

Comentarios

Monday, October 12, 2009 6:47 PM por Jorge Serrano

# re: Buscando "El símbolo perdido" con LINQ

Eres un friki de cuidado,... ahora bien... me ha gustado mucho la idea, sin embargo, una puntualización.

Yo jugué a este tipo de combinatoria cuando estudiaba el colegio y tenía casillas de 9, 16 y 25 elementos.

El tema está en que para la caja de 16 elementos, debes tener en cuenta a los números comprendidos entre el 1 y el 16, o sino, creo recordar... correr un número a la derecha (2 a 17).

En tu ejemplo Octavio, pones 20 y 10, pero deberías correr los elementos. Si te apoyas en el cuadro de Durero,... el resultado de la suma de las filas y columnas sería impar, ya que 20 + 10 es par y a partir de ahí y teniendo en cuenta otra premisa (no se pueden repetir los valores) los valores a izquierda y derecha deberían ser impares... vamos... que tiene miga... jejeje. :-)

Tuesday, October 13, 2009 6:27 AM por Octavio Hernández

# re: Buscando "El símbolo perdido" con LINQ

Cierto, Jorgito, me faltó esa condición de que los números del cuadrado sean los enteros del 1 al 16, de la que no me di cuenta!

En ese caso, usar el 20 por supuesto no tendría sentido, así que mejor dejo el problema tal cual lo he enunciado - los números pueden ser cualesquiera, siempre que no se repitan.

Abrazo - OH

Tuesday, October 13, 2009 11:18 AM por Cristian Manteiga

# re: Buscando "El símbolo perdido" con LINQ

Un planteamiento muy divertido, es bueno ver que siempre sabes encontrar la cara más divertida y curiosa de la programación.

Un placer disfrutar de la lectura de tu blog.

Un abrazo gigante, Maestro.

Cristian

Friday, October 16, 2009 6:59 AM por Octavio Hernández

# re: Buscando "El símbolo perdido" con LINQ

Cristian,

Un planteamiento divertido, pero al parecer complicado... Rainmaker las está pasando canutas :-)

Fuerte abrazo - OH

Monday, October 19, 2009 8:05 AM por Sobre C#, LINQ y algo más...

# Buscando "El símbolo perdido" con LINQ (II)

"Now I know you're all king horse Between tenderness and brute force..." ("King Horse"