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

“Now I know you’re all king horse
Between tenderness and brute force…”
(“King Horse”, Elvis Costello, 2007)

Continuando con el problema propuesto en el post anterior (basado en “El símbolo perdido“, la última obra de Dan Brown), aquí presento el código final utilizado para resolver el problema, así como un análisis somero de los resultados obtenidos.

La adición de las condiciones que faltan al programa del post anterior (que la suma de los cuatro “cuadrantes”, más la del cuadrado central, coincida con la de las filas, columnas y diagonales) nos permite reducir el número de “variables libres” sobre las que el programa debe iterar a 7, con lo que la cantidad de combinaciones a probar es del orden de MAX^7, donde MAX es el valor máximo que queremos poder almacenar en cualquier casilla.Inicialmente establecí MAX a 100, con lo que el número de combinaciones a intentar era realmente enorme. Pero el problema resultó más “flojo” de lo que pensaba: en unos dos días de cálculo ininterrumpido, Rainmaker ya había encontrado unas 500.000 soluciones, y el valor de la primera variable (a11) aún seguía siendo 1. Así que decidí no torturar más al pobre amigo y detuve la ejecución. A continuación, el primero de los cuadrados obtenidos:

1 4 11 29
26 14 3 2
12 7 21 5
6 20 10 9

Entonces decidí restringir la búsqueda a los cuadrados en los que el número máximo utilizado fuera el 20, lo que redujo considerablemente la cantidad de combinaciones a probar. En algo menos de un minuto, ya tenía a mi disposición los 320 cuadrados válidos existentes. De nuevo, aquí solo muestro el primero de ellos; el lector interesado en buscar uno más “bonito” puede ejecutar el programa y estudiar sus resultados.

11 1 13 19
18 14 4 8
3 9 17 15
12 20 10 2

Así que aquí está mi modesto homenaje a Visual Studio 2010 – un programa que utiliza LINQ y que se me antoja combina, usando las palabras de Elvis Costello, “ternura y fuerza bruta” (pero, ¿en qué medida cada una de ellas, amigo lector? 🙂 .

Código utilizado:

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

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

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
let a22 = sum – (a11 + a12 + a21)
where a22 > 0 && a22 <= MAX &&
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 &&
a13 + a14 + a23 + a24 == sum     /
second quadrant /
/
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 &&
a22 + a23 + a32 + a33 == sum     /
middle quadrant /
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 /
a31 + a32 + a41 + firstSeed == sum     /
fourth quadrant /
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 /
a33 + a34 + a43 + a44 == sum     /
third quadrant */
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();
}
}
}


Pop/Rock tip: Elvis Costello, cantante y compositor nacido en Inglaterra, lleva más de treinta años de éxito desde que debutó en 1977 con el excelente album “My Aim is True“. Su eclecticismo musical y letras trabajadas lo han convertido en un referente para varias generaciones de músicos.

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